Path Finding Algorithms - A* vs Dijkstra vs BFS vs DFS

Game Engine - Unreal Engine, C++

Learning Outcome - Implementation of Grids, Pathfinding Algorithms

About the Project :

  • I implemented different pathfinding/searching algorithms for comparing completion time, grid count, and much more of each algorithms.
  • I also implemented visualization flow to understand how each algorithms traverse.
  • Future Update - Random Maze Generator and Web Player Demo with UI interaction so others can visualize all functionality of project.
  • More details about each algorithms and code Snippets are below.

What is pathfinding/searching algorithm?

We frequently search for routes in video games to get from one place to another. In addition to determining the quickest path, we also want to account for travel time. To determine the shortest route, a graph search technique can be used to find this path.

Comparison Table :

A* Dijkstra BFS DFS
Random Map 1 Tiles Visisted 22 143 104 22
Tiles of Path 8 8 8 21
Random Map 2 Tiles Visisted 20 90 68 170
Tiles of Path 6 6 6 169
Random Map 3 Tiles Visisted 25 126 89 84
Tiles of Path 7 7 7 83

Breadth First Search (BFS) :

Breadth First Search traverses in all directions equally. In addition to regular route finding, this approach is extremely helpful for procedural map construction, flow field pathfinding, and other kinds of map analysis.

Beginning at the root, each level's nodes are traversed one at a time, starting with the root, and continuing until all nodes have been traversed.

This is accomplished via a Queue. The current level's unvisited nodes that are immediately surrounding them are all pushed into a queue, and the level's visited nodes are marked and removed from the queue.

Steps:

  1. Queue and Array are initialized and empty.
  2. Enqueue(Insert) Starting Node in Queue and marked that Node as visited, also add Starting Node in Array.
  3. Now Enqueue all Neighbour Nodes of first added Node of Queue, and mark those Neighbour Nodes as visited. Also, set first added node as Parent Node for all Neighbour Nodes.
  4. Dequeue(remove) first added Node od Queue.
  5. Repeat Step 3 and 4 until Target is found.
  6. If target is found, Nodes inside the Array is the path to Target Node from Start Node. tagr


void UBFS::FindPath(FVector StartPos, FVector TargetPos)
{
    //startPos is character's position
    //get starting tile from startPos
    ATile* StartTile = Grid->GetTileFromWorldPoint(StartPos);

    //targetPos is target's position
    //get target tile from targetPos
    ATile* TargetTile = Grid->GetTileFromWorldPoint(TargetPos);
                        
    //add StartTile to queue
    OpenTileSet.Enqueue(StartTile);
    StartTile->IsVisited = true;
                        
    while (!OpenTileSet.IsEmpty())
    {
        //creating pointer for current tile
        ATile* CurrentTile;
                            
        //setting last element(first added) from queue as current tile
        OpenTileSet.Peek(CurrentTile);
                        
        //add current tile to visited tile array
        VisitedTiles.Add(CurrentTile);
                        
        //removing current tile from queue
        OpenTileSet.Dequeue(CurrentTile);
                        
        //if current tile is target tile, means target is found
        if (CurrentTile == TargetTile)
        {
            //GEngine->AddOnScreenDebugMessage(-1, 50.f, FColor::Red, FString::Printf(TEXT("BFS Target Found")));

            //trace path find path by traversing each parent node starting from target tile to start tile
            TracePath(StartTile, TargetTile);

            //exit loop as target is found
            return;
        }
                        
        //if target not found
        //traverse through each neighbour tiles of current tile
        for (ATile* NeighbourTile : Grid->GetNeighbourTiles(CurrentTile))
        {
            //if neighbour tile is not blocked
            if (!NeighbourTile->Walkable)
                continue;
                     
            //if neighbour tile not visited    
            if (!NeighbourTile->IsVisited)
            {
                //set current tile as parent tile for neighbour tile
                NeighbourTile->ParentTile = CurrentTile;
                        
                //add neighbour tile in queue
                OpenTileSet.Enqueue(NeighbourTile);
                //marked neighbour tile as visited
                NeighbourTile->IsVisited = true;
            }
        }
    }
}

Depth First Search (DFS) :

An algorithm for exploring or traversing trees or graphs is called depth-first search. The algorithm begins at the root node (choosing some child node to be the root node in the case of a graph) and proceeds to explore as far as it can along each branch before turning around.

Unlike BFS algorithm, we can use array (which will work as Stack) to store visited nodes. Before adding each surrounding nodes into stack, we will add first child node into stack, and keep on adding first child node and makring them as visited of each nodes into stack. If node does has any child node, we will remove the top most node from stack. Then, we will pick top most node again and follow same logic until we find target node.

Steps:

  1. Stack and Array are initialized and empty.
  2. Push Starting Node in Stack and marked that Node as visited, also add Starting Node in Array.
  3. Now push first Neighbour Node of the top Node from the Stack, and mark first Neighbour Node as visited. Also, set the top Node of Stack as Parent Node for first Neighbour Node.
  4. Repeat Step 3 until there are no Neighbour Nodes found from top Node of the Stack.
  5. If no Neighbour Nodes found from Top Node of the Stack, remove the Top Node from Stack using Pop operation.
  6. Repeat Step 3 to 5 until Target is Found.
  7. If target is found, Nodes inside the Array is the path to Target Node from Start Node.


//find path method start
void UDFS::FindPath(FVector StartPos, FVector TargetPos)
{
    //startPos is character's position
    //get starting tile from startPos
    ATile* StartTile = Grid->GetTileFromWorldPoint(StartPos);

    //targetPos is target's position
    //get target tile from targetPos
    ATile* TargetTile = Grid->GetTileFromWorldPoint(TargetPos);

    //recursive method to check all tiles starting from Start Tile(first param) as current tile
    RecursiveCheck(StartTile, StartTile, TargetTile);
}
//find path method end

//recursive check method start
void UDFS::RecursiveCheck(ATile* CurrentTile, ATile* StartTile, ATile* TargetTile)
{
    //add CurrentTile to stack
    OpenTileStack.Push(CurrentTile);
    CurrentTile->IsVisited = true;

    //add current tile to visited tile array
    VisitedTiles.Add(CurrentTile);

    //if current tile is target tile, means target is found
    if (CurrentTile == TargetTile)
    {
        //DrawDebugSphere(GetWorld(), CurrentTile->WorldPosition, Grid->TileRadius * 1.2f, 5, FColor::Blue, true, -1, 0, 1.0f);
        //GEngine->AddOnScreenDebugMessage(-1, 50.f, FColor::Red, FString::Printf(TEXT("DFS Target Found")));

        //trace path find path by traversing each parent node starting from target tile to start tile
        TracePath(StartTile, TargetTile);

        //exit loop as target is found
        return;
    } 

    //if target not found
    //traverse through each neighbour tiles of current tile
    for (ATile* NeighbourTile : Grid->GetNeighbourTiles(CurrentTile))
    {
        //if neighbour tile is not blocked
        if (!NeighbourTile->Walkable)
            continue;
            
        //if neighbour tile not visited
        if (!NeighbourTile->IsVisited)
        {
            //set current tile as parent tile for neighbour tile
            NeighbourTile->ParentTile = CurrentTile;
            
            //marked neighbour tile as visited
            NeighbourTile->IsVisited = true;
            
            //recursive check to find target in all neighbours
            RecursiveCheck(NeighbourTile, StartTile, TargetTile);
        }
    }
    
    //remove top tile from stack 
    OpenTileStack.Pop();
}
//recursive check method end

Special Note for DFS and BFS Algorithms :

For traversing though each neighbour tiles in both algorithms, differnt search paths can be obtained based on which order we are traversing though neighbour tiles to Queue(BFS) or Stack(DFS).

Dijkstra (also called Uniform Cost Search):

Up until now, we were just exploring neighbours in BFS/DFS algorithms and checking if we have found target or not. BFS/DFS does not generate shortest path, and if we consider weighted graph, BFS/DFS are useless. However, Dijkstra's algorithm always generate shortest path.

Unlike BFS/DFS algorithms, We need to keep track of the total movement cost from the start location. We want to take the movement costs into account when deciding how to evaluate neighbours. We can use Array (which will work as Queue) to store tiles that need to be evaluated in Open List, and we can use Set to store tiles that are already evaluated in Close Set.

Below are some moevment cost that we will keep in mind for this algorithm:
GCost = Distance from Starting node.
HCost = Distance from End node, which is equal to 0, as we won't use HCost(Heuristic Cost) in Dijkstra algorithm.
FCost = GCost + HCost = GCost, as HCost is equal to 0.

Steps:

  1. Set and Array are initialized and empty.
  2. Insert Starting Node in the Array.
  3. Go through all Nodes from the Array and get the Node with the lowest FCost value, and also set that node as a Current Node.
  4. Remove Node with the lowest FCost from the Array and Insert that Node in Set.
  5. Loop thorugh all Neighbour Nodes of Current Node.
  6. Calculate cost of travelling from Start Node to all Neighbour Nodes (To calculate cost, add GCost of current node and cost of travelling from Current Node to Neighbour Node).
  7. If Array does not has Neighbour Node or calculated cost of Neighbour Node is less than Neighbour Node's GCost, then set Neighbour Node's GCost as calculated cost. In addition, set Current Node as Parent Node for Neighbour Node, and Insert Neighbour Node in the Array.
  8. Repeat Step 3 to 7 until Target Node found.
  9. If target is found, Nodes inside the Array is the path to Target Node from Start Node. 

void UDijkstraPathFinding::FindPath(FVector StartPos, FVector TargetPos)
{
    //startPos is character's position
    //get starting tile from startPos
    ATile* StartTile = Grid->GetTileFromWorldPoint(StartPos);

    //targetPos is target's position
    //get target tile from targetPos
    ATile* TargetTile = Grid->GetTileFromWorldPoint(TargetPos);

    //add start tile into open tile array
    OpenTileSet.Add(StartTile);

    //add start tile in visited array
    //visisted tile array is just for visualization purpose only
    VisitedTiles.Add(StartTile);
    
    //perfor Dijkstra until open tile array is empty
    while (OpenTileSet.Num() > 0)
    {
        //set first element of open tile array as curernt tile
        ATile* CurrentTile = OpenTileSet[0];

        //loop thorugh all tiles from open tile array
        for (int32 index = 1; index < OpenTileSet.Num(); index++)
        {
            //if FCost of any tile from array is less than FCost of current tile, set tile with lowest FCost as current tile 
            if (OpenTileSet[index]->GetFCost() < CurrentTile->GetFCost())
            {
                CurrentTile = OpenTileSet[index];
            }
        }
    
        //remove current tile from open tile array
        OpenTileSet.Remove(CurrentTile);

        //add current tile in close tile set
        ClosedTileSet.Add(CurrentTile);
        //DrawDebugSphere(GetWorld(), CurrentTile->WorldPosition, Grid->TileRadius, 5, FColor::Blue, true, -1, 0, 1.0f);
    
        //if current tile is target tile, means target is found
        if (CurrentTile == TargetTile)
        {
            //DrawDebugSphere(GetWorld(), CurrentTile->WorldPosition, Grid->TileRadius * 1.2f, 5, FColor::Blue, true, -1, 0, 1.0f);
            GEngine->AddOnScreenDebugMessage(-1, 50.f, FColor::Red, FString::Printf(TEXT("Dikstra Target Found")));

            //trace path find path by traversing each parent node starting from target tile to start tile
            TracePath(StartTile, TargetTile);

            //exit loop as target is found
            return;
        }
    
        //if target not found
        //traverse through each neighbour tiles of current tile
        for (ATile* NeighbourTile : Grid->GetNeighbourTiles(CurrentTile))
        {
            //if neighbour tile is not walkable
            //or if neighbour tile is close tile set 
            if (!NeighbourTile->Walkable || ClosedTileSet.Contains(NeighbourTile))
                continue;
    
            //calculate cost from start tile to neighbour tile
            //GCost of current tile is equal to distance/cost from start tile to current tile
            //get distance method will return distance/cost from current tile to neighbour tile
            int32 NewCostToNeighbour = CurrentTile->GCost + GetDistance(CurrentTile, NeighbourTile);
    
            //if calculated cost in last step is less than GCost of neighbour tile
            //or if open tile does not have neighbour tile
            if (NewCostToNeighbour < NeighbourTile->GCost || !OpenTileSet.Contains(NeighbourTile))
            {
                //set GCost of neighbour tile as calculated cost in last step
                NeighbourTile->GCost = NewCostToNeighbour;
                NeighbourTile->HCost = 0; //always 0 for Dijkstra
    
                //set current tile as parent tile for neighbour tile
                NeighbourTile->ParentTile = CurrentTile;
    
                //if open tile does not have neighbour tile
                if (!OpenTileSet.Contains(NeighbourTile))
                {
                    //add neighbour tile into open tile array
                    OpenTileSet.Add(NeighbourTile);

                    //add start tile in visited array
                    //visisted tile array is just for visualization purpose only
                    VisitedTiles.Add(NeighbourTile);
                }
            }
        }
    }
}

A* (also called A-Star):

An optimized version of Dijkstra's Algorithm for a single destination is called A*. All locations can be reached by Dijkstra's Algorithm, while only one place or the nearest of many locations can be reached by A*. It gives priority to routes that appear to go in the direction of a goal.

A* works same as Dijkstra algorithm, but we only consider movement cost from starting node to current node(or neighbour nodes) in Dijkstra algorithm. However, we will calculate movement cost from neighbour nodes to target node (Heuristic value) in A* start algorithm when we are evaluating paths and their movement cost. Same as Dijkstra algorithm, we can use Array (which will work as Queue) to store tiles that need to be evaluated in Open List, and we can use Set to store tiles that are already evaluated in Close Set.

Below are some moevment cost that we will keep in mind for this algorithm:
GCost = Distance from Starting node.
HCost = Distance from End node, Heuristic Cost.
FCost = GCost + HCost.

Steps:

  1. Set and Array are initialized and empty.
  2. Insert Starting Node in the Array.
  3. Go through all Nodes from the Array and get the Node with the lowest FCost value. If FCost value is same for any nodes, we will use Node with loweset HCost, and also set that node as a Current Node.
  4. Remove Node with the lowest FCost from the Array and Insert that Node in Set.
  5. Loop thorugh all Neighbour Nodes of Current Node.
  6. Calculate cost of travelling from Start Node to all Neighbour Nodes (To calculate cost, add GCost of current node and cost of travelling from Current Node to Neighbour Node).
  7. If Array does not has Neighbour Node or calculated cost of Neighbour Node is less than Neighbour Node's GCost, then set Neighbour Node's GCost as calculated cost and set Neighbour Node's HCost as distance between Neighbour Node and Target Node. In addition, set Current Node as Parent Node for Neighbour Node, and Insert Neighbour Node in the Array.
  8. Repeat Step 3 to 7 until Target Node found.
  9. If target is found, Nodes inside the Array is the path to Target Node from Start Node. 

void UAStarPathFinding::FindPath(FVector StartPos, FVector TargetPos)
{
    //startPos is character's position
    //get starting tile from startPos
    ATile* StartTile = Grid->GetTileFromWorldPoint(StartPos);

    //targetPos is target's position
    //get target tile from targetPos
    ATile* TargetTile = Grid->GetTileFromWorldPoint(TargetPos);

    //add start tile into open tile array
    OpenTileSet.Add(StartTile);

    //add start tile in visited array
    //visisted tile array is just for visualization purpose only
    VisitedTiles.Add(StartTile);
    
    //perfor Dijkstra until open tile array is empty
    while (OpenTileSet.Num() > 0)
    {
        //set first element of open tile array as curernt tile
        ATile* CurrentTile = OpenTileSet[0];

        //loop thorugh all tiles from open tile array
        for (int32 index = 1; index < OpenTileSet.Num(); index++)
        {
            //if FCost of any tile from array is less than FCost of current tile, set tile with lowest FCost as current tile
            //if FCost is same for any to tiles with lowest FCost value, get tile with minimum HCost
            if (OpenTileSet[index]->GetFCost() < CurrentTile->GetFCost() || 
                (OpenTileSet[index]->GetFCost() == CurrentTile->GetFCost() && OpenTileSet[index]->HCost < CurrentTile->HCost))
            {
                CurrentTile = OpenTileSet[index];
            }
        }
    
        //remove current tile from open tile array
        OpenTileSet.Remove(CurrentTile);

        //add current tile in close tile set
        ClosedTileSet.Add(CurrentTile);
        //DrawDebugSphere(GetWorld(), CurrentTile->WorldPosition, Grid->TileRadius, 5, FColor::Blue, true, -1, 0, 1.0f);
    
        //if current tile is target tile, means target is found
        if (CurrentTile == TargetTile)
        {
            //DrawDebugSphere(GetWorld(), CurrentTile->WorldPosition, Grid->TileRadius * 1.2f, 5, FColor::Blue, true, -1, 0, 1.0f);
            GEngine->AddOnScreenDebugMessage(-1, 50.f, FColor::Red, FString::Printf(TEXT("A* Target Found")));

            //trace path find path by traversing each parent node starting from target tile to start tile
            TracePath(StartTile, TargetTile);

            //exit loop as target is found
            return;
        }
    
        //if target not found
        //traverse through each neighbour tiles of current tile
        for (ATile* NeighbourTile : Grid->GetNeighbourTiles(CurrentTile))
        {
            //if neighbour tile is not walkable
            //or if neighbour tile is close tile set 
            if (!NeighbourTile->Walkable || ClosedTileSet.Contains(NeighbourTile))
                continue;
    
            //calculate cost from start tile to neighbour tile
            //GCost of current tile is equal to distance/cost from start tile to current tile
            //get distance method will return distance/cost from current tile to neighbour tile
            int32 NewCostToNeighbour = CurrentTile->GCost + GetDistance(CurrentTile, NeighbourTile);
    
            //if calculated cost in last step is less than GCost of neighbour tile
            //or if open tile does not have neighbour tile
            if (NewCostToNeighbour < NeighbourTile->GCost || !OpenTileSet.Contains(NeighbourTile))
            {
                //set GCost of neighbour tile as calculated cost in last step
                NeighbourTile->GCost = NewCostToNeighbour;

                //set HCost of neighbour tile as distance from neighbour tile to target tile
                NeighbourTile->HCost = GetDistance(NeighbourTile, TargetTile);
    
                //set current tile as parent tile for neighbour tile
                NeighbourTile->ParentTile = CurrentTile;
    
                //if open tile does not have neighbour tile
                if (!OpenTileSet.Contains(NeighbourTile))
                {
                    //add neighbour tile into open tile array
                    OpenTileSet.Add(NeighbourTile);

                    //add start tile in visited array
                    //visisted tile array is just for visualization purpose only
                    VisitedTiles.Add(NeighbourTile);
                }
            }
        }
    }
}

Special Note :

There is one more algorithm that is similar to Dijkstra and A* algorithm. It is called Greedy Best First Search Algorithm. Dijkstra algorithm uses movement cost from starting node to current node or neighbour node when evaluating paths. Greedy Best First Search uses movement cost from target node to current node or neighbour node when evaluating paths. A* uses both movement cost, that's why it works best from all other options.

Dijkstra's Algorithm works well to find the shortest path, but it wastes time exploring in directions that aren't promising. Greedy Best First Search explores in promising directions but it may not find the shortest path. The A* algorithm uses both the actual distance from the start and the estimated distance to the goal.

Resources :

©All rights reserved by Spandan Patel.