Procedural Level Generation :

An Overview

by Fabien Fouetillou

Abstract

Procedural Content Generation (PCG) is a technique for creating content via the use of well-coded algorithms,

rather than having humans handcraft it from A to Z.

In videogames, there are two mains reasons for its use ; on the developer side, it can be a good tool for

producing, in a matter of seconds, quantities of content that it would otherwise take hours/days/months to do.

On the player side, PCG with the right generation rules and correctly-dosed randomness, is a wonderful way of

discovering something new all the time, and thus add replayability.

In this paper, the focus will be on a specific kind of content: game levels. While generating a weapon with

minor stat variation can be easily achieved, generating a whole playable level and having it be coherent within

the game universe is a much harder task.

Surprisingly, publication of works on the topic of Procedural Level Generation (PLG) – beyond the scope of

simplistic dungeon layouts – is scarcer than expected, therefore, not many external sources will be quoted. Even

PCG Wiki, a site dedicated to this topic, hasn't been updated for the last few years, that's why a fair share of what

will be said in this paper is based personal research and observations.

1 - Introduction

A long time ago, developers with ambitions of creating huge universes

and/or insane amount of content had

to face the issue of very constraining memory limitations. As they couldn't store all the required data on the

media, they basically had two choices: give up and go for something smaller, or find a way to generate said data

at runtime. That's where PCG comes into play.

By programming functions that can output various content depending on what parameters are passed as

input, developers worked out an efficient way of generating objects (weapons, characters, planets, etc) from

minimal amount of data. And depending on their complexity, it could actually also be faster, as creating data on

the fly with simple or optimized algorithms was usually faster than reading it from a slow storage devices.

Another typical reason for PCG is the need to add replay value to a game that might become too predictable

or boring

over time, and keep players excited by always presenting them something new. Be it yet another

variation of a shiny reward, or a whole new area to explore, it is best achieved with the use of randomness (or

more exactly pseudo-randomness) on top of a good set of rules.

That set of rules must be made with balance and feasibility in mind. And this is where things can get very

complicated: distributing points on item stats the moment it's instantiated is hardly a big challenge ; but creating

a complete level, making sure all areas are reachable, and at the same time keeping it coherent with the game's

tone and gameplay surely can become one. Especially if it needs to feel like there is a practical logic behind the

layout.

This paper aims to go deeper into the level design part of PCG, which we'll refer to as Procedural Level

Generation (PLG) from now on. External and personal researches made it clear that there is no “one size fits all”

method for generating levels on-the-fly. Depending of the gameplay, and the eventual need to have a life-like

layout, many different approaches can be taken, each producing different kinds of results. Therefore, several of

them will be exposed, along with with their advantages and drawbacks.

2 - Core Techniques

Procedural Level Generation is a problem for which solutions depend entirely on the expected results. There

is no single all-encompassing solution that matches all the possible scenarios you could think of. As such, you

need to pick one – or a mix of several – to achieve what you are shooting for.

Indeed, an algorithm for generating good-looking and traversable outdoor terrain is of no use for indoor

environments, and the other way around. Developers have to use the methods most suited to their specific

needs, making it harder (or pointless) to write a generic API that could be shared across different projects.

This is not helped by the fact that each game and its gameplay/tone has different needs. Some might just

need a simple layout with no credibility requirement (somewhat easy), while some others need to have a

realistic, practical, almost architect-validatable layout (somewhat harder).

In this section, some of the most typical techniques used in videogames will be described. Unless otherwise mentioned,

all of them make the assumption that the level layout, if its fine details, is organized in a grid of square tiles. Even though it

is not the only way to do it, it is the most common and simplest way to store small scale data.

2.1 - Noise

In signal processing, noise is generally synonymous with unwanted and unpredictable modifications of a given

signal, leading to the presence of perceptible anomalies that decrease its quality. In PCG however, this

unpredictability and perceived randomness is what is needed for creating a virtually infinite amount of different

variations. Also, there is no obvious pattern or coherency in it, which makes it especially suitable for creation of

organic/natural environments. Several kinds of noise exist, and to each case, there is one that is more adapted

than the others. This section explains the most common uses for noise, and which is better suited to each

situation.

2.1.1 - Terrain

Noise-based algorithms are very terrain-friendly. In games, terrains

are generally

treated as a matrix of tiles

that serve as ground surface. To each tile is assigned an elevation value to determine where it will appear in the

vertical axis. With this technique, the application of materials to the surfaces don't need to be handmade, as

elevation values can be used to make a choice or a blending between adequate ones: Grass can be used on low

elevations, and snow on high ones. Angles can also be calculated and used to choose between ground or rock,

depending on the steepness of the slope

Generation can be very simple, a first pass would consist of high amplitude and low frequency noise for

creating the basis for large natural structures. Low elevations can be bottom of lakes, or low altitude ground, and

high values be plains or mountains. Perlin noise is usually a good candidate for such tasks, as it's a smoothed

noise that easily makes natural-looking height maps.

Then on a second pass, adding a lower amplitude but higher frequency noise is all it takes to add interesting

irregularities on what would otherwise be dull terrain. A third pass with even higher frequency but also lower

amplitude can then add the last touch of local transformation that are better seen when visited on foot.

That part was only for the rough terrain geometry, though. It has no gameplay value yet, no decoration, and

bad luck with the values may cause navigation problems, such as unreachable areas. There are means to

circumvent the problem, but as it has nothing to do with noise, it will not be discussed here.

2.1.2 - Population

Another use for noise is level population, which consists in

adding more details and/or gameplay elements to the world

(enemies, treasures, etc).

With the use of a grainy kind of noise, such as the white noise

below, and by choosing the right min/max values and thresholds, it

is very quick to mark a coordinate as candidate for spawning a tree,

without fear that they won't be uniformly placed.

Different values and semantics can be used to place monsters

or items instead of trees.

2.2 - Cellular Automata

A cellular automaton is a model in which a

grid is filled with cells that are set randomly or

arbitrarily to one of two or more possible

states (generally dead or alive). Those cells are

set independently from each other, as the goal

is to animate the grid by making them, on each

tick, change their state according to the states

of their neighbors.

This concept was popularized by John H.

Conway and his Game Of Life

, a game without

player that consists in placing setting some

cells to “alive” on the grid, and watch patterns

evolve from them following some simple rules.

Considering a cell can have four neighbors in

the standard model: a live cell dies if it has less

than two or more than three neighbors, or

stays if it has two or three. Dead cells take life

when surrounded with exactly three live cells.

This simple idea, by replacing the rules and semantics with more appropriate ones, can be used to generate

natural-looking bases for lands or caves for games that use a tile-based grid.

2.2.1 - Cellular Automata for Caves

Very similarly to Conway's Game Of Life, every passes of the resurrects or kills cells depending on their

neighbor's state. The difference is in the rules used. Priority is on destroying cells that do not have enough

neighbors, acting like an erosion filter cleaning isolated cells or those that make walls have a sharp angle.

Reviving dead cells is done only to fill holes between live cells.

The rules usually go like this

: If a cell has three or more neighboring walls, close the hole in the wall by

making it a wall too. If a cell has three or more neighboring floors, convert it to floor. In any other case, do

nothing.

After enough passes, big empty areas are created and walls are filled, leaving only holes too big to be filtered

out. Flood-filling

the floors must be done to detect the different areas. Once done, big ones can be connected by

creasing tunnels between them, and the small ones are generally filled with walls.

Creasing the tunnels can be done by drawing a line of floor cells using the Bresenham

algorithm. To make the

path broad enough to be navigable, cells within a random radius from each cell of the line are converted to floor.

Small holes inside the walls are closed by flood-filling them with wall cells.

2.2.2 - Cellular Automata for Lands

Lands can be generated by using a process very similar to the one used for caves. While the process for

generating caves takes a grid filled with noise and applies multiple passes of filtering to create floor areas

surrounded with walls, the one used for lands does replaces walls with water. Scaled to wider proportions,

regions that are considered holes for cave generation become islands. Those islands can be bridged with an

extended version of the Bresenham line algorithm if need be.

Elevation can be created using cells are the borders of the

islands as reference. By propagating an elevation value to each

neighbor and increasing (for land) or decreasing (for water) it the

further it goes from the coast, it is easy to create mountains on land

and make the bottom of the water deeper and deeper. Of course, to

add variation, that increase/decrease should use a range of values

that allow for small creases and steeper slopes in addition to the

average elevation change.

2.3 - Space Partitioning

Space partitioning is the process of subdividing an area into two or more subareas, that can themselves be

subdivided into more subareas, and so on recursively. In the process, each subarea is attached to its parent in a

tree structure, allowing for quick searches with coordinates as parameters.

2.3.1 - Binary Space Partitioning

In the Procedural Level Generation domain, this space management technique is usually well suited for

generating cities, as it naturally creates blocks of different size that never overlap and can be easily converted to

building blocks.

The most commonly used variant is Binary Space Partitioning (BSP), which consists in splitting an area in only

two parts by recursion step. Those parts don't need to be exact halves, but it is nonetheless good to keep

reasonable ratios so that none of the parts get too tiny to be useful.

In the above screenshot, BSP is applied to strictly rectangular areas and subdivided by respecting few simple

rules. An area cannot be split if it is below a certain surface size, it must always be split split if over a certain size.

Otherwise, when within the minimum and maximum size ranges, it randomly may or may not be split. Also done

randomly, when splitting, is modifying the bounds of the new areas – if they are big enough – in order to create a

gap that will become free space for a road.

Rectangle-shaped Binary Space Partitions can also be used in a similar manner for generating building

interiors. Building blocks becoming room blocks, and roads becoming corridors. But one drawback of such a

simplistic method is that the first split systematically creates a straight path from one border of the grid to the

opposite, which might be an annoyance in projects that expect players to explore a coherent but not

straightforward and predictable layout.

2.3.2 - Voronoi Diagrams

In addition to creating non-rectangular shaped city blocks, which is a much harder process than with

rectangular BSP, Voronoi diagrams

are very good pick for generating caves or lands that don't follow a tiled grid

system.

Voronoi diagrams are tessellation graphs of interconnected polygons. They are made by distributing seed

points randomly on a surface, and connecting each point to its nearest neighbors, creating edges that are half-

way between each pair, and perpendicular to the line connecting them. Random distribution and the way the

connection are chosen might cause the polygons to have very uneven size variation, so it is often better to apply

some relaxation on the graph. Lloyd's algorithm relaxes the graph, on every pass, by moving the seed points to

the center of the previously created polygon, resulting in more evenly distributed space across the diagram.

If we consider the polygons to be cells of cellular automaton, we can apply the same principle to form the

shape of lands and lakes. White noise followed with rules for killing or reviving the cells will work here too. Albeit

with different kill/revive thresholds, as unlike square cells, they can have more than four direct neighbors.

Once the shape is made, elevation for each polygon – or better, each vertex – can be computed relative to its

distance from the closest coast (the same way as with cellular automata).

2.4 - Growth

On a grid of cells, growth is the process of propagating the properties of a cell – or a group of cells – to their

neighbors in order to make them become part of a same group or blend together.

It can be applied on cells after setting them with a pass of space partitioning, or simply on single cells

dropped at random or arbitrary locations over a defined space. In most scenarios, the group is always allowed to

grow on empty cells. Whether they can grow on other already assigned cells all comes down to the set of

established rules.

2.4.1 - Growth for Floor Plans

This method is especially adapted to creation of residential floor

plans that rely more on adjacency between

rooms than on the use of corridors to connect them.

In this example, three initial room positions are set, and each room is given a target size range. Then in a loop,

they are expanded in a rectangular shape until they can no longer grow. This is a case where rectangular growth

is not enough to fill all the cell, but it is not a setback, because the empty space is then filled in an L shape by the

adjacent room that was set at the beginning to require the most space.

2.5 - Modularity

The concept of Modular Design is quite simple to understand. It relies on the assembly of pieces that match

together, not unlike a jigsaw puzzle.

It can be done on several levels, from the general layout of the level to the integration of graphic assets.

While it is not specific to procedural generation, it sure is easier to build structures from compatible blocks than

program a generic solution to every possible scenario.

2.5.1 - Modular Layouts

Module-based Procedural Level Generation is the videogame equivalent of Lego City plates: they have

standardized dimensions and access points, making their roads always compatible.

In PLG, that very principle can be reused easily. The road part can be a city street, or an interior corridor, while

the green part can be free space for buildings or rooms. The plates are modules that can be assembled by setting

some rules, like preventing free-space modules to become passages, making sure it leaves enough ground for big

rooms or building blocks.

Another simpler but less restricted way is to dropping them at random, with low connectivity at first, and

then interconnecting each module to the neighbors that have a pending connection from it. For a better

distribution, it is however best to start with sufficiently spaced passage modules, or else, chances are it will

create a grid.

2.5.2 - Modular Assets

Contrary to the rest of the techniques mentioned earlier, modular assets are not a way to encourage

exploration or improve replay value. It is a mean to rapidly and/or randomly add visual variations, share common

parts between assets, or – last but not least – make the connection between different props or areas look

seamless without having to hand-tweak them.

Said assets can be – and generally are – crafted by artists because complex designs and all their variants are

harder to do get right from code. But although they are prepared by humans, the combination of their parts is

done all from code. It can be just to add cosmetic variation and delay art fatigue

, or because the generation

algorithm requires two adjacent cells to have matching connections.

Below is an example of a kit featuring several variants of plain and windowed walls. Each mesh has a set of

four different textures. They add nothing to the gameplay but prevents the eye from noticing repeated textures,

and thus a break from immersion.

Thanks to their standardized height and width (the large meshes have exactly twice the width of the smaller),

those walls can be interchangeably placed, choosing any of their variants without affecting gameplay.

For more practical gameplay concerns, modular assets allow for automatically selecting compatible and good

looking transitions for every connected part of the level layout. Grid systems make it particularly easy and

convenient to use this approach, as the logic behind placement on square tiles is the simplest of all the

approaches.

The set above has the minimum required assets to make straight corridors, turns and junctions. To make a

cross junction, the level generator only has to place four outer-corner walls (block 5 in the screenshot), a floor

and a ceiling if needed. Obvious as it is, each wall has protruded bricks that blend seamlessly into every other

wall, making it hard for players to notice that they are different pieces of a whole.

2.6 - Grammars

Grammar is the set of rules that restrict how a series of elements (characters, syllables, etc) are chained.

Those rules are generally organized graphs, and more often than not of the tree kind. They can be used to

structure rules in a way that makes the content coherent within its context, adding randomness only to get

enough variation on what is otherwise a predictable logic.

2.6.1 - L-Systems

L-Systems are one of the least used techniques in Procedural Level Generation. The idea behind it is to

associate actions to a series of letters or values, with some of them possibly being a group of the other actions.

The use of recursion is a core part of this design, because it can give more detailed result for each additional

iteration pass. It is therefore closely related to fractal generation, which is, with the addition of randomness, an

excellent way to generate unique trees

at runtime.

In the case of trees, on each iteration of the generation algorithm, new branches are spawned at the tip of

already existing branches. The random variables serve the purpose of managing the angles of new branches,

their length, and sometimes whether they spawn at all. The latter parameter is not mandatory but always

welcome to prevent a too homogeneous density.

2.6.2 - Markov Chain

The Markov Chain is a graph in which each node only has a set of condition determining the next node to be

selected, as opposite to the L-System, where everything depends on the previous node. Thus, a node can lead to

several other nodes, and can be pointed to by more than one. And a node can even point to itself. This

connectivity and the way rules are set lead make the Markov Chain both predictable but more flexible. It is a

good tool to use when some pattern repetition is wanted, but with enough variation to break its lightly. Outside

of PLG, it is often used for generating music procedurally

Games with very linear gameplay and level architecture, like scrolling platformers or endless runners can

easily benefit from this approach. It is good way to make sure different types of platforms or obstacles match

correctly in continuity without breaking the gameplay or visual coherence.

In the screenshot below, the landscape or generated from a Markov Chain that is made in such a way that it

ensures navigability at all times.

The Markov Chain is also particularly suited at generating words and names that may or may not exist, but are

always readable, pronounceable, and not distinguishable from ones made up by a human. In level design, it is

then a good way to name places on procedurally generated levels, as well as the NPCs contained in them.ybrid

Design

In the previous part, we saw some of the most used bases for Procedural Level Generation, but separately. In

practice, levels are not generated using only one techniques. The process is more often than not an association

of several of those, and depending on the required level of control by the designers, it usually includes partially

hand-made patterns, presets, and assets.

3 - Hybrid Design

In the previous part, we saw some of the most used bases for Procedural Level Generation, but separately. In practice,

levels are not generated using only one techniques. The process is more often than not an association of several of those,

and depending on the required level of control by the designers, it usually includes partially hand-made patterns, presets,

and assets.

3.1 - Mixing things up

Most of the time, each of the techniques for from the previous section have advantages and drawbacks,

target results for which they shine, and others for which they are useless. Indeed they are only programming

tools, not all-purposes magical tools. While some of them are good at several things, they cannot do everything.

Think of them as Swiss Army knives: they can do a lot of things, but will they do usually contain a knife, they

cannot fix a nail. This is why one is usually only used at a certain step of the generation, and then another one at

another step.

An example of this would be using Binary Space Partition to plan subdivisions of a grid, then fill that grid with

noise, and applying cell automaton passes on it to carve cave rooms within the con

3.2 - Level designer assistance

Procedural Level Generation doesn’t always mean that the level is mostly automatically computed.

Sometimes, it is only a tool to streamline the level design process.

3.2.1 - Prop Generation and Distribution

One often-used example of procedural shortcuts is the generation and distribution of trees and grass over

vegetation-fertile areas

Creating dozens of different trees or plants is by itself a very time-consuming task, but placing

hundreds/thousands of a instances of them by hand, one at a time, is beyond that: it’s time-wasting. That is why

developers prefer using tools to automate the process. First off, a good piece of code can easily generate good-

looking tree on the fly, without having them being copy-pasted instances. Creating a tree is then just a matter of

inputting/presetting good settings, like broadness of the trunk, overall size, the applied materials on branches

and leaves, etc.

Placing them is another task, which can be approached from different angles: the level designer can use a

brush to paint a bunch of trees within a chosen radius, or simply assigning a certain tree density on a given floor

material, click “distribute” and then just fine-tune the result if some slight undesirable effects occur.

3.2.2 - Modular Design

Already mentioned earlier, modularity is one of the key components for the prevention of time-wasting.

Indeed, having parts that match together as long as they are correctly aligned – or their misalignment correctly

hidden – is a good way to ensure that they will blend seamlessly and won’t shock the eye with bad transitions.

Making modules match also means that less time is spent creating individual meshes and more is available for

placing them

. Some amount of automation is also possible, and can even be part of the gameplay

For example, imagine the editor lets you draw rooms and corridors with simple rectangle selections or

brushes: the cells are automatically given walls if they are the border, corridor cells automatically become

junctions when two perpendicular corridors meet, or plain walls are automatically converted to walls with doors

on both cells when a door connection is added. This is the kind of feature that enhance productivity and design

iteration times considerably.

4 - Conclusion

Procedural Level Generation, if done well, is a very powerful tool. In the iterative phase of game

development, it allows for testing many different situations without having to handcraft every test level. It also

lowers the memory footprint by a huge amount, because redundant data doesn’t need to be stored, only

generated or instanced where and when it is needed. And last but not least, it enables developer to offer a lot

more replayability potential, due to the ability of adding unpredictability to the mix.

Fabien Fouetillou received a degree in Computer Science from the University of La

Rochelle, France, in 2015.

He is currently studying for a Masters degree in Videogame Programming at the

ENJMIN, the National School of Videogames and Interactive Digital Media. His interests

include game-design, graphic arts, storytelling and artificial intelligence.

1 Elite (1984)

2 Diablo 3

3 Terrain generator on Stackoverflow.com

4 Noise in PCG

5 Conway's Game Of Life

6 RaoDaoZao's blog

7 Flood filling

8 Bresenham's line drawing algorithm

9 Voronoi diagrams

10 Publication on Growth-based floor plan generation

11 Modular level design on Skyrim

12 Several PCG techniques, including L-systems

Trees from L-Systems

13 Markov-generated music

14 Random tree scattering

15 Modular design on Skyrim

16 The Sims (lower the volume before clicking)

Tiled terrain before normal smoothing

Room growth

City plan using Binary Space Partitioning

White noise becoming cave rooms after 4 passes

Lego City plates

Examples of mutations in the Game Of Life

Islands from cellular automaton

Set of mesh with their texture variants

Modular straight walls and corners

Island and water polygons on a relaxed Voronoi diagram

L-System generated tree

Markov Chain diagram

2D white noise, aka TV snow

Markov-made platforms and landscape