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
GetPathBFSfunction: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<Vertex>(); Vertex src = GetNearestVertex(srcObj.transform.position); Vertex dst = GetNearestVertex(dstObj.transform.position); Vertex v; int[] previous = new int[vertices.Count]; for (int i = 0; i < previous.Length; i++) previous[i] = -1; previous[src.id] = src.id; q.Enqueue(src); - Implement the BFS algorithm for finding a path:
while (q.Count != 0) { v = q.Dequeue(); if (ReferenceEquals(v, dst)) { return BuildPath(src.id, v.id, ref previous); } neighbours = GetNeighbours(v); foreach (Vertex n in neighbours) { if (previous[n.id] != -1) continue; previous[n.id] = v.id; q.Enqueue(n); } } return new List<Vertex>();
The BFS algorithm is similar to the DFS algorithm because it's based on the same in-order traversing of a graph but, instead of a stack such as DFS, BFS uses a queue for visiting the discovered nodes.
In case you haven't noticed, we didn't implement the method BuildPath. This is because we talked about it at the end of the Depth-First Search recipe.