Sign in to follow this  
cpsmusic

Beginner Question: Finding the Geometric Shortest Distance Between Two Points

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
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

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this