Click here to Skip to main content
15,181,193 members
Articles / Programming Languages / C#
Posted 3 Jan 2004


75 bookmarked

Path finding in C#

Rate me:
Please Sign up or sign in to vote.
4.62/5 (22 votes)
3 Jan 20045 min read
A generic implementation of the A* (AStar) path finding algorithm in C#.


As I was working on my own little game project, I searched the net for implementations of the A* path finding algorithm in C#, but I could not find any.

There were many, in pretty much every other language, but they either used very language specific features (like templates in C++) or were implemented in a way that just didn't seem very extensible, so I decided to write my own in C#.

I will give a brief introduction to the inner workings of the A* algorithm spiced up with some code samples from the actual implementation. I will also spend a little time explaining how to make your own AStarNode class.

The A* algorithm

There are a few choices in path finding when it comes to algorithms. A* is probably the most popular one, because it is quite flexible.

A* can be used to solve a myriad of different problems, like:

  • Combinatory puzzles like Rubric Cube or 8-puzzles.
  • Route finding.
  • Robot navigation.
  • And, of course, path finding in video games, which is what we are going to use it for.

The reason the A* algorithm works so well, is that it favors points that are close to the starting point, and points that are close to the goal as well.


As mentioned earlier, the A* algorithm both favors the distance from the start state (this is called the Cost in the program, traditionally this is called g()) and the estimated distance to the goal (this is called GoalEstimate in the program, traditionally this is called h()).

In my test of the A* class, I let the character move in 8 possible directions on a 2-dimensional map, so I will be using the "Diagonal Distance" approach.

Many different mathematical formulas can be used as heuristic functions when doing an A* search, it all depends on how your character moves.

This article discusses which formula is best used for which movement.

Data structures

Internally the A* algorithm has two lists, the OPEN list, which holds all the nodes that are possible ways to the goal, this is also known as the frontier, and the CLOSED list, which holds all the nodes we have expanded.

Many different data structures are possibly good choices for these lists, but to keep complexity down, I have implemented an "always sorted" array list, that I call Heap. It implements both the IList and IClonable interfaces, even though they are not really used in this project.

The two most important methods relating to the A* search:

/// <summary>
/// Returns the topmost object on the list and removes it from the list
/// </summary>
/// <returns>Returns the topmost object on the list</returns>
public object Pop();

/// <summary>
/// Pushes an object on list. It will be inserted at the right spot.
/// </summary>
/// Object to add to the list
/// <returns></returns>
public void Push(object Object); 

I am considering tuning this part in a later article, possible using a binary heap as the data structure. More on this later.


The class has been designed to be very extensible. No code in the actual AStarNode class does any calculations relating to coordinates and such, so it should be possible to use this class to solve any A* problem, not just relating to 2-dimensional grids.

Later I will explain how to implement your own child of the AStarNode class.

The actual A* algorithm

The implementation of the A* main loop is pretty straight forward. I will go through it step-by-step and explain what is going on.

First we assign the starting node and the goal node to private variables. These will be used through-out the entire pathfinding. Then we add the starting node as our initial search state:

FStartNode = AStartNode;
FGoalNode = AGoalNode;


Then we start our main loop. We will keep looping as long as there are still nodes on our heap:

while(FOpenList.Count > 0) 

Then we get the node with the lowest TotalCost off the OPEN list. Since the heap is always sorted according to the IComparable interface implementation of the AStarNode class, this happens just by popping the value off the heap:

// Get the node with the lowest TotalCost
AStarNode NodeCurrent = (AStarNode)FOpenList.Pop();

If the current node is the solution, we will now copy the completed path to the Solution list:

// If the node is the goal copy the path to the solution array
if(NodeCurrent.IsGoal()) {
  while(NodeCurrent != null) {

    NodeCurrent = NodeCurrent.Parent;

Then we ask the AStarNode child to give us all possible successors of the current node (except the parent of the current node of course):

// Get successors to the current node

Then we loop through the successors and see if they are worth anything:

foreach(AStarNode NodeSuccessor in FSuccessors)

First we see if the successor node is already on the OPEN list, if it is and the TotalCost is higher than the existing one, we will discard this successor node:

// Test if the currect successor node is on the open list, if it is and
// the TotalCost is higher, we will throw away the current successor.
AStarNode NodeOpen = null;
  NodeOpen = (AStarNode)FOpenList[FOpenList.IndexOf(NodeSuccessor)];
if((NodeOpen != null) && (NodeSuccessor.TotalCost > NodeOpen.TotalCost)) 

Then we do the exact same thing on the CLOSED list:

// Test if the currect successor node is on the closed list, if it is and
// the TotalCost is higher, we will throw away the current successor.
AStarNode NodeClosed = null;
  NodeClosed = (AStarNode)FClosedList[FClosedList.IndexOf(NodeSuccessor)];
if((NodeClosed != null) && (NodeSuccessor.TotalCost > NodeOpen.TotalCost)) 

Then we remove the instances found on the OPEN and CLOSED list:

// Remove the old successor from the open list
// Remove the old successor from the closed list

Then we add the current successor to the OPEN list and end the loop:

  // Add the current successor to the open list

Then last, but not least, we will add the current node to the closed list and end the loop:

  // Add the current node to the closed list

This concludes the main loop in the A* algorithm. Note, that there are circumstances where this implementation can enter an end-less loop. If, for example, the goal is unreachable. It is easy to implement ways to exit the loop, but I will leave the refinement of the implementation for a later time.

Here's how it looks when you run it with one of the test maps:

Sample screenshot

Creating your own AStarNode class

To create your own AStarNode descendant, you need to override all the virtual members of the AStarNode class:

public virtual bool IsSameState(AStarNode ANode);
public virtual void Calculate();
public virtual void GetSuccessors(ArrayList ASuccessors);
public virtual void PrintNodeInfo();

The implementation of the IsSameState() method must check all state information (i.e. coordinates), if it's the same state it should return true, otherwise false.

The implementation of the Calculate() method must calculate the GoalEstimate (the heuristic) according the state information and the GoalNode.

The implementation of the GetSuccessors() method must place all possible successors of the node itself on the ASuccessors ArrayList.

The implementation of the PrintNodeInfo() method should print whatever information is available about the state. The current code calls it from the private method PrintNodeList() on the AStar class to print information about the lists. You can place calls to PrintNodeList in strategic places in the code if you want to see what is going on when the code is path finding.


With this class, you should be able to implement A* path finding to your own C# projects. The implementation allows for any kind of A* search to be done. Other people have implemented solving of 8-puzzles using the same generic algorithm.

More information

This article was inspired by other peoples' work:

And for a very interesting graphical look:


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


About the Author

Sune Trudslev
Team Leader momondo
Denmark Denmark
Sune has been programming since 1985.

He has worked with both assembler and many different programming languages, such as: Basic, Fortran, Pascal, C, C++, Delphi, and lately C#.

Sune is married and has two small children and is currently working as a developer for a Danish company called Skygate, currenly working on a cheap flight search engine called Momondo.

Personal blog can be found here.

Comments and Discussions

QuestionHeuristic used doesn't work well with different movement weights Pin
Member 79100464-May-14 7:49
MemberMember 79100464-May-14 7:49 
QuestionFixed Code Here; Shortest Paths returned Pin
Dan DiCicco26-Aug-13 12:20
MemberDan DiCicco26-Aug-13 12:20 
AnswerRe: Fixed Code Here; Shortest Paths returned Pin
Member 1076198120-Apr-14 11:33
MemberMember 1076198120-Apr-14 11:33 
GeneralRe: Fixed Code Here; Shortest Paths returned Pin
StudioWolfox27-Apr-14 1:43
MemberStudioWolfox27-Apr-14 1:43 
GeneralRe: Fixed Code Here; Shortest Paths returned Pin
Member 131754156-May-17 5:57
MemberMember 131754156-May-17 5:57 
QuestionQuestion about full cost, opened and closed lists Pin
DmitrijNik14-Apr-13 1:05
MemberDmitrijNik14-Apr-13 1:05 
NewsExistent combinatorial optimization component Pin
dark_sidus19-Aug-07 1:36
Memberdark_sidus19-Aug-07 1:36 
QuestionSum nodes cost? Pin
stevenkong20-Apr-06 3:16
Memberstevenkong20-Apr-06 3:16 
GeneralBug responsible for slow Pin
Wojciech Wawrzyniak4-Mar-06 12:32
MemberWojciech Wawrzyniak4-Mar-06 12:32 
GeneralClosed List Pin
jcuglo7-Feb-06 7:58
Memberjcuglo7-Feb-06 7:58 
Generalquestion Pin
Nadav_h18-Jan-06 6:40
MemberNadav_h18-Jan-06 6:40 
GeneralRe: question Pin
BuggyBrain2-Jun-06 2:47
MemberBuggyBrain2-Jun-06 2:47 
Question.Contains?? Pin
luketheduke6-Jan-06 3:01
Memberluketheduke6-Jan-06 3:01 
AnswerRe: .Contains?? Pin
DrGLaZ1-May-06 0:45
MemberDrGLaZ1-May-06 0:45 
GeneralRe: .Contains?? Pin
luketheduke1-May-06 5:33
Memberluketheduke1-May-06 5:33 
GeneralRe: .Contains?? [modified] Pin
Vecware8-Sep-08 13:39
MemberVecware8-Sep-08 13:39 
Generalsmall fix Pin
coyotesoftware13-Dec-05 10:24
Membercoyotesoftware13-Dec-05 10:24 
GeneralQuestion about IComparer Pin
Johnny Scanner31-Jul-05 21:13
MemberJohnny Scanner31-Jul-05 21:13 
GeneralRe: Question about IComparer Pin
terpstradave28-May-07 11:15
Memberterpstradave28-May-07 11:15 
GeneralPath Finding with Collision Avoidance Pin
sridevi swamy22-Jun-05 4:17
Membersridevi swamy22-Jun-05 4:17 
GeneralRe: Path Finding with Collision Avoidance Pin
Johnny Scanner31-Jul-05 21:16
MemberJohnny Scanner31-Jul-05 21:16 
GeneralAn issue for games... Pin
LynxRaven30-Mar-05 19:29
MemberLynxRaven30-Mar-05 19:29 
GeneralRe: An issue for games... Pin
Johnny Scanner31-Jul-05 21:21
MemberJohnny Scanner31-Jul-05 21:21 
GeneralSlow and lot of bugs... Pin
jplacombe28-Feb-05 5:43
Memberjplacombe28-Feb-05 5:43 
GeneralBug Pin
Alex_V_X8-Feb-05 21:08
MemberAlex_V_X8-Feb-05 21:08 

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.