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.
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.
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.
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