Dijkstra & A* Direction oriented pathfinding Terrain Analysis RTS Games

Dijkstra's Algorithm

A common example of a graph-based pathfinding algorithm is Dijkstra's algorithm. This algorithm begins with a start node and an "open set" of candidate nodes. At each step, the node in the open set with the lowest distance from the start is examined. The node is marked "closed", and all nodes adjacent to it are added to the open set if they have not already been examined. This process repeats until a path to the destination has been found. Since the lowest distance nodes are examined first, the first time the destination is found, the path to it will be the shortest path.

Dijkstra's algorithm fails if there is a negative edge weight. In the hypothetical situation where Nodes A, B, and C form a connected undirected graph with edges AB = 3, AC = 4, and BC = -2, the optimal path from A to C costs 1, and the optimal path from A to B costs 2. Dijkstra's Algorithm starting from A will first examine B, as that is the closest. It will assign a cost of 3 to it, and mark it closed, meaning that its cost will never be reevaluated. Therefore, Dijkstra's cannot evaluate negative edge weights. However, since for many practical purposes there will never be a negative edgeweight, Dijkstra's algorithm is largely suitable for the purpose of pathfinding.

procedure DIJKSTRA(G, s)
    begin
        for each node v from G.V do
            begin
                d[v] := ?
                ancestor[v] := NIL
            end
        d[s] := 0
        INSERT_NODES(Q, G.V)
        while not (EMPTY(Q)) do
            begin
                u := MIN(Q)
                for each node v from G.Neighbours(u) do
                    if d[v] > d[u] + G.P[(u, v)].weight then
                        begin
                            d[v] := d[u] + G.P[(u, v)].weight
                            ancestor[v] := u
                        end
            end
    end

procedure PATH(G, s, v)
    begin
        if v = s then
            print s + ": lenght: " + G.d[s]
        else if G.ancestor[v] = NIL then
            print "between " + s + " and " + v + " is no path"
        else
            begin
                PATH(G, s, G.ancestor[v])
                print v + ": lenght: " + G.d[v]
            end
    end


A* Algorithm

A* is a variant of Dijkstra's algorithm commonly used in games. A* assigns a weight to each open node equal to the weight of the edge to that node plus the approximate distance between that node and the finish. This approximate distance is found by the heuristic, and represents a minimum possible distance between that node and the end. This allows it to eliminate longer paths once an initial path is found. If there is a path of length x between the start and finish, and the minimum distance between a node and the finish is greater than x, that node need not be examined.

A* uses this heuristic to improve on the behavior relative to Dijkstra's algorithm. When the heuristic evaluates to zero, A* is equivalent to Dijkstra's algorithm. As the heuristic estimate increases and gets closer to the true distance, A* continues to find optimal paths, but runs faster (by virtue of examining fewer nodes). When the value of the heuristic is exactly the true distance, A* examines the fewest nodes. (However, it is generally impractical to write a heuristic function that always computes the true distance.) As the value of the heuristic increases, A* examines fewer nodes but no longer guarantees an optimal path. In many applications (such as video games) this is acceptable and even desirable, in order to keep the algorithm running quickly.

Dijkstra & A* Direction oriented pathfinding Terrain Analysis RTS Games