Pseudo randomness is a remarkable concept—one that we rarely put a lot of thought into how it actually works. So, the purpose of this blog post is to detail everything that went into our custom pseudo random generation class and to explain exactly how it works.

When we talk about random generation, we aren’t just talking about generating numbers from 0 to 1 or even from -2 to 17. We’re talking about more complex generation like points on the surface of a sphere, points within the area of a circle/disc, and more.

Up until very recently, our game engine used the random functionality available in GLM whenever we needed any randomness. This worked well for ages, but we recently realized that Spacegame actually has a few extra requirements on random number generation that GLM can’t give us.

- We need our random number generation to be predictable.
- We need to maintain and advance discrete random generation states.
- We need strong performance!

Let’s take a look at why we need these guarantees, why GLM can’t provide them, and how our new random generation class provides them.

For a multiplayer game with random elements, there are two ways to keep everything in sync across the server and clients.

- Do random generation on the server and transfer everything across to clients.
- Do random generation on the server and clients, having the server transfer the random seed across to clients.

Option 1 is kind of a non-starter as the complexity and bandwidth required to do this increases linearly as the number of things we’re generating increases, so option 2 is the most optimal for us in every way. However, this comes with the caveat that the random generation algorithm we’re using has to be identical and consistent across whatever platform, computer, etc, the game is running on.

GLM’s random generation functions happen to use the C `rand`

function, which gives us absolutely zero guarantees about what algorithm is used or anything like that. We thought about forking GLM and stripping out the `rand`

stuff, replacing it with custom code, but that’s too much work and too high maintenance to update our fork from upstream.

What we decided on was to write a completely new `random`

class for our game engine, based around C++’s random engine classes—in particular, one of linear congruential, Mersenne twister, and subtract-with-carry. Currently we’re using Mersenne twister but we’re pretty confident that we’ll be able to use subtract-with-carry for greater performance without a noticeable loss in quality of randomness. Either way, all of these engine have one thing in common—they’re all well-defined in how their algorithm should be written. This means we can use them across different platforms, be it Windows, macOS, Steam OS + Linux, BBC Micro(?), etc, and they’ll always dump out the same result given the same random seed.

When a Spacegame client connects to a server, we need the server to transfer the current state of the random engine back across to the client so that we can generate and display stuff based on what state the server is currently in. Combining this with the requirement to randomly generate client-side objects at, say, the main menu—or even generating random normals for disparate points in 3D space—we need to be able to maintain separate random contexts, each needing to be able to advance its state independently of the others.

As I mentioned, GLM uses the C `rand`

function which, unfortunately, does the complete opposite of what we need here. C maintains a global random state initially seeded by the `srand`

function, and calling `rand`

advances that state, whilst also rendering us completely unable to save/restore the current random state (which I briefly considered as a way of emulating multiple random engine contexts for GLM).

Another advantage of writing a `random`

class for our game engine—especially as it uses the C++ random engine classes—is that it acts as an entirely self-contained object, allowing us to create and advance as many of them as we want, all independently of each other. We can even throw them in a special component class and associate random engines with specific objects.

So, GLM is pretty performant in general. However, when I was going through its code to try and figure out how it does random generation of points within sphere volumes and stuff like that, I discovered something quite interesting. To generate a point within a sphere volume, GLM just generates a random point between (-radius, -radius, -radius) and (radius, radius, radius). If the magnitude of that point vector is greater than radius, then it loops and does it again, and in theory it would keep looping indefinitely while the point falls outside of the sphere volume.

I was pretty ~~stubborn~~ determined to make this work without doing what feels like a horrible hack and avoiding doing the proper mathematical research on how to do this properly. After several iterations on this problem, I managed to come up with a really nice solution.

- Generate a random point vector magnitude between 0 and radius. This gives us the distance from the center to the randomly generated point in the sphere volume.
- Do a cube root on our magnitude. This counteracts a bias towards the center of the sphere that results from the distance between units of angles increasing as we get further away from the center of the sphere.
- Generate a random yaw angle between 0 and 2π. Yaw is the left/right rotation around the Y (up) axis, so we want any yaw angle in the full circle of rotation.
- Generate a random pitch angle between -1 and 1. We want to rotate from looking down to looking up, so that should be in the range -π/2 to π/2. However…
- Take the arc sine of our random pitch angle. For an input range of -1 to 1, this gives us an effective range of -π/2 to π/2. Why don’t we just generate a random pitch in this range to begin with? Because there’s yet another bias relationship between yaw and pitch that we need to counteract in order to achieve uniformity. Think of it like this—as the pitch moves up/down (further away from the forward resting pitch), the distance between each unit of yaw
*decreases*, so there’s a bias towards the poles of our sphere.

So, this covers most of the work we’ve done on our engine’s custom random class. There are other subtleties like something as ‘simple’ as converting a uniformly distributed integer to a uniformly distributed floating point value, but those are probably a bit outside of the scope of this article ~~and they’re also horrible hacks :D~~

Anyway, thanks for reading through to the end. I hope this at least provided some insight into some of the problems we face on a weekly basis throughout the development of Spacegame and its engine. Until next time, see you later!

⚡ Shockk, Lead Programmer