A* Search PathFinding Algorithm In C#

If you’ve ever taken part in an AI challenge or contest over the years, you’ve probably had to work out a path finding algorithm along the way. I remember many moons ago, as part of the Google AI Challenge (ended a few years ago which is a real shame), I actually swapped my solution to use Java just so I could use an A* search algorithm that I found on the internet. C# can be a bit weird in that for business applications, you can find a million examples on how to talk to Sharepoint, but when it comes to AI, Machine Learning, or even just data structures and algorithms in general, it can be a bit bare. So I thought I would quickly whip up a post on a dead simple implementation of the A* path finding algorithm in C#.

What Is A* Search?

It probably makes sense to rewind a little bit and ask, what exactly is the A* algorithm? A* Search is a path finding algorithm. Or in simpler terms, given a map, starting at one location, what is the most efficient way of getting to a second location, walking around walls, obstacles and ignoring dead ends.

For example if we had a map that looked like so :

A           |
--| |-------|
            | 
   |-----|  | 
   |     |  |
---|     |B |

How do we get from point A to point B? Obviously we can’t walk through walls, but a human can easily trace a nice easy path with your eye, so why can’t a computer do it? Well it can using A*!

The main thing about using A* Search is that it’s cost based. That is that it tries to find the optimal path to take, even if that may take additional processing.

Wikipedia will obviously explain a heck of a lot better than me! https://en.wikipedia.org/wiki/A*_search_algorithm

Jumping into the Code

While I’ll walk through the code in this post, you can get the entire gist here : https://gist.github.com/DotNetCoreTutorials/08b0210616769e81034f53a6a420a6d9 which has a complete working example. But I do recommend following along in this post anyway as I try and explain it as we go so it may be a bit easier to digest.

The first thing we want to do is create a “Tile” object. This essentially represents a square on a grid.

class Tile
{
	public int X { get; set; }
	public int Y { get; set; }
	public int Cost { get; set; }
	public int Distance { get; set; }
	public int CostDistance => Cost + Distance;
	public Tile Parent { get; set; }

	//The distance is essentially the estimated distance, ignoring walls to our target. 
	//So how many tiles left and right, up and down, ignoring walls, to get there. 
	public void SetDistance(int targetX, int targetY)
	{
		this.Distance = Math.Abs(targetX - X) + Math.Abs(targetY - Y);
	}
}

To walk through the properties for this object :

• X,Y are locations on a grid that we will use.
• Cost is how many tiles we had to traverse to reach here. So for example if this is right next to the starting tile, it would be a cost of “1”. If it was two tiles to the right, it would be a cost of 2 etc.
• Distance is the distance to our destination (e.g. the target tile). This is worked out using the SetDistance method where it’s basically, ignoring all walls, how many tiles left/right and up/down would it take to reach our goal.
• CostDistance is essentially the Cost + the Distance. It’s useful later on because given a set of tiles, we work out which one to “work on” by ordering them by the CostDistance. e.g. How many tiles we’ve moved so far + how many tiles we think it will probably take to reach our goal. This is important!
• Parent is just the tile we came from to get here.

Inside our main method (We are doing this inside a console app but you are welcome to edit this to your needs). We set up some basic code :

static void Main(string[] args)
{
	List<string> map = new List<string>
	{
		"A          ",
		"--| |------",
		"           ",
		"   |-----| ",
		"   |     | ",
		"---|     |B"
	};

	var start = new Tile();
	start.Y = map.FindIndex(x => x.Contains("A"));
	start.X = map[start.Y].IndexOf("A");

	var finish = new Tile();
	finish.Y = map.FindIndex(x => x.Contains("B"));
	finish.X = map[finish.Y].IndexOf("B");
	
	start.SetDistance(finish.X, finish.Y);

	var activeTiles = new List<Tile>();
	activeTiles.Add(start);
	var visitedTiles = new List<Tile>();
}

• Set up the “map” which is essentially a grid. In our example we use a list of strings but this grid or map can be made up any way you like.
• We record the “Start” tile, e.g. where we start,
• We record the “End” tile, e.g. where we finish
• And we create a list of “ActiveTiles” and “VisitedTiles”. We populate the “ActiveTiles” with our start block. These are tiles that we will essentially work on.

The next thing we need to do is a little helper method. What this does is that, given a particular tile (and the target tile), we want to get all the tiles around itself. It’s used to find the next set of tiles we can try and walk on. We actually don’t do many checks inside of here (For example, if it’s even optimal to walk to the tile beside us, we may be walking the wrong way!), but we do check whether it’s a valid tile to walk on.

The code looks like so :

private static List<Tile> GetWalkableTiles(List<string> map, Tile currentTile, Tile targetTile)
{
	var possibleTiles = new List<Tile>()
	{
		new Tile { X = currentTile.X, Y = currentTile.Y - 1, Parent = currentTile, Cost = currentTile.Cost + 1 },
		new Tile { X = currentTile.X, Y = currentTile.Y + 1, Parent = currentTile, Cost = currentTile.Cost + 1},
		new Tile { X = currentTile.X - 1, Y = currentTile.Y, Parent = currentTile, Cost = currentTile.Cost + 1 },
		new Tile { X = currentTile.X + 1, Y = currentTile.Y, Parent = currentTile, Cost = currentTile.Cost + 1 },
	};

	possibleTiles.ForEach(tile => tile.SetDistance(targetTile.X, targetTile.Y));

	var maxX = map.First().Length - 1;
	var maxY = map.Count - 1;

	return possibleTiles
			.Where(tile => tile.X >= 0 && tile.X <= maxX)
			.Where(tile => tile.Y >= 0 && tile.Y <= maxY)
			.Where(tile => map[tile.Y][tile.X] == ' ' || map[tile.Y][tile.X] == 'B')
			.ToList();
}

So we generate the tile above, below, left and right of us. We set the distance value to the goal on each tile. Then we check whether the tile is within the bounds of our map (e.g. X is not less than 0). Finally, we ensure that the tile we want to walk to is either empty (e.g. No wall), or it’s actually our destination.

Also note that we set the “Cost” of the tile to be always +1 of the parent. This makes sense as whatever the cost of the parent was, one more step is always going to cost… one more. Kinda seems dumb to point it out but it is important!

Now we are into the meat and bones of this. Heading back to our Main method (I’ve commented where the generation of the Map was before), we are going to now loop through our tiles and actually start walking through the map!

static void Main(string[] args)
{
	//This is where we created the map from our previous step etc. 

	while(activeTiles.Any())
	{
		var checkTile = activeTiles.OrderBy(x => x.CostDistance).First();

		if(checkTile.X == finish.X && checkTile.Y == finish.Y)
		{
			Console.Log(We are at the destination!);
			//We can actually loop through the parents of each tile to find our exact path which we will show shortly. 
			return;
		}

		visitedTiles.Add(checkTile);
		activeTiles.Remove(checkTile);

		var walkableTiles = GetWalkableTiles(map, checkTile, finish);

		foreach(var walkableTile in walkableTiles)
		{
			//We have already visited this tile so we don't need to do so again!
			if (visitedTiles.Any(x => x.X == walkableTile.X && x.Y == walkableTile.Y))
				continue;

			//It's already in the active list, but that's OK, maybe this new tile has a better value (e.g. We might zigzag earlier but this is now straighter). 
			if(activeTiles.Any(x => x.X == walkableTile.X && x.Y == walkableTile.Y))
			{
				var existingTile = activeTiles.First(x => x.X == walkableTile.X && x.Y == walkableTile.Y);
				if(existingTile.CostDistance > checkTile.CostDistance)
				{
					activeTiles.Remove(existingTile);
					activeTiles.Add(walkableTile);
				}
			}else
			{
				//We've never seen this tile before so add it to the list. 
				activeTiles.Add(walkableTile);
			}
		}
	}

	Console.WriteLine("No Path Found!");
}

So how does this work?

• First we keep looping until we have no more “active” tiles, that is, there’s basically no where we haven’t walked. If we break this loop, it means we couldn’t find any way to reach our goal (e.g. walls in the way). This is important so we don’t end up in an infinite loop.
• Next we take a tile off our list. Note that it’s not the first tile, nor the last tile. It’s the tile with the lowest current CostDistance. This ensures that we are always working on the most cost effective path at that very moment. It also ensures that should we come across a tile that is in our VisitedList, we can be sure that the cost of that tile in the VisitedList is going to be lower than whatever we currently have (Because the cost is only going to go up each loop!).
• If the tile we pull out matches our finish tile, then boom! We are done! I’ll add some more code in here shortly to show how to print out our entire path (Or you can check the Gist!)
• We remove our tile from the ActiveList, and add it to the VisitedList, as we are working on it now and anyone else that comes to this tile, should just know we’ve taken care of it.
• Next we get all the tiles adjacent to the current tile using our GetWalkableTiles method. Then we loop through them.
• If the walkable tile has already been visited in the past, then just ignore it.
• If the walkable tile is in the active tiles list, then that’s cool! But check that what we have now is not actually a better way to get to the same tile. In most cases this is just because of a small zigzag instead of going directly there.
• If we’ve never seen the tile before, then add it to the active tiles list.

And that’s it! We repeat this over and over and because we are pulling the tile with the lowest cost each time and walking from it, we can be sure that whenever we find a result, we don’t have to keep processing!

Now the code I used to output a nice way of looking at the path was like so :

if(checkTile.X == finish.X && checkTile.Y == finish.Y)
{
	//We found the destination and we can be sure (Because the the OrderBy above)
	//That it's the most low cost option. 
	var tile = checkTile;
	Console.WriteLine("Retracing steps backwards...");
	while(true)
	{
		Console.WriteLine($"{tile.X} : {tile.Y}");
		if(map[tile.Y][tile.X] == ' ')
		{
			var newMapRow = map[tile.Y].ToCharArray();
			newMapRow[tile.X] = '*';
			map[tile.Y] = new string(newMapRow);
		}
		tile = tile.Parent;
		if(tile == null)
		{
			Console.WriteLine("Map looks like :");
			map.ForEach(x => Console.WriteLine(x));
			Console.WriteLine("Done!");
			return;
		}
	}
}

Really all we are doing here is looping through each tile, and traversing to their parent. While doing so we are adding a * on the map to indicate we walked there, and also outputting the co-ordinates.

End Result

What does the end result output?

Retracing steps backwards...
10 : 5
10 : 4
10 : 3
10 : 2
9 : 2
8 : 2
7 : 2
6 : 2
5 : 2
4 : 2
3 : 2
3 : 1
3 : 0
2 : 0
1 : 0
0 : 0
Map looks like :
A***
--|*|------
   ********
   |-----|*
   |     |*
---|     |B
Done!

Pretty damn cool!

Again if you are struggling to follow along, you can grab the entire gist as a single file from here : https://gist.github.com/DotNetCoreTutorials/08b0210616769e81034f53a6a420a6d9 . Feel free to modify for your needs!