Procedural Level Generation – Other Algorithms

The last couple of times I went into greater detail about the Procedural Level Generation Algorithm used in Wizards’ Duel. Procedural Generation is actually one of the most fun and interesting aspects of developing a Roguelike so, to close it up nicely, I wanted to briefly present some other ways to generate dungeons that you may find interesting. I hope you found this series of articles useful, I surely had fun writing them.

Hedge Maze

Different algorithm may generate various kind of layouts and they are not limited to 2D levels… and not even 3D ones!

Rooms and Corridors

This is one of the most simple algorithms. A number of rectangular rooms are created, of random size (they can be allowed to overlap, thus generating non rectangular rooms, or not) and then, starting with the first two, they are connected with orthogonal or diagonal corridors.

The corridors can connect the centers of two rooms or connect two random points inside of them.

The generated map will look like a dungeon carved from stone. The final result will not be the most interesting but the map will be serviceable and connectedness is guaranteed.

Rooms and Corridors example

Very simple Rooms (blue) and Corridors (yellow) with connections between each couple of rooms (1 to 2, 2 to 3, etc)

Variations include non square rooms and keeping track of corridors intersections to reuse them.

Binary Space Partitioning

This algorithm is recursive, it begins by dividing the level in two sides of random size along one of the axis (horizontal or vertical), then each part is divided in two along a different direction (vertical or horizontal), then again until possible or until a specific number of repetitions or a minimum area threshold is reached.

After that the algorithm “unwinds” itself and in each section a room is created. Finally, rooms are connected by corridors that can run perpendicular to the division lines or randomly connect every couple of rooms.

The created level can resemble the interior of a building.

To add variation, parameters can be set up to randomly join any number of adjacent areas, thus creating bigger and non aligned rooms, or to fill only part of a section, again breaking the sense that every room is aligned to a grid.

BSP Example

Simple BSP level with complete connections, random sized and joint rooms (bottom-left)

Digger Algorithms

The Digger Algorithms are the application of a sort of specialized Artificial Intelligence. In its base form it starts with a level filled with walls then a Digger object is added in a random position. This Digger starts to move according to what rules are defined, sometimes spawning other diggers, until a certain number of floor cells are excavated.

The Diggers works a bit like an ant colony, creating chambers and corridors, guaranteed to be reachable from everywhere.

Digger Algorithms are as varied as the possible rules that they implement. For example you can define Diggers that every N steps change direction and generate a new Digger and that diggers must only create corridors one cell wide, creating a maze. You can also have multiple Digger types, for example a Room Digger will create a room and then “die” after spawning a random number of Corridor Diggers, that will depart from the room and start excavating corridors until they, again, die after spawning a single Room Digger, thus continuing the cycle.

Cellular Automata

The Automaton works iteratively on each cell of the level. At the start the level is filled with noise, then a number of iterations of the Automaton are run. For each iteration every cell is checked against a rule that modifies its content. For example you can decide that a wall surrounded by open cells also becomes an open cell, or that if a cell has at least three walls around it is converted to a wall itself.

Rules can be of any kind and there are a large number of well-known Cellular Automata that are extensively studied in mathematics for their unique properties such as Conway’s Game of Life and Langton’s Ant.

Cellular Automata can create impressive natural-looking caves or also mazes, depending on the defined rules, but they cannot guarantee the full connectedness of the level (generating blobs of non connected open structures). This means that after generating a level you have to check if all the cells are reachable; if not you can dig corridors to connect them or just fill the smaller ones with walls.

Noise Algorithms

Some noise functions, like 2D Perlin Noise, can be used to create levels by simply applying a threshold on the generated lattice.

Noise Generation example

From Simplex Noise (left) to a cave structure (right)

Depending on the parameters of the noise these algorithms can create natural looking caves like Cellular Automata, and are usually easier to implement and faster to run, but they have the same drawbacks.

Vaults

Not really an algorithm, but a way to incorporate static set-pieces, like Blocks, into other generation algorithms. After a level is generated using another algorithm a space large enough to contain a vault is searched (or created by diggers) and the vault is inserted in place.

Vaults usually containing special quest items or unique monsters and treasures.

At a later time I will go back and talk a bit about level design in a procedurally generated game. Thanks for reading.

Advertisements

2 thoughts on “Procedural Level Generation – Other Algorithms

  1. What a nice and short, easy to understand overview on procedural algorithms. The example pictures make all the difference in “just getting it”. Thanks for sharing.

    • Thank you for your interest and support. Procedural generation is a topic that I find really fascinating and I believe that in the future it may become as important as user created content is today.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s