Finding the Shortest Path with BFS

Now that our CoordVector supports all the necessary operations to be used as a queue, we can implement breadth-first search (BFS) to find the shortest path through our mazes!

BFS: The Level-by-Level Approach

While DFS dives deep into one path before trying others, BFS explores all paths simultaneously, one step at a time. Think of it like ripples spreading out from a stone dropped in water—we explore everything at distance 1, then distance 2, then distance 3, and so on.

Your Task, Step 1: Try the Provided BFS

We're providing you with a mostly-complete BFS implementation. Replace your placeholder solveMazeBFS function in solver.cpp with this code (click to copy):

bool solveMazeBFS(Maze& maze) {
    // Queue stores coordinates for BFS traversal
    CoordVector toDoQueue;
    toDoQueue.pushBack(maze.getStart());
    Coord end = maze.getEnd();

    // BFS to find path from start to end
    while (!toDoQueue.isEmpty()) {
        Coord current = toDoQueue.front();
        toDoQueue.popFront();

        if (maze.hasState(current, Maze::VISITED)) {
            continue;  // Already visited
        }

        // Mark current cell as visited
        maze.setState(current, Maze::VISITED);

        // Check if we've reached the end
        if (current == end) {
            break;
        }

        // All ways we can go from here get pushed onto the queue
        for (size_t dir = 0; dir < NUM_DIRECTIONS; ++dir) {
            Coord newCoord = current + DIRECTIONS[dir];

            if (maze.hasState(newCoord, Maze::PATH)) {
                toDoQueue.pushBack(newCoord);
                // Use the ACTIVE state to show items in the queue,
                // which also prevents them from being added multiple times
                maze.setState(newCoord, Maze::ACTIVE);
            }
        }
    }

    // Clear out any remaining faux ACTIVE states that didn't get used
    while (!toDoQueue.isEmpty()) {
        Coord current = toDoQueue.front();
        toDoQueue.popFront();
        maze.setState(current, Maze::PATH);
    }

    // Bail out if we didn't reach the end
    if (!maze.hasState(end, Maze::VISITED)) {
        return false;
    }

    // Unfortunately, BFS doesn't leave us with a path marked ACTIVE
    // TODO: Fix that!

    return true;
}

Test It Out

Compile and run on the cracked maze:

make
./amaze --bfs mazes/maze-79x23-cracked.txt

The Missing Piece: Tracking the Path

To reconstruct the shortest path, for each cell we visit, we need to remember which cell we came from. So we'll create a “parent pointer” tree that we can follow backwards from the end to the start.

Your Task, Step 2: Add Path Tracking

Add the CoordGrid Helper

First, add the following helper class to solver.cpp right before the solveMazeDFS function (after the DIRECTIONS array but still in the anonymous namespace):

// This is a tiny private helper class to manage a CoordVector as a 2D grid
// of coordinates.  It just does the index arithmetic for us.  Because it
// is just a tiny wrapper, it uses inside-the-class implementation rather than
// separate header and implementation files.

class CoordGrid {
 public:
    CoordGrid(int width, int height)
        : width_(width), height_(height), vector_(width * height) {
        // Nothing else to do
    }

    Coord& at(const Coord& cell) {
        if (cell.x < 0 || cell.x >= width_ || cell.y < 0 || cell.y >= height_) {
            throw std::out_of_range("CoordGrid index out of range");
        }
        return vector_[cell.y * width_ + cell.x];
    }

 private:
    int width_;
    int height_;
    CoordVector vector_;
};

This little class is basically a 2-D array of Coord values implemented using our CoordVector, doing all the annoying index calculations for you.

Modify the BFS Function

Now modify solveMazeBFS to track and reconstruct the path:

1. Create a tracking grid (right after creating toDoQueue):

   CoordGrid cameFrom(maze.width(), maze.height());
   

2. Track where we came from (when adding a neighbor to the queue): After the line maze.setState(newCoord, Maze::ACTIVE);, add

   cameFrom.at(newCoord) = current;
   

3. Reconstruct the path (replace the TODO: Fix that! comment):

   You need to loop, starting from end, following the cameFrom coordinates back to the start, marking each cell as Maze::ACTIVE.

Test Your Solution

Rebuild and test on various mazes. Here we've turned off the display to show the answer instantly rather than animating it:

make
./amaze --bfs -n mazes/maze-79x23.txt          # Original maze, same as DFS
./amaze -n mazes/maze-79x23-cracked.txt        # Cracked maze with DFS
./amaze --bfs -n mazes/maze-79x23-cracked.txt  # Cracked maze with BFS

Scroll back in your terminal to contrast the DFS and BFS results, or use the -o option to save the output to files and compare them side-by-side.

Comparing the Algorithms

Feel free to run more comparisons or just watch the animations. Notice that

• DFS might find a path faster but it's often a longer path.
• BFS always finds the shortest path but explores more cells.
• DFS uses less memory (just a stack of the current path).
• BFS uses more memory (queue + parent pointers for all visited cells), but the queue is often smaller than the full stack DFS might build up.

There's opportunity for more investigation in the next part of the assignment!

maze.showStatusText("Queue size: " + std::to_string(toDoQueue.size()));

End ← ... ← Cell3 ← Cell2 ← Cell1 ← Start

(When logged in, completion status appears here.)