Advertisement
Gamedev Glossary

Gamedev Glossary: Sequence Generators and Pseudorandom Number Generators

by

Procedural generation helps boost replayability by using internal rules to create parts of the game on the fly: from designing the plan of a dungeon to building a solar system. These rules are often based on a series of numbers which are then interpreted by the program to create the required content.

There are many ways to generate these numbers; in this article we'll look at Sequence Generators and Pseudorandom Number Generators, and their differences.


Sequence Generator

The first option - a Sequence Generator - is the most hardcore of the two procedures mentioned. But what is it?

A Sequence Generator is an algorithm which uses a mathematical formula to produce a sequence of numbers. As an example, we're going to look at a very simple sequence - the one I'm going to explain is a derivation of the well-known Fibonacci Sequence.

Basically the standard Fibonacci sequence always starts with 0 and 1. These numbers are then added together to give 1 - so the second and third numbers in this sequence are 1 and 1. When added together the result is 2, and this is the fourth number in the sequence. The sequence continues on like this, always adding the previous two numbers in the sequence to generate the next.

The standard Fibonacci sequence
The standard Fibonacci sequence

Implementing a Simple Sequence Generator

Programming a Sequence Generator could seem simple, especially if one is basing its foundations on the Fibonacci sequence, yet first impressions are deceiving. As an example, let's imagine that we're trying to create a two-dimensional starfield like this:

A simple starfield
A simple starfield

Looking at this starfield we can see that each star can be defined by its coordinates and its size. Taking the range of each value to be between 0 and 99, we can then divide a sequence of numbers into groups of three - interpreting each number as a star's x-coordinate, y-coordinate, or size.

Manipulating a sample sequence
Manipulating a sample sequence

If taken step-by-step, programming a Sequence Generator based on the Fibonacci Sequence to create a similar sequence isn't a difficult task.

We start off with one number (called a seed) consisting of four digits - for example 1234. The seed is then split into a pair of two-digit numbers which take the place of the 0 and 1 of the Fibonacci sequence. These numbers are then processed using a formula to produce a third number in the stream.

When building a Sequence Generator, you will probably want the generated numbers to fall in a specific range (for example 0-99). It is therefore important to truncate this number if it falls out of range. (For our example, we can just cut off the "hundreds" column.) Although this might seem insignificant, it facilitates the workflow when manipulating this sequence later on.

As this process is repeated, a string of numbers that is ready to be manipulated is created, and thus can be implemented:

Creating a sequence Creating a sequence

Unfortunately it's only after you implement the sequence as a 2D drawing that you start noticing recurring patterns. Most of the time, solving these kind of problems will result in spending long hours of trial and error testing out different algorithms.


Pseudorandom Number Generator

The second approach mentioned above is using a Pseudorandom Number Generator (PRNG). Before I explain what a PRNG is, keep in mind that the computer is a logical machine - it has to obey a certain set of rules. Therefore, nothing in a computer is truly random.

A Pseudorandom Number Generator is just an algorithm which produces a stream of (seemingly) random numbers. I say "seemingly" because a PRNG still uses pre-defined formulae to generate the numbers. This means that a PRNG is still a Sequence Generator.

The key property of a PRNG compared to other sequence generators is that it balances the number of times different numbers will appear. This process is done through complex formulae and algorithms, and means that the numbers it produces will appear just as varied as the numbers from repeated dice throws, or winning lottery numbers.

An example of a PRNG sequence
An example of a PRNG sequence

While a Sequence Generator is usually specifically-made for one problem, a PRNG is used when the generated sequence is usually discarded, or does not need to be retained.


PRNG vs Sequence Generator

A PRNG is easier to use and implement than a Sequence Generator and has various uses. Despite this, sometimes it's more sensible to go the extra mile and use a Sequence Generator. Why?

In complex systems, it's important that you make the best use of space. Using a PRNG means that, to save the details of a solar system, you would have to save the whole lengthy sequence. On the other hand, if you're using a Sequence Generator, you could simple save the initial seed and the length of the sequence. (In this case, it is crucial that the Sequence Generator produces the same sequence froma given seed.) The same can't be said about PRNGs: in general, a PRNG doesn't expose its seed, nor does it accept one. This makes replicating a PRNG sequence extremely difficult.

Sometimes, albeit rarely, a PRNG could provide you with a seemingly biased sequence (in the same way that a fair coin can occasionally land heads five times in a row). This might not be easy to detect at first glance, or when you look at the sequence as a whole. However, when you look at the produced image, you might notice clusters of stars or planets. By using a Sequence Generator, this problem can be minimized since such an algorithm is tailor-made for the problem at hand.

Another advantage, similar to the previous one, is content control. When you want to procedurally generate a far-off starfield, it's only natural that you want small stars to appear more frequently than the bigger stars. Using an unaltered PRNG, this bias isn't possible. However, by using a Sequence Generator you can provide the required bias yourself. Once again, it all boils down to the formula or formulae you decide to use, and the way you interpret the resulting string.

Whilst a PRNG could be useful, when creating a procedural generation engine it would probably be best to choose a more specific Sequence Generator. The advantages it brings with it are beneficial and ensure that the implementation has an enhanced possibility of standing out from the rest.

Related Posts