Our board : a random 30x20 maze generated using a Prim's algorithm.
Globo (the green square in the middle) is the player and the blue capsule is the goal.

Trace let by the player using a Breadth First Search pathfinding algorithm to reach the goal.

Here is, to be compared, the trace let by the player using a Depth First Search pathfinding algorithm to reach the goal.

Breadth First Search (BFS) is one of the two most fundamental graph traversal algorithms. First published in 1959 by Edward F. Moore to find the shortest path out of a maze, it is now used in a daily basis not only for regular traversal, but also for networks analysis, GPS, Search Engines, scheduling and other types of graph analysis.

In short : this is an incredibly useful algorithm that guarantees the shortest path between two nodes (when connections have the same cost).

Breadth First Search explores equally in all directions until the goal is reached. In other words, it starts from a chosen node and examine all its neighbors, then it examines all the neighbors of the neighbors, and so on... If we consider a tree (which is a simplified graph), the BFS will proceed as follows:

Steps

• Add the start node in the queue and mark as visited.
• While there is a node waiting in the queue:
• 1. Take the node at the front of the line (queue).
• 2. Add to the queue all available neighbors, note the parent and mark as visited
• Done: backtrack from goal to start using parent link in order to get the shortest path.

BFS uses the opposite strategy as depth-first search (DFS), which instead explores the node branch as far as possible before being forced to backtrack. Still, both algorithms have the same lines of code; the only difference is the data structure used:

BFS use a Queue (FIFO)	DFS use a Stack (LIFO)

This algorithm is, compared to the DFS, a little more tricky to implement in a recursive manner. As such we will only see the iterative approach ;)

Code

BFS(Maze maze, Node start, Node end)
{
  // Put the start node in the queue
  start.visite = true;
  Queue queue(start);

  // While there is node to be handled in the queue
  while (!queue.empty())
  {
    // Handle the node in the front of the lineand get unvisited neighbors
    Node curNode = queue.pop();

    // Terminate if the goal is reached
    if (curNode == end)
      break;

    // Take neighbors, set its parent, mark as visited, and add to the queue
    auto neighbors = curNode.GetUnvisitedNeighbors();
    for (auto i = 0; i < neighbors.size(); ++i)
    {
      neighbors[i].visite = true;
      neighbors[i].parent = curNode;
      queue.push(neighbors[i]);
    }
  }

  // Done ! At this point we just have to walk back from the end using the parent
  // If end does not have a parent, it means that it has not been found.
} 

1. Here is our board.

2. Add all unvisited neighbors to the queue, they will be processed in order.

3. Here we have handled the two first neighbors:
- The left one has no unvisited neighbor.
- We add to the queue the unvisited neihbors of the right one.
- Note: the top one is now in the front of the queue (cf. next slide).

4. Here we go for the last neighbor of the first circle.

5. After few iterations...

6. Exit found : we can now retrieve the shortest path from end to start!