Know your Randomizer

While working on the particle effects for the lava, one of the Terrain Features of the Fire Level, I was faced with an odd problem that, at first, I attributed to the physical engine that manages the particles’ behavior: the particles were lining up on the screen, always in the same way.

Lapilli comparison

What was happening (left) vs what I wanted (right)

It took me some time, but I finally realized what the problem was: the Random Number Generator (RNG).

Strange, uh? Actually, it is quite reasonable if you know how RNGs work and I believe that if you are working with procedural generation it pays to know what is happening behind the curtains, maybe even implement your own RNG as a learning experience.

First thing to know is that there are no software that generates random numbers. Second, also generating truly random numbers using physical props is exceedingly difficult. If you want to figure exactly why I suggest a couple of videos from two of my favorite youtube channels that did a joint dissertation about randomness: vsource and veritasium. Yeah… I am a big-time science geek.

When speaking about computer generated numbers the technically correct description is Pseudo-random Generation, meaning that the sequence of generated numbers seems aleatory but it is actually a pattern, defined by mathematical rules.

There are a lot of RNG algorithms out there. I will use one of the most simple to discuss the main concepts behind them: the Linear Congruential Generator. The algorithm for the LCG works like this:

x(n+1) = (a * x(n) + c) modulo M

meaning that the next number that will be generated, x(n+1), can be calculated from the previous, x(n), using that formula above. As you can see there is no randomness here, it is as deterministic as any other mathematical equation. The trick for making it look random is to select the various coefficients (a, c and M) in a specific way.

The algorithm above also imply that there is a x(0), a starting point of the sequence, what is called a Seed. After you set the Seed the sequence of generated numbers will be the same. The second or millionth number starting from that Seed will always be the same! (And each number in the sequence can be, in itself, a Seed that will generate the same sequence)

For procedural generation it means that you will always generate the the same levels and the same loot. It also means that you will always make that “critical hit” on your forth attack and so on. A trick that is used to get different sequences each time you run the game is to have the Seed determined at startup by the system clock. This assures that every time you start the game the Seed will be different than the previous (unless you start N games at the exact same time, to the millisecond).

You may already have guessed what was my problem with the lava. C# offers a RNG in its standard library as an instanceable object, that automatically uses the system clock as Seed. Each component of the Particles Emitter was instancing its own RNG object, and the process was so quick that all of them were using the same Seed thus generating the same outcomes!

Of course that was just bad design from my part, but as a placeholder it was good enough, and it was convenient. Now I have added the random generation to the Singleton that manages the whole “game simulation” and the particles started behaving as expected.

I believe that there are several lessons to be learned here. One is that it always pays to know what you are doing. Another is that bad design is bad at any stage of the development!

Thanks for reading.

Advertisements

4 thoughts on “Know your Randomizer

    • So true! But these surprises are a great way to learn or to remind. And sometimes it’s just nice to learn something for a second time 😀
      Thanks for your comment!

    • Very nice, clean and compact, thanks for sharing! I am actually not 100% sure what algorithm is used by C# standard library but from what I know it is not of very high quality, so much that there are two different ones, the second to be used with cryptography.
      For our purposes it should be more than good enough, but I love these things so I may try my own implementation for the final release.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s