Graph-based dungeon generation is an advanced procedural system where the structure of a dungeon is defined using graph theory.
Instead of random placement, the generator constructs a graph of nodes (rooms) connected by edges (paths), giving developers precise control over structure, pacing, difficulty, and flow.

1. Why Use Graph‑Based Generation?

Compared to traditional random level generation, graph‑based systems offer:

• Predictable structural control: Designers can enforce rules like “boss room must be far from start.”
• Gameplay flow planning: Difficulty, pacing, and branching paths are encoded in the graph.
• Modularity: Rooms can be swapped while the structure stays intact.
• Rule enforcement: Ensures valid connections, no dead-ends (unless desired), and proper graph connectivity.

2. Core Concepts

2.1 Nodes (Rooms)

Each node represents a playable room and stores metadata:

• Room type (start, corridor, combat, treasure, boss)
• Door positions
• Difficulty level
• Possible room connections
• Tags (secret, puzzle, hub, etc.)

2.2 Edges (Connections)

Edges represent valid connections between rooms:

• Door‑to‑door compatibility
• Direction constraints
• Required connections (e.g., corridor must connect to 2+ rooms)

2.3 Graph Rules

Rules define how nodes can link together:

• Boss room must have exactly one previous node
• Treasure rooms cannot be on main path
• Loops allowed only after 4th depth
• Start → Corridor → Combat → Corridor → Boss (example path)

3. Graph Data Structure

public class RoomNode
{
    public string ID;
    public RoomType Type;
    public List<RoomNode> connections = new List<RoomNode>();

    public Vector3 position;
    public Quaternion rotation;

    public int depth; // distance from start
}

public class DungeonGraph
{
    public RoomNode startNode;
    public List<RoomNode> allNodes = new List<RoomNode>();
}

4. Generating the Dungeon Graph

Most systems follow this pipeline:

1. Create start node
2. Expand graph using DFS, BFS, or hybrid
3. Apply room type rules
4. Validate connectivity
5. Optionally add loops or branches
6. Convert graph nodes into actual room prefabs

5. Graph Expansion Example (DFS)

void ExpandGraphDFS(RoomNode current, int maxSize)
{
    if (graph.allNodes.Count >= maxSize)
        return;

    var possibleRooms = GetValidRoomTypes(current);

    foreach (var roomType in possibleRooms)
    {
        RoomNode next = new RoomNode
        {
            ID = System.Guid.NewGuid().ToString(),
            Type = roomType,
            depth = current.depth + 1
        };

        current.connections.Add(next);
        graph.allNodes.Add(next);

        ExpandGraphDFS(next, maxSize);
        if (graph.allNodes.Count >= maxSize)
            break;
    }
}

6. Rule‑Based Selection Logic

Rules enforce structural coherence:

List<RoomType> GetValidRoomTypes(RoomNode current)
{
    List<RoomType> options = new List<RoomType>();

    foreach (var type in System.Enum.GetValues(typeof(RoomType)))
    {
        if (!IsAllowed(current, (RoomType)type))
            continue;

        options.Add((RoomType)type);
    }

    return options;
}

bool IsAllowed(RoomNode parent, RoomType candidate)
{
    // Example rules:

    if (candidate == RoomType.Boss && parent.depth < 4)
        return false;

    if (candidate == RoomType.Start)
        return false;

    if (candidate == RoomType.Treasure && parent.Type == RoomType.Start)
        return false;

    return true;
}

7. Converting Graph to Physical Dungeon Layout

After the graph structure is complete, the system must place rooms in the world.

The placement stage includes:

• Finding valid positions for each room
• Aligning doors via rotation and translation
• Checking for collisions/overlaps
• Spawning corridor connectors

void PlaceDungeonRooms()
{
    foreach (var node in graph.allNodes)
    {
        DungeonRoom prefab = SelectPrefab(node.Type);

        Vector3 pos = CalculateRoomPosition(node);
        Quaternion rot = Quaternion.identity;

        Instantiate(prefab, pos, rot);
    }
}

8. Collision‑Free Placement

Ensure rooms do not overlap:

bool IsPlacementFree(Vector3 pos)
{
    return !Physics.CheckBox(pos, new Vector3(5, 5, 5));
}

9. Adding Optional Features

• Weighted room distribution
• Graph-based difficulty progression
• Secret paths and hidden cycles
• Smart enemy placement based on depth
• Loot rarity defined by node distance
• Editor visualization of the graph structure

10. Visualizing the Graph (Debug)

void OnDrawGizmos()
{
    if (graph == null) return;

    Gizmos.color = Color.yellow;

    foreach (var node in graph.allNodes)
    {
        Gizmos.DrawSphere(node.position, 0.5f);

        foreach (var c in node.connections)
        {
            Gizmos.DrawLine(node.position, c.position);
        }
    }
}

Conclusion

Graph‑based dungeon generation is one of the most powerful procedural techniques available in game development.
It allows a perfect balance between randomness and designer intention by defining the structure using nodes, edges, and rules.
This architecture creates levels that feel handcrafted while remaining infinitely replayable.