Labyrinth Procedural Dungeon Generator

Blueprints are the backbone of the algorithm. They must exist in order for any rooms to generate. Blueprints are simply single-celled marks on a grid that tell the algorithm "a room can eventually spawn here". When the blueprints are done generating, a second pass parses the blueprints and generates rooms based on a set of rules. Think of how Rule Tiles work in game engines.

public class Blueprint
{
    public readonly string CellID;
    public readonly Vector3Int Position;    // Position of blueprint coords on grid
    public bool Available { get; set; }     // Prevents/allows parsing algorithm to use blueprint
    public bool[] EntryPointFlags { get; set; }

    // Constructor
    public Blueprint(Vector3Int position, string cellID = "Blueprint")
    {
        Available = true;
        CellID = cellID;
        Position = position;
        EntryPointFlags = new bool[6];      // A flag to mark which entrances should be open for a room
    }
}

To prevent blueprints from spawning on top of other blueprints, a Dictionary is used. A C# dictionary has O(1) lookup time, cannot contain duplicates, and can allocate space dynamically. To prevent rooms from spawning on top of each other, blueprints house a flag called Available that tells the room parser whether or not to include the blueprint in its check. Finally, EntryPointFlags tell the room which doorways it needs to open. These flags are determined during the blueprint pass of the algorithm.

Blueprint Operations are individual instruction-set style units of execution that can generate Blueprints in a specific pattern. This not only fosters a more organically catered dungeon but also makes the generation easy to debug by stepping through each operation individually one-by-one.

The Blueprint Graph determines the order of execution of each individual Blueprint Operation. Taking inspiration from Unreal's Blueprint system, the developer can mix and match operations in order to generate specific progression patterns in the dungeon. The operations responsible for generation are Pathfinding, Random Placement, and the Drunkard's Walk. Although, these generation patterns can be combined and expanded via set operations - union, intersection, and difference. There are also random access operations for even more variation. Generation patterns can be repeated via the branch and jump operations.

Right now, all nodes are hardcoded into a controller, though this feature would work perfectly with Unity's graphing toolkit in a future implementation. Below is the controller used to both store and execute operations. Operations can be stepped through by a specified stepLength, given via the Advance() function.

public class MapGenerationController
{
    private void LoadOperations()
    {
        // Hardcoded operations listed in their order of execution. Loaded into context to be executed later.

        ...
    }

    private void ConsumeStep()
    {
        if (_runToEnd)
            return;

        if (_stepBudget > 0)
            _stepBudget--;
    }

    public void Advance(int stepLength)
    {
        if (stepLength <= 0)
            return;

        _stepBudget += stepLength;
        _runToEnd = false;
    }

    public void AdvanceAll()
    {
        if (!IsGenerating)
            return;

        _runToEnd = true;
    }

    private IEnumerator ExecuteOperations()
    {
        // Execute operations and generate blueprints
        while (_context.OperationQueue.Count > 0)
        {
            // Halt the execution of operations
            while (!_runToEnd && _stepBudget <= 0)
                yield return null;

            ConsumeStep();

            // Dequeue the current operation
            BlueprintOperation operation = _context.OperationQueueDequeue();
            if (operation == null)
                throw new ArgumentNullException(nameof(operation));

            // Execute Operation
            bool result = operation.Execute();

            // Operation failed to execute; stop running coroutine
            if (!result)
            {
                GenerationFailed();
                yield break;
            }
        }
    }

    ...
}

One of the most important problems I set out to solve was a way to generate themed areas and connect them together in a seamless fashion, allowing the player to move back and forth between them. Alongside rogue-likes I'm also a huge fan of RPGs that can transport the player to different areas but also require them to come back to earlier areas for progression purposes. The concept of "Zones" helped me accomplish this.

Zones connect to one another through intermediary zones I call "Connection Zones." These zones simply intersect their bounds with others and connect them via their own blueprint operations. In the clip, blue blueprints are part of the zone and purple ones are part of the connection zone.

As of now, Zones are purely containers that house unique rooms, branches, and bounds that contain their blueprints. A controller still determines zone generation, though in a future update, Zones will be able to house their own operations and blueprint graph for unique generation rules.

Delaunay Triangulation takes a set of defined points and creates a mesh such that no vertex lies inside the circumcircle of a triangle in the mesh. That mesh can later be used as a graph for pathfinding. In 2D it's fairly simple, but in 3D it gets more complicated: instead of triangles we must use tetrahedra and find the circumsphere of each tetrahedron using the determinant. This article helped me calculate those things.

My implementation of Delaunay uses a set of blueprint positions as points and creates edges connecting them. It also helps prevent the generation of a dungeon with too many long and unnecessary paths between rooms.

Greedy Algorithms

Delaunay ensures every point in the resultant graph is connected, which means no room is left out. However, this can still result in many edges, leading to an excess of branches and rooms. To manage this, I use a greedy algorithm, Prim's Algorithm, to find the MST (minimum spanning tree) in the graph. From there, we can randomly select other edges in the graph if we want some loops in our dungeon.

The final pass of the algorithm parses all available blueprints using a process I call Lexgen. The parsing determines what rooms can be generated from an orientation and pattern of blueprints. The parsing system is based on a top-down recursive technique commonly used in compilers called Recursive Descent Parsing.

Shape Data

ShapeData is an object that essentially functions as a token for parsing. Generated blueprint cells are checked against each possible shape, the shapes that fit the blueprint structure perfectly are chosen to be generated. By generate I mean spawning the rooms that the shapes represent, each shape having a respective list of rooms. You can think of this method as similar to the old "Fitting Shapes In Their Correct Holes" game that toddlers play.

Many pathfinding algorithms exist that could help connect blueprints together, but none are as fast and versatile as A*. Encapsulating A* into an operation, I can either connect two blueprints directly or pass in a graph and connect all of its nodes. A* returns all the positions needed to connect the blueprints, and from there I simply spawn new blueprints in their place.

Heuristic Functions

A cost/heuristic function tells A* how to path toward each blueprint. The heuristic can make the path curvy, straight, or zig-zagged. There are endless possibilities for what the cost function can be, but as of now I use four well-known functions:

1. Euclidean — creates a fairly straight path to the target.
   D = √((x₂ − x₁)² + (y₂ − y₁)² + (z₂ − z₁)²)
2. Manhattan — causes the path to stay parallel to the x, y, and z axes.
   D = |x₂ − x₁| + |y₂ − y₁| + |z₂ − z₁|
3. Chebyshev — causes the path to zig-zag and staircase.
   D = max(|x₂ − x₁|, |y₂ − y₁|, |z₂ − z₁|)
4. Dijkstra — guaranteed optimal path; cheapest route.
   D = 0

Originally, before I became obsessed with the procedural generator, this project leaned more toward a game than a tech demo. The player could wield multiple weapons, each housing its own set of abilities, and also cycled through situational states like falling, climbing, and emoting. Without a formal state model, the player codebase would have devolved into an unmanageable tangle of flags and booleans, so I turned to finite automata instead.

Using the principles from Introduction to the Theory of Computation by Michael Sipser, I modeled the player as an NFA: a set of states Q, whose transitions are triggered by an input symbol from the alphabet Σ, or by an empty input. The rules break down as follows:

• States (Q) = { Idle, ComboPrimary, PowerPrimary, ComboSecondary, PowerSecondary, Charge, Cast, Fall, Land, Climb, Dash, DashAttack, Hit, Death, Emote }
• Alphabet (Σ) = { button_south, button_east, button_west, button_north, left_stick, right_stick, right_shoulder, left_shoulder, right_trigger, left_trigger, interact, take_damage, IsGrounded() = true, IsGrounded() = false, left_stick + right_stick, left_shoulder + right_shoulder, emote }
• Start State (q0 ∈ Q) = { Idle }
• Final States (F ⊆ Q) = { Death }

Each state in code is represented as a class. A new instance is created and held in the player's currentState variable. Every state implements a shared interface with three required functions:

public class SomePlayerState : PlayerState
{
    public SomePlayerState(PlayerStateMachine stateMachine) : base(stateMachine) { }

    // Enter is called on the first frame when the state is created.
    public override void Enter() { }

    // Tick is called on every frame of the stateMachine.
    public override void Tick(float deltaTime) { }

    // Exit is called right before the state is switched.
    public override void Exit() { }
}

• Enter() fires on the first frame the state becomes active, before any Tick() calls. It's best used for subscribing to events and setting up animations.
• Tick() runs every frame the player remains in the state, handling whatever needs continuous updating.
• Exit() runs on the state's final frame, right before the switch occurs — the next state won't begin executing until this finishes. It's the right place to unsubscribe from events and cancel any in-progress actions or animations.

This state machine kept the player controller predictable even as the ability list grew; new states could be added without worrying about which combination of booleans might silently break another. In hindsight, that discipline ended up mattering more than I expected: once the procedural generator became the focus of the project, having a player controller that was already modular and easy to scale meant I could add more states and abilities in the future without worrying about changing source code.