Maze Game

Introduction

This project is a 2D Maze Game developed in Python to demonstrate and visualize fundamental Artificial Intelligence pathfinding algorithms. It combines procedural generation techniques with graphical representations of search strategies, allowing players to either solve the maze manually or watch AI agents compete to find the optimal path.

Summary (Key Features)

Procedural Generation: Utilizes Randomized Depth-First Search (DFS) to create perfect mazes dynamically.
Algorithm Visualization: Watch Breadth-First Search (BFS) and A* (A-Star) search algorithms navigate the maze in real-time.
Dynamic Difficulty: Player-selectable grid sizes and energy constraints.
User Management: Integrated login/registration system with a leaderboard stored in a local JSON database.

Technical Architecture

The game is built using Object-Oriented Programming (OOP) principles in Python, leveraging Pygame for rendering and Pygame-menu for the user interface.

Procedural Maze Generation

To ensure that the generated mazes are solvable and have exactly one path between any two points (a “perfect” maze, structurally equivalent to a spanning tree), we implemented Randomized Depth-First Search (DFS).

The grid starts entirely filled with walls.
The algorithm picks a random cell, marks it as visited, and pushes it to a stack.
It randomly chooses an unvisited neighbor, removes the wall between them, and moves to that neighbor, pushing it to the stack.
If a cell has no unvisited neighbors (a dead end), it pops the stack and backtracks until it finds a cell with unvisited neighbors.

Pathfinding Algorithms

The core of the AI component lies in solving the generated mazes.

Breadth-First Search (BFS)

BFS explores the maze level by level, ensuring that the first time it reaches the destination, it has found the shortest path in terms of steps.

Note (BFS Complexity)

While BFS guarantees the shortest path in an unweighted grid like our maze, it is memory-intensive because it explores all possible paths in all directions equally. It uses a FIFO Queue, leading to $O(|V|)$ space complexity where $|V|$ is the number of open cells.

A* Search Algorithm

To optimize the search, we implemented A* using a Priority Queue (heapq). A* evaluates nodes based on $f(n) = g(n) + h(n)$ :

$g(n)$ : The exact cost from the start to the current node.
$h(n)$ : The heuristic estimated cost from the current node to the goal.

1
# We used squared Euclidean distance to avoid costly square root operations
2
def heuristic(curr_x, curr_y, end_x, end_y):
3
    return (end_x - curr_x)**2 + (end_y - curr_y)**2

Tip (A* vs BFS Performance)

In our 100x100 grid benchmarks, A* consistently outperformed BFS by directing its search towards the goal rather than exploring blindly. However, because we used a Priority Queue, insertion and extraction take $O(\log N)$ , compared to BFS’s $O(1)$ queue operations. Thus, in very simple or highly constrained mazes, BFS occasionally performed comparably.

Game Mechanics & UI

Beyond the algorithms, we focused heavily on user experience and game mechanics:

Hint System: If a player gets stuck, they can request a hint. The game uses a background BFS to pre-calculate the solution tree from the goal to all points. A hint simply traces back this tree from the player’s current position to the next junction.
Energy System: We introduced an optional “Energy” game mode. The player has limited steps and must collect randomly spawned energy orbs. This transformed the simple pathfinding problem into a more complex combinatorial optimization challenge.
State Saving: Players can pause the game, and their exact state (position, maze layout, time elapsed) is serialized and saved, allowing them to resume later.