Procedural Content Generation for C++ Game Development

Procedural generation is the process of creating content using an algorithm. This in itself has no element of randomness. If the functions, expressions, algorithms, and inputs that are used to generate the content remain the same, then you'll always get the same results. This is due to the fact that computers are deterministic, which is something that we'll cover shortly. Procedural generation is not inherently random.

Randomness is induced when we give these algorithms different inputs or alter their expressions. This variance is what creates the variety of the output. When someone says something was procedurally generated, they usually mean procedurally generated utilizing randomness.

Random number generation is simply the process of picking a number at random. This is pretty straightforward for us, but it is a much tougher task for a computer. In fact, it's impossible for a computer to generate a truly random number without special hardware. You'll understand why this is so in a moment.

The next best thing is pseudorandom number generation. The word pseudo literally means not genuine. Therefore, pseudorandom number generation can be thought of as a fake random number generation. The numbers appear to be random but are actually the result of complex equations and algorithms that could in fact be calculated in advance.

Bear in mind that not all pseudorandom number generators are built equally. For applications such as trivial simulations and games, fairly linear algorithms can be used and are perfectly suitable. However, pseudorandom number generation is also used in applications such as cryptography, and will use much more complex algorithms so that the outcome cannot be determined via patterns created from earlier outputs.

The pseudorandom number generators that we use as developers fall firmly into the first category and are perfectly suitable. Luckily for us, C++ offers a number of ways in which trivial pseudorandom numbers can be generated. Throughout the course of this book, we will use std::rand() and std::srand(), both of which standard C++ functions that are included in <cstdlib> library.

We now know that computers can't generate random numbers, and that we generate pseudorandom numbers instead. Let's have a look at why this is so.

The reason behind this is the same as the reason why two computers will reach the same output given the same input and operation; computers are deterministic. Everything that a computer produces is the result of an algorithm or equation. They are nothing more than highly sophisticated calculators. Therefore, you can't ask them to act unpredictably.

True random numbers can be generated, but you need to utilize systems outside the machine. For example, at https://www.random.org/ you can generate truly random numbers using atmospheric noise. There are other systems that are akin to this, but unless you are generating random numbers for something important such as security purposes, trivial pseudorandom number generation will suffice.

Let's start coding by writing a small program to generate some pseudorandom numbers. To do this, we will use the std::rand() function. It generates a pseudorandom integer in the range between 0 to RAND_MAX. The RAND_MAX variable is a constant defined in <cstdlib>. Its value will vary depending on the library that you are using. On a standard library implementation, it's guaranteed to be at least 32767.

You can download the code for this program from the Packt website at http://www.packtpub.com/support. It will be present in the Examples folder, and the project name is random_numbers:

// Random number generation
// This program will generate a random number each time we press enter.

#include <iostream>

using namespace std;

int main()
{
  while (true)
  {
    cout << "Press enter to generate a random number:";
    cin.get();

    // Generate a random integer.
    int randomInteger = rand();

    cout << randomInteger << endl << endl;
  }

  return 0;
}

This is a very simple console application that makes a call to std::rand() every time we press the Enter key. This returns us the pseudorandom number, and we pass it to std::cout to display it. That's how easy it is!

The previous code generated numbers between 0 and RAND_MAX. That's great, but we'll usually want more control over this in order to generate numbers within a certain range. To do this, we are going to use the modulo operator.

The modulo operator returns the remainder of the division between two numbers. So, 9 mod 2 is 1, as 2 goes into 9 four times with 1 left over. We can use this to create a range for the pseudorandom number generation. Let's generate a number between 0 and 249.

To do this, we need to make the following change:

// Generate a random integer.
//int randomInteger = rand();
int randomInteger = rand() % 250;

Run the program a few times now, and you'll see that all the results are limited to the range that we just defined. So now we can generate a number between 0 and n, but what if we don't want our range to start from 0? To do this, we need to make one more change to the line that generates a number:

// Generate a random integer.
//int randomInteger = rand() % 250;
int randomInteger = rand() % 201 + 50;

Remember that the number we used in the mod calculation will generate a number between 0 and n-1, and the number we add afterwards will increase the range by that amount. So here, we generate a number between 0 and 200 and then increase the range by 50 to get a number between 50 and 250.

Run the program and note the first five numbers that are generated. In my case, they are 91, 226, 153, 219, and 124. Now, run it again. You'll notice that something strange happens; we received the exact same numbers.

They were generated in a pseudorandom manner, right? Maybe it was just a fluke. Let's run it again and see what we get. You will get the same result again. To understand what's happening here, we need to take a look at seeds.

A seed provides a starting point for an algorithm. So, in the previous example, yes we're using complex algorithms to generate numbers, but we're kicking off the algorithm at the same point each time. No matter how complex the algorithm is, if you start at the same point, and perform the same operations, you're going to get the same results.

Imagine that we have three people, and each person is about to walk the same path by 5 steps. If they all start from the same square, they will end at the same square:

Now, in the next diagram, we give these three people unique starting positions. Even though they are doing the same actions as before, and are on the same path, their results are different because they started from different locations:

In this analogy, the path is the algorithm, and the starting square is the seed. By changing the seed we can get different results from the same actions.

You will have most likely used seeds before and not even known it. Games that procedurally generate worlds, such as Minecraft and Lego Worlds, give you the option to set a seed manually before generating a world. If your friend generates a world that looks great, they can grab their seed and give it to you. When you input that seed yourself, you kick off the algorithm at the same place that your friends did and you end up with the same worlds.

Now that we know what seeds are, let's fix the previous example so that we don't keep generating the same numbers. To do this, we will use the std::srand() function. It's similar to std::rand(), but it takes an argument. This argument is used to set the seed for an algorithm. We'll add the call to std::srand() before we enter the while loop.

The updated code should look like this:

// Random number generation
// This program will generate a random number each time we press enter.

#include <iostream>

using namespace std;

int main()
{
  // Here we will call srand() to set the seed for future rand() calls.
  srand(100);

  while (true)
  {
    cout << "Press enter to generate a random number:";
    cin.get();

    // Generate a random integer.
    int randomInteger = rand() % 201 + 50;

    cout << randomInteger << endl << endl;
  }

  return 0;
}

Now when we run this code we get different results! I got 214, 60, 239, 71, and 233. Don't worry if your numbers don't match mine exactly; they are both CPU- and vendor-specific. So, what will happen if we run the program again? We changed the seed. So we should get different numbers again, right?

Not quite. We called std::srand() and set a new seed, but each time we run the program we're setting the same seed again. We're kicking the algorithm off at the same position each time, so we're seeing the same results. What we really want to do is randomly generate a seed during runtime so that the algorithm always starts at a new position.

There are many ways to achieve this, and your use case will determine which method is suitable. For us, as game developers, something relatively trivial such as the current system time will usually suffice.

This does mean that if you run the program at the exact same time you'll get the same results, but that's almost never going to be a problem for our use. C++ provides us with a nice function to get the current time, time(), which is located in <ctime>.

Let's update the program one last time and pass time() as a parameter in std::srand() so that we generate unique numbers with every run:

// Here we will call srand() to set the seed for future rand() calls.
//srand(100);
srand(time(nullptr));

Now, every time we run the program, we get unique numbers! You may have noticed that if you run the program multiple times in succession, the first number is always very similar to the last run. That's because between the runs time doesn't change a lot. This means that the starting points are close to each other and the results reflect this.

The process of generating random numbers is a huge component in creating systems that procedurally generate game content. There are lots of ways in which random data is generated, such as noise maps and other external systems, but in this book, we'll stick to these simple C++ functions.

We want systems that are predictable enough to give us control over them as developers, but they should be dynamic enough to create variations for the player. This balance can be hard to achieve, and sometimes games get it wrong. Later in this chapter, we'll look at some of the things that you have to watch out for when incorporating procedural generation into a game project to avoid this.

Necessity, as the saying goes, is the mother of invention. As developers of today we're spoiled with the hardware that we have at our disposal. Even the most baseline machines that you'll get today will have a hard drive of 500 GB in size and up as standard. This is quite a luxury considering that just a couple of decades ago that would be MB and not GB.

Game distribution was also a very different game back then. Today, we either buy games on a physical disk, with Blu-ray disks offering a whopping 25 GB per layer, or download them off the Internet, where there are no size restrictions at all. Keeping this in mind, now consider the fact that the size of most Nintendo Entertainment System (NES) games was a mere 128 to 384 KB! These storage restrictions meant that game developers had to fit lots of content into a small space, and procedural generation was a great way to do this.

Since building large levels and storing them wasn't possible in the past, games were designed to build their levels and resources algorithmically. You'd put all the resources needed on your storage media, and have the software assemble the level at the player's end.

Hopefully now, the earlier desk analogy makes more sense. It's just like how flat-packed furniture is easier to transport, and it can then be built at home. As hardware has developed, this has become less of a problem, but it was a great solution for early developers who had storage concerns.

One of the most prominent uses of procedural generation in modern video games is the generation of game maps and terrain. The extent to which this can be used is vast, and ranges from generating simple 2D maps to full 3D worlds and terrain.

When procedurally generating 3D terrain, noise maps, such as the ones generated by Perlin noise, are used to represent random distribution by producing an image with areas of both high and low concentration. This data, the variance in concentration and intensity, can then be used in many ways. When generating a terrain, it's commonly used to determine the height at any given position.

The procedural generation of complex 3D terrain is beyond the scope of this book. However, we will generate 2D dungeons later in this book.

Traditionally, game animations are created by animators, and then exported as an animation file that is ready for use in the game. This file will store the various movements that each part of a model will go through during animation. It then gets applied to the game character during runtime. The player's current state will determine which animation should be playing. For example, when you press A to jump, the player will change to a jumping state, and the jumping animation will be triggered. This system works great, but it is very rigid. Each step, jump, and roll is identical.

However, procedural generation can be used to create real-time, dynamic animation. By taking the current position of the character's skeleton and calculating the multiple forces that are being imparted upon it, a new position can be calculated. The most prominent example of procedural animation is ragdoll physics.

Although less common than the previous examples, procedural generation is also used to create game sounds. This will commonly be in the form of manipulating existing sounds. For example, sound can be spatialized, meaning it appears to be coming from a specific position when heard by the user.

At a stretch, short, one-shot sound effects may be synthesized, but due to the little benefit that it brings as compared to the amount of work needed to implement it, it's seldom used. It's simply much easier to load premade sounds.

If your game world is hand-built, it's going to have size restrictions for a number of reasons. Every object needs to be placed manually, every texture/model needs to be handcrafted, and so on. All of this takes time and money. Even the largest handcrafted game's world sizes, such as those seen in The The Witcher 3: Wild Hunt and Grand Theft Auto V, pale in comparison to what procedurally generated worlds can achieve.

If a game utilizes procedural generation correctly, then theoretically, there is no limit to the world size. For example, No Man's Sky is a science-fiction game set in an infinite, procedurally generated galaxy. When you start to get really big maps however, hardware becomes a limiting factor. Areas that have been generated need to be saved to the disk in order to revisit them, and this quickly adds up. For example, to generate the biggest world possible in Minecraft, you will need around 409 petabytes of storage for the level data!

Making games is expensive. Really expensive. In fact, most AAA games cost tens, if not hundreds, of millions of dollars to make. With budgets that are this high, any option to save money is welcome. Procedural generation can do just that.

Let's say that we are working on a title that needs 100 brick textures. Traditionally, you'd have one of your artists create each brick. While they will have top quality, this will cost both time and money. Alternately, by utilizing procedural generation techniques, you can have an artist create a handful of resources and use them to generate however many resources you need to use.

This is just one example, and the same goes for modeling, design, and so on. There are pros and cons of using procedural generation in this way, but it's a valid option.

If your game world is handmade, the experience that players have is going to be fixed. Everyone will collect the same items, the terrain will be the same, and as a result, the overall experience will be the same. The defining feature of procedurally generated games is that experiences differ. There is a sense of unknown to the game, and every time you play, there will be something new waiting that you haven't encountered yet.

Let's continue from the last point. If a game is linear, without any procedural generation, the challenge is gone after you've played the game once. You know the plot, you know where the enemies will be, and unless it has an amazing story or mechanics, there's not much reason why you'd want to play the game again.

However, if your game utilizes procedural generation, then the challenge is fresh each time the game is run. The game is always evolving; the environments are always new. If you look at the games that have the greatest replayability, they tend to be the ones that give the player the greatest amount of control. Most of these games will utilize some form of procedural generation to do so.

As we now know, procedural generation is the creation of content through running algorithms. These algorithms can be intense and require a lot of computing power. If you develop a game that makes heavy use of procedural generation, you need to ensure that a regular consumer PC or console is able to meet its demands.

For example, if you choose to generate trees procedurally in an open world game, there's going to be a big load on the CPU and GPU whenever that area needs to be generated. Lesser PCs might not have the power to do so, and therefore, they may stutter.

Another potential drawback is the fact that worlds can feel repetitive. If you allow your game system to generate incredibly large worlds, but use few and basic algorithms to do so, you'll inevitably have a lot of repetitive areas being generated. Patterns and repeating areas will be very easy to spot, and this will diminish from your game greatly.

Computers may be faster at crunching numbers than us humans, but there's one thing that we're vastly superior at, and that's creativity. No matter how amazing the procedural algorithm is, you lose the human touch. The little changes and subtleties that a seasoned designer can bring to a project are sacrificed.

It also means that you can't guarantee the same gameplay quality to all players. Some players may generate a really great map that facilitates gameplay, while others may generate a map that actively prohibits it.

In extreme cases of the previous point, a level that is completely unplayable may be generated. The risk of this happening depends on how well your procedural content is generated, but it should always be considered.

When generating a 3D terrain map, you may accidently generate a terrain that is too high for the player to climb, or blocks off an area that needs to be accessible. The same goes for a 2D map. Later in this book we'll be generating dungeon rooms randomly. So for example, we need to ensure that each room has a valid entrance and exit.

Continuing with the previous point, procedural generation is uncertain. If the entire world around you is generated exclusively procedurally and randomly, then it makes it almost impossible to script fixed game events.

Game events are pre-scripted events, and the nature of procedural generation is to create unscripted worlds. Getting the two to work together is a tough challenge. For this reason, games tend to use a mix of procedural generation and premade game development. With this, you get the fixed game events and moments that are needed to drive a narrative, and in between all of this, you create a unique and open world for the player to explore and interact with at their own whim.

When we load the game for the first time our objects will be in fixed locations. We're going to start our efforts by fixing this, implementing what we've learned in this chapter about random number generation to spawn our objects at random locations.

At the end of this chapter there are a few optional exercises that include generating numbers within a collection of different ranges. I suggest completing them if you're not comfortable with it already, as we'll be relying on it to achieve this.

One of my personal favorite aspects of procedural generation is the creation of unique objects and items. Knowing that there is a wide variety of items in a game is awesome. Knowing that the items don't even exist yet, and that the possibilities are limitless, is even better!

We'll start simply by initializing our object's member variables randomly, and move up to giving our objects unique sprites and properties. We'll also look at creating dynamic classes that can create highly unique objects from a single base class.

It's not just the static items and resources that can be generated procedurally. To add more variance to our gameplay, we'll use some procedural techniques to create dynamic gameplay mechanics. Specifically, we'll create a system that will generate a random goal for the player, and present them with a random reward should that goal be achieved.

We'll also give our enemies some basic Artificial Intelligence (AI) in the form of A Star (A*)pathfinding, allowing them to chase a player through the level.

Towards the end of the book, once we're comfortable using Random Number Generator (RNG) with procedural systems, and with our game project, we are going to implement the defining feature of roguelikes; randomly generated dungeons.

I've mentioned a few times that procedural generation can be used to create theoretically never-ending game worlds. So, we're going to do just that. We'll implement a system where every room that we visit is generated randomly, and we'll give each floor a distinct feel using the graphics manipulation techniques we'll learn in later chapters.