C# - Visualizing Path Finding With Dijkstra, AStar, Bi-directional Dijkstra's, and Bi-directional A* Algorithms

• Download source and Demo - 94.2 KB
 

Overview

This article demonstrates path finding with the most popular path-finding algorithms: Dijkstra and AStar. It considers two additional derivative algorithms: Bi-Directional Dijkstra and Bi-Directional A*. It can be very useful for illustrating these algorithms.

Objective

After reading this article and its code, you should understand the A* and Dijkstra's algorithms, and be able to implement them yourself.

Introduction

Dijkstra's and A* algorithms are very popular. AStar algorithm, which is an enhanced version of Dijkstra's, is widely used in navigation systems and in games. Usually, AStar is used when we know the target location, while Dijkstra's is used when we don't know where the target is exactly. Both algorithms find the shortest path between two points on a graph, though AStar may find a bit longer path (rarely) than Dijkstra's. In terms of speed, AStar is much faster than Dijkstra's, because AStar searches first where it "predicts" to find the target. In contrast, Dijkstra's searches everywhere. For time, this makes the worst case of AStar the same as Dijkstra's.

We will consider a demo that illustrates the algorithms. Walls that cannot be crossed can be generated randomly and manually (walls are denoted as blue squares).

These are some snapshots of our demo while the algorithms are working. Start and target points are denoted with green and red, respectively.

Dijkstra's algorithm illustration: searches everywhere.

A* algorithm illustration: firstly searches where it expects to find the target.

Background

You should feel comfortable using C#. A basic knowledge of GDI+ graphics is also appreciated.

The Graph

A graph is a group of connected nodes. The node maybe any point: a city, a house, or anything else. Each node connects to the other with an "edge", which maybe the "street" between two cities (nodes). Sometimes the "node" is referred to as the "vertex". Each node has a distance between it and the other connected vertex, which we call "the cost of edge" (so the street length in kilometers is the "cost" of it). The nodes and graph maybe in whatever shape, we will consider square nodes here. We will assume a distance of 10 units between the two neighboring squares horizontally or vertically, and we will assume 14 units between two diagonal neighbors. Nevertheless, on a real-world graph, distance is not constant. We will mark every square with its cost values from the start point (or start and end points, according to the used algorithm), as we will see shortly.

Graph algorithms are used usually to find a path between two nodes. In this article, we are interested in finding the shortest path between two nodes. This problem was raised in the middle of the last century. Computer scientist Edsger Dijkstra invented a good algorithm, in 1956, that solves the single-source shortest path problem for a graph with nonnegative edge path costs, producing a shortest path tree. Later in 1968, an enhanced version of Dijkstra's algorithm was published: A* algorithm. A* uses Dijkstra's algorithm with some heuristics to find a path. There are several heuristics for A*, one of them is called "Manhattan", which we will consider here.

Dijkstra's and A* Algorithms

I highly recommend this excellent A* tutorial: click here. This demo is a result of learning this tutorial. Thanks to the author Patrick Lester.

As we saw in the previous illustrations, AStar searches first where it expects to find the target node. But how can it predict the target location, so it searches near it firstly?

Well, let's take it simply, and from the start.

Imagine you are in a street and you want to go to your home. You want to reach your home using the shortest way. 

What you will do is divide the area into squares. You will give each square a distance from the starting point (i.e., the number of steps required to reach it). So, for example, your square (starting square) has a distance of 0. The right square from your position has a distance of 1. The right of that right square has a distance of 2, and so on.

Now, you will move anywhere until you reach home. In order to move anywhere, you write the 8-neighbor (2 horizontally, 2 vertically, and 4 diagonally) squares from you to a list. Call this list "open list". To calculate their distances, you add your square distance from the starting point to the distance between you and the new square (i.e., new_distance = myDistanceFromStart + distanceBetweenNewAndMe). Then, we choose the square having the lowest distance and move to it. 

In order to remember the path later, we add an arrow that points to the parent (the square that leads to it). So we add an arrow from our new square to the old one. When you move to this lowest-distance square, add again the 8 neighbor squares of that square to the open list, then choose the one having the lowest distance, move to it, and add a parent arrow. Keep repeating until you reach the target. When we find the target, we will follow the parent arrows from the target point in reverse until we reach the starting point, and thus we find the shortest path.

You don't want to back to already visited squares, so when you visit a square, you remove it from the open list and write it in a list in which you put squares you don't want to back to. Call this list "closed list". While you are checking the 8 neighbors, what if one of them is in the open list already? In this case, check if your distance is lower than the old distance in this square. If so, change its arrow to point to your square (i.e., your square's path is shorter). Recall that after we add a square to the closed list, we don’t back to it again. Hence, if we find that the neighbor square is in the closed list, we ignore it. 

Well, what we were taking about is Dijkstra's algorithm; we calculate a distance from the starting point for every square, and let's call this distance "G cost",  and select each time the lowest cost square. Hence, Dijkstra's algorithm is branched as a "greedy" algorithm, since it selects each time best square from the open list.

AStar has a small addition. To find the shortest path, we consider another measure: H. H is the estimated distance between you and the target node. We choose the squares according to the lowest sum of G (distance from the start) and H (estimated distance to the target). Call this sum F (so, obviously, F = G + H). Dijkstra's algorithm has the same method; expect that the H value will be 0 always. For A*, we estimate H by counting the required squares (horizontally and vertically) to reach the target, regardless if they are walkable (walls) or not.

To conclude, we have the following algorithm:

• Add the staring square to your open list.
• While the target square is not in the closed list (i.e., you didn't find the target), and the open list is not empty (i.e., you didn't visit all squares and failed to find the target):
• Find the lowest F cost square from the open list. Call this square 'current'.
• Add 'current' to the closed list and remove it from the open list.
• For each adjacent square S to 'current':
• @ If S is not walkable (e.g., wall), or if it is in a closed list:
• Continue (ignore it).
• @ Else If S is not in the open list:
• Add S to the open list.
• Make 'current' the parent of S.
• Record G, H, and F costs for S.
• @ Else If S is in the open list already:
• If current.G is lower than S.G:
• $ Make 'current' the parent of S.
• $ Re-calculate G and F costs for S.

• Obtain the path (if you have found it): start from the target square and follow the parent arrows in reverse, until you find the starting point.

Bi-Directional A* and Bi-Directional Dijkstra's Algorithms

Many thanks to this project. It was very useful.

Bi-directional graph algorithms are usually modified versions of existing graph algorithms. Instead of making the start point find the target point, Bi-directional A* and Bi-directional Dijkstra's make both points find each other:

Illustration of bi-directional Dijkstra's from our demo.

Illustration of bi-directional A* from our demo.

This may consume more memory, yet can reduce the time to half. However, it is not appreciated in terms of shortest path, since the path found with bi-directional algorithms is often a little bit longer than single-direction algorithms.

The algorithms are the same as the previous versions, but will duplicate the open list to be two open lists (one for start-to-end and another for end-to-start). For the parents, we have a parent from start-to-end and a parent from end-to-start. We will duplicate G, H, and F costs as well. When one of the two points finds a square that is in the close list of other, we stop and collect the path.

Using the code

We are representing our graph as a two-dimensional array of square vertices (actually it is a rectangle, not a square; throughout the article, we refer to the rectangle as square).

The Vertex class

We have a small class Vertex, which represents a square on the graph.

Note: We have duplicated the cost and parent variables. They are used as needed. For example, we have F1 and F2. If we are finding path with just single-directional, F2 is 0 (not used). Another example is G1 and H1. If we are just using Dijkstra's algorithm, we don't need H1 (the estimated distance to the target) since it is used in A* only. So we set it to 0. And so on.

// Upload to codeproject.com
// By Ibraheem AlKilanny
// d3_ib@hotmail.com - http://sites.google.com/site/ibraheemalkilany/
// all rights reserved 2011

using System.Drawing;

namespace Path_Finding
{
    /// <summary>
    /// Represents a graph node
    /// </summary>
    internal class Vertex
    {
        /// <summary>
        /// Initializes new instance of Vertex
        /// </summary>
        /// <param name="location">The vertex location on the graphics surface</param>
        /// <param name="position">The vertex location on the 2d container</param>
        /// <param name="walkable">Indicates whether the vertex
        //     can be visited (false if the vertex can not be)</param>

        public Vertex(Point location, Point position, bool walkable)
        {
            Location = location;
            this.Position = position;
            this.Walkable = walkable;
            this.Adjacents = new Point[8]
            {
                new Point(this.Position.X + 1, this.Position.Y),
                new Point(this.Position.X + 1, this.Position.Y - 1),
                new Point(this.Position.X, this.Position.Y - 1),
                new Point(this.Position.X - 1, this.Position.Y - 1),
                new Point(this.Position.X - 1, this.Position.Y),
                new Point(this.Position.X - 1, this.Position.Y + 1),
                new Point(this.Position.X, this.Position.Y + 1),
                new Point(this.Position.X + 1, this.Position.Y + 1)
            };
        }

        /// <summary>
        /// Indicates whether the vertex can be visited (false if the vertex can not be)
        /// </summary>
        public readonly bool Walkable;

        /// <summary>
        /// The vertex location on the two-dimensional container
        /// </summary>
        public Point Position
        {
            get;
            private set;
        }

        /// <summary>
        /// The vertex location on the graphics surface
        /// </summary>
        public Point Location
        {
            get;
            private set;
        }

        /// <summary>
        /// The vertex height and width on the graphics surface
        /// </summary>
        public static int Size = 30;

        /// <summary>
        /// Indicate the vertex statuses through the path finding
        /// </summary>
        public enum Statuses
        {
            /// <summary>
            /// The vertex is in opened list (discovered but not finished)
            /// </summary>
            OpenList,
            /// <summary>
            /// The vertex is in closed list (discovered and finished)
            /// </summary>
            ClosedList,
            /// <summary>
            /// The vertex has not been visited yet (not discovered)
            /// </summary>
            Unvisited
        }

        /// <summary>
        /// Gets an array of the vertex's adjacent vertices
        /// </summary>
        public readonly Point[] Adjacents;

        /// <summary>
        /// Gets or sets a vertex status from start to end direction
        /// </summary>
        public Statuses Status1 = Statuses.Unvisited;

        /// <summary>
        /// Gets or sets a vertex status from end to start direction
        /// </summary>
        public Statuses Status2 = Statuses.Unvisited;


        /// <summary>
        /// Gets or sets a value whether the vertex
        /// is being searched from start to end
        /// </summary>
        public bool StartToEnd;

        /// <summary>
        /// Gets or sets the vertex parent in the path finding (from start to end)
        /// </summary>
        public Vertex Parent1;

        /// <summary>
        /// Gets or sets the vertex parent in the path finding (from end to start)
        /// </summary>
        public Vertex Parent2;

        /// <summary>
        /// Gets or sets the vertex cost G (from start to end)
        /// </summary>
        public int G1;

        /// <summary>
        /// Gets or sets the vertex cost G (from end to start)
        /// </summary>
        public int G2;

        /// <summary>
        /// Gets or sets the H vertex cost (from start to end)
        /// </summary>
        public int H1;

        /// <summary>
        /// Gets or sets the H vertex cost (from end to start)
        /// </summary>
        public int H2;

        /// <summary>
        /// Gets the F cost for the vertex (from start to end)
        /// </summary>
        public int F1
        {
            get { return this.G1 + this.H1; }
        }

        /// <summary>
        /// Gets the F cost for the vertex (from end to start)
        /// </summary>
        public int F2
        {
            get { return this.G2 + this.H2; }
        }
    }
}

The Graph class

Our interest centers on the PathFinding method which takes a parameter of type enum Algorithms. For the bi-directional AStar and Dijkstra's, we have the method biDirectionalPathFinding which works in a very similar way.

Note: in the algorithms, we need to find the least cost vertex each time. So instead of linear search (which is inefficient), we are keeping our vertices in a sorted list, so the lowest F cost vertex is always at index 0. To accomplish that, each time the method Graph.insert is called to insert a vertex into an open list using a modified binary search.

/// <summary>
/// Finds path using Dijkstra's and A* algorithms
/// </summary>
/// <param name="algorithm">The used algorithm</param>
public void PathFinding(Algorithms algorithm)
{
    if (algorithm == Algorithms.BiDirectionalDijkstra 
        || algorithm == Algorithms.BiDirectionalAStarManhattan)
    {
        this.biDirectionalPathFinding(algorithm);
        return;
    }
    List<Vertex> openList = new List<Vertex>();
    Vertex goal = this.getVertex(ref this.End);
    Vertex first = this.getVertex(ref this.Start);

    Vertex current = first;
    bool pathFound = false;
    current.Status1 = Vertex.Statuses.OpenList;
    // we don't need to call Graph.insert() since its empty
    openList.Add(current);

    // Repeat while the openlist is not empty and you haven't reached the end
    while (openList.Count > 0)
    {
        if (algorithm != Algorithms.LongestPath)
        {
            // In 0 position we have always the lowest F cost
            current = openList[0];
            openList.RemoveAt(0);
        }
        else
        {
            // In the last position we have always the heighest F cost
            current = openList[openList.Count - 1];
            openList.RemoveAt(openList.Count - 1);
        }

        // mark as closed (i.e. we won't back to it again)
        current.Status1 = Vertex.Statuses.ClosedList;
        if (current == goal)
        {
            // we have found the end
            pathFound = true;
            // longest path should not stop to find the longest path
            if (algorithm != Algorithms.LongestPath)
                break;
        }

        // don't visit a wall!
        if (current.Walkable)
        {
            // we have it always true, since we are not using bi-directional
            current.StartToEnd = true;
            this.checkAdjacents(openList, current, goal, algorithm);
        }

        this.sleep(this.Sleep);
    }

    if (pathFound)
    {
        // collect path
        this.foundPath.Clear();
        Vertex last = current;
        while (current != first)
        {
            this.foundPath.Add(current);
            if (current.Parent1 == last)
                break;
            last = current;
            current = current.Parent1;
        }
        this.foundPath.Add(current);

        // fire the event
        EventHandler temp = null;
        while (temp == null)
        {
            temp = this.PathFound;
        }
        temp(this, null);
    }
    else
    {
        current.Status1 = Vertex.Statuses.ClosedList;
    }
}

We have other methods such as Draw which draws the graph and DrawPath that draws the found path.

In the source code, you will find every method with an XML summary documentation. A lot of comments are also written to help achieve more understanding.

The Form class

The form has a combobox that indicates the used algorithm. It uses a BackgroundWorker for the process of path finding, so the GUI doesn't hang. We have two NumericUpDowns, one that controls the speed of operation and the other that controls the size of the square. For performance, we reserve the 2D array of vertices with the maximum size in the constructor and hence we can select any size <= the array size.

Start and end points are denoted with green and red colors, respectively. They can be moved through the graph with arrows and the A, S, D, and W keys, respectively. Random walls can be generated with the G key. The R key causes the graph to be reset (clears all walls and resets vertices). Walls can also be made\removed with the left and right mouse buttons, respectively.

In every square, we draw its costs: F at the top, H at the middle, and G at the bottom. If the used algorithm doesn't use the H cost, we draw only G at the bottom. We draw the parent arrows as well. The open list squares are denoted with gray, and the walls with blue. Every "closed list" square is denoted with white edges.

We also measure the found path's length and the time elapsed and view it.