Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
I removed the "logic" tag. While this is an interesting problem, it is not in the scope of mathematical logic. –  Carl Mummert Nov 2 '12 at 11:54

2 Answers 2

up vote 5 down vote accepted

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

share|improve this answer
    
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? –  Ghost Nov 2 '12 at 18:08

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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