Grid Simulator

A C++ application that visualize various pathfinding algorithms and maze generation strategies on a 2D grid using the SFML library.

Architecture & Design

The project is built using the Strategy Design Pattern to allow for easy interchangeability and extension of algorithms.

• Path Finding: The Path_finder_context manages the active pathfinding strategy. All algorithms implement the IPath_finder interface.
• Maze Generation: The Maze_generator_context manages the maze generation strategy. All generators implement the IMaze_generator interface.

This design makes it simple to add new algorithms without modifying the core simulation logic.

Supported Algorithms

Path Finding

Currently, the following pathfinding algorithms are implemented:

• BFS (Breadth-First Search): Explores the grid layer by layer. It guarantees the shortest path in an unweighted grid.
• DFS (Depth-First Search): Explores as deep as possible along each branch before backtracking. It does not guarantee the shortest path.

Maze Generation

• Dummy Generator: Clears the map (creates an empty grid).
• DFS (Recursive Backtracker): Generates mazes with long, winding corridors and few dead ends.
• BFS (Randomized): Generates mazes with a branching structure, often resulting in a more "bushy" texture compared to DFS.

Roadmap & Future Features

We are actively working on expanding the simulation with more complex and interesting algorithms.

Planned Path Finding Algorithms

• Dijkstra's Algorithm: For finding the shortest paths in weighted graphs.
• A (A-Star):* An optimized search algorithm using heuristics to find the shortest path faster.
• RRT (Rapidly-exploring Random Tree): A probabilistic algorithm designed for high-dimensional search spaces (adapted for grid use).

Planned Maze Generation Algorithms

• Randomized Prim's Algorithm: Grows the maze from a starting cell by adding random frontier walls, creating a Minimum Spanning Tree (MST) structure.
• Kruskal's Algorithm: Uses a disjoint-set data structure to randomly merge sets of cells, creating a maze with a distinct texture.

Prerequisites

• C++ Compiler: Compatible with C++23 standard (e.g., GCC 13+, Clang, MSVC).
• CMake: Version 3.16 or higher.
• SFML: Version 2.6.x (System, Window, Graphics modules).

Build Instructions

1. Clone the repository:

   git clone <repository-url>
   cd GridSimulator

2. Configure the project:

   cmake -S . -B build

3. Build the executable:

   cmake --build build

4. Run the application:

   ./build/GridSimulator

Debugging with AddressSanitizer (ASan)

This project has AddressSanitizer (ASan) and UndefinedBehaviorSanitizer (UBSan) enabled in the build configuration to help detect memory errors and undefined behavior.

To use it:

1. Build the project as described above. The flags -fsanitize=address -fsanitize=undefined are already active.
2. Run the application. If a memory issue (like out-of-bounds access) occurs, the application will crash and print a detailed error report to the terminal.

Note: running with sanitizers might slow down the application slightly.

Controls / Usage

Key	Action
1	Select BFS Path Finder
2	Select DFS Path Finder
3	Select Dummy Maze Generator (Empty Map)
4	Select DFS Maze Generator
S	Start Pathfinding (Selects random start/end points)
G	Generate Maze (using selected generator)
P	Pause / Resume Simulation
R	Reset Simulation (Clear map and states)

Project Structure

• src/: Source code files.
  • Grid/: Grid visualization logic.
  • maze_generators/: Maze generation algorithms (Strategy Pattern).
  • path_finders/: Pathfinding algorithms (Strategy Pattern).
  • utils/: Utility classes (Map, Cell, Coords, Random_engine).
• doc/: Documentation files.
• cmake/: CMake configuration files.