Dungeon Generation: A Procedural Generation Guide
Intro
What is procedural generation?
This RDC 2019 keynote best describes what it is.
As @Crazyman32 stated in this video,
Procedural generation, loosely defined, is a way of using algorithms in order to create data using pure functions - so it sounds like a lot of gibberish right away - but basically a pure function is one in which you always get the same output as long as you have the same input. So a really simple way to think of this is an addition function- you know you add two numbers together- so maybe you know two plus three equals five that will always be true as long as you feed the addition function a two and a three you can always expect a five out of it that would be a pure function. One that’s not pure would be one where you give it a two and a three and it might give you something different every time. This is opposed to creating data manually so you know we’re not just going by hand and place data here and there; we are letting an algorithm do it for us.
TLDR:
Essentially, it’s when you use some sort of algorithm and get some desired output. It’s like a function in math, when you plug in numbers and get back some value based on it.
Instead of manually calculating or putting everything together, you can use algorithms to do it for you.
.
IMO I find algorithms very aesthetically pleasing to make, especially non-pure, or random generation ones, because you can really get cool formations no one would ever think of. This is the basis of the dungeon generation algorithm I decide to teach in this guide.
We’ll be creating something like this on Roblox!
So, if you don’t know what a dungeon is (why wouldn’t you?), it’s like a maze consisting of a number of rooms connected by corridors.
We’re going to make a simple top-down 2D dungeon.
Here’s something a random 2D dungeon would look like.
Of course there are many algorithms to generate mazes, but I’m going with a room-maze-corridor type of algorithm.
You’ll see in the next part.
Designing the Algorithm
Arguably the most important part of this guide.
You don’t even have to be a programmer to understand this.
Okay, face the fact. If you don’t have an algorithm behind something, you can’t make it.
Knowing the battle is winning like 80% of it.
It’s important that the algorithm you design has to be (The 3 -ables);
- Implementable (to be able to actually script it)
- Understandable (know what’s going on)
- Trustable (you can rely it gives accurate results)
In this case, for our dungeon generation algorithm, we’re going to design using top-down design, when you design the ideas first then implement.
Our design in this.
- Create the dungeon area.
- Create rooms randomly. Brute force set amounts of times to a max number of rooms.
- Run a maze algorithm to fill spaces outside of rooms
- Create openings to the rooms
- Find pathways from room to room using flood fill
- Remove other non-path cells
Scripting the Algorithm
For the scripters out there.
We’ll be creating an object oriented approach to it.
Here’s a good thread from 2014 on the DevForums.
Step 1: Create the dungeon area.
.
We start by creating a simple Cell class.
local Cell = {};
Cell.__index = Cell;
Cell.new = function(x, y)
local Self = {};
Self.x = x;
Self.y = y;
Self.Visited = false;
Self.isRoom = false;
Self.availDirs = {N = true, E = true, S = true, W = true};
Self.closeToRoom = false;
Self.Door = false;
Self.Filled = false;
Self.outRef = nil;
return setmetatable(Self, Cell);
end;
return Cell;
Then as we create more and more classes to create the dungeon we add more auxiliary methods to it.
You can see more of the auxiliary methods implemented here.
.
Then we make the maze class itself (that’s responsible for filling the “canvas” with cells)
local Maze = {};
Maze.__index = Maze;
local Cell = require(script.Cell);
Maze.new = function(sizeX, sizeY)
if (sizeX < 1 or sizeY < 1) then
return;
end;
local Self = {};
Self.Map = {};
local mazeInfo = {x = sizeX, y = sizeY};
for X = 1, sizeX do
Self.Map[X] = {};
for Y = 1, sizeY do
Self.Map[X][Y] = Cell.new(X, Y);
end;
end;
Self.sX = sizeX;
Self.sY = sizeY;
return setmetatable(Self, Maze);
end;
We get something like this.
Step 2: Create rooms randomly
.
We create a Settings module to organize some of the constants to use here.
FYI.
ROOM_BORDER_LENIANCY is the minimum spacing between rooms.
MAX_ROOM_TRIES is the number of bruteforce tries to fit a room if it’s under MAX_ROOMS.
ROOM_BORDER_RETRIES is the number of retries for the openings of the room.
You can figure out the rest.
local Room = {};
setmetatable(Room, {__index = Room});
local Sett = require(script.Parent.Parent.Settings);
local l = Sett.ROOM_BORDER_LENIANCY;
local r = Sett.ROOM_BORDER
local function ir(min, max, num)
return num >= min and num <= max;
end;
local function assign(Self, Cell, Dir)
table.insert(Self.Outsiders, Cell);
Cell.outRef = Self;
Cell.onlyDir = Dir;
end
Room.new = function(Maze, x1, y1, x2, y2)
local Self = {};
local sX = Maze.sX;
local sY = Maze.sY;
Self.ref = Maze;
Self.tl = {x = x1, y = y1};
Self.br = {x = x2, y = y2};
Self.Outsiders = {};
local Map = Maze.Map;
for x = math.max(1, x1 - l), math.min(x2 + l, sX) do
for y = math.max(1, y1 - l), math.min(y2 + l, sY) do
local Cell = Map[x][y];
if not (x < x1 or y < y1 or x > x2 or y > y2) then
Cell.Visited = true;
Cell.isRoom = true;
do
local Dirs = Cell.availDirs;
if (x ~= x1) then Dirs.W = nil; end;
if (x ~= x2) then Dirs.E = nil; end;
if (y ~= y1) then Dirs.N = nil; end;
if (y ~= y2) then Dirs.S = nil; end;
end;
end;
Cell.closeToRoom = true;
if (x >= 1 and y >= 1 and x <= sX and y <= sY) then
if (x > 1 and y > 1 and x < sX and y < sY) then
if (
(x == x1 and ir(y1, y2, y)) or
(y == y1 and ir(x1, x2, x)) or
(x == x2 and ir(y1, y2, y)) or
(y == y2 and ir(x1, x2, x)) )
then
table.insert(Self.Outsiders, Cell);
Cell.outRef = Self;
end;
end;
do -- This section is poorly optimized. I can do better maybe.
local d = Cell.availDirs;
if (x == x1 and x == 1) or (x == x2 and x == sX) then
if (y == y2 and d.S and y ~= sY) then
assign(Self, Cell, 'S');
end;
if (y == y1 and d.N and y ~= 1) then
assign(Self, Cell, 'N');
end;
end;
if (y == y1 and y == 1) or (y == y2 and y == sY) then
if (x == x2 and d.E and x ~= sX) then
assign(Self, Cell, 'E');
end
if (x == x1 and d.W and x ~= 1) then
assign(Self, Cell, 'W');
end
end;
end;
end;
end;
end;
return setmetatable(Self, Room);
end;
return Room;
This creates a room of random size and position using brute force algorithm and gives up if it reaches the max.
Also, it labels the outmost cells as candidates for openings. It’d also be a good idea to include special cases for when those cells are on edges.
Then, we create a “House” of Rooms for easy manipulation.
And in our main class, Dungeon, set up the canvas and house itself.
Dungeon.new = function(sX, sY)
local Self = Maze.new(sX, sY);
Self.House = House.new(Self);
return setmetatable(Self, Dungeon);
end;
function Dungeon:init()
-- We will write stuff in the next steps!
end;
Step 3: Run a maze algorithm to fill spaces outside of rooms
.
So if we run some tests with the rooms, we’d have something like this.
The problem with mazes with rooms as holes in them is that some maze generation algorithms, like Hunt and Kill creates blocked off areas. In fact, you can try experimenting with the GitHub place and files, I’ve written a Hunt and Kill algorithm in the Maze class and you can replace that with Maze:Recursive(), it just doesn’t work as well.
Recursive Backtracker is our main maze algorithm. You can read more of it in the link. I want to keep this guide as concise as possible.
function Maze:Recursive()
self.unfixedCells = {}; -- internal
local uCells = self.unfixedCells;
local sX, sY = self.sX, self.sY;
local Map = self.Map;
for i = 1, sX do
for j = 1, sY do
local Cell = Map[i][j];
if (not Cell.isRoom) then
table.insert(uCells, Cell);
end;
end;
end;
while (#uCells > 0) do
local curCell = uCells[#uCells];
curCell.Visited = true;
local Neighbors = curCell:GetUnvisitedNeighbors(self);
if (#Neighbors ~= 0) then
local pickedNeighbor = Neighbors[Rand:NextInteger(1, #Neighbors)];
local relDir, oCell = pickedNeighbor.Dir, pickedNeighbor.Cell;
curCell:DelInBetween(oCell, relDir);
table.insert(uCells, oCell);
else
table.remove(uCells);
end;
end;
end;
Look at it now!
Step 4: Create openings to the rooms
.
This is when our bordering room cells come to play.
Do know that you must have 2 or more rooms for openings.
In the Dungeon init method, we also brute force openings! We have 2 doorways max (or more if you want, just change the number in the for loop).
if (#oHouse.Rooms > 1) then
for _, v in next, oHouse.Rooms do
local Outsiders = v.Outsiders;
local Tries = 0;
for i = 1, 2 do
local selRoom;
repeat
local Cand = Outsiders[Rand:NextInteger(1, #Outsiders)];
if (not Cand.Door) then
local Dir do
if (Cand.onlyDir) then
Dir = Cand.onlyDir;
else
local availDirs = table.keys(Cand.availDirs);
Dir = availDirs[Rand:NextInteger(1, #availDirs)];
end
end
local Opp = Cand:getCellOfDirection(Map, Dir);
Cand:DelInBetween(Opp, Dir);
Cand.Door = Dir;
table.insert(oHouse.Doors, Cand);
break;
end;
Tries = Tries + 1;
until Tries >= Sett.ROOM_BORDER_RETRIES;
if (Tries >= Sett.ROOM_BORDER_RETRIES) then return end;
end;
end;
self:searchForDoor(oHouse);
end;
We delete the walls between the room and the chosen door as its picked.
self:searchForDoor(oHouse); will be explained in the next step.
We have this now!
Step 5: Find pathways from room to room
.
We’ll be implementing a flood fill algorithm.
For every door in a room that has not been checked, it will carve a path cell by cell to the nearest possible door of another room. If failed, then it will close off that door checked from the maze.
Here’s the flood fill in the Maze class.
We actually start the check in the cell adjacent to the door.
function Maze.Search(oMaze, origCell)
oMaze:wipeFilled();
local cPath;
local function Search(tCell, Path)
if (tCell.isRoom) then
if (tCell.outRef ~= origCell.outRef) then
return;
end;
end;
table.insert(Path, tCell);
tCell.Filled = true;
if (tCell.isRoom) then
return;
end;
local Neighbors = tCell:GetNonRoomNeighbors(oMaze);
for _, v in next, Neighbors do
local relDir, Cell = v.Dir, v.Cell;
if (Cell.Door and origCell.outRef ~= Cell.outRef) then
table.insert(Path, Cell);
cPath = Path;
break;
end;
end;
if (not cPath) then
for _, v in next, Neighbors do
if ((not v.Cell.Filled or v.isPath)) then
Search(v.Cell, table.shallow(Path));
end;
end;
end;
end;
local look = origCell.Door;
local lookCell = origCell:getCellOfDirection(oMaze.Map, look);
Search(lookCell, {origCell});
if (cPath) then
for _, v in next, cPath do
v.isPath = true;
end;
end;
end;
Then we can run it with every door in the grid.
function Maze:searchForDoor(House)
local Doors = House.Doors;
for _, v in next, Doors do
if (not v.Filled) then
Maze.Search(House.Maze, v);
end;
end;
for _, v in next, Doors do
if (not v.isPath) then
local look = v.Door;
local lookCell = v:getCellOfDirection(self.Map, look);
v.availDirs[look] = true;
lookCell.availDirs[oppDir[look]] = true;
end;
end;
end;
The blue specifies the path of the cells while the pink cells are the adjacent door cells.
Step 6: Remove other non-path cells
.
Our last step, all we do is simply remove the rest of the non-room cells that aren’t part of a path. If a non-room cell is next to a path cell, just re-create the walls between them.
In our Dungeon:init() method, all we do is tack on this to the end and call it a day!
for i = 1, sX do
for j = 1, sY do
local Cell = Map[i][j];
if (not Cell.isRoom and not Cell.isPath) then
local Dirs = Cell.availDirs; -- Avoid new table creation
Dirs.W = false;
Dirs.E = false;
Dirs.S = false;
Dirs.N = false;
local Neighbors = Cell:GetNonRoomNeighbors(self);
for _, v in next, Neighbors do
local Dir, oCell = v.Dir, v.Cell;
if (oCell.isPath) then
oCell.availDirs[oppDir[Dir]] = true;
break;
end
end;
end;
end;
end;
(We could just set availDirs to {}, but creating tables = more memory.)
Our end result?
This!
TLDR of everything?
At first, I thought making random dungeons were hard. But I realized all it took was thinking of design and we end up with a basic 2D dungeon with rooms and paths!
I couldn’t include all the code in this tutorial alone, so all the code is on my GitHub! It’s open source, so everyone can learn from it and use it.
(I’d appreciate it if you’d credit me, if you’re making a game with this and monetizing it.)
— Happy scripting everyone! - Nyapaw (iiau)
As a bonus, here’s a massive 6400 cell dungeon.
