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.

image

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

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. :slight_smile:

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.

OP offers a guide so readers can follow along.

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 :grimacing: