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.
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.
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:
Declare the
GetPathBFS
function:public List<Vertex> GetPathBFS(GameObject srcObj, GameObject dstObj) { if (srcObj == null || dstObj == null) return new List<Vertex>(); // next steps }
Declare and initialize the variables we need for the algorithm:
Vertex[] neighbours; Queue<Vertex> q = new Queue...