I recently made a post about two generic delegates introduced in version 3.5 of the .NET Framework. As an example, I mentioned an implementation of the A* search algorithm. For those not familiar with the algorithm, A* (pronounce A Star) is one, if not the, most popular search algorithms in artificial intelligence. Generally, the algorithm visits nodes in a graph, taking certain aspects into consideration, until it finds a node that meets a specific goal condition or until there are no more nodes left. The algorithm is, usually, optimal and complete, which means it will always find the least expensive solution. This, however, can change depending on certain factors I will get into later on in the post.

Like many other search algorithms, A* performs its search over a, usually, weighted graph. This structure, depending on the implementation, can be implicit or explicit. The purpose of the algorithm is to find the shortest path to a node that meets a certain criterion. One typical application of these algorithms is path-finding, where an intelligent agent must navigate from one point in space to another. To facilitate the search process, the traversable world is represented in a navigation graph. The meaning of each node depends on how the continuous space through which the agent can move is being made discrete. A few popular choices are imposing a grid on top of the world and making each tile a node in the graph (This approach will be familiar to players of typical 2D role-playing games) and making each node a ‘waypoint’, which are points that define paths through which the agents can travel. It is easy to visualize that in this domain the optimal solution would be the shortest path from one point to another. The weights on the edges of the graph would be the distance separating the two points represented by each node. Formally, the navigation graph is known as the problem’s search space.

A* differs from algorithms like breadth-first and depth-first in that it is an informed search algorithm. This means that domain-specific information is used in the process of finding a solution. This information takes the form of a heuristic function, which is responsible for estimating the cost to reach a node that meets the goal condition from any other node. For the algorithm to be optimal, it is required that the heuristic function be admissible, that is, it must never overestimate the cost of reaching a goal node. In path-finding it is common to use the length separating the current location of the agent and the point it wants to get to. Since the shortest path between two points will always be the straight line joining them, it is impossible for this function to overestimate the distance that the agent must travel.

The algorithm uses a few auxiliary data structures, in particular one list (or similar) and one priority queue. The priority queue is called the open list, which holds those nodes that have yet to be visited, and the list is called the closed list, which holds the nodes that have already been visited. You usually want the priority list to treat the lowest number as the highest priority. It is also common for implementations to use additional data structures to simplify the algorithm and improve its performance. I will mention those cases further on.

Once with the heuristic and data structures in place, the algorithm performs the following steps:

1. Add the starting node to the open list with the highest possible priority
2. While there are nodes in the open list do the following
3. Remove the node with the highest priority from the open list
4. If the node meets the goal condition return the appropriate value and exit
5. For each of the nodes connected to this node do the following and add the current node to the closed list
6. Calculate the cost to reach this node from the starting node (It is common to use an additional data structure to store the cost to each node as the algorithm executes to avoid having to calculate this)
7. Calculate the value of the heuristic function for this node
8. Add these two values. If the node is not in the closed list and if the resulting value is lower than the cost obtained from a previous possible path, add it to the open list (It is also common to use the data structure holding the cost to each node to calculate the original cost).
9. If no solution has been found and the open list is empty, there is no node that meets the goal condition.

What the algorithm does is iteratively visit the node with the lowest estimated cost, which is obtained by adding the result of the heuristic to the cost of reaching the node. When visiting a node the algorithm checks if it meets the goal condition, in which case a solution has been found, and if not it adds every node connected to it to a priority queue and uses the estimated cost as the node’s priority. To all those familiar with Dijkstra’s algorithm, it can be viewed as a variation of A* where the heuristic is always 0.

Here is a possible implementation using C#. This implementation uses additional data structures to simplify certain steps. It is also assumed that the heuristic function is an instance variable of the containing class, as shown before in this post.

   1:  public GraphNode<T> PerformSearch(GraphNode<T> startNode, Predicate<GraphNode<T>> goalCondition)

   2:  {

   3:      Dictionary<GraphNode<T>, double> costToNode = new Dictionary<GraphNode<T>, double>();

   4:      PriorityQueue<double, GraphNode<T>> openList = new PriorityQueue<double, GraphNode<T>>(PriorityTarget.MinimumFirst);

   5:      GraphNodeList<T> closedList = new GraphNodeList<T>();

   6:   

   7:      GraphNode<T> currentNode = startNode;

   8:      costToNode[currentNode] = 0;

   9:   

  10:      openList.Push(Double.MinValue, currentNode);

  11:      while (openList.Count > 0)

  12:      {

  13:          currentNode = openList.Pop();

  14:   

  15:          if (goalCondition(currentNode))

  16:          {

  17:              closedList.Add(currentNode);

  18:              return currentNode;

  19:          }

  20:   

  21:          foreach (GraphNode<T> neighbour in currentNode.Neighbors.Keys)

  22:          {

  23:              double costToNeighbour = costToNode[currentNode] + currentNode.Neighbors[neighbour];

  24:              double totalUnderestimate = costToNeighbour + heuristicFunction(neighbour);

  25:              if (!closedList.Contains(neighbour) && (!costToNode.ContainsKey(neighbour) || costToNode[neighbour] > costToNeighbour))

  26:              {

  27:                  costToNode[neighbour] = costToNeighbour;

  28:                  openList.Push(totalUnderestimate, neighbour);

  29:              }

  30:          }

  31:          closedList.Add(currentNode);

  32:      }

  33:      return null;

  34:  }

As you can see the implementation is not really complex, taking about 30 lines of code. If you’re not concerned about the algorithm being generic then the code can be simplified and optimized quite a bit more. It should be noted that if you want to retrieve the path followed, a small bit of post-processing is necessary. In particular, you need to store how you got to each node, possibly using a dictionary, and then walk backwards from the goal node using that store until you find the starting node.

All in all, A* is a very popular algorithm with a very beautiful and easy to follow process. I would definitely recommend anyone with some time in their hands to play around with it, at least for a while.