Finding the shortest path in a grid with BFS

The Breadth-First Search (BFS) algorithm is just another basic technique for graph traversal and is aimed at getting the shortest path in the fewest steps possible, with the trade-off of being expensive in memory; thus, it is aimed especially at games for high-end consoles and computers.

Getting ready

This is a high-level algorithm that relies on each graph's implementation of the general functions, so the algorithm is implemented in the Graph class.

How to do it...

Even though this recipe is only defining a function, please take into consideration the comments in the code for better understanding of the implementation and code flow:

1. Declare the GetPathBFS function:

public List<Vertex> GetPathBFS(GameObject srcObj, GameObject dstObj) 
{ 
    if (srcObj == null || dstObj == null) 
        return new List<Vertex>(); 
    // next steps 
}

 

 

2. Declare and initialize the variables we need for the algorithm:

Vertex[] neighbours; 
Queue<Vertex&gt...