A sophisticated C++ application that algorithmically generates unique, playable 2D maps using multiple data structures and algorithms. This project demonstrates the practical application of core computer science concepts in game development and procedural content generation.
This map generator showcases the synthesis of multiple algorithms working together to create complex, emergent systems. Each generator type demonstrates different algorithmic approaches to the same problem: creating interesting, navigable spaces.
- Algorithm: Depth-First Search with randomized neighbor selection
- Data Structures: Stack (for backtracking), 2D Array (grid representation)
- Key Concept: Graph traversal on an implicit grid graph
- Result: Perfect maze with exactly one path between any two points
- Algorithm: BSP (Binary Space Partitioning) inspired room placement with corridor connection
- Data Structures: Vector (room storage), Collision detection
- Key Concept: Spatial partitioning and graph connectivity
- Result: Classic dungeon layout with distinct rooms connected by corridors
- Algorithm: Iterative cellular automata with neighbor-based rules
- Data Structures: 2D Array with double buffering
- Key Concept: Emergent complexity from simple rules
- Result: Organic, natural-looking cave systems
- Algorithm: Perlin Noise with octave layering
- Data Structures: Permutation table, gradient vectors
- Key Concept: Procedural noise for natural randomness
- Result: Realistic terrain with water, grass, forests, deserts, and mountains
- Algorithm: Breadth-First Search for flood fill
- Data Structures: Queue, Hash Set (visited tracking)
- Key Concept: Graph connectivity and component analysis
- Result: Ensures all generated areas are reachable
- Algorithm: A* with Manhattan distance heuristic
- Data Structures: Priority Queue (min-heap), Hash Map (node tracking)
- Key Concept: Informed search with heuristics
- Result: Optimal path visualization proving map traversability
src/
├── core/ # Core data structures (Grid, Tile)
├── generators/ # Map generation algorithms
├── algorithms/ # Pathfinding, connectivity, noise
├── visualization/ # SFML rendering
└── utils/ # Configuration constants
- Strategy Pattern: Polymorphic generator interface for easy swapping
- Separation of Concerns: Clean division between generation, analysis, and visualization
- Data-Oriented Design: Grid-based representation optimized for cache locality
- CMake 3.16+
- C++17 compatible compiler (GCC, Clang, MSVC)
- SFML 2.5+
# Install SFML via vcpkg
vcpkg install sfml
# Build
mkdir build
cd build
cmake .. -DCMAKE_TOOLCHAIN_FILE=[path-to-vcpkg]/scripts/buildsystems/vcpkg.cmake
cmake --build . --config Release# Install SFML
sudo apt-get install libsfml-dev # Ubuntu/Debian
# OR
sudo pacman -S sfml # Arch
# Build
mkdir build
cd build
cmake ..
make# Install SFML
brew install sfml
# Build
mkdir build
cd build
cmake ..
make| Key | Action |
|---|---|
SPACE |
Generate new map |
1 |
Switch to Maze generator |
2 |
Switch to Dungeon generator |
3 |
Switch to Cave generator |
4 |
Switch to Terrain generator |
P |
Toggle A* pathfinding visualization |
ESC |
Quit application |
- Time Complexity: O(W × H) where W = width, H = height
- Space Complexity: O(W × H) for visited tracking + O(W × H) worst-case stack depth
- Time Complexity: O(N × R) where N = room attempts, R = existing rooms (collision checking)
- Space Complexity: O(R) for room storage
- Time Complexity: O(I × W × H) where I = iterations
- Space Complexity: O(W × H) for double buffering
- Time Complexity: O(W × H × log(W × H)) with priority queue
- Space Complexity: O(W × H) for node tracking
- Algorithm Synthesis: Combining multiple algorithms into a cohesive system
- Data Structure Selection: Choosing appropriate structures (stack for DFS, priority queue for A*, etc.)
- Emergent Complexity: Simple rules creating complex, unpredictable results
- Performance Optimization: Cache-friendly data layouts, efficient neighbor lookups
- Software Architecture: Clean, modular, extensible design
- Export maps to image files (PNG)
- Biome blending and smooth transitions
- Animated generation (watch algorithms work in real-time)
- Room graph visualization showing connectivity
- Save/load map seeds for reproducibility
- 3D height map visualization
- Interactive editing tools
- Maze Generation: "Mazes for Programmers" by Jamis Buck
- Perlin Noise: Ken Perlin's original 1985 paper
- Cellular Automata: "A New Kind of Science" by Stephen Wolfram
- Pathfinding: "Artificial Intelligence: A Modern Approach" by Russell & Norvig
This project is open source and available under the MIT License.
Author: Ritish Khichi
Purpose: portfolio project demonstrating DSA proficiency
Tech Stack: C++17, SFML, CMake