Games can benefit from procedural generation greatly. It can provide a game with many hours of (re)playability without the effort of designing new content for the game. There are several games that embrace procedural generation and incorporate it as main mechanic. Notable examples are Binding of Isaac and Faster Than Light. These examples however can benefit from the fact that only at a discrete number of points, (randomised) decisions have to be made. In action games like Roche Fusion, the player has to be continuously challenged by a procedural and adaptive algorithm. In this post I will briefly look into procedural generation techniques, and discuss how these can be generalised to be applicable in a continuous game or application.

## The discrete case

For the purpose of this post we will look at an abstract game: the player is continuously challenged by waves of enemies. We can have different kind of enemies. Each of them is assigned a certain value. Enemies that are more difficult to deal with (e.g. have more health, do more damage, etc.) will be assigned a higher value.

In our simplified game the enemies will come in waves that are increasingly more difficult. This translates to: the sum of the values of the enemies is a monotonically increasing function w.r.t. the wave number.

To create a simple procedural generator, we can decide on the desired total value of enemies per wave. Then for each wave we select a random set of enemies to roughly add up to this desired value. Trying to find a set of enemies that adds up to this number exactly is an NP-hard problem, so introducing a heuristic is generally a good idea.

A simple way of selecting enemies given a value is choosing the type of enemy and keep adding one enemy at a time until we reach the value we have already decided upon. If you want more types of enemies, we can set an upper bound on the amount of enemies of the same type based on wave number, and switch to another type when that bound is reached. There are many ways of doing this, and it depends on the circumstances which solution works best.

## The continuous case

Let’s take our abstract game and change it to not have fixed waves. We just want to send enemies to the player. We will start with our solution to the discrete procedural wave generation and expand from there.

First we have to look at the value. Instead of using up a certain amount of credits at the start of every wave, we continuously generate credits. The growth rate of these credits will increase over time, making the game gradually more difficult. Whenever we now decide to generate a wave of enemies we can just take the currently acquired credits, and proceed as before.

This reduces the problem to finding the right moment to generate these waves. We could for example take a fixed timespan between wave generation. This would give us an algorithm that is equivalent to the discrete algorithm we discussed before, as we could pre-calculate the values we would have at every point of wave generation easily.

A second solution is to always spawn an enemy whenever we have enough credit to do so. This also is not a very interesting choice, as it will only spawn the enemy (or enemies) with the lowest value.

Under most circumstances, we will want a mix between easy and more difficult waves. As we want the difficulty to change over the course of the game, we can keep a window of minimum and maximum values of a wave. This window would slowly move towards higher values, causing the waves to become more difficult on average.

This window can be used to not pick a specific time to execute the next wave, but to decide on a credit threshold at which the next wave will be generated. This means that after every wave we already pick the cost of the next wave from the current window, and wait until the current amount of credits passes that cost to execute the next wave.

The values of the lower and upper bound of the window can be chosen depending on the desired result: it is both possible to spawn single enemies and large waves of enemies by tweaking the parameters. Fixing the lower bound will also cause an interesting effect: very easy waves still occur late in the game, but as the player gets further in the game, these easy waves will follow each other more quickly, and occur less often as the probability that we choose a wave cost that fits with an easy wave becomes smaller as the window grows.

We can also approach the decision about when the next wave should be generated differently: instead of taking the credits as basis, we can also use a time window. This means that we pick a random amount of time between the current wave and the next wave. If we want waves to follow each other more quickly, we can alter the time window to achieve that over the course of the game. This solution is equivalent to the solution described above, given the right parameters, but is based on the time rather than the credits.

## In debt

There is one major flaw in selecting the cost for the next wave from a window. If we generate a particularly difficult wave, it is likely that the player will require more time to deal with this wave, and we want the gap between this wave and the next to be longer. Analogously, the amount of time after an easy wave should be relatively short to keep the game challenging.

The solution described does not achieve this. Instead there will be a longer pause before large waves and shorter pauses before small waves, as the following image shows.

This means that it is entirely possible that nothing happens for a long while, then a very difficult wave spawns, quickly followed by another easy wave.

Under most circumstances this behaviour is not desired. This is why we will take a slightly less intuitive approach to generating waves. Where we previously assumed the cost of the wave was given at the time we generated a wave, we will now assume that only the time at which a wave is generated is given.

We will still assume the that we have a credit balance. Instead of saving credits and then generating a wave we will generate a wave every time this balance becomes positive. The cost of this wave will be subtracted from our balance, leaving us with a negative balance, which will slowly regenerate.

The previously discussed use of a window of possible wave costs can still be applied to decide the actual cost of the wave.

By using a negative credit balance instead of a positive balance we create the desired effect in pauses between waves, as can be seen in the image below. If we generated a difficult wave, the balance will take a longer time to reach a positive balance again, creating the pause we wanted.

## Final words

There is no one solution for procedural generation. Different types of games benefit from a different approach to the subject. The solutions presented in this post will probably not apply to every project, but hopefully some concepts presented are considered useful in other solutions and will be applied in a different context.

Please let me know if you used any of the presented ideas for your own tailored generation algorithm. I am always interested to hear how other people approach the subject. Of course, if you have any questions, let me know in the comments or drop me an email.

## Place comment