In part 1 I have defined the building blocks of the Level Genaration Algorithm that we will be using for Wizards’ Duel. Today I will describe in detail the algorithm, but first we need to talk about the level properties.
The Level in itself, in fact, has some properties to fine tune the generation process:
Valid Blocks. A list of references to what Blocks are allowed (Blocks are not a property of the level, so that they can be reused).
Guaranteed Blocks. A list of Blocks that must be generated for the level to be valid.
Starting Block. A reference to what Block used as the first iteration of the algorithm, it can be empty to use a random one.
Ending Block. A reference to what Block used as the first iteration of the algorithm, it can be empty to use a random one.
Minimum Area. The minimum used area for a level to be considered valid.
Maximum Width and Maximum Height. These give a sort of shape to a level, but are used mostly to instantiate the empty level.
Default Tile. At creation, the level is filled with this Tile. Usually the Default Tiles are walls, normally meant to be impassable, for this reason many level generation algorithms also use the term Digger to define themselves or part of the procedure.
Other than that some post process operations may be defined. These can be a number of runs from a Cellular Automaton or some specific algorithms like:
Dead Ends Removal. Removes all the cells that can be accessed from a single side, with respect of the 4 cardinal directions.
Gaps Removal. Change a cell from a wall to open if it could be reached from two sides, with respect of the 4 cardinal directions.
First all the level assets (Blocks, Tile Blueprints and Level Properties) are loaded. Then a blank level of the specified size is created, empty.
The algorithm starts by placing the Starting Room as defined in the level properties. The placement can follow some special rules, like always place it in a certain position on the map, but is otherwise guaranteed to succeed and no special checks is necessary.
With the Starting Room also its exits are added to a list of Potential Exits. This list keeps track of what exits can be currently used to connect to another room.
Now the core of the algorithm begins. One of the Potential Exits is randomly selected and a random block, with a matching access, is selected (see the yellow dots in the picture), prioritizing Blocks in the “Guaranteed” category.
The algorithm then checks if the selected room has enough space to be correctly placed.
If there is enough space, the room is drawn on the map and its exits, if any, are added to the Potential Exits lists, while the original exit is removed (see for example the yellow and green rooms). During this step the Block is parsed for special situations, like Conditional Tiles (tiles that can randomly have different properties, like being a wall half of the time) or unique Objects.
If there is not enough space a new room is random selected and the check is performed again. If no rooms are found that can be placed then the exit is closed and the cycle restarts, selecting a new Potential Exit.
Rooms are added until a target number of used cells is reached, thus guaranteeing a level of a specific size.
It can happen, depending on the list of Blocks to be used, that certain combinations may empty the list of Potential Exits before the level has reached the threshold size. In this case the algorithm can simply be restarted.
Finally the Ending Block is placed, attached to one of the remaining exits.
After the level is complete some post-processing may occur to remove spurious elements like dead ends or non connected corridors.
For dead ends it is possible to iteratively remove all cells that can be accessed from only one side until no dead end cells remains.
For gaps between corridors it is possible to convert to open cells all the walls that can be accessed from exactly two opposing sides.
Bear in mind that the order of these post process may affect the end result, see for example the following figure center and right images (with dead ends removal and gaps removal executed first, respectively).
The algorithm can be summarized in the following steps:
Place the starting block, according to the level parameters,
Add its exits to the list of Potential Exits,
While the level has too few open cells:
Randomly select a Potential Exit,
Find a random block that can be connected to the exit and place it,
Add the new block exits to the list of Potential Exits while removing the one that was used,
- Select an unused exit and place the end block, accordinf to the level parameters,
- Run the post process algorithm (close gaps and dead ends).
That wraps up the level generation algorithm. Just by changing the Blocks you can have a lot of variations and generate different kind of level, the following is an example using the same blocks defined above minus the room.
Of course there are a ton of algorithms for Procedural Level Generation, and I will briefly describe them in my next post. What do you think so far? Have you got any suggestions to improve the algorithm? You can always share them in the comments or on twitter.
Thanks for reading.