All-angle pathfinding algorithm?

Hello!

I have a small problem with finding a decent pathfinding algorithm. Dijkstras is super. Unfortunately it can only find paths that go along the edges of a graph. In other words, only a limited amount of angles.

I have an example: If you want to find the closes way between two points in a plane, the air distance will be the closest if the plane has no obstacles and lets you move with the same speed everywhere. Say that instead of a simple plane, you have a square grid, where every square lets you move over it in a unique speed. If you where only allowed to move in the directions north, south, east and west, maybe as well north-west, north-east, south-west and south-east, the problem of finding the fastest path could be easily solved with Dijkstras algorithm. But if you are allowed to move in any angle, for example 30 or 40 degrees, allowing you to take a short cut over the edge of a square, the problem gets much more difficult. Is there some way to use Dijkstras anyway? How would you solve the problem? Any suggestion is welcome.

Use A*. It works off of 'costs' and to my knowledge does not depend on squares.

Quote:

---

Originally Posted by Bubba

Use A*. It works off of 'costs' and to my knowledge does not depend on squares.

---

As far as I know A* is jus an extended version of Dijkstras, it's complemented with a heuristic function which allows it to complete the same task faster ... I got a little bit unsure now, am I wrong?

A* is graph based as well.

You could probably reduce your problem to a graph one though. Start with the simplest solution, the shortest path between two points is a straight line. If that line violates a boundry, find a point outside of the obstacle that minimizes the sum of the distances to the original two points. Rinse and repeat (recursively).

The "find a point" part is the ambiguous bit of my explanation. It won't be trivial. If all of your weights are constant you could use some kind of hill climbing algorithm.

My idéa was maybe using some kind of light simulating algorithm, combined with Dijkstras or A*, light always find the closest way you know ^^ ... the problem is just that light spread in a circle at the beginning, but when it enters another square with another traveling speed (can be seen as if it has another refractive index), it's spreading becomes much more complicated ... damit. :(

A* doesn't have to be graph based. You can have something like:

Code:

---

stack = Stack()
stack.push_back(from)
current = stack.pop_front()
while not samePoint(current,dest):
    expandList = expandPoint(current)
    for expandPoint in expandList:
        if validPoint(expandPoint):
            inStack = False
            for stackPoint in stack:
                if samePoint(expandPoint,stackPoint):
                    inStack = True
            if not inStack:
                stack.push_back(expandPoint)
    //sort the stack by distance traversed so far plus estimate to destination for each node
    current = stack.pop_front()

---

Then, if you look at the theory, this is guaranteed to find the optimal solution, but it might take a long time. You might want to look at some preprocessing to ease computation at runtime to prevent runaways.

Picture imaginary lines that represent the transitions between your "points" and you have a graph. Same with a grid.