GameMaker: Custom pseudorandom number generators!

I wrote a bunch of PRNGs for GameMaker!

This is a large-ish post about what these are, how they work, when you might want to use them, and performance comparisons.

What's a PRNG

Most random number generators that you see on computers are pseudorandom number generators.

These are algorithms that output random-looking numbers based on one or other form of initial seed or state. Same input means same outputs!

Typically each iteration the generator will modify its internal state and return a value.

For example, a tiny, pitiful implementation of Lehmer random number generator might look something like this:

newState = (oldState * 7) % 11;

Given an initial state/seed of 3, this would output

( 3 * 7) % 11 = 21 % 11 = 10
(10 * 7) % 11 = 70 % 11 = 4
( 4 * 7) % 11 = 28 % 11 = 6
( 6 * 7) % 11 = 42 % 11 = 9
( 9 * 7) % 11 = 63 % 11 = 8
( 8 * 7) % 11 = 56 % 11 = 1
( 1 * 7) % 11 =  7 % 11 = 7
( 7 * 7) % 11 = 49 % 11 = 5
( 5 * 7) % 11 = 35 % 11 = 2
( 2 * 7) % 11 = 14 % 11 = 3
( 3 * 7) % 11 = 21 % 11 = 10
...

As you can see, the algorithm traverses all of its 10 possible states in a shuffled order before it will start repeating the values.

A "real" generator can be not unlike this one, but with larger parameters like 2 147 483 647 for modulo and 48 271 for multiplier (more on this later).

Uses

These are some of the things that a custom generator can be good for.

Separating generators

Suppose you have your big dragon boss or anything.

GameMaker's built-in random number generator has reasonably uniform distribution, so if your boss has 4 attacks, picking a random one with irandom or choose will have each occur just about 1/4 of the time, on average.

But, if you also call the random number functions between these, such as to give the player/boss attacks a little spread or spawn particles, you are using up the generator outputs and the results might not no longer be so uniform.

By giving the boss a "personal" random number generator, you can ensure that things stay fairer on average.

Another layer of defense with or without a "personal" RNG is to check that an action has already happened too many times in a row and re-roll if it's so. The game has to feel fair, not be fair.

A different approach to this specific scenario is to make a shuffled list of possible actions and re-shuffle it whenever you reach the end of it. This, however, can look a little too uniform as actions will always happen 0 ... 2N-2 steps apart and will never happen more than twice in a row.

Bonus: Nuclear Throne trivia

When I first started working on widescreen support (now in open beta!), I have noticed something peculiar: depending on your aspect ratio, the levels would generate differently, but consistently for each ratio.

Levels in Nuclear Throne generate over multiple frames and the player gets to see this kind of screen while the generator is busy placing everything:

Here you can see a HUD, a bunch of stats, and a Cool Swirling Portal in the background. And that portal was the reason why the level generation would vary!

See, the portal's curvature is represented by series of instances with position/rotation/radius that are destroyed when they're outside the screen. And the larger the screen, the later these get destroyed!

By giving the portal effects a separate RNG the level generation was no longer reliant on aspect ratio.

"Save scumming"

If your game involves chance actions and allows to save/load the game before performing such actions, players will inevitably figure out that they can save and re-load the game to re-try the roll until they get what they want.

GameMaker does not currently allow to save/load state of the built-in random generator (and likely won't in the near future), but with a custom generator, you could save its state along with the game and load it back so that performing the same action after loading the game will always yield the same result.

Rollback

If you are doing rollback and using RNG functions, it is nice to be able to save/load RNG state so that you can replay the frame(s) with the same RNG outputs.

Force-setting the seed every frame is an option, but that leads us to...

What's wrong with random_set_seed

People regularly try to solve any of above problems by calling random_set_seed before each PRNG call.

That is not a good idea, but you probably wouldn't believe the extent of it. Let me show you:

I made this little app (called prng_distro_test in the GitHub repository) that picks an n based on window size, does n * 1000 calls to irandom(n - 1), and displays the results as a grid of squares where the brightness indicates how often each number was returned relative to how often it should (ideally) be returned.

If we set the PRNG seed once or let GM set it, value distribution looks like this:

Pretty smooth, right? Just about 12% variation.

And here's what happens if you call random_set_seed before each irandom:

The results are visibly less distributed - the picture looks much noisier overall, some numbers were returned 3x more often than they should have been, and there are even a few numbers that weren't returned once across ten million calls!

There are two parts to why this happens:

PRNGs offer adequate distribution over a number of calls on any valid seed, but they cannot promise anything for doing a couple calls on arbitrary seeds.
GameMaker's random_set_seed uses a hash function.
Its job is to produce sufficiently different generator states for any X and X+1, not to produce seeds that create any specific distribution on first PRNG use.

The situation can be improved by generating a good bunch (at least 100, preferably 1000 or more) values from the same seed at a time and using these up until you run out of them.

However, if you need a separate generator or to save/load generator state, you should probably be doing that instead of trying to stick adhesive tape on the built-in generator.

... and random_get_seed

You've probably seen people do something like this:

var prevSeed = random_get_seed();
random_set_seed(...);
...

random_set_seed(prevSeed);

So we store the current seed, do some stuff, and then restore it, right?

But the function doesn't work like that - it returns the generator's seed from the last random_set_seed or randomize call, not the generator's state. And to "roll back" the generator, you need the state.

If you were to do something like this:

random_set_seed(1234);
repeat (3) show_debug_message("pre " + string(irandom(1000)));
//
var prevSeed = random_get_seed();
random_set_seed(5678);
show_debug_message("change " + string(irandom(1000)));
random_set_seed(prevSeed);
//
repeat (3) show_debug_message("post " + string(irandom(1000)));

The output would be

pre 320
pre 806
pre 377
change 267
post 320
post 806
post 377

because you're not restoring the generator's state, you're restarting the generator.

With that out of the way, the algorithms!

Algorithms

I have implemented a few of these in my library for a good sample.

Here, result is a value between 0 (inclusive) and 1 (exclusive).
Some generators might never return an actual 0, but you probably shouldn't rely on a 1:2³¹ (or rarer) event anyway.

MINSTD

This is a so-called Lehmer random number generator with modulo of 2147483647 and multiplier of 48271. The code's just this:

state = (state * 48271) % 2147483647;
result = state / 2147483647;

It's a dead-simple generator that's commonly used for actions that happen a lot, though I think its most important property is that it's hard to mess this up: you can do this with either integers and floats, signed or unsigned - so long as it's a 64-bit number, it'll work fine.

The state should be initialized with a value between 1 (inc.) and 2147483646 (inc.).

random_r

I'm not sure if there's a "proper name" for this one, but it's a linear congruential generator that's primarily known for being the TYPE_0 generator in GLIBC/GCC. The code goes like this:

state = (state * 1103515245 + 12345) & 0x7fff_ffff;
result = state / 2147483648; // <- that's 0x8000_0000

You might think that it's hard to mess this one up, but that's wrong! The number is just about big enough that if state is a real (rather than an integer), you'll lose precision bits on some multiplications and your generator will loop weirdly.

Also I found a YYC/VM inconsistency while implementing this one.

Xorshift (64-bit)

This one's all bit operations, no multiplications!

There are over two thousand possible set of parameters/order of operations for the 64-bit version, but I wasn't not feeling adventurous so I used the one that was tested the most.

Adapting the code straight from the Wikipedia article, you might think that it should look something like this:

state ^= state << 13;
state ^= state >> 7;
state ^= state << 17;
result = state / 18446744073709551616.0; // <- that's 2^64

And that should work, right?

But no. GameMaker's 64-bit integers are signed, so your output is in -0.5 .. 0.5 range.

It might be tempting to add 0.5 to result and call it a day, but that too would be wrong.

The reason for that is that when you bit-shift a negative number to the right (in GM or in general), the sign bit pads out. So the following

state = 0x8000_0000_0000_0000;
show_debug_message(ptr(state >> 7));

would show not 0100000000000000 as one might expect, but FF00000000000000.
And that's pretty bad for the generator!

The best thing I could up quickly come with is this:

state ^= ((state & $7fff_ffff_ffff_ffff) >> 7) | ((state < 0) * $0100_0000_0000_0000);

So we're cutting off the sign bit and we're putting back what would be the sign bit shifted by 7 to the right (if it was on).

And if we'll have to remove the sign anyway, might as well take the portion that actually fits in a real number:

result = (state & 0x1F_FFFF_FFFF_FFFF) / 9007199254740992.0; // <- that's 0x20_0000_0000_0000

WELL512

This is the PRNG that GameMaker itself uses!

Standing for Well Equidistributed Long-period Linear, it's a RNG with state consisting of an index and 16 unsigned 32-bit numbers. Allegedly it's all-around pretty good.

This is another one where the code almost works if you copy-pasted it:

var a, b, c, d; // originally `unsigned long`
a = state[index];
c = state[(index + 13) & 15];
b = a ^ c ^ (a << 16) ^ (c << 15);
c = state[(index + 9) & 15];
c ^= (c >> 11);
a = b ^ c;
state[index] = a;
d = a ^ ((a << 5) & 0xDA442D24);
index = (index + 15) & 15;
a = state[index];
a = a ^ b ^ d ^ (a << 2) ^ (b << 18) ^ (c << 28);
state[index] = a;
result = a;

but you have to add a & 0xFFFF_FFFF to each array write to keep numbers within the unsigned 32-bit integer range. And then random_set_seed works very much like

var s = seed;
for (var i = 0; i < 16; i++) {
    s = ((s * 214013) + 2531011) >> 16;
    state[i] = s;
}
index = 0;

but you'll need to apply & 0xFFFF_FFFF after multiplication.

Tests

Starting with some notes:

I have implemented each of these generators in Haxe➜GML and as a C++ DLL.

A DLL is advantageous for some of these, but more importantly offers a way to verify that the GML version works correctly in arbitrary scenarios by calling the same thing from GML/C++ versions.
For your uses you would be picking one or the other, depending on which platform(s) you target.

The test cases found below are the following:

Built-in: GameMaker's built-in WELL512 generator.
GML, struct: RNG state is stored in a constructor with methods, like so:
```
var rng = new WELL512();
rng.setSeed(100);
var num = rng.float(4);
```
This is what you would usually want for multiple generators.
GML, array: RNG state is stored inside an array, like so:
```
var rng = well512_create();
well512_set_seed(rng, 100);
var num = well512_float(rng, 4);
```
Honestly I was expecting a larger boost given that looking up things in an array is a much simpler operation than pulling out items from a struct's hashtable.
GML, global: RNG state is stored in global variables, so you get
```
well512_set_seed(100);
var num = well512_float(4);
```
This is always faster and especially faster on YYC.
C++, array: RNG references are tiny arrays.
These consist of a "what is this" tag and a pointer to a C++ structure.
The functions verify that the structure exist and call the underlying C++ function.
Same APIs as "GML, array"!
C++, struct: RNG references are structs with methods.
Had to write a new code generator just for this!
Good results though! Same APIs as "GML, struct".
C++, raw pointer: you can grab a C++ pointer from a struct/array and call the underlying function yourself. This is as fast as it gets for these.
But be careful! If you use a pointer a wrong/non-existing thing, your game will crash.

Benchmarking is done using Dragonite's GMBenchmark.
Graphs show relative time so lower is better.

WELL512

Let's start with the interesting question: how close can you get to the built-in RNG?

On VM, pretty close!

On YYC, not very close...

But that's because the built-in function call is very fast! It gets special treatment so random(1234) generates the same code as if you called the underlying function yourself in C++.

MINSTD

This generator is much simpler so it manages to beat some of the extension calls even on VM:

And on YYC, a global version almost beats the C++ raw pointer version!

You can squeeze a little more performance out of it by turning the generator into a set of macros:

Here I'm also testing a script that modifies a self.state variable with a forceinline tag, but that is not as efficient as doing this during a GML build with a macro.

random_r

Largely similar - after all, it's only one more operation per call than MINSTD.

For lack of a better name, I'm calling it Rand0 here.

Xorshift

This one's slightly more expensive for VM, but not as expensive as WELL512!

But YYC performs much better!

The generated code doesn't seem to include any "special sauce" so without delving into disassembly I take it that the C++ compiler figures out that the function is just wiggling an int64 and skips the type checks.

Turning this into a set of macros makes it 3 times faster than calling the same code in a DLL:

Says something about the cost of external calls, doesn't it?

Oh, and also I found another runtime inconsistency while doing this! I checked and apparently it has been around since GM:S, so this feels like taking a stroll through a forest and stepping on a rake that someone forgot there years ago.

For GML implementations, global/single-instance versions are always faster than multi-instance struct/array ones and should be preferred if you need a fixed number of additional PRNGs.
If you are slightly concerned about performance,
- Xorshift is the best choice on YYC.
  If you test in VM on Windows during development, you can make the game instantiate the GML Xorshift constructor on YYC and the C++ Xorshift constructor on VM.
- MINSTD and random_r are good choices for VM-only games.
  If you only target Windows, you can use the C++ extension instead.
If you need to squeeze every last bit of performance out of a PRNG,
- Macro-based Xorshift is the absolute winner for YYC.
- Macro-based MINSTD is good for games that are tested on both YYC and VM.
  (when ran in VM, it's only ~15% slower than a C++ extension call)
WELL512 is slightly slower when running in GML, but has a much longer period for use cases where that matters.

Downloads

And that's about it!

You can grab the extension on itch.io or build it yourself from the source code.

See you next time

YellowAfterlife

GameMaker: Custom pseudorandom number generators!

What's a PRNG

Uses

Separating generators

Bonus: Nuclear Throne trivia

"Save scumming"

Rollback

What's wrong with random_set_seed

... and random_get_seed

Algorithms

MINSTD

random_r

Xorshift (64-bit)

WELL512

Tests

WELL512

MINSTD

random_r

Xorshift

Tests, part 2

C++

GML, structs

GML, global

Conclusions

Downloads

Related posts:

Leave a Reply Cancel reply