I was looking at what the guys in the Mario AI Competition have been doing and some of them have built some pretty neat Mario bots utilizing the A* (A-Star) Pathing Algorithm.
(Video of Mario A* Bot In Action)
My question is, how does A-Star compare with Dijkstra? Looking over them, they seem similar.
Why would someone use one over the other? Especially in the context of pathing in games?
Dijkstra is a special case for A* (when the heuristics is zero).
It has one cost function, which is real cost value from source to each node: f(x)=g(x).
It finds the shortest path from source to every other node by considering only real cost.
It has two cost function.
g(x): same as Dijkstra. The real cost to reach a node x.h(x): approximate cost from node x to goal node. It is a heuristic function. This heuristic function should never overestimate the cost. That means, the real cost to reach goal node from node x should be greater than or equal h(x). It is called admissible heuristic.The total cost of each node is calculated by f(x)=g(x)+h(x)
A* search only expands a node if it seems promising. It only focuses to reach the goal node from the current node, not to reach every other nodes. It is optimal, if the heuristic function is admissible.
So if your heuristic function is good to approximate the future cost, than you will need to explore a lot less nodes than Dijkstra.
What previous poster said, plus because Dijkstra has no heuristic and at each step picks edges with smallest cost it tends to "cover" more of your graph. Because of that Dijkstra could be more useful than A*. Good example is when you have several candidate target nodes, but you don't know, which one is closest (in A* case you would have to run it multiple times: once for each candidate node).
Dijkstra's algorithm would never be used for pathfinding. Using A* is a no-brainer if you can come up with a decent heuristic (usually easy for games, especially in 2D worlds). Depending on the search space, Iterative Deepening A* is sometimes preferable because it uses less memory.
Dijkstra is a special case for A*.
Dijkstra finds the minimum costs from the starting node to all others. A* finds the minimum cost from the start node to the goal node.
Dijkstra's algorithm would never be used for path finding. Using A* one can come up with a decent heuristic. Depending on the search space, iterative A* is is preferable because it uses less memory.
The code for Dijkstra's algorithm is:
// A C / C++ program for Dijkstra's single source shortest path algorithm.
// The program is for adjacency matrix representation of the graph
#include <stdio.h>
#include <limits.h>
// Number of vertices in the graph
#define V 9
// A utility function to find the vertex with minimum distance value, from
// the set of vertices not yet included in shortest path tree
int minDistance(int dist[], bool sptSet[])
{
// Initialize min value
int min = INT_MAX, min_index;
for (int v = 0; v < V; v++)
if (sptSet[v] == false && dist[v] <= min)
min = dist[v], min_index = v;
return min_index;
}
int printSolution(int dist[], int n)
{
printf("Vertex Distance from Source\n");
for (int i = 0; i < V; i++)
printf("%d \t\t %d\n", i, dist[i]);
}
void dijkstra(int graph[V][V], int src)
{
int dist[V]; // The output array. dist[i] will hold the shortest
// distance from src to i
bool sptSet[V]; // sptSet[i] will true if vertex i is included in shortest
// path tree or shortest distance from src to i is finalized
// Initialize all distances as INFINITE and stpSet[] as false
for (int i = 0; i < V; i++)
dist[i] = INT_MAX, sptSet[i] = false;
// Distance of source vertex from itself is always 0
dist[src] = 0;
// Find shortest path for all vertices
for (int count = 0; count < V-1; count++)
{
// Pick the minimum distance vertex from the set of vertices not
// yet processed. u is always equal to src in first iteration.
int u = minDistance(dist, sptSet);
// Mark the picked vertex as processed
sptSet[u] = true;
// Update dist value of the adjacent vertices of the picked vertex.
for (int v = 0; v < V; v++)
// Update dist[v] only if is not in sptSet, there is an edge from
// u to v, and total weight of path from src to v through u is
// smaller than current value of dist[v]
if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX
&& dist[u]+graph[u][v] < dist[v])
dist[v] = dist[u] + graph[u][v];
}
// print the constructed distance array
printSolution(dist, V);
}
// driver program to test above function
int main()
{
/* Let us create the example graph discussed above */
int graph[V][V] = {{0, 4, 0, 0, 0, 0, 0, 8, 0},
{4, 0, 8, 0, 0, 0, 0, 11, 0},
{0, 8, 0, 7, 0, 4, 0, 0, 2},
{0, 0, 7, 0, 9, 14, 0, 0, 0},
{0, 0, 0, 9, 0, 10, 0, 0, 0},
{0, 0, 4, 14, 10, 0, 2, 0, 0},
{0, 0, 0, 0, 0, 2, 0, 1, 6},
{8, 11, 0, 0, 0, 0, 1, 0, 7},
{0, 0, 2, 0, 0, 0, 6, 7, 0}
};
dijkstra(graph, 0);
return 0;
}
The code for A* algorithm is:
class Node:
def __init__(self,value,point):
self.value = value
self.point = point
self.parent = None
self.H = 0
self.G = 0
def move_cost(self,other):
return 0 if self.value == '.' else 1
def children(point,grid):
x,y = point.point
links = [grid[d[0]][d[1]] for d in [(x-1, y),(x,y - 1),(x,y + 1),(x+1,y)]]
return [link for link in links if link.value != '%']
def manhattan(point,point2):
return abs(point.point[0] - point2.point[0]) + abs(point.point[1]-point2.point[0])
def aStar(start, goal, grid):
#The open and closed sets
openset = set()
closedset = set()
#Current point is the starting point
current = start
#Add the starting point to the open set
openset.add(current)
#While the open set is not empty
while openset:
#Find the item in the open set with the lowest G + H score
current = min(openset, key=lambda o:o.G + o.H)
#If it is the item we want, retrace the path and return it
if current == goal:
path = []
while current.parent:
path.append(current)
current = current.parent
path.append(current)
return path[::-1]
#Remove the item from the open set
openset.remove(current)
#Add it to the closed set
closedset.add(current)
#Loop through the node's children/siblings
for node in children(current,grid):
#If it is already in the closed set, skip it
if node in closedset:
continue
#Otherwise if it is already in the open set
if node in openset:
#Check if we beat the G score
new_g = current.G + current.move_cost(node)
if node.G > new_g:
#If so, update the node to have a new parent
node.G = new_g
node.parent = current
else:
#If it isn't in the open set, calculate the G and H score for the node
node.G = current.G + current.move_cost(node)
node.H = manhattan(node, goal)
#Set the parent to our current item
node.parent = current
#Add it to the set
openset.add(node)
#Throw an exception if there is no path
raise ValueError('No Path Found')
def next_move(pacman,food,grid):
#Convert all the points to instances of Node
for x in xrange(len(grid)):
for y in xrange(len(grid[x])):
grid[x][y] = Node(grid[x][y],(x,y))
#Get the path
path = aStar(grid[pacman[0]][pacman[1]],grid[food[0]][food[1]],grid)
#Output the path
print len(path) - 1
for node in path:
x, y = node.point
print x, y
pacman_x, pacman_y = [ int(i) for i in raw_input().strip().split() ]
food_x, food_y = [ int(i) for i in raw_input().strip().split() ]
x,y = [ int(i) for i in raw_input().strip().split() ]
grid = []
for i in xrange(0, x):
grid.append(list(raw_input().strip()))
next_move((pacman_x, pacman_y),(food_x, food_y), grid)
You can consider A* a guided version of Dijkstra. Meaning, instead of exploring all the nodes, you will use a heuristic to pick a direction.
To put it more concretely, if you're implementing the algorithms with a priority queue then the priority of the node you're visiting will be a function of the cost (previous nodes cost + cost to get here) and the heuristic estimate from here to the goal. While in Dijkstra, the priority is only influenced by the actual cost to nodes. In either case, the stop criterion is reaching the goal.
Dijkstra finds the minimum costs from the starting node to all others. A* finds the minimum cost from the start node to the goal node.
Therefore it would seem that Dijkstra would be less efficient when all you need is the minimum distance from one node to another.
If you look at the psuedocode for Astar :
foreach y in neighbor_nodes(x)
if y in closedset
continue
Whereas, if you look at the same for Dijkstra :
for each neighbor v of u:
alt := dist[u] + dist_between(u, v) ;
So, the point is, Astar will not evaluate a node more than once,
since it believes that looking at a node once is sufficient, due
to its heuristics.
OTOH, Dijkstra's algorithm isn't shy of correcting itself, in case
a node pops up again.
Which should make Astar faster and more suitable for path finding.
BFS and Dijkstra’s algorithms are very similar to each other; they both are a particular case of the A* algorithm.
A* algorithm is not just more generic; it improves the performance of Dijkstra’s algorithm in some situations but this is not always true; in the general case, Dijkstra’s algorithm is asymptotically as fast as A*.
Dijkstra algorithm has 3 arguments. If you ever solved network delay time problem :
class Solution:
def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
A* method has extra 2 arguments:
function aStar(graph, start, isGoal, distance, heuristic)
queue ← new PriorityQueue()
queue.insert(start, 0)
# hash table to keep track of the distance of each vertex from vertex "start",
#that is, the sum of the weight of edges that needs to be traversed to get from vertex start to each other vertex.
# Initializes these distances to infinity for all vertices but vertex start .
distances[v] ← inf (∀ v ε graph | v <> start)
# hash table for the f-score of a vertex,
# capturing the estimated cost to be sustained to reach the goal from start in a path passing through a certain vertex. Initializes these values to infinity for all vertices but vertex "start".
fScore[v] ← inf (∀ v ε graph | v <> start)
# Finally, creates another hash table to keep track, for each vertex u, of the vertex through which u was reached.
parents[v] ← null ( v ε graph)
A* takes two extra arguments, a
distance function, and aheuristic. They both contribute to the computation of the so-called f-score. This value is a mix of the cost of reaching the current node u from the source and the expected cost needed in order to reach the goal from u.By controlling these two arguments, we can obtain either BFS or Dijkstra’s algorithm (or neither). For both of them, the
heuristicwill need to be a function that is identically equal to 0 , something we could write like
lambda(v) → 0
Both of these algorithms, in fact, completely disregard any notion of or information about the distance of vertices to goal.
For the distance metrics, the situation is different:
Dijkstra’s algorithm uses the edge’s weight as a distance function, so we need to pass something like
distance = lambda(e) → e.weight
BFS only takes into account the number of edges traversed, which is equivalent to considering all edges to have the same weight, identically equal to 1! And thus, we can pass
distance = lambda(e) → 1
A* gains an advantage only in some contexts where we have extra information that we can somehow use. we can use A* to drive search faster to the goal is when we have information about the distance from all or some vertices to the goal.
Notice that in this particular case, the key factor is that the vertices, carry extra information with them (their position, which is fixed) that can help estimate their distance to the final goal. This isn’t always true and is usually not the case for generic graphs. To put it differently, the extra information here doesn’t come from the graph, but from domain knowledge.
The key, here and always, is the quality of the extra information
captured by the Heuristic function: the more reliable and closer
to real distance the estimate, the better A* performs.
Dijkstra's algorithm finds the shortest path definitely. On the other hand A* depends on the heuristic. For this reason A* is faster than Dijkstra's algorithm and will give good results if you have a good heuristic.
In A*, for each node you check the outgoing connections for their .
For each new node you calculate the lowest cost so far (csf) depending on the weights of the connections to this node and the costs you had to reach the previous node.
Additionally you estimate the cost from the new node to the target node and add this to the csf. You now have the estimated total cost (etc). (etc = csf + estimated distance to target)
Next you choose from the new nodes the one with the lowest etc.
Do the same as before until one of the new nodes will be the target.
Dijkstra works almost the same. Except that the estimated distance to target is always 0, and the algorithm first stops when the target is not only one of the new nodes, but also the one with the lowest csf.
A* is usually faster than dijstra, though this will not always be the case. In video games you often prefare the "close enough for a game" approach. Therefore the "close enough" optimal path from A* usually suffices.
Dijkstra's algorithm is definitely complete and optimal that you will always find the shortest path. However it tends to take longer since it is used mainly to detect multiple goal nodes.
A* search on the other hand matters with heuristic values, which you can define to reach your goal nearer, such as manhattan distance towards goal. It can be either optimal or complete which depends on heuristic factors. it is definitely faster if you have a single goal node.
