# Dungeon Generation: A Procedural Generation Guide

## `Dungeon Generation: A Procedural Generation Guide`

Intro
What is procedural generation?

This RDC 2019 keynote best describes what it is.
https://developer.roblox.com/en-us/videos/procedural-generation-not-just-for-terrain

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.

• 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.)

Iâ€™m pretty sure by now Iâ€™d feed a lot of people if they become successful devs from this guide and DevEx for their lunch money.

â€” Happy scripting everyone! - Nyapaw (iiau)

As a bonus, hereâ€™s a massive 6400 cell dungeon.

276 Likes

This will help lots of developers including me! Once someone understands the process, they could expand on this and make a full game! Great tutorial!

5 Likes

This is a stunning achievement. Wow! Iâ€™ll be rereading this post a few times to make sure I have taken in all the details.

1 Like

Thatâ€™s awesome! Nice work. Thanks for referencing my talk!

15 Likes

This is very helpful people who want to make a dungeon crawler game. Great work Nyapaw.

Amazing Post, Sure this will help me in a game in the future, thanks!

3 Likes

Amazing tutorial, will definitely be using this. I know that procedural generation can also be used to place items in specific chunks and I am wondering if you plan to add that in a later tutorial.

Some example that comes in my head is that a room will try to spawn a chest with a chance of 20%.

Thanks man! I had literally no knowledge on how to create something like this, thank you very much!

Thanks for this amazing post, great job, as always.

Thanks for this tutorial and letting me be lazy when making a custom dungeon map for my Dungeons and Dragons campaigns! I really think this is a nice dungeon making process that is honestly much better than any of the other ways Iâ€™ve seen. I really hope to see more great resources!

1 Like

Could you give us a file or free model of this thing?

Just take the place.

You could always turn it into a model.

I know this is kinda old but, could you attach a place or model file? Anything.

Would be awesome. Thanks for making this amazing tutorial.

I just used the Github link at the bottom of OP, then copy and paste source lua into a new .rbxl file.

Then you can play with it and either customize or learn more from it.

2 Likes

what does this do exactly?

does this add x to the self.map array or does it create its own array.

or does it have something to do with 2d arrays???

1 Like

I know that this may be somewhat difficult to do, but I have a request for a tutorial. I am attempting to create a game similar to this:

In this game, the creator has made different little plots, each one having a different floor and different furniture. For instance, if you 5 types of plots, one could have planks as a flooring, one could have fabric, another ice, another grass, and another pebbles. I was wondering how I would make these plots with different variety and with spaces between them for walkways. Iâ€™d also like to know how I could have a set plot at a set location, like the pillars in the game. For instance, every 3 plots, a pillar. I am a beginner scripter, so I would really like a tutorial for this. Thank you!

2 Likes

Amazing tutorial defiantly needed this for my game Iâ€™m working on thanks!

Perhaps you could go to scripting help and ask people how you would do this? Iâ€™m sure a lot of people there can answer your question. (Btw IF you decide to do that, Donâ€™t ask them to make a full script.)

1 Like

In fact after a few hours, I did make my own topic. Unfortunately, like I said, Iâ€™m a horrible scripter.

thatâ€™s really really simple actually. start by choosing the map size; letâ€™s say thereâ€™s 4 plots on each side

``````local plots = 4
for a = -plots, plots do
for b = -plots, plots do

end
end
``````

this code goes through each point in our imaginary grid. in each of those points you need to choose a random plot model like so; (this code goes inside both loops)

``````local size = 20 -- let's say 20 is the size of our plot

local clone = game.ServerStorage["plot"..math.random(1,5)]
clone.Parent = workspace
clone:SetPrimaryPartCFrame(a*size, 1, b*size)
``````

keep i mind you need to have a primarypart set for all of these models, so the script can move them into their position.
if you want a specific room in a specific spot you can just do

`if a == number and b == number then clone = workspace.ServerStorage.specificRoom:Clone() end`

sorry if i formatted anything wrongly whoops iâ€™m new to this