An interactive terminal-based 2D maze game developed in C++ showcasing core Data Structures and Algorithms (DSA). Players navigate a dynamically generated grid filled with hidden traps and moving enemies to reach the ultimate treasure.
- Breadth-First Search (BFS) Pathfinding: Implements a BFS hint system using
std::queueto dynamically compute and display the shortest path from the player's current position to the treasure (*). - Stack-Based Undo Mechanism: Uses
std::stackto record coordinate histories, allowing players to reverse previous movements at a minor score penalty. - Proximity-Based Enemy AI: Enemies dynamically track and chase either the player or the treasure based on Manhattan distance criteria, adding dynamic challenge.
- Randomized Level Generation: Procedurally generates walls, traps (
X), treasure (T), and enemy spawn points on a 20x32 grid with guaranteed safe spawning zones. - ANSI Color Terminal Output: Uses extended character sets and ANSI color escape sequences for visual appeal directly in the terminal console.
| Key | Action |
|---|---|
| Arrow Keys | Move Player (P) |
| H | Display Shortest Path Hint (BFS) |
| U | Undo Last Move (Costs 5 points) |
| Q | Quit / Restart Game |
-
Breadth-First Search (BFS):
$\mathcal{O}(V + E)$ where$V = \text{ROWS} \times \text{COLS}$ (used for path hints). -
LIFO Stack (
std::stack):$\mathcal{O}(1)$ push/pop operations for player trajectory undo/rollback. -
Dynamic Grid Representation:
$20 \times 32$ character array for state tracking and matrix manipulation.