MazeEngine - Procedural Maze Generator (C++ Implementation)

MazeEngine is a configurable maze generation algorithm implementing autonomous path-building agents with real-time console visualization.

Project Description

This C++ maze generator employs an innovative agent-based approach to create complex procedural labyrinths through autonomous path-building entities called "Conquerors." Designed for both educational study and practical implementation, the system combines user-defined parameters with emergent behavior to generate infinitely varied maze structures.

At initialization, users configure three core parameters:

• Grid Size: Determines maze dimensions (odd numbers recommended for optimal path spacing)
• Number of Kernel Points: Strategic spawn locations that seed the conquerors that will generate the paths.
• Path Constraints: Minimum and maximum straight-line distances conquerors travel before making a random turn.

The algorithm then deploys two critical agent types:

1. Gate Guardians: Permanent conquerors spawned from entry/exit points that guarantee solvable connectivity.
2. Kernel Explorers: 1-4 agents per kernel point (at least one direction/at most, all directions) that navigate randomly within path constraints.

As generation unfolds, conquerors exhibit distinct behaviors:

• Carve paths in cardinal directions until reaching user defined path movement limits
• Make 90° turns when exhausting their path-length allowance
• Collide with existing paths, creating organic junctions
• "Die" gracefully when trapped by their own (or other agents') trails

Parameter combinations produce radically different maze personalities:

• Dense Networks emerge from many kernel points with short path constraints (4-10 units), creating intricate webs of interconnected passages.
• Bold Corridors form with few kernels and long paths (50-100 units), yielding sweeping arterial routes with minimal branching.
• Balanced Labyrinths arise from moderate settings, blending exploration and efficiency.

Despite real-time console visualization adding modest overhead, the engine demonstrates remarkable efficiency. Memory-only tests with extreme scales (1,000,000 tiles grids, 5,000 concurrent conquerors) complete generation in under 30 seconds on modern hardware. The C++ implementation prioritizes algorithmic clarity while maintaining practical performance through:

• Spatial partitioning for collision checks
• RAII-managed resource handling
• Standard library optimized containers

The system's true power lies in balancing user control with procedural chaos - while parameters set boundaries, each conqueror's micro-decisions create unpredictable macro-structures. This ensures unique mazes on every generation, even with identical starting conditions, making it ideal for game development, AI training environments, and procedural content research.

Building the Project

Requirements

• C++14 compatible compiler
• CMake 3.15 or newer

Build Instructions

git clone https://github.com/binaryalley/maze-engine-cpp.git
cd cpp-maze-generator
mkdir build && cd build
cmake .. -DCMAKE_BUILD_TYPE=Release
cmake --build .

Usage

Run the executable:

./MazeGenerator

You will then be asked for an output type (console, memory - not implemented, file - not implemented), and the required parameters: map size, number of starting points, minimum and maximum path segments distance.

Parameters example

Argument	Description	Default
size	Maze dimension (N x N)	33
spawners	Number of path origin points	5
min_distance	Minimum straight path segment length	4
max_distance	Maximum straight path segment length	8

Algorithm Overview

The generation process follows three phases:

1. Initialization

   • Create entry/exit gates with guaranteed paths
   • Place kernel points for organic path branching
   • Initialize Conqueror agents with movement constraints

2. Path Construction

   • Autonomous agent navigation using:
     • Weighted directional selection
     • Path memory (prevents revisiting)
     • Collision detection
   • Dynamic turn probability based on local density

3. Termination

   • Natural termination when all agents exhaust movement options
   • Validation of full connectivity
   • Final gate placement verification

Technical Details

Key C++ Features

• RAII for resource management
• Template-based collection operations
• Bitmask enums for cell types and directions

Visualization System

• Abstract IWriter interface
• Platform-specific console implementations:
  • Windows: WinAPI console functions
  • Unix: ANSI escape sequences
• Real-time ASCII display refresh

Contributing Guidelines

Contributions are welcome under these requirements:

1. Code Style:
   • Google C++ Style Guide
   • clang-format enforcement
   • Doxygen-style comments for public APIs

License

This project is licensed under the GPLv3.0. See the LICENSE file for details.