A* pathfinding search in C# - Part 1
A* pathfinding search in C# - Part 2
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)
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 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 2008 C# Console Application
You can get the Microsoft Visual Studio Project at:
http://sites.google.com/site/leniel/blog/AStar.zip
To try out the code you can use the free Microsoft Visual C# 2008 Express Edition that you can get at: http://www.microsoft.com/express/vcsharp/
7 comments:
Interesting! but why Romania?
Hi Anonymous,
Romania is used in various pieces of teaching material about Artificial Intelligence (AI).
When I was studying Artificial Intelligence in the Computer Engineering course (2007), the material my teacher used had Romania to illustrate a workspace for the path finding algorithms.
I decided to maintain Romania as way to remember teaching material related to AI.
All the best,
Leniel Macaferi
ello MR. Lenie ;)
my name is nor amalina and from malaysia. i'm take degree of mathematical.. i'm doing A* algorithm
for my final year project. MY friend teach me about how to calculate manually
using A* algorithm and we use the same map, "Romania".
But, she teach me about to find straight line cost.
unfortunALy, her leture only teach them manually.
so, its difficult to me.
To find straight line cost takes long time,
i must find one by one of each node. (i'm using google draft) and
i only can use excell.
Luckily, i find your blog and i can see the way u find using c#.
I see that ur program is very interesting
and easy to find the shortest path.
For ur information, this is my first time using c#.
i try to follow what you doing and download the c# and the file that u have done.
but, there are certain following i cannot understand. i read ur blog path1,2 and 3
many times but still cannot get.Actually, i cannot understand about how u get this one:
private static void FillGraphWithGridMap(Graph graph)
{
// Vertexes
graph.AddNode("Arad", null, 46, -114);
graph.AddNode("Bucharest", null, 452, -329);
.
.
.
.
.
the number of (46,-114), (452,-329) and etc....
// Edges
// Arad <-> Zerind
graph.AddUndirectedEdge("Arad", "Zerind", 53);
// Arad <-> Timisoara
graph.AddUndirectedEdge("Arad", "Timisoara", 107);
.
.
.
.
and the number (53), (107) and etc....
so, can u explain to me how do u get that number. only this one i cannot get.
I try many times but still cannot get the answer.so, can u help me? i hope so..
sorry for disturbing u..
thank you very very much..=)
Hello Nor Amalina,
I had a hard time to remember these ones... :) Great question indeed.
Let's shed some light into this:
If you open this image inside Paint and pass your mouse over each city, you'll get it's proximate coordinates within the map/grid. The left/top most position being (X = 0, Y = 0). The coordinates values (X, Y) were the values I used to fill the graph with data.
// Vertexes
graph.AddNode("Arad", null, 46, -114);
46 = (X) position in the grid
-114 = (Y) position in the grid
// Edges
// Arad <-> Zerind
graph.AddUndirectedEdge("Arad", "Zerind", 53);
I just subtract the values to get a supposed cost between the cities:
ABS(-114) - ABS(-61) = 53
-114 = Y position of Arad
-61 = Y position of Zerind
ABS = absolute value not considering the negative sign.
That's it.
Hope it helps.
All the best (final project) and keep improving your knowledge.
Leniel
hello leniel, ;)
thank you for reply my post..=)
i will check by using the paint.
thanks a lot~
may god bless u =)
hello leniel,
sorry for disturbing u again ;)
i have problem and question in this c# and hope u can help me~
firstly, i already key in my data into ur c#..it's successful but some of my node cannot compute..for ur information, my nodes are 60 nodes.
when i check with my maps, i can see that error appear when the calculation calculate the second time.
it's look like looping and after that error appear.So, i cannot get my shortest path by using a* algorithm in C# because the error.
why its happen? it is because my nodes are so many?
the error that appear in my c#:
..........................................
node1.Neighbors.Cast().Single(
etn => etn.Neighbor.Key == node2.Key).Cost;
..............................................
secondly, what mean by "etn"?
it seen that error from this, but i don't know it is true or not..
thirdly, i wonder where manhattan distance are used in c#? i understand about haversine and the uses in c# by using longitud & latitude but, about manhattan distance, i still cannot get the idea how it work..
thats all.hope u can help me =)
thank U very very much..
Nor Amalina
Hey Nor,
I won't be able to assert for sure where is the error.
If you don't mind, I'd like to run a test with your data.
Send me your C# project with the modified source files. My e-mail is in this post.
etn means Edge to Neighbour.
Manhattan distance is a Estimation/Heuristic function. You can read more about it here.
I'm waiting your e-mail so that I can help you more. :D
Leniel
Post a Comment