Thread: All-angle pathfinding algorithm?

  1. #1
    Algorithm engineer
    Join Date
    Jun 2006
    Posts
    286

    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.
    Come on, you can do it! b( ~_')

  2. #2
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    Use A*. It works off of 'costs' and to my knowledge does not depend on squares.

  3. #3
    Algorithm engineer
    Join Date
    Jun 2006
    Posts
    286
    Quote Originally Posted by Bubba View Post
    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?
    Come on, you can do it! b( ~_')

  4. #4
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    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.

  5. #5
    Algorithm engineer
    Join Date
    Jun 2006
    Posts
    286
    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.
    Come on, you can do it! b( ~_')

  6. #6
    GA ichijoji's Avatar
    Join Date
    Nov 2002
    Posts
    179
    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.
    Illusion and reality become impartiality and confidence.

  7. #7
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    Picture imaginary lines that represent the transitions between your "points" and you have a graph. Same with a grid.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Implement of a Fast Time Series Evaluation Algorithm
    By BiGreat in forum C Programming
    Replies: 7
    Last Post: 12-04-2007, 02:30 AM
  2. My pathfinding algorithm
    By BobMcGee123 in forum Game Programming
    Replies: 7
    Last Post: 09-23-2005, 05:08 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM