Imagine launching your favorite rogue-like game. Every time you press “New Game,” the layout changes. The hallways twist in new directions, the loot is hidden in different corners, and the enemies lie in wait behind doors you’ve never seen before. This isn’t magic; it is Procedural Content Generation (PCG).
For game developers, static level design is a double-edged sword. While it allows for meticulous control, it limits replayability. Once a player knows the map, the mystery vanishes. Procedural generation solves this by using algorithms to create game levels dynamically. However, many beginners find the concept daunting. How do you ensure the dungeon is beatable? How do you prevent rooms from overlapping? How do you turn a grid of numbers into a beautiful environment?
In this comprehensive guide, we will break down the wall of complexity. We will explore the fundamental logic of procedural dungeon generation in Unity using C#, focusing on two industry-standard algorithms: the Drunkard’s Walk and Binary Space Partitioning (BSP). By the end of this post, you will have a robust system capable of generating infinite, playable dungeons.
Why Use Procedural Generation?
Before we dive into the code, it is essential to understand the “why.” PCG is not just about saving time; in fact, writing a good generator often takes more time than hand-crafting a single level. The benefits lie elsewhere:
- Replayability: Games like The Binding of Isaac or Hades thrive because players cannot memorize the layout.
- Scalability: You can create massive worlds (like in No Man’s Sky) that would be impossible to build manually.
- Reduced File Size: Since the world is generated at runtime from a “seed” (a simple string or number), you don’t need to store gigabytes of level data.
Core Concepts: The Building Blocks
To build a dungeon generator, we need to think in terms of data structures rather than visual objects. In Unity, we often represent a dungeon as a grid of Vector2Int coordinates.
The Seed
Procedural generation is rarely truly “random.” It is pseudo-random. By using a “seed,” you can ensure that the same number sequence is generated every time. This is how players can share a “world seed” with friends so they can play the exact same map.
The Grid vs. The Tilemap
In the logic phase, we treat the dungeon as a HashSet<Vector2Int>. This collection stores the coordinates of every “floor” tile. Once the math is done, we pass this data to Unity’s Tilemap component to render the actual sprites.
Method 1: The Drunkard’s Walk Algorithm
The Drunkard’s Walk is one of the simplest yet most effective algorithms for organic, cave-like dungeons. Imagine a person standing in the middle of a grid. They take a step in a random direction (North, South, East, or West), mark that spot as a floor, and then repeat the process for a set number of steps.
Step 1: Defining the Directions
We need a helper class to handle our 2D movement logic. This makes the code cleaner and more readable.
using System.Collections.Generic;
using UnityEngine;
public static class Direction2D
{
// Cardinal directions: Up, Right, Down, Left
public static List<Vector2Int> cardinalDirectionsList = new List<Vector2Int>
{
new Vector2Int(0, 1), // UP
new Vector2Int(1, 0), // RIGHT
new Vector2Int(0, -1), // DOWN
new Vector2Int(-1, 0) // LEFT
};
public static Vector2Int GetRandomCardinalDirection()
{
return cardinalDirectionsList[Random.Range(0, cardinalDirectionsList.Count)];
}
}Step 2: The Logic Implementation
Now, let’s create the actual generation logic. This script will return a collection of positions that represent our dungeon floors.
public static class SimpleRandomWalkAlgorithm
{
public static HashSet<Vector2Int> SimpleRandomWalk(Vector2Int startPosition, int walkLength)
{
HashSet<Vector2Int> path = new HashSet<Vector2Int>();
path.Add(startPosition);
var previousPosition = startPosition;
for (int i = 0; i < walkLength; i++)
{
// Calculate new position by adding a random direction to the previous one
var newPosition = previousPosition + Direction2D.GetRandomCardinalDirection();
path.Add(newPosition);
previousPosition = newPosition;
}
return path;
}
}Why use a HashSet?
Notice we use HashSet<Vector2Int> instead of a List. A HashSet automatically prevents duplicate coordinates. If the “drunkard” steps on the same tile twice, the HashSet simply ignores the second entry, saving memory and processing time later.
Method 2: Binary Space Partitioning (BSP)
If you want structured, room-based dungeons (like in the original Legend of Zelda), BSP is the way to go. It works by taking a large rectangular area and repeatedly splitting it into smaller rectangles until you reach the desired room size.
How it works:
- Start with a large area (e.g., 50×50).
- Split it either horizontally or vertically at a random point.
- Take the resulting two rectangles and split them again.
- Stop when the rectangles are small enough to be “rooms.”
- Carve rooms inside these rectangles and connect them with corridors.
public static List<BoundsInt> BinarySpacePartitioning(BoundsInt spaceToSplit, int minWidth, int minHeight)
{
Queue<BoundsInt> roomsQueue = new Queue<BoundsInt>();
List<BoundsInt> roomsList = new List<BoundsInt>();
roomsQueue.Enqueue(spaceToSplit);
while (roomsQueue.Count > 0)
{
var room = roomsQueue.Dequeue();
if (room.size.y >= minHeight && room.size.x >= minWidth)
{
// Decide whether to split or keep as a room
if (Random.value > 0.5f)
{
if (room.size.y >= minHeight * 2)
{
SplitHorizontally(minHeight, roomsQueue, room);
}
else if (room.size.x >= minWidth * 2)
{
SplitVertically(minWidth, roomsQueue, room);
}
else
{
roomsList.Add(room);
}
}
else
{
if (room.size.x >= minWidth * 2)
{
SplitVertically(minWidth, roomsQueue, room);
}
else if (room.size.y >= minHeight * 2)
{
SplitHorizontally(minHeight, roomsQueue, room);
}
else
{
roomsList.Add(room);
}
}
}
}
return roomsList;
}Visualizing the Dungeon: Tilemaps
Once you have the logic (the coordinates), you need to show them in Unity. The most efficient way is using the Tilemap system. Creating thousands of individual GameObjects for walls and floors will crash your game performance. Tilemaps batch these into a single draw call.
The Tilemap Visualizer
Create a script that takes your HashSet<Vector2Int> and paints it.
using UnityEngine;
using UnityEngine.Tilemaps;
public class TilemapVisualizer : MonoBehaviour
{
[SerializeField] private Tilemap floorTilemap;
[SerializeField] private TileBase floorTile;
public void PaintFloorTiles(IEnumerable<Vector2Int> floorPositions)
{
Clear();
foreach (var position in floorPositions)
{
PaintSingleTile(floorTilemap, floorTile, position);
}
}
private void PaintSingleTile(Tilemap tilemap, TileBase tile, Vector2Int position)
{
var tilePosition = tilemap.WorldToCell((Vector3Int)position);
tilemap.SetTile(tilePosition, tile);
}
public void Clear()
{
floorTilemap.ClearAllTiles();
}
}Step-by-Step Implementation Guide
Follow these steps to build your first generator:
Step 1: Project Setup
- Create a new 2D project in Unity.
- Create a Grid object (Right-click in Hierarchy -> 2D Object -> Tilemap).
- Organize your folders:
Scripts,Tiles,Sprites.
Step 2: Create the Generator Script
Create a script named AbstractDungeonGenerator. This will be the base class for all your algorithms, allowing you to swap “Drunkard’s Walk” for “BSP” without rewriting the visualization code.
Step 3: Handle the Walls
A common mistake is only generating floors. Players need walls! To create walls:
- Find all floor coordinates.
- For every floor tile, check its 8 neighbors (including diagonals).
- If a neighbor is NOT a floor tile, it must be a wall tile.
public static HashSet<Vector2Int> FindWalls(HashSet<Vector2Int> floorPositions)
{
HashSet<Vector2Int> wallPositions = new HashSet<Vector2Int>();
foreach (var position in floorPositions)
{
foreach (var direction in Direction2D.cardinalDirectionsList)
{
var neighborPosition = position + direction;
if (!floorPositions.Contains(neighborPosition))
wallPositions.Add(neighborPosition);
}
}
return wallPositions;
}Common Mistakes and How to Fix Them
1. The “Island” Problem
The Issue: Your algorithm creates two separate rooms that aren’t connected, making the level unbeatable.
The Fix: Use a spanning tree or simply ensure that every time you create a new room in BSP, you draw a “corridor” (a line of floor tiles) to the previous room’s center.
2. Infinite Loops
The Issue: Your Drunkard’s Walk is confined to a small area and can’t find new tiles to fill, causing the for loop to run forever (if using while loops).
The Fix: Always use a iteration limit or a timeout variable. In the code above, we use a fixed walkLength which prevents this.
3. Poor Performance (Overshooting Tile Updates)
The Issue: Calling SetTile inside a loop for 10,000 tiles is slow.
The Fix: Use tilemap.SetTiles(positionsArray, tilesArray) which is an optimized bulk operation, rather than calling SetTile individually.
Advanced Optimization Techniques
When you move from a small 20×20 dungeon to a 500×500 world, performance becomes critical. Here are two ways to optimize:
Bitmasking for Auto-Tiling
Instead of manually placing corners and edges, use Bitmasking. By checking the neighbors of a wall tile, you can assign it a unique ID (from 0 to 255). This ID corresponds to a specific sprite (e.g., an “Inner Corner” vs. a “Straight Top Wall”). This makes your dungeons look professional and organic.
Object Pooling for Entities
Don’t Instantiate enemies and loot every time the dungeon generates. Use an Object Pool. When the dungeon is generated, “activate” the objects from the pool; when the player leaves, “deactivate” them. This prevents the “GC (Garbage Collector) Spike” that causes stuttering in Unity games.
Summary & Key Takeaways
- PCG is Logic First: Always separate your mathematical generation logic from your Unity visualization (Tilemaps).
- Data Structures Matter: Use
HashSetfor fast lookups and to avoid duplicate tiles. - Algorithm Choice: Use Drunkard’s Walk for caves/organic shapes and BSP for structured, rectangular rooms.
- Seeds are Essential: They allow for debugging, sharing levels, and consistency.
- Optimization: Use Tilemaps for visuals and Object Pooling for dynamic entities like enemies and loot.
Frequently Asked Questions (FAQ)
1. Is procedural generation better than hand-crafted levels?
Neither is strictly “better.” Hand-crafted levels allow for tight narrative control and “hero moments.” PCG is better for games focused on replayability and systemic interaction. Many modern games use a hybrid approach (hand-crafted chunks arranged procedurally).
2. How do I place the Player in a generated dungeon?
A simple way is to pick the first coordinate in your HashSet<Vector2Int> floor list. Since that tile is guaranteed to be a floor, the player won’t spawn inside a wall.
3. How do I make sure the exit is reachable from the entrance?
In algorithms like BSP, connection is guaranteed if you connect children rooms during the split. For other algorithms, you can use a Pathfinding Algorithm (like A*). If A* can’t find a path from Start to Exit, the dungeon is invalid—throw it away and regenerate it (this happens in milliseconds).
4. Can I use this for 3D games?
Yes! The logic is identical. Instead of Vector2Int, you would use Vector3Int. Instead of Tilemaps, you would spawn 3D “Room Prefabs” or use a Voxel system.