I needed a dungeon generation algorithm for my current project. Anyone who has played dungeon crawlers will no doubt have come across levels that look like someone scanned a clump of noodles and called it a day. I wanted layouts that wouldn’t immediately be recognized as being generated by an algorithm, much less a bad one.
Binary space partitioning is a commonly used technique, and that’s what I started with too. However it eventually became quite a mess to maintain as I kept adding more features to the game. I knew from early on that eventually I would have to at least clean the code up a bit, so I set out to write a more clean implementation of the BSP algorithm that I could expand on in the future too. I also thought the levels were too repetitive, they all looked similar. Although all of them were unique, you wouldn’t be able to tell whether you had moved on to the next level.
While rewriting my BSP implementation, I played around with only dividing some of the partitions, instead of all of them. This led to more interesting layouts than just a square filled with smaller squares. I couldn’t immediately figure out how to sensibly connect all the partitions without ending up with isolated rooms, though. But the layouts were infinitely more interesting, and I wanted an algorithm that would allow for more variety in layouts.
I ended up devising my own algorithm, and it turned out better than I could’ve hoped for. I named it “crawling algorithm” in my code, but I think Cell Flow
sounds cooler is more descriptive. The layouts now feel distinct from each other, you end up with recognizable areas instead of squares of varying sizes next to each other. The whole thing plays better since there’s a whole new element of exploration, since the levels are more unpredictable as a result. There’s also a bunch of parameters that can be tweaked to get wildly different experiences, which is a big bonus because it means I can make the early levels linear and simplistic, and up the complexity later just by tweaking a few values.
Start with a small grid. We’re going to use 10×10. Each point on the grid will hold an integer.
In code I would define this grid as int[10,10]
Next, we’re going to create the first cell. Assign this cell a unique number. And decide on a randomized size. We’re going to call it cell 1. Pick a random point on the grid and assign this number to that position.
Now, pick a random point on the grid, connected to your starting point. Ensure that this point is empty (has a value of 0), and is not out of bounds. If the point is not free, pick another random point. Repeat until you have a valid point, or there are no possible points left.
Once you find a valid point, assign the cell’s number to that point. Keep track of which point this new point originated from. This is what I call the “flow”, and it’s what ensures that every room is connected and traversable.
Keep doing this until you’ve hit the cell’s size limit or there are no available points.
I figured the easiest implementation would be to make a Cell class to hold all the cell’s data. It includes a list of points the cell occupies, as well as which points those points flow to. The flow is represented by the red arrow.
Next, decide how many times you want the cell to split. We’re doing two splits per cell here. So let’s choose two points from the original cell that have free space next to them. Create new cells at those points, assign them unique numbers, and do the same flow algorithm as the first cell.
We now have three cells total, each of them interconnected through the flow.
If you want your level to have corridors, when splitting the cells choose the new cell’s starting point a few points away, instead of right next to the splitting cell. Assign a special number to the points between the new cell’s starting point and the splitting point. Then later we can iterate over the specially marked points and generate corridors around them.
Split the new cells the same way, and keep doing this until you’ve reached your desired amount of splits. We’re ending at a split depth of three.
We now have our base layout. Next up is making a new grid with enough resolution to fit in walls, doors, props and what have you.
Simply multiply the original grid’s size by at least three. You can choose any amount you see fit, we’re gonna use 5 here. We now have a brand new 50×50 grid.
Let’s call this new grid our Level Grid, since it’ll represent our final generated level. We’re going to call our first grid the Layout Grid from now on.
Next, we iterate over every cell and map their occupied positions into the level.
We first take the cell’s occupied positions and multiply them by our level size multiplier. So the first cell’s occupied position at [4,3] would become [20,15] on the level grid.
We can then map every point on the level grid back to its corresponding point on the layout grid by doing something like:
s = levelGrid.size / layoutGrid.size = 50/10 = 5
levelGrid[22, 17] = layoutGrid[floor(22 / s), floor(17/ s)]
And now we know that point [22,17] belongs to the cell occupying position [4,3] on our layout grid. Based off this we can decide whether or not a given position in the level should contain a wall, a floor or nothing.
For every cell, iterate over its occupied points in the level grid and do the following checks:
If position in level grid maps to cell number in layout grid, add a floor.
If position in level grid maps to cell number in layout grid and an adjacent position in the level grid maps to a different cell number, zero or a special identifier, and that position does not contain a wall, add a wall.
This will leave us with the first cell walled off.
We’ll now simply iterate the rest of the cells.
Next we take the flows we kept track of in the beginning, and map them into lines on the level grid. If these lines go over a wall, remove the wall and place a door.
If you want your levels to have random connections between rooms, you can iterate through random flow points, and add a new flow into a neighboring cell’s occupied position from that random point.
We will also mark every point on the lines so they will never have props or details generating over them, ensuring that there are no blocked off rooms.
And there we have it.
After this we can add different parameters as desired. In my game I have parameters for split depth, minimum and maximum cell size, minimum and maximum splits per cell, cell growth per split, cell growth probability, maximum split distance, corridor width, door placement probability and loop probability.
All these allow for fine control over what you get in the end. Changing split amount, depth and loop probability especially will give you levels ranging from linearly connected rooms to sprawling mazes.