Scattering rooms at random gives you overlaps to untangle and islands nobody can reach. Binary space partitioning (BSP) avoids both by construction: rooms can't overlap because each one lives in its own slice of the map, and the corridors follow the same tree that made the slices, so every room is connected.
The whole generator is four steps: split, place rooms, connect, draw.
Split the map until the pieces are room-sized
Start with one rectangle covering the map. Cut it in two, then cut each half, and keep going until a piece is too small to cut again. Each cut makes a node with two children; the pieces that are left uncut are the leaves, and each leaf gets one room.
using UnityEngine;
public class BspNode
{
public readonly RectInt area;
public BspNode left, right;
public RectInt room; // leaves only
public BspNode(RectInt area) => this.area = area;
public bool IsLeaf => left == null;
}Always cut across the longer side, or the map turns into long thin strips:
static void Split(BspNode node, System.Random rng, int minSize)
{
RectInt a = node.area;
bool canCutX = a.width >= minSize * 2;
bool canCutY = a.height >= minSize * 2;
if (!canCutX && !canCutY) return;
bool cutX = canCutX && (!canCutY || a.width > a.height || (a.width == a.height && rng.Next(2) == 0));
if (cutX)
{
int cut = rng.Next(minSize, a.width - minSize + 1);
node.left = new BspNode(new RectInt(a.x, a.y, cut, a.height));
node.right = new BspNode(new RectInt(a.x + cut, a.y, a.width - cut, a.height));
}
else
{
int cut = rng.Next(minSize, a.height - minSize + 1);
node.left = new BspNode(new RectInt(a.x, a.y, a.width, cut));
node.right = new BspNode(new RectInt(a.x, a.y + cut, a.width, a.height - cut));
}
Split(node.left, rng, minSize);
Split(node.right, rng, minSize);
}The cut always leaves at least minSize on both sides, so no leaf ends up too small to hold a room.
Put one room in each leaf
A room fills between half and nearly all of its leaf, with a little padding so two rooms in neighbouring leaves never share a wall:
static void PlaceRooms(BspNode node, System.Random rng, int padding, List<RectInt> rooms)
{
if (!node.IsLeaf)
{
PlaceRooms(node.left, rng, padding, rooms);
PlaceRooms(node.right, rng, padding, rooms);
return;
}
RectInt a = node.area;
int w = rng.Next(a.width / 2, a.width - padding * 2 + 1);
int h = rng.Next(a.height / 2, a.height - padding * 2 + 1);
int x = rng.Next(a.x + padding, a.xMax - padding - w + 1);
int y = rng.Next(a.y + padding, a.yMax - padding - h + 1);
node.room = new RectInt(x, y, w, h);
rooms.Add(node.room);
}Keep padding at no more than a quarter of minSize, or a small leaf has no room left once the padding is taken off.
Connect every split
Here's where BSP earns its keep. Walk the tree, and at every node join one room from its left side to one room from its right side. Each side is already connected inside itself, so joining the two sides connects everything below the node. Do it at every node and the root covers the whole dungeon: every room is reachable, and you never have to check.
static RectInt AnyRoom(BspNode node, System.Random rng)
{
while (!node.IsLeaf) node = rng.Next(2) == 0 ? node.left : node.right;
return node.room;
}
static void Connect(BspNode node, System.Random rng, List<(Vector2Int start, Vector2Int end)> corridors)
{
if (node.IsLeaf) return;
Connect(node.left, rng, corridors);
Connect(node.right, rng, corridors);
Vector2Int a = Vector2Int.FloorToInt(AnyRoom(node.left, rng).center);
Vector2Int b = Vector2Int.FloorToInt(AnyRoom(node.right, rng).center);
corridors.Add((a, b));
}Picking a room at random on each side, rather than always the nearest, gives the corridors some variety. A corridor will sometimes cut through a third room on its way; that only adds a shortcut.
Draw it into a grid
Everything so far is rectangles. Turn it into floor cells: every cell of every room, plus an L-shaped corridor for each join.
using System;
using System.Collections.Generic;
using UnityEngine;
public static class BspDungeon
{
public static bool[,] Generate(int width, int height, int seed, int minSize = 10, int padding = 1)
{
var rng = new System.Random(seed);
var root = new BspNode(new RectInt(0, 0, width, height));
Split(root, rng, minSize);
var rooms = new List<RectInt>();
PlaceRooms(root, rng, padding, rooms);
var corridors = new List<(Vector2Int start, Vector2Int end)>();
Connect(root, rng, corridors);
var floor = new bool[width, height];
foreach (RectInt room in rooms)
foreach (Vector2Int cell in room.allPositionsWithin)
floor[cell.x, cell.y] = true;
foreach ((Vector2Int start, Vector2Int end) in corridors)
CarveCorridor(floor, start, end, rng);
return floor;
}
static void CarveCorridor(bool[,] floor, Vector2Int start, Vector2Int end, System.Random rng)
{
// Along x then y, or along y then x.
Vector2Int corner = rng.Next(2) == 0 ? new Vector2Int(end.x, start.y) : new Vector2Int(start.x, end.y);
CarveLine(floor, start, corner);
CarveLine(floor, corner, end);
}
static void CarveLine(bool[,] floor, Vector2Int start, Vector2Int end)
{
var step = new Vector2Int(Math.Sign(end.x - start.x), Math.Sign(end.y - start.y));
for (Vector2Int p = start; p != end; p += step) floor[p.x, p.y] = true;
floor[end.x, end.y] = true;
}
// Split, PlaceRooms, AnyRoom and Connect from above go here.
}Then put tiles on a Tilemap. For big maps, collect the positions and call SetTiles once instead of SetTile per cell, which redraws far less often.
using UnityEngine;
using UnityEngine.Tilemaps;
public class DungeonView : MonoBehaviour
{
[SerializeField] Tilemap tilemap;
[SerializeField] TileBase floorTile;
[SerializeField] int width = 64, height = 48, seed = 12345;
void Start()
{
bool[,] floor = BspDungeon.Generate(width, height, seed);
tilemap.ClearAllTiles();
for (int x = 0; x < width; x++)
for (int y = 0; y < height; y++)
if (floor[x, y]) tilemap.SetTile(new Vector3Int(x, y, 0), floorTile);
}
}Use your own random numbers
Everything above draws from one System.Random made from the seed, never from UnityEngine.Random. Unity's random is a single generator shared by every script: seeding it with Random.InitState resets it for the rest of the game too, and if generation ever runs across several frames, behind a loading screen or in a coroutine, any script that rolls a number in between changes the dungeon. A private generator means one seed always gives one dungeon: the same level after a reload, a daily challenge everyone shares, and a bug report you can reproduce from a single number.
