• Advertisement
Sign in to follow this  

Beginner Question: Finding the Geometric Shortest Distance Between Two Points

This topic is 4223 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi, I need to find the shortest distance between two points in a 3D environment (without the path going through any walls). For example, say I have a U-shaped or S-shaped corridor with a point at each end. Is there an algorithm for finding the geometric shortest distance between the two points? Cheers, Chris

Share this post


Link to post
Share on other sites
Advertisement
This is called path-finding. You start by describing your problem as a problem of finding the shortest path in a weighted graph (use the origin, destination and all vertices as nodes, connect two nodes if you can move from one to the other in a straight line, use the distance as weight). Then you use an algorithm like A* to find the shortest path.

It's very easy to find explanations of A* on the web, like this one.

Share this post


Link to post
Share on other sites
Is your world subdivided in any way? There are straightforward pathfinding solutions if your world is divided up into a regular grid.

Otherwise, you'll have to use a less algorithmic approach. A basic method would be to just ray trace from the start point to the end point. If you hit an obstacle, then you need to move along the surfaces of the obstacle such that you maximize the change in distance (this change should be negative of course). Once you're not "on" the obstacle anymore, do another ray trace to the end point and repeat the process. I don't know if this is a particularly good solution because it's quite slow, but it's close to what you'd have to do unless you divide up the world.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement