# Beginner Question: Finding the Geometric Shortest Distance Between Two Points

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

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

1. 1
2. 2
3. 3
frob
13
4. 4
5. 5

• 9
• 13
• 14
• 68
• 14
• ### Forum Statistics

• Total Topics
632133
• Total Posts
3004302

×