Procedural Generation

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

Probably to focus more on rogue-like level generation of rooms and corridors.

Random Worlds

Focus more on the creation of planet-like textures and height-maps

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);
    }
}
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License