Modular 3D Dungeon Generation Tool With A*
Personal Project
Details
- Solo Personal Project
- Unity Engine
- August 2024 - November 2024
Project Details
- Implemented Prim's algorithm for adjustable connectivity between rooms based on designer input.
- Utilized the BFS algorithm to find and mark optimal paths through the dungeon from the entrance to the exit.
- Built a modified A* pathfinding system for generating optimal, traversable hallways and staircases within a 3D grid.
- Developed custom Unity Editor tools for dungeon movement, scaling, and visualization.
- Added phase based tile placement and tile weight adjustments to support gameplay progression and modular level creation.
- Focused on user friendly UI with dynamic sliders and real time parameter updates.
- Integrated telemetry and unit testing for performance monitoring and seed based debugging.
Tool Purpose
This tool is designed to streamline the creation of procedurally generated portions of levels for 3D games. It is focused on enhancing the workflow for generating connected room systems, such as dungeons. The tool should feature options for generating in an area, room placement, room adjustment, hall placement, staircase placement, and other adjustable values for how it generates. It’s mainly a tool to connect more major set pieces of level together through procedural dungeons rather than being a standalone dungeon itself.
Target Audience
The tool is intended for level designers and game developers working on procedurally generated environments in 3D games, particularly those working on 3D roguelike, dungeon crawler, or adventure genre games.
Problem the Tool Solves
Making parts of a large and re-playable level can be difficult. This tool allows developers to generate connected, cohesive, and traversable dungeons procedurally without super extensive manual placement. This tool should simplify the process by providing intuitive features for dungeon generation, improving the speed and efficiency of level creation or allowing for dungeons to be rerolled at runtime.
Vision Statement
This tool's vision is to create a modular, flexible, and intelligent way of procedurally generating a portion of a level. The design principles revolve around accessibility for non-programmers, ease of integration into existing projects, and adaptability/modularity for various game mechanics. The tool should allow for iterative adjustments and scalability for various game sizes and complexities.
Implementation in Review
Procedural Dungeon Tool: Optimizing Modular 3D Dungeons Paths with A*
Marked rooms for placement in a 3D grid structure, ensuring to also mark down door exit positions and check for placement validity.
Cited below, I utilized the Bowyer Watson Tetrahedralization algorithm, to generate a complete graph structure out of these positions nodes in 3D space.
Using Prim's Algorithm, I created a Minimum Spanning Tree out of the graph structure in order to simplify the number of dungeon connections.
Added back connections into the graph based on an adjustable value in the editor tool for dungeon connectivity.
In order to get an optimal path out of the graph, a Breadth First Search algorithm is run from the entrance node to the exit node and the paths are marked accordingly. This step was done in case any later tooling or additions wanted to add items such as signifiers or progression mechanics to that path.
Using a modified version of A* for either one tile wide or two tile wide staircases, paths are then created on the grid structure using the connections in the graph.
When specified, tiles are then loaded and spawned using weighted random and phase based tile selection.
The Custom Unity Editor offers many features for dungeon modification including regeneration on scene start, showing gizmos, spawning tiles, the dungeon's grid and axis sizes, phase generation settings, hall settings, room settings, seeding, and unit testing. Many features are dynamic and automatically adjust to other parameters, such as the room size maximums when the dungeon size is updated.
Gif showing an example traversable dungeon structure with the path gizmos enabled.
Level Generation Telemetry
I implemented a custom telemetry unit test within Unity to gather data under specific generation settings: a dungeon size of 25x25x25 (15,625 tiles per grid), room sizes varying from 3-8 tiles in the X and Z directions and 1-2 tiles in the Y direction, a graph connectivity factor of 1/8, and 100 iterations for each stair mode. This data has been invaluable for optimizing the generator and addressing errors and edge cases within the algorithm.
Project Outcome
This project was an exciting opportunity to combine technical problem solving with my passion for creating tools that empower other developers. I was able to focus on making a tool that’s flexible, intuitive, and easy for level designers to use, so that they can focus their creativity without getting too stuck in the technical complexity of procedural generation. With customizable options and debugging tools, this tool makes building modular dungeons efficient and easy to use.
