Click here to Skip to main content
13,762,671 members
Click here to Skip to main content
Add your own
alternative version

Tagged as

Stats

53.7K views
2.6K downloads
138 bookmarked
Posted 14 Dec 2017
Licenced CPOL

Pathfinding Algorithms in C#

, 12 Jan 2018
Rate this:
Please Sign up or sign in to vote.
A comparison of Dijkstra and Astar

Unzip and open solution in Visual Studio 2017

Image

Introduction

Have you ever wondered how GPS applications calculate the fastest way to a chosen destination? As you will see, it is actually quite simple.

This article explains this and provides sample code that you are free to use as you like. The article also compares two common basic algorithms, Dijkstra and A*.

The Problem

Let’s say you have a map. You know where you are and where you want to go. The map has roads (they are called edges) that connect the nodes (places with coordinates).

From every node, you can go to one or many edges. An edge has a cost (e.g. length or time it takes to travel it).
For small maps, one could perhaps calculate all possible routes to the destination and select the shortest. But that is not very practical for maps with many nodes as the combinations grow exponentially.

Dijkstra

The Dijkstra algorithm was discovered in 1959 by Edsger Dijkstra. This is how it works:

  1. From the start node, add all connected nodes to a priority queue.
  2. Sort the priority queue by lowest cost and make the first node the current node.
    For every child node, select the best that leads to the shortest path to start.
    When all edges have been investigated from a node, that node is "Visited" and you don´t need to go there again.
  3. Add each child node connected to the current node to the priority queue.
  4. Go to step 2 until the queue is empty.
  5. Recursively create a list of each nodes node that leads the shortest path from end to start.
  6. Reverse the list and you have found the shortest path

In other words, recursively for every child of a node, measure its distance to the start. Store the distance and what node led to the shortest path to start. When you reach the end node, recursively go back to the start the shortest way, reverse that list and you have the shortest path.

Below is my Dijkstra Algorithm implementation in C# code. It might be easier to understand than the above.

public List<Node> GetShortestPathDijkstra()
{
    DijkstraSearch();
    var shortestPath = new List<Node>();
    shortestPath.Add(End);
    BuildShortestPath(shortestPath, End);
    shortestPath.Reverse();
    return shortestPath;
}

private void BuildShortestPath(List<Node> list, Node node)
{
    if (node.NearestToStart == null)
        return;
    list.Add(node.NearestToStart);
    BuildShortestPath(list, node.NearestToStart);
}

private void DijkstraSearch()
{
    Start.MinCostToStart = 0;
    var prioQueue = new List<Node>();
    prioQueue.Add(Start);
    do {
        prioQueue = prioQueue.OrderBy(x => x.MinCostToStart).ToList();
        var node = prioQueue.First();
        prioQueue.Remove(node);
        foreach (var cnn in node.Connections.OrderBy(x => x.Cost))
        {
            var childNode = cnn.ConnectedNode;
            if (childNode.Visited)
                continue;
            if (childNode.MinCostToStart == null ||
                node.MinCostToStart + cnn.Cost < childNode.MinCostToStart)
            {
                childNode.MinCostToStart = node.MinCostToStart + cnn.Cost;
                childNode.NearestToStart = node;
                if (!prioQueue.Contains(childNode))
                    prioQueue.Add(childNode);
            }
        }
        node.Visited = true;
        if (node == End)
            return;
    } while (prioQueue.Any());
}

Dijkstra

This is a randomly generated map in my test program. The dots are nodes and between them are lines which represent edges. This map consists of 5000 nodes and 15000 edges.

Lighter colored dots are visited by the search algorithm and the best path is drawn in green.

A* Algorithm

There are many improvements of Dijkstra’s algorithm. One of the most common is called A*. It is basically the same as Dijkstra with one simple modification.

Edges are prioritized also with respect to how much closer that edge leads to a straight-line distance to the goal. So before running an A* search, the straight-line distance to the final destination has to be measured for every node, which is easy if you know each nodes coordinate. This is the simplest form of A* and its definition also allows for improvments of the heuristics function. (In this case StraightLineDistanceToEnd)

This algorithm has a big performance advantage since it does not need to visit as many nodes when the direction of the path end is known.

See my implementation below. Marked in yellow what is added to Dijkstra’s Algorithm.

public List<Node> GetShortestPathAstar()
{
    foreach (var node in Map.Nodes)
        node.StraightLineDistanceToEnd = node.StraightLineDistanceTo(End);
    AstarSearch();
    var shortestPath = new List<Node>();
    shortestPath.Add(End);
    BuildShortestPath(shortestPath, End);
    shortestPath.Reverse();
    return shortestPath;
}

private void AstarSearch()
{
    Start.MinCostToStart = 0;
    var prioQueue = new List<Node>();
    prioQueue.Add(Start);
    do {
        prioQueue = prioQueue.OrderBy(x => x.MinCostToStart + x.StraightLineDistanceToEnd).ToList();
        var node = prioQueue.First();
        prioQueue.Remove(node);
        NodeVisits++;
        foreach (var cnn in node.Connections.OrderBy(x => x.Cost))
        {
            var childNode = cnn.ConnectedNode;
            if (childNode.Visited)
                continue;
            if (childNode.MinCostToStart == null ||
                node.MinCostToStart + cnn.Cost < childNode.MinCostToStart)
            {
                childNode.MinCostToStart = node.MinCostToStart + cnn.Cost;
                childNode.NearestToStart = node;
                if (!prioQueue.Contains(childNode))
                    prioQueue.Add(childNode);
            }
        }
        node.Visited = true;
        if (node == End)
            return;
    } while (prioQueue.Any());
}

Astar

This is the same map as above, but the path is calculated with A* algorithm. As you can see, there are much less nodes that needs to be visited.

Results

When running both algorithms on the same map of 500,000 nodes, I get these results.

  Dijkstra A*
Visited nodes 330,871 19,410
Time to calculate (ms) 850 127
Cost of best path 14,322 22,994
Distance of shortest path 0,82446 0,82446

As you can see in the table above, A* algorithm is about 7 times faster than Dijkstra, and they both find the shortest path.
However, when a random number is generated for the cost of an edge, Dijkstra finds a path of lower cost.
In a real map, for example, the shortest path isn’t always the best. Driving on roads with higher speed limit will probably take you to your destination sooner. That is why adding a random number to the cost of an edge makes this experiment more realistic.

Conclusion

So what algorithm is the best path finding algorithm of Dijkstra and A*?
I’d say it depends. If you are only interested in the shortest path, it is A*.
It is much faster, and it gives the same result as Dijkstra. But if there are other aspects of the cost of an edge than its length, Dijkstra is better in finding the best path than this version of A*. After all, it is still very fast. I think 500,000 nodes is a very large data set. I also think my implementation can be optimized a lot.

Challenge

If you are also childishly fond of programming challenges, maybe you want to program a robot to find its way out of a maze?

You might need some path finding algorithms to solve it.
See this site: http://airobots.azurewebsites.net/

Thanks for reading and I hope you find path finding algorithms are as much fun as I do by now.

Have a nice day!

History

  • December 10, 2017 - Version 1.0
  • December 20, 2017 - Version 1.0.1
    • Minor spelling fixes
  • Januari 13, 2018 - Version 1.0.2
    • Clarified that A* can be improved.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

KristianEkman
Software Developer (Senior)
Sweden Sweden
No Biography provided

You may also be interested in...

Comments and Discussions

 
QuestionArticles Pin
Explorer Whiz8-Jul-18 19:48
professionalExplorer Whiz8-Jul-18 19:48 
QuestionRapidly-exploring random trees? Pin
ipavlu1-Jul-18 15:19
professionalipavlu1-Jul-18 15:19 
AnswerRe: Rapidly-exploring random trees? Pin
KristianEkman3-Jul-18 2:51
memberKristianEkman3-Jul-18 2:51 
GeneralRe: Rapidly-exploring random trees? Pin
ipavlu4-Jul-18 13:53
professionalipavlu4-Jul-18 13:53 
QuestionThanks! :thumbsup: Pin
cheyennedev76-Feb-18 9:52
membercheyennedev76-Feb-18 9:52 
PraiseYou had me at Dijkstra Pin
AnotherKen15-Jan-18 15:44
professionalAnotherKen15-Jan-18 15:44 
GeneralRe: You had me at Dijkstra Pin
KristianEkman16-Jan-18 8:19
memberKristianEkman16-Jan-18 8:19 
GeneralMy vote of 5 Pin
wmjordan12-Jan-18 15:30
professionalwmjordan12-Jan-18 15:30 
GeneralRe: My vote of 5 Pin
KristianEkman12-Jan-18 21:16
memberKristianEkman12-Jan-18 21:16 
GeneralA* tweak : Marco Polo Pin
HeshanHenry8-Jan-18 18:27
memberHeshanHenry8-Jan-18 18:27 
GeneralRe: A* tweak : Marco Polo Pin
KristianEkman8-Jan-18 21:15
memberKristianEkman8-Jan-18 21:15 
GeneralRe: A* tweak : Marco Polo Pin
HeshanHenry15-Jan-18 3:59
memberHeshanHenry15-Jan-18 3:59 
GeneralRe: A* tweak : Marco Polo Pin
cheyennedev76-Feb-18 7:44
membercheyennedev76-Feb-18 7:44 
GeneralRe: A* tweak : Marco Polo Pin
HeshanHenry6-Feb-18 13:52
memberHeshanHenry6-Feb-18 13:52 
GeneralMy vote of 5 Pin
Igor Ladnik6-Jan-18 9:07
professionalIgor Ladnik6-Jan-18 9:07 
GeneralRe: My vote of 5 Pin
KristianEkman8-Jan-18 11:36
memberKristianEkman8-Jan-18 11:36 
GeneralMy vote of 5 Pin
Mike Barthold5-Jan-18 21:27
professionalMike Barthold5-Jan-18 21:27 
GeneralRe: My vote of 5 Pin
KristianEkman5-Jan-18 22:03
memberKristianEkman5-Jan-18 22:03 
Praise"Real" calculation Pin
leif neland27-Dec-17 2:29
memberleif neland27-Dec-17 2:29 
GeneralRe: "Real" calculation Pin
KristianEkman27-Dec-17 2:55
memberKristianEkman27-Dec-17 2:55 
PraiseMy vote of 5 Pin
Antony James22-Dec-17 11:39
memberAntony James22-Dec-17 11:39 
GeneralRe: My vote of 5 Pin
KristianEkman24-Dec-17 9:45
memberKristianEkman24-Dec-17 9:45 
QuestionHalfway there Pin
Emile van Gerwen21-Dec-17 0:36
memberEmile van Gerwen21-Dec-17 0:36 
AnswerRe: Halfway there Pin
KristianEkman21-Dec-17 2:09
memberKristianEkman21-Dec-17 2:09 
GeneralRe: Halfway there Pin
Sacha Barber22-Dec-17 13:29
mvpSacha Barber22-Dec-17 13:29 

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.

Permalink | Advertise | Privacy | Cookies | Terms of Use | Mobile
Web06-2016 | 2.8.181112.3 | Last Updated 13 Jan 2018
Article Copyright 2017 by KristianEkman
Everything else Copyright © CodeProject, 1999-2018
Layout: fixed | fluid