Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

It is possible for A* Path Finding to return all the shortest paths given a graph/map?

For example, given the map below:

-----------
--a--X--b--
-----------

The said map can return four (4) distinct path.

-----1-----
--a11X11b--
-----------
-----------
--a22X22b--
-----2-----
----333----
--a3-X-3b--
-----------
-----------
--a4-X-4b--
----444----

The paths follow the Manhattan Heuristic and a Eight (8) directional transition with a default G-value of 1.0f for testing.

The question given the Pseudocode of A* will only return me one (1) of the four (4) distinct paths which I wish to return all four (4) paths instead.

share|improve this question
1  
This isn't a problem with A*, A* will return one shortest path and not all shortest paths. I changed the title of the question to reflect that. –  bummzack Apr 10 '13 at 6:22
    
Suppose I will use other path finding techniques derived from A* (i.e., HPA*, Annonated A*, etc.) will make a difference? –  Dr. Java Apr 10 '13 at 9:29

1 Answer 1

Yes it is possible, but it requires that your queue of nodes can have the same node more than once with different source path. This may require some changes to the data structures you are using with the path finding. For example you can't store the visiting information directly in a tilemap, since the information on how you reached a specific node is not unique.

Anyway what you need to do is add a neighbour to the queue even if it already exists with the same (but not lower) estimated cost. When you reach the goal, get all other nodes from the queue that also reached the goal with the same cost. From this list you can reconstruct all possible shortest paths.

By the way the given example can return a lot more than those 4 paths (I counted 18) such as

-----------
--a--X55b--
---555-----

That also means that the algorithm will run a lot slower than the basic version.

Edit: Pseudo code as requested:

struct RouteNode {
    Node node;
    RouteNode previousNode;
    float cumulativeCost;
    float estimatedCost; // This specifies the ordering in priority queue
}

openSet = new PriorityQueue();
openSet.add(new RouteNode(start, null, 0, getEstimate(start, goal)));

while (!finished) {
    RouteNode current = openSet.takeFirst();
    if (current.node == goal) {
        routes = new List();
        routes.add(current);
        foreach alternative in openSet {
            if (alternative.cost == current.cost && alternative.node == goal) {
                routes.add(alternative);
            }
        }
        finished = true;
    }
    else {
        foreach neighbour in getNeighbours(current.node) {
            cost = current.cumulativeCost + distance(current.node, neighbour);
            if (openSet not contains RouteNode where RouteNode.cumulativeCost < cost && RouteNode.node == neighbour) {
                openSet.add(new RouteNode(neighbour, current, cost, cost + getEstimate(neighbour, goal));
            }
        }
    }
}

foreach route in routes {
    path = new List();
    current = route;
    while (current != null) {
        path.add(current.node);
        current = current.previousNode;
    }
    path.reverse();
}

I can't tell how much slower this will be, but it is proportional to the number of alternative path options.

share|improve this answer
    
I see. Can you provide a Pseudocode for this approach? And in your opinion how much will it take for this to process all paths - in percentage quantity? –  Dr. Java Apr 10 '13 at 6:57

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.