How would an algorithm find the shortest distance between 2 points on a horizontal 2d plane , especially when a straight path is not possible? Could it be something on the lines of calculating least displacement from the straight path?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
The problem of computing the shortest path between two points is known as pathfinding, and there are many exact and approximate algorithms for solving it in a variety of settings. A very commonly used one is the A* search algorithm and its variants.
To use A* search, you first need to discretize your search space into a graph (a navigation mesh). For a two-dimensional space with polygonal obstacles, I believe a suitable discretization would be to take as nodes all corners of the polygons (plus the starting and goal points) and as edges the straight-line paths between them, excluding any paths that would pass through the obstacles (but including the edges of the polygons themselves).
In three dimensions, things get more complicated, as evidenced by the fact that there can be points which are not even reachable via a straight path from any corner point of a polyhedral obstacle.
Ps. The red path in your image is not actually the shortest possible one, as it makes turns at points other than at the corners of the obstacles. In particular, the green path below (which does only turn at corners) is clearly shorter: