Procedural Generation

This page is a collection of resources and information relating to the random-ish generation of content. This is a very wide topic, and includes things like:

• Texture generation
• Level creation
• World creation
• Story generation

Recently, the term has been applied more to level creation, but really any algorithm that spits out content is going to be "procedural".

Procedural Gen Definition

Procedural generation (procGen) is colloquially defined as "random generation", and in most cases this wording is born from an inadequate understanding of what procedural generation entails.
ProcGen is not random, and intrinsically requires the aspect of being deterministic. I.e. to have the same output, for the same input, and therefor the important concept of a seed emerges.
Determinism is an important characteristic of procGen due to the necessity of reproducibility of results, bugs, and instabilities in your algorithm. F.e. in testing for bugs, stability of the algorithm in extreme value ranges (defining value ranges in a parametric algorithm), and thus the usability of the procGen algorithm in a real game scenario.

Technical

Random Numbers

Random numbers are important in order to produce variety. Because computers can't ever really be random, at least not in any that you would want to do in a game, you need to use what's called pseudo-random generation. This is a good thing, because it requires a "seed". Basically, the random number is generated via a fast but complicated math/comp-sci equation (of which there are several that are suitable), but all of these equations and algorithms need a starting point. This number that acts as the starting point is called the "seed". If you use the same seed, no matter what, the algorithm will generate the same sequence of random numbers.

This property of reliably producing the same sequence of numbers, which appear random, as in there's no discernible pattern to them, allows us to do some interesting things. The original Age of Empires for example, allowed you to generate a random map by providing it with a "seed" value. You could give this seed value to a friend, and he would be able to generate the exact same random map. Consider that you can easily turn a string of characters into numbers, and you are able to do things like generate a map based on a character name, making it easy to remember the seed values.

If your use case requires that things are not predictable, you can use the current time as a seed. Often you might use the "time since epoch" which is implemented differently across platforms and programming languages, but you can be reasonably sure that it will be different every time you use it. The result is that the non-patterned sequence of numbers becomes "random", at least as random as you need them to be for a video game. You likely wouldn't use this stuff for computer security or in-depth statistical analysis of a rocket.

Nearly all of the time, you will want Random Numbers within a certain range. Sometimes you might want a random number between 0 and 1, other times you'll want it between 10 and 1247. This is an implementation details, an example of which is below.

The random number you generate is typically a floating point number between 0 and 1. This can easily be turned into any range of numbers with simple math. For example, to turn it into 0-100, simply by multiply it by 100: 0*100=0, 0.25*100=25, 0.6*100=60, 1*100=100. To turn it into 50-200, multiply it by 150 and then add 50: 0*150+50=50, 0.5*150+50=125, 1*150+50=200. There's one caveat with this though, see integer rounding below.

Integer rounding

[this section needs confirmation/clarification and solutions by someone with more experience]

When you generate a floating point number between 0-1 and turn it into an integer range, you need to take into account the fact that integers round down. Multiplying a 0-1 random number by 100 does not make it equally 0-100, instead it becomes 0-99… UNLESS your random number by some miracle was exactly 1. If your 0-1 random number generator can generate a 1, then each number between 0-99 will have a ~1% chance of appearing, and there will be an incredibly small chance to get a 100.

While a rounding function prevents a super rare number from appearing, it creates a new problem because the lowest and highest numbers will have a different chance of appearing than other numbers. Let's say you multiply by 4 and round it:
0-0.499.. = 0 (0.5 range)
0.5-1.499.. = 1 (1 range)
1.5-2.499.. = 2 (1 range)
2.5-3.499.. = 3 (1 range)
3.5-4 = 4 (0.5 range)

A better, more simplistic solution is to discard the number and generate another one if you get exactly 1, or replace 1 with 0.99 or something.

Utilizing Random Numbers

Now that you have some random numbers in a reliable sequence (or more generally random through the use of time as a seed), we can utilize them to generate content. As a simple example, let's say that we're using this random number to produce a town of characters.

Firstly, let's pretend we "seed" our random number generator using the value of "2133242". There's all sorts of math and proof that mention good numbers to use etc (often primes), but we don't really need to care about all that for a game.

Next, we need to decide, how many people are in our town. We want our town to be between 3 and 10 people. So, we'll grab a random number between 3 and 10. Let's say the result is 6. So this means, we will generate 6 Non-Player Characters for our town.

Next we have 2 different genders (because there's only 2). So let's grab a number between 1 and 2. If it's a 1, the NPC will be male, otherwise a female.

Now the next number we might use to determine the job this NPC has. We might then have a series of jobs defined in a table like this:

Number	Job
0	Wizard
1	Fighter
2	Commoner

So naturally, we will grab a number between 0 and 2 to determine the job. BUT, we want wizards to be really rare, and Commoners to be really common. So maybe we say something like:

Number	Job
0-5	Wizard
6-20	Fighter
20-99	Commoner

Now we can generate a number between 0 and 100, then we're treating each of these Jobs as the percentage possible. With random numbers, we might still end up with a village of 6 wizards, but it would be rare.

We can continue down this path, utilizing numbers to determine which option of many to chose at each step. This is the "procedural" part of the generation, just going through each step of the character generation process, the same process our Players would follow, and randomly selecting options, possibly based on some percentage chance. The beauty of this is that we could share our seed with a friend, and they would have the exact same towns created.

We are now procedurally generating a character. This same concept can be expanded to anything where there's a finite list of options to chose from on a well defined serious of questions. Character generation obviously works well, but we could also generate character stats, we could generate the number of buildings in town, we could generate the list of items that the store sells. These are all relatively simple use-cases, but is the beginning of procedural generation.

Random Textures

Random Levels

There are tons of different algorithms that can be used for level generation. Each of them produces different results and some are more suited for certain types of levels than others (for example, the Cellular Automata algorithm is often used for "cave-like" levels). For simplicity's sake we are going to generate a simple roguelike dungeon using a variant of the Tunneler's algorithm. In the Tunneler's algorithm, you start with a room filed with "dirt" tiles and you have one or more tunneler objects that have a position on the map along with the direction they are facing. They randomly move around the map and dig tunnels where ever they go. Occasionally, they will also create rooms adjacent to the tunnels that they create.

For this example, we will just have one tunneler (marked as "X") that will create corridors and rooms. Let's have the algorithm start by creating one room and have the tunneler go from there.

....................
....................
...................X
....................
....................

As the tunneler traverses the map, it digs out floor tiles.

....................
....................
.............................X
....................
....................

The tunneler will change direction after digging a certain number of tiles

....................
....................
..............................
....................         .
....................         .
                             .
                             .
                             .
                             .
                             .
                             X

Eventually the tunneler will create another room

....................
....................
..............................
....................         .
....................         .
                             .
                             .
                             .
                             .
                             .
                             ........................
                             ........................
                             ........................
                             ........................
                             ........................
                             ........................

Rinse and repeat until you have a dungeon size that you are comfortable with. After that, you can add monsters, treasure, etc at random locations.

Random Worlds

There are many different ways to generate terrain for planets/worlds. The most popular is probably Diamond-square algorithm, but to keep things simple let's just use a quick and dirty algorithm for generating planet/world-like terrain. The easiest way to generate random landmasses (IMO) is a simple algorithm known as "Random walk" or "Drunkard's walk". Basically you start at a random point and just mark random adjacent points as "visited" (or land in this case) until you reach a random threshold. This can be done using a recursive function like this (represented as pseudocode):

create a 2D array of tiles and have them set to water
function markLand(int x, int y, int threshold) {
    if (tiles[y][x] is marked as land) {
       mark tiles[y][x] as land
       if (threshold > 0) {
          for each direction, run the same function on adjacent tiles, based on a random "coin-flip", with threshold being threshold - 1
      }
    }
}
for (int i 0-random(0, 5) {
   markLand(randomX, randomY, randomThreshold)
}

Using ASCII characters for tiles (land marked as "." and water marked as "~"), the resulting map should looking something like this:

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~.~..........~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~.............~~...~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~...........~~.~....~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~..........~~.......~~~~
~~~~~~~~~~~~~~~~~~~~~.~~................~~~.~~~~
~~~~~~~~~~~~~~~~~~~~.........~~~..~......~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~............~~.....~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~.....~....~~~~....~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~...~....~~~~...~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~........~~.~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~....~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~......~~~~~~~~~~~~~~~~
~~~~~~~~~.~~~~~~~~~~~~~~~~~~~..~~~~~~~~~~~.~~.~~
~~~~~..~~.~~~~~~~~~~~~~~~~~~~~.~~~~~~~~~~......~
~~~~....~.~~~~~~~~~~~~~~~~~~~~..~~~~~~~~~......~
~~~~~.....~~~~~~~~~~~~~~~~~~~~.~~~~~~~~~~~......
~~~~~.....~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~.~....
~~~~~.~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~......~
~~~....~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~....~~~
~~~~~..~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~....~~~
~~~~~.~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~...~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~...~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~..~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~...~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~.~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~.~.~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~.....~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~...~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~....~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~...~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~....~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~....~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~.....~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~.....~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~.......~.~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~........~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~.........~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~......~~..~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~...~.~~~.~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~...~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Looks nice, but having just flat land and water is kind of boring. Let's spice it up. We can use the same Random Walk algorithm to add things like forests and mountain ranges. Just be sure to check if the tile is a land tile. Otherwise, you will have forests, mountain ranges, etc growing on top of your oceans. The maximum threshold should also be much smaller than the threshold used to generating landmasses, obviously. Let's have mountain ranges be marked as "#" and forests marked as "^". The resulting map should look something like this.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~.~..........~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~..^^^........~~...~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~....^^.....~~.~....~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~.#^^^.....~~.......~~~~
~~~~~~~~~~~~~~~~~~~~~.~~.###^^..........~~~.~~~~
~~~~~~~~~~~~~~~~~~~~......#..~~~..~......~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~............~~.....~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~.....~#^..~~~~....~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~.^^~#^..~~~~...~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~#^^^....~~.~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~^^^.~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~..^^^.~~~~~~~~~~~~~~~~
~~~~~~~~~.~~~~~~~~~~~~~~~~~~~^.~~~~~~~~~~~.~~.~~
~~~~~..~~#~~~~~~~~~~~~~~~~~~~~.~~~~~~~~~~......~
~~~~....~#~~~~~~~~~~~~~~~~~~~~..~~~~~~~~~......~
~~~~~..###~~~~~~~~~~~~~~~~~~~~.~~~~~~~~~~~......
~~~~~....#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~.~....
~~~~~.~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~#.....~
~~~....~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~.^..~~~
~~~~~..~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^^^^~~~
~~~~~.~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~.^^~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~.^^~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^^~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~.^.~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~.~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~.~.~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~.....~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~..#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~.##.~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~...~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~..^^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~..^^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~...^^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~..^^^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~.......~.~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~........~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~......#..~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~......~~..~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~...~.~~~.~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~...~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

You should get the basic idea by now. You can place towns, dungeons, etc by picking random tiles that are marked as land. If you want to be more logical with the placement of settlements, you can have them placed only near water, in forests, next to rivers, etc.

This algorithm is good enough for 2D or text-based games, but if you want something more advanced (especially for 3D games), you should look into heightmaps and algorithms like Diamond-square.

Story Generation

No idea what to put in this

Example code

Example of a function that generates a random number between 0 and 1. This function isn't good if you need very reliable randomness, but it's relatively fast and works for most cases.

    double random(long seed) {
        double r = sin(seed) * 10000;
        return r - floor(r);
    };

A function that returns a random number in a given range, and handles the integer rounding problem.

    int randomRange(long seed, int min, int max) {
        // generate 0-1 number
        double r = sin(seed) * 10000;
        double rand = r - floor(r);
        // failsafe incase exact 1 appears
        if (rand == 1) rand = 0.999999;
 
        return rand*(max+1-min) + min; // +1 is added to max because rand will never be 1 and the number is rounded down, so the highest number will never appear
    };

Example of a function for spawning randomly generated people.

void world_generatePeople (long seed) {
    int peopletogenerate = randomRange(seed, 3, 10); // get random number, 3-10 people
    seed ++; // change seed so the next call to randomRange won't give the same result
 
    for (int i=0; i<peopletogenerate; i++) {
        Person person = {}; // create an empty Person object
 
        // gender
        int gender = randomRange(seed, 0, 1);
        seed ++;
        if (gender == 0) {
            person.gender = GENDER_MALE;
        }
        else {
            person.gender = GENDER_FEMALE;
        }
 
        // job
        int job = randomRange(seed, 0, 100);
        seed ++;
        if (job > 20) {
            // create commoner
            person.job = JOB_COMMONER;
        }
        else if (job > 5) {
            // create fighter
            person.job = JOB_FIGHTER;
            person.can_fight = true;
            person.HP *= 2; // fighters have twice the HP as other people
        }
        else {
            // create wizard
            person.job = JOB_WIZARD;
            person.can_fight = true;
 
            person.magicpower = randomRange(seed, 50, 100); // 50-100 magic power
            seed ++;
        }
 
        // spawn the person we generated above
        world_spawnPerson(person);
    }
}