Finding the shortest path in a grid with BFS

The Breadth-First Search (BFS) algorithm is another basic technique for graph traversal and it's aimed to get the shortest path in the fewest steps possible, with the trade-off being expensive in terms of memory; thus, aimed specially at games on 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 to understand the indentation and code flow more effectively:

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> q = new Queue...