Rat in a Maze: Solving Pathfinding with Stacks and Queues in C++

Introduction to the Rat in a Maze Problem

The Rat in a Maze problem is a classic algorithmic challenge that involves finding a path from the start to the exit in a grid. It's an excellent way to understand stack and queue data structures, which are fundamental in C++ programming. In this tutorial, you'll implement a solution using these ADTs, reinforcing concepts like abstract data types, separate compilation, and makefiles. This problem mirrors real-world pathfinding used in AI navigation and game development, such as in the latest GTA VI or Minecraft updates.

Understanding Stacks and Queues

Stacks follow Last-In-First-Out (LIFO) order, while queues follow First-In-First-Out (FIFO). In maze solving, a stack implements depth-first search (DFS), and a queue implements breadth-first search (BFS). DFS explores one path deeply, while BFS explores all paths level by level. Imagine a Spotify playlist: a stack is like playing the last added song first, while a queue plays songs in order. For the maze, DFS might find a solution quickly but not the shortest, whereas BFS guarantees the shortest path.

Setting Up the Project with Makefiles

We'll use separate compilation: header files (.h) for declarations, implementation files (.cpp) for definitions, and a main file. A makefile automates compilation, saving time. Here's a sample makefile for Linux/Unix:

# Makefile for Rat In A Maze
CXX = g++
CXXFLAGS = -std=c++11 -Wall

all: maze

maze: main.o maze.o stack.o queue.o
	$(CXX) $(CXXFLAGS) -o maze main.o maze.o stack.o queue.o

main.o: main.cpp maze.h
	$(CXX) $(CXXFLAGS) -c main.cpp

maze.o: maze.cpp maze.h stack.h queue.h
	$(CXX) $(CXXFLAGS) -c maze.cpp

stack.o: stack.cpp stack.h
	$(CXX) $(CXXFLAGS) -c stack.cpp

queue.o: queue.cpp queue.h
	$(CXX) $(CXXFLAGS) -c queue.cpp

clean:
	rm -f *.o maze

This makefile ensures you only recompile changed files. It's a standard practice in professional software development and open-source projects.

Implementing the Stack ADT

Create stack.h and stack.cpp. The stack stores positions (row, col) as a struct. Use a dynamic array or linked list. Here's a header example:

// stack.h
#ifndef STACK_H
#define STACK_H

struct Position {
    int row;
    int col;
};

class Stack {
public:
    Stack();
    ~Stack();
    void push(Position pos);
    Position pop();
    bool isEmpty() const;
private:
    struct Node {
        Position data;
        Node* next;
    };
    Node* top;
};

#endif

The implementation uses a linked list. The push adds a node at the top, and pop removes it. This is similar to undo features in apps like Photoshop.

Implementing the Queue ADT

Create queue.h and queue.cpp. Use a linked list with front and rear pointers:

// queue.h
#ifndef QUEUE_H
#define QUEUE_H

#include "stack.h" // for Position

class Queue {
public:
    Queue();
    ~Queue();
    void enqueue(Position pos);
    Position dequeue();
    bool isEmpty() const;
private:
    struct Node {
        Position data;
        Node* next;
    };
    Node* front;
    Node* rear;
};

#endif

Queues are used in task scheduling and print spooling, like how Uber queues ride requests.

Solving the Maze with DFS (Stack)

Represent the maze as a 2D vector of cells: 0 = open, 1 = wall, 2 = visited. The DFS algorithm:

1. Push start position onto stack.
2. While stack not empty:
   • Pop top position.
   • If it's the exit, return path.
   • Mark as visited.
   • Push unvisited neighbors (up, down, left, right).
3. If stack empties, no solution.

Here's a snippet:

bool solveMazeDFS(std::vector<std::vector<int>>& maze, Position start, Position end) {
    Stack s;
    s.push(start);
    while (!s.isEmpty()) {
        Position cur = s.pop();
        if (cur.row == end.row && cur.col == end.col) return true;
        if (maze[cur.row][cur.col] != 0) continue;
        maze[cur.row][cur.col] = 2; // visited
        // Push neighbors
        Position neighbors[4] = {{cur.row-1,cur.col},{cur.row+1,cur.col},{cur.row,cur.col-1},{cur.row,cur.col+1}};
        for (auto& n : neighbors) {
            if (n.row >=0 && n.row < maze.size() && n.col >=0 && n.col < maze[0].size() && maze[n.row][n.col]==0)
                s.push(n);
        }
    }
    return false;
}

DFS is like exploring a dungeon in Zelda – you go deep until you hit a dead end, then backtrack.

Solving the Maze with BFS (Queue)

BFS uses a queue. It finds the shortest path. Algorithm:

1. Enqueue start position.
2. While queue not empty:
   • Dequeue front position.
   • If exit, return path (use parent tracking).
   • Mark visited.
   • Enqueue unvisited neighbors.

To reconstruct the path, store parent for each position. Here's a BFS example:

bool solveMazeBFS(std::vector<std::vector<int>>& maze, Position start, Position end) {
    Queue q;
    q.enqueue(start);
    std::map<Position, Position> parent; // need custom comparator
    while (!q.isEmpty()) {
        Position cur = q.dequeue();
        if (cur.row == end.row && cur.col == end.col) {
            // reconstruct path
            return true;
        }
        if (maze[cur.row][cur.col] != 0) continue;
        maze[cur.row][cur.col] = 2;
        Position neighbors[4] = {{cur.row-1,cur.col},{cur.row+1,cur.col},{cur.row,cur.col-1},{cur.row,cur.col+1}};
        for (auto& n : neighbors) {
            if (n.row >=0 && n.row < maze.size() && n.col >=0 && n.col < maze[0].size() && maze[n.row][n.col]==0) {
                q.enqueue(n);
                parent[n] = cur;
            }
        }
    }
    return false;
}

BFS is like flood fill in Photoshop or how Google Maps finds shortest routes.

Using Makefiles Effectively

Makefiles track dependencies. The make utility checks timestamps and recompiles only what's needed. This speeds up development, especially in large projects like Linux kernel or game engines. Always use make clean to remove object files before final build.

Testing and Debugging

Test with small mazes. Use gdb or print statements. Verify that stacks and queues work correctly. Common bugs: infinite loops due to not marking visited, or off-by-one errors in neighbor checks. Consider using Valgrind to detect memory leaks.

Real-World Applications

Pathfinding is used in autonomous vehicles, robot vacuum cleaners, and AI in video games. For example, the Boston Dynamics Spot robot uses similar algorithms to navigate. Understanding stacks and queues is crucial for coding interviews at top tech companies like Google, Amazon, and Meta.

Conclusion

You've implemented the Rat in a Maze using stacks (DFS) and queues (BFS) in C++. You've practiced separate compilation, ADTs, and makefiles. These skills are foundational for advanced topics like graph algorithms and AI pathfinding. Keep experimenting with different mazes and optimize your code. Happy coding!