Click here to Skip to main content
15,867,453 members
Articles / Programming Languages / C#
Article

Very simple A* algorithm implementation

Rate me:
Please Sign up or sign in to vote.
4.29/5 (17 votes)
17 Mar 20052 min read 197.6K   5K   49   15
Simple A* pathfinding algorithm implementation for beginners

Sample Image - pic.gif

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.

C#
ArrayList SolutionPathList = new ArrayList();

//Create a node containing the goal state node_goal
Node node_goal = new Node(null,null,1,15,15);

//Create a node containing the start state node_start
Node node_start = new Node(null,node_goal,1,0,0);


//Create OPEN and CLOSED list
SortedCostNodeList OPEN = new SortedCostNodeList ();
SortedCostNodeList CLOSED = new SortedCostNodeList ();


//Put node_start on the OPEN list
OPEN.push (node_start);

//while the OPEN list is not empty
while (OPEN.Count>0)
{
 //Get the node off the open list
 //with the lowest f and call it node_current
 Node node_current = OPEN.pop ();

 //if node_current is the same state as node_goal we
 //have found the solution;
 //break from the while loop;
 if (node_current.isMatch (node_goal))
 {
   node_goal.parentNode = node_current.parentNode ;
   break;
 }

 //Generate each state node_successor that can come after node_current
 ArrayList successors = node_current.GetSuccessors ();

 //for each node_successor or node_current
 foreach (Node node_successor in successors)
 {
   //Set the cost of node_successor to be the cost of node_current plus
   //the cost to get to node_successor from node_current
   //--> already set while we were getting successors

   //find node_successor on the OPEN list
   int oFound = OPEN.IndexOf (node_successor);

   //if node_successor is on the OPEN list but the existing one is as good
   //or better then discard this successor and continue

   if (oFound>0)
   {
     Node existing_node = OPEN.NodeAt (oFound);
     if (existing_node.CompareTo (node_current) <= 0)
       continue;
   }


   //find node_successor on the CLOSED list
   int cFound = CLOSED.IndexOf (node_successor);

   //if node_successor is on the CLOSED list
   //but the existing one is as good
   //or better then discard this successor and continue;
   if (cFound>0)
   {
     Node existing_node = CLOSED.NodeAt (cFound);
     if (existing_node.CompareTo (node_current) <= 0 )
       continue;
   }

   //Remove occurences of node_successor from OPEN and CLOSED
   if (oFound!=-1)
      OPEN.RemoveAt (oFound);
   if (cFound!=-1)
      CLOSED.RemoveAt (cFound);

   //Set the parent of node_successor to node_current;
   //--> already set while we were getting successors

   //Set h to be the estimated distance to node_goal
   //(Using heuristic function)
   //--> already set while we were getting successors

   //Add node_successor to the OPEN list
   OPEN.push (node_successor);

  }
  //Add node_current to the CLOSED list
  CLOSED.push (node_current);
}

Once we get to the goal, follow parent nodes to find the solution path.

C#
//follow the parentNode from goal to start node
//to find solution
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.

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here


Written By
Korea (Republic of) Korea (Republic of)
Working in SK Communications,South Korea
as a web site developer.

Comments and Discussions

 
QuestionDiagonals Pin
Member 1170670329-Sep-15 23:53
Member 1170670329-Sep-15 23:53 
QuestionFreeze Pin
Member 1066570423-Feb-15 7:32
Member 1066570423-Feb-15 7:32 
AnswerRe: Freeze Pin
Member 1066570423-Feb-15 7:35
Member 1066570423-Feb-15 7:35 
SuggestionThank you! Pin
FrankRiese30-Jul-14 18:07
FrankRiese30-Jul-14 18:07 
QuestionGood job Pin
Member 1061706722-Feb-14 5:27
Member 1061706722-Feb-14 5:27 
General[Message Deleted] Pin
Danny Rodriguez27-Jan-08 9:19
Danny Rodriguez27-Jan-08 9:19 
GeneralI realy needed this.Thanks. Pin
toslavdsf329-Oct-07 14:22
toslavdsf329-Oct-07 14:22 
GeneralHELP W/ ROGUELIKE Pin
adiikan9-Oct-07 7:43
adiikan9-Oct-07 7:43 
QuestionWhat about isometric maps? Pin
worldspawn6913-Jul-07 17:18
worldspawn6913-Jul-07 17:18 
GeneralJust what I was looking for. Pin
f*** YOU18-Sep-06 5:27
f*** YOU18-Sep-06 5:27 
GeneralMapLittle Mistake Pin
Djooneagain15-Sep-05 22:39
Djooneagain15-Sep-05 22:39 
GeneralAn issue in the algorithm Pin
LynxRaven30-Mar-05 18:37
LynxRaven30-Mar-05 18:37 
GeneralRe: An issue in the algorithm Pin
Hyrum2-Dec-05 7:25
Hyrum2-Dec-05 7:25 
GeneralCan't Download Pin
Regina11_200018-Mar-05 9:44
Regina11_200018-Mar-05 9:44 
I haven't been able to download the demo. Is there something wrong with the link to the demo?

Thanks for the posting though. I'm keen on trying it.

Cheers;

Daver
GeneralRe: Can't Download Pin
Nish Nishant20-Mar-05 19:10
sitebuilderNish Nishant20-Mar-05 19:10 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.