Dungeon Generator
Procedural Level Generation Tool
An AI-driven tool for procedurally generating dungeon layouts with advanced algorithms
About The Project
The Dungeon Generator is an AI-powered procedural content generation tool that creates unique dungeon layouts for video games. Built from scratch in C++ using ESAT's graphics library, this tool implements multiple advanced algorithms to generate varied, balanced, and visually consistent dungeon environments.
The tool employs a multi-stage generation process: first using Binary Space Partitioning (BSP) to subdivide the space into rooms, then applying Kruskal's algorithm to create a Minimal Spanning Tree that connects all rooms with corridors, and finally utilizing Wave Function Collapse for procedural texturing that follows consistent rules. The entire process is highly customizable through an ImGui interface that allows for real-time parameter adjustment.
This project demonstrates the power of combining established algorithmic approaches with modern procedural generation techniques to create a versatile tool that could be integrated into a game development pipeline to rapidly create varied level layouts.
Features
- BSP (Binary Space Partitioning) for dynamic room layout generation
- Kruskal's algorithm implementation for creating minimum spanning trees that connect all rooms
- Wave Function Collapse algorithm for coherent procedural texturing of rooms and corridors
- ImGui interface for real-time parameter adjustments and visualization controls
- Customizable generation parameters including room size, corridor width, and complexity
- Visualization modes showing different stages of the generation process
Project Information
- Category: AI/Procedural Generation
- Project Date: 2024
- Showcase: YouTube
- Language: C++
- Graphics: ESAT Library
Technical Highlights
Binary Space Partitioning (BSP)
Implemented a recursive BSP algorithm that intelligently subdivides the dungeon space into rooms of varying sizes. The implementation includes customizable parameters for controlling minimum room size, partition variance, and subdivision depth to ensure diverse yet playable room layouts.
Kruskal's Algorithm for MST
Applied Kruskal's algorithm to generate a Minimal Spanning Tree that connects all dungeon rooms with optimal pathway efficiency. The implementation includes disjoint-set data structures for efficient room connectivity checks and prioritizes connections based on distance measures to create natural-feeling dungeon flow.
Wave Function Collapse
Developed a constraint-based Wave Function Collapse implementation for procedural texturing that follows coherent visual rules. This system observes adjacency constraints between different texture types, resulting in natural-looking environments where wall textures properly connect to floor textures and special features appear in appropriate locations.
Interactive Parameter Control
Created an intuitive ImGui interface that exposes all generation parameters for real-time adjustment. This allows users to fine-tune the dungeon generation process while immediately seeing the results, making it easy to discover interesting parameter combinations and design dungeon layouts with specific characteristics.
Technologies Used
Applications & Future Work
This procedural dungeon generator has numerous applications in game development, from quickly prototyping level designs to generating endless content for roguelike games. The tool could be extended in several ways:
- Integration with game engines like Unity or Unreal Engine as a plugin
- Addition of more advanced constraint systems for themed dungeons (castles, caves, temples)
- Implementation of difficulty mapping to create progressively challenging dungeon layouts
- Expansion to include procedural object and enemy placement based on room types and connections
- Development of 3D dungeon generation capabilities using similar algorithmic approaches
The algorithmic foundations implemented in this project provide a solid basis for more complex procedural content generation systems that could significantly reduce level design time while maintaining high-quality, coherent environments.