Leniel Maccaferri's blog

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.

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:

A* Search console application

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:

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 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 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)

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 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 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)

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

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/

During my childhood I used to play video games. I started playing the Atari in my older cousins’ house in 1989-1990 when I was 6 to 7 years old, and then my uncle gave me a Phantom System in 1992. For some time I played a Master System in 1994/1995?. While in the house of my neighbor I played the Mega Drive. My newer cousins also had videogames and I used to play with them the Super Nintendo in 1996 and after that the Nintendo 64 bits in 1997.

My parents gave me a computer ( oh, a computer… how I wanted it! ) in 1997 and of course I played games on the computer. I kept playing games on the computer for a long time. It was only after I started the computer engineering graduation in 2003 that I definitely stopped playing games. What’s the reason for that? I also would like to know. : )

A hiatus of 6-7 years till I write this post.

Firstly I’ve decided to buy a video game console because I think it’s a excellent way to relax and one of the best pastimes. After all a computer engineer/software developer needs some fun too!
Secondly, I love technology and I get mesmerized by the evolution the videogame industry brings to our life and our eyes. Video games simulate the real world and help us understand the environment in which the game is built upon.
Last but not least because today I can afford a video game console.

How can those guys develop such things? Wow, that’s what I thought when I started playing again.

I chose the PlayStation 3 (PS3) platform having in mind its great graphics. There’s no limit to innovation when it comes to computer graphics and PS3 shows us just that.

On November 19 I bought the new PS3 slim model - 120 GB. To pair with it I also bought the so acclaimed game Call of Duty - Modern Warfare 2 also known as COD - MW2.

PlayStation 3 slim model

The combination of PS3 with COD MW 2 is fantastic. You pass exciting moments in front of the TV.

In just 3 days I completed all the single player missions in the recruiter profile. The only part that I didn’t like in the game: the single player campaign is too short! Despite that you get what you pay for, that is, great graphics, great playability and great sensations.

I have a wireless home network and the PS3 has wireless support. The wireless router is in my bedroom and the PS3 is in the living room. The network setup is really straightforward. After configuring your network you can connect to the PlayStation Store to download demos, see movies, read news about the gaming world and of course play online against fellow gamers (not AI) in multiplayer mode.

Below you can see my portable Id in the PlayStation Network also known as the PSN Network.

Other great feature PS3 has is the support to playback Blu-ray video.

That’s it. I’m back to the gaming world.

Feel free to invite me to your PSN friends list. It’s always good to play online. My PSN name is johnleniel.

I really recommend to anyone who can afford it to buy a modern seventh generation video game console. You won’t be disappointed. You’ll have a lot of fun. :- )