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
  • Code
    Web Development
    Test Code Coverage: From Myth to RealityXdebug wide retina preview
    Learn the myths about test code coverage and how to use it to analyze how much of your production code has been tested.Read More…
  • Code
    Web Development
    Refactoring Legacy Code: Part 1 - The Golden MasterRefactoring wide retina preview
    Learn techniques for how to deal with complex and complicated unknown legacy code, how to understand it, and finally writing the Golden Master tests for future changes.Read More…
  • Code
    ASP.NET
    Preventing Code InjectionCsrf dotnet retina preview
    Often, websites seem to exist primarily to put something into a database in order to pull it out later. While other database methods, such as NoSQL, have gained popularity in recent years, data for many websites still resides in the traditional SQL database. This data often consists of valuable personal information such as credit card numbers and other personal information of interest to identity thieves and criminals. Hackers therefore always look to get this data. One of the most common targets of these attacks is the SQL databases that lie behind many web applications through a process of SQL Injection.Read More…
  • Game Development
    Implementation
    Bake Your Own 3D Dungeons With Procedural RecipesProcedural content generation 3d dungeon maps 400px
    In this tutorial, you will learn how to build complex dungeons from prefabricated parts, unconstrained to 2D or 3D grids. Your players will never run out of dungeons to explore, your artists will appreciate the creative freedom, and your game will have better replayability.Read More…
  • Photography
    Shooting
    Creating a Starlight Time Lapse VideoStarlapse ss prelg
    In this tutorial, we are going to take a look at how to shoot and process a time lapse video of the stars. As the earth rotates, the stars appear to move across the sky during the night, but they move so slowly that the only way to really appreciate this phenomenon is through time lapse footage. We'll cover finding a location, choosing your gear, setting up your camera and doing the post-production.Read More…
  • Game Development
    Implementation
    Coding a Custom Sequence Generator to Render a StarscapeSequence generator starscape hires
    In my previous article, I explained the difference between a pseudorandom number generator and a sequence generator, and examined the advantages a sequence generator has over a PRNG. In this tutorial we'll code a fairly simple sequence generator. It generates a string of numbers, manipulates and interprets this sequence, and then uses it to draw a very simple starscape.Read More…