A* pathfinding search in C# - Part 1

A* pathfinding search in C# - Part 2

Code available at GitHub: https://github.com/leniel/AStar

This is the last installment in the series about A* (A star) search.

The C# source code implemented is available in the final part of this post.

As promised in the last words of A* pathfinding search in C# - Part 2 today we’re gonna run a test case using the Romania map.

If you want to understand the whole process implemented in this solution, please start reading A* pathfinding search in C# - Part 1.

When you run the console application, you get the following screen:

You start by entering a Start and a Destination city picking up the ones you want from the list of Romania cities.

When you press Enter the console app will show you the shortest or best path based on the A* search algorithm.

As you can see in the above screenshot, the app shows us that the best path to go from Arad to Bucharest is the one that goes as follows:

From Arad to Sibiu -> Total cost = 223.236 km From Sibiu to Rimnicu Vilcea -> Total cost = 301.317 km From Rimnicu Vilcea to Pitesti -> Total cost = 348.536 km From Pitesti to Bucharest -> Total cost = 456.108 km

Note that the Total cost is the cost calculated so far for each path, that is, in the example shown above, Total cost = 348.536 km is the distance in kilometers for travelling from Arad to Pitesti.

No doubt this is the shortest path to follow if you plan to go from Arad to Bucharest. We could choose different possible routes but the total distance traveled would be greater than the one the app calculated for the shortest path. Let’s see why this is so using the method ViewOtherPaths (I commented about it in A* pathfinding search in C# - Part 2).

The following is the output of the console app when the method ViewOtherPaths is uncommented inside the FindPath method. This helps you debug and see why the app has chosen the above shortest path.

A* Search - Sample implementation by Leniel Macaferi, June 7-20, 2009

These are the Cities you can choose as Start and Destination in Romania:

Arad

Bucharest

Craiova

Dobreta

Eforie

Fagaras

Giurgiu

Hirsova

Iasi

Lugoj

Mehadia

Neamt

Oradea

Pitesti

Rimnicu Vilcea

Sibiu

Timisoara

Urziceni

Vaslui

Zerind

Enter a Start city: Arad

Enter a Destination city: Bucharest

Possible paths:

From Arad to Sibiu -> Total cost = 223.236 km

Estimation = 213.803 km

Priority Queue Cost = 437.039 km = (Total cost + Estimation)

From Arad to Timisoara -> Total cost = 48.459 km

Estimation = 408.79 km

Priority Queue Cost = 457.249 km = (Total cost + Estimation)

From Arad to Zerind -> Total cost = 51.908 km

Estimation = 431.034 km

Priority Queue Cost = 482.942 km = (Total cost + Estimation)

Possible paths:

From Arad to Sibiu -> Total cost = 223.236 km

From Sibiu to Rimnicu Vilcea -> Total cost = 301.317 km

Estimation = 154.102 km

Priority Queue Cost = 455.419 km = (Total cost + Estimation)

From Arad to Timisoara -> Total cost = 48.459 km

Estimation = 408.79 km

Priority Queue Cost = 457.249 km = (Total cost + Estimation)

From Arad to Sibiu -> Total cost = 223.236 km

From Sibiu to Fagaras -> Total cost = 287.59 km

Estimation = 178.296 km

Priority Queue Cost = 465.886 km = (Total cost + Estimation)

From Arad to Zerind -> Total cost = 51.908 km

Estimation = 431.034 km

Priority Queue Cost = 482.942 km = (Total cost + Estimation)

From Arad to Sibiu -> Total cost = 223.236 km

From Sibiu to Lugoj -> Total cost = 397.029 km

Estimation = 356.126 km

Priority Queue Cost = 753.155 km = (Total cost + Estimation)

From Arad to Sibiu -> Total cost = 223.236 km

From Sibiu to Arad -> Total cost = 446.473 km

Estimation = 420.536 km

Priority Queue Cost = 867.009 km = (Total cost + Estimation)

From Arad to Sibiu -> Total cost = 223.236 km

From Sibiu to Oradea -> Total cost = 444.358 km

Estimation = 434.745 km

Priority Queue Cost = 879.104 km = (Total cost + Estimation)

Possible paths:

From Arad to Sibiu -> Total cost = 223.236 km

From Sibiu to Rimnicu Vilcea -> Total cost = 301.317 km

From Rimnicu Vilcea to Pitesti -> Total cost = 348.536 km

Estimation = 107.572 km

Priority Queue Cost = 456.108 km = (Total cost + Estimation)

From Arad to Timisoara -> Total cost = 48.459 km

Estimation = 408.79 km

Priority Queue Cost = 457.249 km = (Total cost + Estimation)

From Arad to Sibiu -> Total cost = 223.236 km

From Sibiu to Fagaras -> Total cost = 287.59 km

Estimation = 178.296 km

Priority Queue Cost = 465.886 km = (Total cost + Estimation)

From Arad to Zerind -> Total cost = 51.908 km

Estimation = 431.034 km

Priority Queue Cost = 482.942 km = (Total cost + Estimation)

From Arad to Sibiu -> Total cost = 223.236 km

From Sibiu to Rimnicu Vilcea -> Total cost = 301.317 km

From Rimnicu Vilcea to Craiova -> Total cost = 400.614 km

Estimation = 183.042 km

Priority Queue Cost = 583.656 km = (Total cost + Estimation)

From Arad to Sibiu -> Total cost = 223.236 km

From Sibiu to Rimnicu Vilcea -> Total cost = 301.317 km

From Rimnicu Vilcea to Sibiu -> Total cost = 379.398 km

Estimation = 213.803 km

Priority Queue Cost = 593.201 km = (Total cost + Estimation)

From Arad to Sibiu -> Total cost = 223.236 km

From Sibiu to Lugoj -> Total cost = 397.029 km

Estimation = 356.126 km

Priority Queue Cost = 753.155 km = (Total cost + Estimation)

From Arad to Sibiu -> Total cost = 223.236 km

From Sibiu to Rimnicu Vilcea -> Total cost = 301.317 km

From Rimnicu Vilcea to Mehadia -> Total cost = 461.891 km

Estimation = 299.853 km

Priority Queue Cost = 761.744 km = (Total cost + Estimation)

From Arad to Sibiu -> Total cost = 223.236 km

From Sibiu to Rimnicu Vilcea -> Total cost = 301.317 km

From Rimnicu Vilcea to Lugoj -> Total cost = 504.328 km

Estimation = 356.126 km

Priority Queue Cost = 860.454 km = (Total cost + Estimation)

From Arad to Sibiu -> Total cost = 223.236 km

From Sibiu to Arad -> Total cost = 446.473 km

Estimation = 420.536 km

Priority Queue Cost = 867.009 km = (Total cost + Estimation)

From Arad to Sibiu -> Total cost = 223.236 km

From Sibiu to Oradea -> Total cost = 444.358 km

Estimation = 434.745 km

Priority Queue Cost = 879.104 km = (Total cost + Estimation)

Possible paths:

From Arad to Sibiu -> Total cost = 223.236 km

From Sibiu to Rimnicu Vilcea -> Total cost = 301.317 km

From Rimnicu Vilcea to Pitesti -> Total cost = 348.536 km

From Pitesti to Bucharest -> Total cost = 456.108 km

Estimation = 0 km

Priority Queue Cost = 456.108 km = (Total cost + Estimation)

Estimation = 408.79 km

Priority Queue Cost = 457.249 km = (Total cost + Estimation)

From Arad to Sibiu -> Total cost = 223.236 km

From Sibiu to Fagaras -> Total cost = 287.59 km

Estimation = 178.296 km

Priority Queue Cost = 465.886 km = (Total cost + Estimation)

Estimation = 431.034 km

Priority Queue Cost = 482.942 km = (Total cost + Estimation)

From Arad to Sibiu -> Total cost = 223.236 km

From Sibiu to Rimnicu Vilcea -> Total cost = 301.317 km

From Rimnicu Vilcea to Pitesti -> Total cost = 348.536 km

From Pitesti to Rimnicu Vilcea -> Total cost = 395.755 km

Estimation = 154.102 km

Priority Queue Cost = 549.858 km = (Total cost + Estimation)

From Arad to Sibiu -> Total cost = 223.236 km

From Sibiu to Rimnicu Vilcea -> Total cost = 301.317 km

From Rimnicu Vilcea to Craiova -> Total cost = 400.614 km

Estimation = 183.042 km

Priority Queue Cost = 583.656 km = (Total cost + Estimation)

From Arad to Sibiu -> Total cost = 223.236 km

From Sibiu to Rimnicu Vilcea -> Total cost = 301.317 km

From Rimnicu Vilcea to Sibiu -> Total cost = 379.398 km

Estimation = 213.803 km

Priority Queue Cost = 593.201 km = (Total cost + Estimation)

From Arad to Sibiu -> Total cost = 223.236 km

From Sibiu to Rimnicu Vilcea -> Total cost = 301.317 km

From Rimnicu Vilcea to Pitesti -> Total cost = 348.536 km

From Pitesti to Craiova -> Total cost = 452.104 km

Estimation = 183.042 km

Priority Queue Cost = 635.146 km = (Total cost + Estimation)

From Arad to Sibiu -> Total cost = 223.236 km

From Sibiu to Rimnicu Vilcea -> Total cost = 301.317 km

From Rimnicu Vilcea to Pitesti -> Total cost = 348.536 km

From Pitesti to Fagaras -> Total cost = 458.356 km

Estimation = 178.296 km

Priority Queue Cost = 636.653 km = (Total cost + Estimation)

From Arad to Sibiu -> Total cost = 223.236 km

From Sibiu to Lugoj -> Total cost = 397.029 km

Estimation = 356.126 km

Priority Queue Cost = 753.155 km = (Total cost + Estimation)

From Arad to Sibiu -> Total cost = 223.236 km

From Sibiu to Rimnicu Vilcea -> Total cost = 301.317 km

From Rimnicu Vilcea to Mehadia -> Total cost = 461.891 km

Estimation = 299.853 km

Priority Queue Cost = 761.744 km = (Total cost + Estimation)

From Arad to Sibiu -> Total cost = 223.236 km

From Sibiu to Rimnicu Vilcea -> Total cost = 301.317 km

From Rimnicu Vilcea to Lugoj -> Total cost = 504.328 km

Estimation = 356.126 km

Priority Queue Cost = 860.454 km = (Total cost + Estimation)

From Arad to Sibiu -> Total cost = 223.236 km

From Sibiu to Arad -> Total cost = 446.473 km

Estimation = 420.536 km

Priority Queue Cost = 867.009 km = (Total cost + Estimation)

From Arad to Sibiu -> Total cost = 223.236 km

From Sibiu to Oradea -> Total cost = 444.358 km

Estimation = 434.745 km

Priority Queue Cost = 879.104 km = (Total cost + Estimation)

This is the shortest path based on the A* Search Algorithm:

From Arad to Sibiu -> Total cost = 223.236 km

From Sibiu to Rimnicu Vilcea -> Total cost = 301.317 km

From Rimnicu Vilcea to Pitesti -> Total cost = 348.536 km

From Pitesti to Bucharest -> Total cost = 456.108 km

Do you wanna try A* Search again? Yes or No?

**A small change **One thing I changed in the code I posted on A* pathfinding search in C# - Part 2 was the foreach that enumerates the shortest path to write it on the screen. Before it read:

// Prints the shortest path. foreach(Node n in shortestPath.Reverse()) { Console.WriteLine(n.Key); }

Now it reads:

// Prints the shortest path. foreach(Path<Node> path in shortestPath.Reverse()) { if(path.PreviousSteps != null) { Console.WriteLine(string.Format("From {0, -15} to {1, -15} -> Total cost = {2:#.###} {3}", path.PreviousSteps.LastStep.Key, path.LastStep.Key, path.TotalCost, distanceType)); } }

As you can see I changed from Node to Path<Node>. To get this working I had to change the type returned by GetEnumerator in the class Path so that it returned Path<Node> instead of Node.

public IEnumerator<Path<Node>> GetEnumerator() { for(Path<Node> p = this; p != null; p = p.PreviousSteps) yield return p; }

This allowed me to enumerate over each path that composes the whole shortest path so that we can show the LastStep of the previous path and the LastStep of the current path. The Total cost travelled so far for each path is also available because we’re working with a path object.

**Last note**

A* is a really powerful search algorithm.

Hope you liked this series of posts about A* search as I liked to implement and write about it! It was a really good programming exercise.

** Visual Studio 2013 Solution with C# Console Application Project
**You can get the Microsoft Visual Studio Project at this GitHub repository:

https://github.com/leniel/AStar

To try out the code you can use the free Microsoft Visual C# Express Edition that you can get at: http://www.microsoft.com/express/vcsharp/