Random() Thoughts

In the interests of contributing even when not directly asking/answering a question, here’s some code I wrote because I needed an instanceable PRNG for the game I’m working on.

Basically the problem, if you want to call it that, was that the normal, built-in PRNG is global across all rand() calls (directly or indirectly) in the entire game. I needed the ability to have PRNGs that were “local” to individual things exhibiting random behavior. Think of a simple game where the player can either roll a single six-sided die or flip a single coin. The player rolls the die, gets a 5, rolls again and gets 2, rolls again and gets 6. Now the player flips the coin, gets heads. Then there’s a time warp that sends the player back to the start of the scene.

What I needed is for the behavior of the “random” bits to be the same. So the first time the player flips the coin it will come up heads again, the next three rolls of the die will come up 5, 2, and 6, and so on.

But even if you reset the global PRNG seed to the value it was at the start, if the player rolls the die (getting a 5), and then they flip the coin next (instead of rolling the die again), the PRNG will produce the same value…but instead of using it to generate a die roll, it’s going to be used for flipping the coin. Which can come up tails. Because instead of being generated by the 4th PRNG value after seeding, it gets the second. Then the second die roll is no longer necessarily 2, because it’s now using the third PRNG value instead of the second, and so on.

You can kludge this by a lot of elaborate juggling (saving and restoring) the global PRNG seed, but that’s a mess. So instead, here’s a very simple instanceable PRNG, and everything that needs to be “independently” (but deterministically) generated can get their own.

I’m putting all this stuff into a library because it involves a lot of other RNG/procgen stuff, but here’s just the “basic” PRNG stuff in a simple sample “game”:

#charset "us-ascii"
#include <adv3.h>
#include <en_us.h>

// Include BigNumber support.  This is a part of TADS3, but isn't enabled
// by default.  It's only needed for the randomBigNumber() and
// randomBigNumberNormal() functions, so if you don't need them you can
// get rid of them and not have to include bignum.h.
#include <bignum.h>

// Simple PRNG class.
// This is a TADS3 implementation of Marsaglia's xorshift algorithm.  We
// make a couple of simplifying assumptions/kludges to work around the fact
// that TADS3 doesn't have any unsigned integer types.
class PRNG: object
        _seed = nil                     // current seed
        _max = 2147483647               // max integer we can handle

        construct(seed?) { _seed = (seed ? seed : rand(_max)); }
        getSeed() { return(_seed); }
        setSeed(v) { _seed = v; }
        toRange(v, min, max) {
                min = (min ? min : 0);
                max = (max ? max : _max);
                // KLUDGE:  this produces not-quite-uniform results, but
                // it's much, much faster than any of our alternatives
                return((v % (max - min + 1)) + min);
        random(min?, max?, seed?) { return(toRange(nextVal(seed), min, max)); }
        nextVal(seed?) {
                local v;

                if(seed != nil) v = seed;
                else v = _seed;
                if(v == 0) v = 1;
                v ^= v << 13;
                v ^= v >> 17;
                v ^= v << 5;
                // KLUDGE:  if we overflow, we just take the negation
                if(v < 0) v = ~v;
                if(seed == nil) _seed = v;

// Returns a number in the given range, inclusive.
// Example:  randomInt(0, 4) will return 0, 1, 2, 3, or 4 with equal
// probability.
// A PRNG instance can optionally be specified.  If none is given, tads-gen's
// rand() will be used instead.
randomInt(min, max, prng?) {
        if(prng != nil) return(prng.random(min, max));
        return(rand(max - min + 1) + min);

// Roll n d-sided dice.
// Example:  randomDice(2, 6) is 2d6, or the results of two six-sided dice
// added together for a number between 2 and 12.
randomDice(n, d, prng?) {
        local i, v;
        for(i = 0, v = 0; i < n; i++) v += randomInt(1, d, prng);

// Return a decimal number in the given range.  If no range is given, 0 and 1
// are assumed.
// Example:  randomBigNumber(0.5, 0.75) will return a decimal number between
// 0.5 and 0.75.  randomBigNumber() will return a decimal number between 0
// and 1.0.
randomBigNumber(min?, max?, prng?) {
        local v;

        v = new BigNumber(randomInt(0, 2147483647, prng)
                / new BigNumber(2147483647));
        if((min == nil) || (max == nil)) return(v);
        min = new BigNumber(min);
        max = new BigNumber(max);
        return((v * (max - min)) + min);

// Return random values which match the given normal distribution.
// This means that, for example, ~68.2% of the returned values will
// be the given mean plus or minus sigma (the standard deviation);
// 95.4% will be the mean plus or minux two sigma;  99.6% will be the
// mean plus or minus three sigma, and so on.
randomBigNumberNormal(mean, sigma, prng?) {
        local one, u, v, x;

        mean = new BigNumber(mean);
        sigma = new BigNumber(sigma);
        one = new BigNumber(1.0);
        u = one - randomBigNumber(0, 1, prng);
        v = one - randomBigNumber(0, 1, prng);
        x = (new BigNumber(-2.0) * u.log10()).sqrt()
                * (new BigNumber(2.0) * BigNumber.getPi(10) * v).cosine();

        return(mean + (x * sigma));

// Returns a shuffled copy of the passed List.
// Uses Fischer/Yates to do the shuffling.
randomShuffle(lst, prng?) {
        local i, k, r, tmp;

        if((lst == nil) || !lst.ofKind(List)) return([]);
        r = lst.sublist(1, lst.length);
        for(i = r.length; i >= 2; i--) {
                k = randomInt(1, i, prng);
                tmp = r[i];
                r[i] = r[k];
                r[k] = tmp;

versionInfo:    GameID
        name = 'sample'
        byline = 'nobody'
        authorEmail = 'nobody <foo@bar.com>'
        desc = '[This space intentionally left blank]'
        version = '1.0'
        IFID = '12345'
gameMain:       GameMainDef
        newGame() {
                local i, prng, seed;

                prng = new PRNG;
                seed = prng.getSeed();
                "Seed = <<toString(seed)>>\n ";
                for(i = 0; i < 5; i++) {
                        "val 0/<<toString(i)>>:  <<randomInt(1, 10, prng)>>\n ";
                "<.p> ";
                for(i = 0; i < 5; i++) {
                        "val 1/<<toString(i)>>:  <<randomInt(1, 10, prng)>>\n ";
                "<.p>Native rand():\n ";
                for(i = 0; i < 5; i++) {
                        "rand() <<toString(i)>>:  <<randomInt(1, 10)>>\n ";
        showGoodbye() {}

Just offering it in case it’s useful to anyone else.


A couple notes on the above:

  • randomInt(min, max, prng) generates an integer between min and max, inclusive. The optional third argument is a PRNG instance. If omitted, TADS3’s builtin rand() implementation will be used instead.
  • randomDice(n, d, prng) rolls a d-sided die n times and returns the sum. So randomDice(2, 6) is equivalent to a D&D-ish 2d6. The third arg is again optional.
  • randomBigNumber(min, max, prng) generates a decimal number between min and max. This is much slower than random integer generation.
  • randomBigNumberNormal(mean, sigma, prng) generates random decimal values that follow a normal distribution with an average value of mean and a standard deviation of sigma. So roughly 70% of all the values will be mean +/- sigma. This is probably a little esoteric for most IF needs, but picking a number from a random distribution is often used, for example, in random walk algorithms.
  • randomShuffle(lst, prng) shuffles the list lst using the Fischer/Yates algorithm. This is the same underlying algorithm used in many places in the native TADS3 code (like in shuffling EventLists, for example) but this is version usable with our instanceable PRNGs.

The main caveats/kludges/warnings are called out in the comments in the code. Notably:

  • Overflows are handled by just taking the negation of the number. This is just a way of working around the fact that TADS doesn’t have any unsigned integer intrinsic datatypes. This slightly biases the behavior of the PRNG because it means the highest-order bits aren’t uniform.
  • Conversion of raw PRNG values is done using a method that moderately biases the behavior of the PRNG; it just takes the raw value mod the requested range, which means the uniformity of the output bits will depend on the size of the range relative to the domain of the PRNG. Simple statistical testing (not included here, but part of the larger library) shows that the result is “good enough” in that it still passes e.g. the runs test, a simple Chi square test, and so on. So the output still looks random-ish, which is all that I really demand of a PRNG for an IF game.

On the last bit, a more uniform version of PRNG.toRange() can trivially be implemented by something like:

        toRange(v, min, max) {
                min = (min ? min : 0);
                max = (max ? max : _max);
                return(((new BigNumber(v) / new BigNumber(_max))
                        * new BigNumber(max - min + 1)).getFloor() + min);

…but this is something like two orders of magnitude slower than the version as implemented.

uhm… on the timetravel without changing fate (a thing whose destroy the very core of timetravel narration, but it’s another matter) I can suggest storing the results of the first die roll, then retrieve the fateful rolls during the timetravels.

Best regard frm Italy,
dott. Piergiorgio.

That works, but the amount of stuff that needs to be stored scales with the number of values generated. That’s fine if you’re just worried about saving the state of a single die and a single coin, but if you want this to work across the entire game world, it’s very convenient to only have to save a single value for each object.

In fact for my purposes it’s even less than that: I generate a “primary” seed for each “day”, and then deterministically generate a seed for each object based on its properties (think of something like objSeed = mainSeed ^ crc32(obj);), so it’s got a very small resource footprint regardless of how complex the game state ends up being.