Introduction
This is about A* algorithm implementation which is about the way how we can find a best path between two positions. I already know that there are other A* implementations in this codeproject site. They are good, but I bet this is more simple and an easy implementation for beginners to understand.
There is no unnecessary code in this implementation, I just implement the A* algorithm pseudocode step by step in very intuitive ways. As you can see in the picture above, '#' means wall, each dot means available road, and 'o' means path that AI finds.
About A* algorithm
Shorty, A* is the most popular pathfinding algorithm to go from start to goal, based on efficiency of movement cost.
You can visit A* Pathfinding for Beginners(http://www.policyalmanac.org/games/aStarTutorial.htm) to learn how this algorithm works.
You can see pseudocode for A* that I used in this implementation at Justin Heyes-Jones A* tutorial. Visit here (http://www.geocities.com/jheyesjones/pseudocode.html) to see orginal pseudocode. The print-out of this pseudocode will help you a lot to understand this implementation.
Class Design
There are three primary classes in this implementation.
- Map - This class represents a map.
- Node - This class represents each tile on the map. It has two primary methods.
CompareTo
- This method allows us to decide which node is better. We can say current node is better if this method returns negative number, which means current node has lower cost than the other node being compared.
isMatch
- This allows us to decide whether two node's geomatical positions are same or not.
- SortedCostNodeList - This is a list that stores
Node
object list. We need to get off the lowest cost node from the list, so this list is implemented as sorted list order by cost value of the node, and we don't need to examine the costs of all elements in the list every time to pop the node which has the lowest cost because they are already sorted. Just pop one.This list has two primary methods.
push
- add node elements to the list at proper position order by node cost.
- Node's
CompareTo
method is used internally to sort order by cost.
pop
- just returns the lowest cost node from the list and remove it from the list.
Implementation
This is the core loop of the algorithm.
ArrayList SolutionPathList = new ArrayList();
Node node_goal = new Node(null,null,1,15,15);
Node node_start = new Node(null,node_goal,1,0,0);
SortedCostNodeList OPEN = new SortedCostNodeList ();
SortedCostNodeList CLOSED = new SortedCostNodeList ();
OPEN.push (node_start);
while (OPEN.Count>0)
{
Node node_current = OPEN.pop ();
if (node_current.isMatch (node_goal))
{
node_goal.parentNode = node_current.parentNode ;
break;
}
ArrayList successors = node_current.GetSuccessors ();
foreach (Node node_successor in successors)
{
int oFound = OPEN.IndexOf (node_successor);
if (oFound>0)
{
Node existing_node = OPEN.NodeAt (oFound);
if (existing_node.CompareTo (node_current) <= 0)
continue;
}
int cFound = CLOSED.IndexOf (node_successor);
if (cFound>0)
{
Node existing_node = CLOSED.NodeAt (cFound);
if (existing_node.CompareTo (node_current) <= 0 )
continue;
}
if (oFound!=-1)
OPEN.RemoveAt (oFound);
if (cFound!=-1)
CLOSED.RemoveAt (cFound);
OPEN.push (node_successor);
}
CLOSED.push (node_current);
}
Once we get to the goal, follow parent nodes to find the solution path.
Node p = node_goal;
while(p != null)
{
SolutionPathList.Insert(0,p);
p = p.parentNode ;
}
This A* implementation is very simple and good for beginners who want to know how A* algorithm works. Change map data in variety of ways, and check out how AI is smart to find the good path. Enjoy your programming.