When I started working on Magicmaker, I was deeply obsessed with procedural generation. Based on that, and my lack of any real level design skills, I decided on random level generation.

These are really bad reasons to pick random level generation over handcrafted levels! Even though it ended up being the right decision in the end, you have to pick what do to with your levels based on what your game needs, not what you're interested in. Additionally, randomly generated levels don't make up for poor level design. Your system can only be as smart as you are, after all! I had to learn quite a bit about level design before I created the system in its current form

Level Generation is divided into two phases: room placement and cellular automata.

Room Placement

Level generation begins with grid of possible rooms, called a super-grid. This is not the same grid that the level tiles live on, but an abstraction. Each cell of the super-grid represents some X by Y number of tile grid cells, defined by the level file. Basic room definitions are placed in the grid as the algorithm iterates. The dimensions of the super-grid are also defined in the level file, with a wee bit of randomness. For instance, generally the Forest Zone is a very horizontal area but there is a decent chance it will be predominantly vertical.

Sample super-grids for the forest zone. Each grid cell represents a 16x12 tile area.

Every level has about 4 or 5 rooms that it can place randomly. Each room is defined with a minimum width, maximum width, minimum height, maximum height, and percent chance to be spawned. There are other arguments, like that define opening to other rooms and where it can be placed in the level. 

The 3 most common rooms in the forest, openings are marked "O". These 3 rooms make up 75%-ish of a level.

Cells in the super-grid have 4 different states: "Empty", "Open(Horizontal)", "Open(Vertical)", and "Filled". 

Initially, every cell of the super-grid is marked "Empty". One random space is marked "Open". The algorithm begins at this location.

Every iteration the algorithm moves around in the "Filled" cells, until it happens upon a space marked "Open(Horizontal)" or "Open(Vertical)", and places one of the random rooms. To handle required rooms, like the player's start room and the boss room, the algorithm will occasionally pick from a list of "required rooms" instead of randomly selecting a room. Some rooms are filtered out based on the location's position in the level, I.E. some rooms only spawn in the bottom half of the level. When a room is picked, it tests the room to see if it overlaps with previously placed rooms. If the position is valid, the room is placed, marking each cell of the room at "Filled". Any "Empty" cell horizontally adjacent to the room  is marked "Open(Horizontal)". The algorithm continues until enough rooms have been placed, or until enough attempts to place a room have failed. This handles most rooms types.

A few iterations of the algorithm.

There are two special rooms that we need to account for: descending-only rooms and rooms with vertical entrances.

Descending-only rooms are 2-grid-height or higher rooms where the player cannot get to the top entrances from the bottom entrances. This is actually handled very simply. When a super-grid cell is marked "Filled" by a descending-only room, this fact is stored by the cell. When the algorithm is searching for a new "Open" space, it may not move up, only down/left/right when on a descending-only cell. Basically the algorithm can only go where the player can go. This eliminates situations where the player falls into a pit they cannot escape from.

This 2x4 room is a tree the the player cannot climb up. If the player can't ascend, neither can the algorithm.

Rooms with vertical entrances are also pretty easy. These are room with entrances directly above or direction below. When placed, vertically adjacent cells are marked "Open(Vertical)". Rooms that have both vertical and horizontal entrances can be spawned on either "Open(Vertical)" or "Open(Horizontal)". Rooms with only vertical entrances can be spawned only on "Open(Vertical)". Rooms with only horizontal entrances can be spawned only on "Open(Horizontal)"

There's three major pitfalls in this step, only one of which I managed to solve.

The first one you might have noticed. If all the required rooms are randomly pulled from a list, what happens if the level finishes generating before we've placed all the required rooms? Well I'm not clever enough to come up with a good solution, so we just throw it out. There end up being a lot of rejected level layouts on the cutting room floor, and a precious few seconds are lost. It doesn't end up taking too long but I wish I had a something better.

Secondly, notice that each room is defined with only a percent chance to spawned, not a percent chance to be placed. A room with a 33% chance to spawn isn't guaranteed to be placed 33% of the time. This leads to small rooms being very common and large room being very rare even if their percent chance is equal. A great deal of time was wasted tweaking percent values in order to achieve desired outcomes!

Last of all, things get pretty boring when we keep seeing the same 4 or 5 rooms. Even though the details of each individual room are different, the player detects the pattern pretty quickly and gets bored. This was solved by adding rare rooms. Random systems are only interesting if they generate outliers. You need to surprise the player. These rooms where hand-crafting in the level editor, usually based around a puzzle, big set-piece, or trap. Only one can be generated per level, and each world has between 5 and 10 of them.

A sample tile grid generated from the room placement algorithm.

Once the level layout is completed, we create a tile grid of empty rooms, and move onto our next stage.

Cellular Automata

Cellular Automata is a pretty popular and fun academic topic. You could spend a million years reading about but its actually a very simple principal.

A cellular automaton is a grid of some size where each cell contains some value. (Like our tile-based levels) Each generation, a new grid is created. Each cell in the new generation is determined by the contents of the cell in the previous generation and the adjacent cells.

For example, say there was a rule that stated if an X is surrounded by exactly 3 other X's, it becomes a O. So the grid:

XXX
OXO
OOO

becomes

XXX
OOO
OOO

In order to avoid getting the same results every time, add a percent chance that the rule is triggered. IE, if an X is surrounded by exactly 3 other X's, it has a 50% chance to become an O.

Very quickly, its easy to see how we can use this to generate some very complicated results.

However since this is sidescroller, we need to take a couple things into consideration. The first thing we need to examine is the spacial relationships of the cells. That is, rules need to take into account the space's relationship to each other. Say you wanted to smooth out the floor of a room, but leave the ceiling jagged.

You want a rule that says if an X has exactly 3 adjacent X's below it, it becomes a O. So now

XXX
OXO
OOO

stays

XXX
OXO
OOO

and the grid

OOO
OXO
XXX

becomes

OOO
OOO
XXX

We can also make it so certain rules only trigger on certain passes. We can have one pass to fill in the ground, another to grow the trees, and another to clean up stray tiles. Otherwise too many things are happening at once sometimes things interfere with each other.

Each room has its own rule-set that dictates its final appearance. We run the rules for each room seperately, then we run a global pass over the entire level to smooth out transitions between rooms.

Note: I shouldn't have to tell you this, bu it is VERY IMPORTANT that you comment and document your cellular automata rules carefully. These rules can be numerous, very complex and not immediately obvious. For example, there are 650 rules in the forest, all impossible to tell what they do on their own.

Once cellular automata has run, we have a finished level!

Lessons Learned: