Skip to content

About

No description, website, or topics provided.

Resources

Stars

0 stars

Watchers

0 watching

Forks

Latest commit

 

History

4 Commits

Folders and files

NameName
Last commit message
Last commit date
 
 
 
 

Repository files navigation

Procedural Map Generator - DSA Project

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.

🎯 Project Overview

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.

🧠 Algorithms Implemented

Phase 1: Maze Generation (Randomized DFS)

  • 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

Phase 2: Dungeon Generation (Rooms + Corridors)

  • 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

Phase 3A: Cave Generation (Cellular Automata)

  • 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

Phase 3B: Terrain Generation (Perlin Noise)

  • 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

Phase 4A: Connectivity Analysis (BFS)

  • 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

Phase 4B: Pathfinding (A* Search)

  • 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

🏗️ Architecture

src/
├── core/           # Core data structures (Grid, Tile)
├── generators/     # Map generation algorithms
├── algorithms/     # Pathfinding, connectivity, noise
├── visualization/  # SFML rendering
└── utils/          # Configuration constants

Design Patterns

  • 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

🚀 Building the Project

Prerequisites

  • CMake 3.16+
  • C++17 compatible compiler (GCC, Clang, MSVC)
  • SFML 2.5+

Windows (MSVC)

# 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

Linux

# Install SFML
sudo apt-get install libsfml-dev  # Ubuntu/Debian
# OR
sudo pacman -S sfml  # Arch

# Build
mkdir build
cd build
cmake ..
make

macOS

# Install SFML
brew install sfml

# Build
mkdir build
cd build
cmake ..
make

🎮 Controls

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

📊 Complexity Analysis

Maze Generator (Randomized DFS)

  • 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

Dungeon Generator

  • Time Complexity: O(N × R) where N = room attempts, R = existing rooms (collision checking)
  • Space Complexity: O(R) for room storage

Cave Generator (Cellular Automata)

  • Time Complexity: O(I × W × H) where I = iterations
  • Space Complexity: O(W × H) for double buffering

A* Pathfinding

  • Time Complexity: O(W × H × log(W × H)) with priority queue
  • Space Complexity: O(W × H) for node tracking

🎓 Key Learning Outcomes

  1. Algorithm Synthesis: Combining multiple algorithms into a cohesive system
  2. Data Structure Selection: Choosing appropriate structures (stack for DFS, priority queue for A*, etc.)
  3. Emergent Complexity: Simple rules creating complex, unpredictable results
  4. Performance Optimization: Cache-friendly data layouts, efficient neighbor lookups
  5. Software Architecture: Clean, modular, extensible design

🔮 Future Enhancements

  • 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

📚 References

  • 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

📝 License

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

About

No description, website, or topics provided.

Resources

Stars

0 stars

Watchers

0 watching

Forks

Releases

Packages

Contributors

Languages