Randomization

Welp, it’s been fun, but Dark Souls III comes out this week, which means Gunmetal Arcadia Zero is paused indefinitely. (Not really but yeah but not really but yeah.)

The last few weeks’ or months’ worth of blogs have been iterative progress updates, and I’ve been itching to do an in-depth, technical, tutorial-style blog for a little while now. So today I’ll be talking about random number generation in Gunmetal Arcadia Zero. I’ve written about some of these concepts in the past, but I don’t think I’ve ever done a complete top-to-bottom review of the entire scope of this facet of the game, and certainly not since making some important changes for the vertical slice build.

Motivation

Let’s start with the obvious. Some things in this game should be random, enemy behavior and loot drops being the prime examples. But how should they be random, and how random should they be?

(As an aside, I should note that I’ll be using “random” to mean “pseudorandom” throughout this blog. I’ll leave the substitution to the reader’s mind.)

I made the decision at some point that enemy behaviors, while “random” in the sense that two instances of the same enemy may choose different actions than each other, should be consistent across each play session. That is to say, when you see a particular slime blob, it will behave exactly as it has in previous sessions, all else being equal. Enemies who react to cues from the player or their environment may diverge from normal patterns based on this input, but they will still behave consistently and reproducibly. This decision was based partly on how enemies tended to behave in classic games and partly on the assumption that it would make the game more palatable for speedrunning.

Loot drops, on the other hand, wouldn’t be very interesting if they exhibited this same consistent, reproducible behavior. These need to be more random, such that the player can’t predict what they will receive for killing an enemy or destroying an environmental object.

In both cases, however, the ability to completely save and restore the state of random number generators is important. Consider the case of an attract loop recorded from a previous game session. If loot drops changed each time the attract loop were played, the results could be disastrous. Imagine if a torch that had originally dropped  a new type of subweapon now dropped a coin, throwing the rest of the session out of whack when the player attempted to use that subweapon and failed.

So, with these use cases in mind, we want to be able to generate numbers in two ways: deterministically (consistently and reproducibly) and non-deterministically (unpredictably), and we also need to be able to serialize RNG state in both cases.

Implementation

I chose to use Mersenne twisters for random number generation in Gunmetal Arcadia Zero. I won’t go too much into the basics of how Mersenne twisters work, as that topic has been covered frequently and in greater depth than I would be capable here, but the important things to understand are:

  • A Mersenne twister must be seeded with an input number in order to produce valid results.
  • Seeding the twister with the same value will always guarantee the same results.
  • The internal state of a Mersenne twister can be saved and loaded such that a position in a “stream” of random numbers may be maintained.
  • A typical implementation of a Mersenne twister regenerates its internal representation every 624 times a random number is extracted.

The first three points are true of most random number generators; the last has some ramifications on serialization of RNG state in Gunmetal Arcadia Zero specifically. The simplest way to save and load a Mersenne twister is to copy its entire internal state to and from a file on disk. In fact, this is how my implementation worked for a while, and for an application with a single RNG (or only a few), this would be acceptable. The problem I ran into is that I create one or two Mersenne twisters for each entity in the game that deals in random numbers, including dynamically generated things like slimes that spawn from eggs. When each of these wrote its own state to file, I wound up with an unmanageable amount of file bloat on disk which would have made it difficult to port saved games from machine to machine, whether manually or via a cloud save system.

In the future, a system that aggregates all active RNGs and publishes all their internal states to a single file might be a good solution, but what I’ve chosen to do in the meantime is to serialize a minimal amount of data to the normal saved game file which can be used to restore the Mersenne twister to its previous state at the expense of some extra cycles.

As noted previously, a Mersenne twister must regenerate its internal state every 624 extractions. So if we keep track of (1) its seed, (2) the number of times we’ve regenerated the set, and (3) the current index (0-623), we can restore its previous state from scratch. In theory, doing this regeneration step this is more expensive than saving and loading the entire set of 624 values, but in practice, I rarely extract more than a handful of values from any given twister, meaning we only have to redo the initial seeding in most cases.

Generation

Now that we’ve covered the technical side of things, let’s look at the really interesting stuff, which is how we produce the seeds that are going to ultimately be responsible for the uniqueness of the random number streams.

As I’ve said, one of my goals is to allow multiple instances of the same enemy type to behave differently. Each enemy gets its own random number generator, so in order to get different results out of each, we need to seed them differently.

My solution was to lean on an existing piece of data: entity GUIDs. My editor automatically assigns a 31-bit GUID to any entity placed in the map. (The reason this is 31-bit and not 32-bit is that the high bit is reserved for GUIDs created by the game itself, with half of that space being further reserved specifically for dynamically-generated entities.)

Beyond these reserved values, my GUIDs don’t currently have any constraints, considerations, or intrinsic meaning. But they must be unique, of course, and there are any number of methods I could use to generate unique values. At the moment, I’m using the millisecond value of the system timer truncated to 31 bits, which gives me a period of twenty-four days before values start reappearing. The likelihood of a collision is therefore trivially larger than zero.

So if every entity has a unique GUID (yes, I realize that’s redundant), then I can use that GUID to seed that entity’s Mersenne twister, and each one will produce a unique random number stream. So that’s one problem solved. But now there’s the problem of things like loot drops that don’t want a completely deterministic random number stream.

Before I get into my solution for that problem — it’s going to be a long one — let’s start by observing that the system clock has historically been considered a satisfactory way to seed a random number generator to produce unpredictable results, as exemplified by the prevalence of “srand(time(NULL))” in C/C++. This operates on the assumption that the system’s clock will never be in the same state as it was on a previous run, so the results should be unlike any seen before.

Time-based random seeding

When I first encountered the need for unpredictably random loot drops, my first idea was to use the time() function to seed these entities’ random number generators. However, this quickly proved a flawed solution, as time() returns the system time in seconds, meaning that each and every entity spawned within the same second would get the same seed, and would in turn produce the same random number stream. This briefly created a bug where all the torches in a given room would drop the same item as each other.

My fix for this issue was to hash the result of time() with the entity’s GUID, producing a value that would be unique at any given time and unique per entity. (For the curious, my “hashing function” was to simply XOR these two numbers together. It seems good enough.)

That worked well enough for a while, but when I finally got around to implementing attract loops, it fell apart once again. Because the time-based seed would be produced at the moment an entity were first spawned, the results would vary depending on when the attract loop were played back. This necessitated moving away from time() to an alternative solution which would provide the same element of randomness but in a deterministic fashion.

My game session now keeps track of something I call a “fixed time seed.” This is a value that can be used in place of time() but which follows some additional rules to better serve my needs.

The fixed time seed is generated at the start of each session. At this point, it is actually just the result of time(), cached off once when starting a new game. In this manner, I can have the benefits of time-based randomness, but I can also save and restore this value in order to predictably generate the same values.

Where this gets a little tricky is in determining when — and how — to reroll this fixed time seed. Consider the case in which the player kills some enemies, breaks some torches, sees a few random loot drops, and then dies and replays the same section again. Given the same fixed time seed, these RNGs would produce the same values, and the same loot would drop on this life. That’s not what I want; loot drops should be re-randomized on each life, and the easiest way to do this is to update the fixed time seed once again to the value of time() at the start of a new life.

Attract loops foil this once again, however. I didn’t want to rule out the possibility of an attract loop that contained a death and respawn, and as before, requesting a new time() value during an attract loop would lead to bad results, so in this case, I needed a way to deterministically update the fixed time seed such that it would give me different values on the next life, but so that they would also be the same different values every time.

My solution to this was to simply increment the fixed time seed by one at the start of a new life.

That was the extent of my RNG solution for a few months, but just recently, I began to notice how strange it felt to load a saved game repeatedly and see the same loot drops every time. This was consistent with the rules I had previously established and with my initial goals for wanting saved games to be a completely accurate snapshot of the game in progress, but it didn’t feel right as a player. So as of last week, the fixed time seed now gets reset to the value of time() whenever a saved game is loaded.

Conclusion

Numbers are hard, yo.


Upcoming tasks for the week of April 11, 2016:

  • Monday: Dialog and vendor inventory pass on the entire game
  • Tuesday: Cutscene work, intro and ending
  • Wednesday: Cutscene work, intro and ending
  • Thursday: Finalize all menus and options
  • Friday: Record Ep. 34, write blog, addl. work as time allows
  • Saturday: Audio pass on the entire game
  • Sunday: Play and take notes

I had had cutscene work scheduled for last weekend, but after revisiting my schedule in light of wrapping the soundtrack and key art earlier than expected, I realized I could space my remaining tasks out a bit so I don’t have to crunch so much. So, that.