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? enter image description here

  • $\begingroup$ I removed the "logic" tag. While this is an interesting problem, it is not in the scope of mathematical logic. $\endgroup$ – Carl Mummert Nov 2 '12 at 11:54

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:

A shorter path

  • $\begingroup$ Firstly, thanks a lot! :) Secondly, isn't there a more smarter way to do this? Can't we use first-order logic to construct rules, like The shortest path is the one with least displacement from the straight path and then have the agent use logical inference and deduction to get the answer? More like how we humans do? $\endgroup$ – Ghost Nov 2 '12 at 18:08

the shortest path will be a straight line between the pivot corners


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.