Implementing a random number generator

Sep 29, 2015

Games typically have some randomness in them. The roll of dice, the deal of a hand of cards, or the selection of tiles in scrabble are all example of randomness in games. Implementing this in code can be as simple as calling the random number generator in the programming language you are using. However, when dealing with games that sync with a server and have some validation of results on the server, or that otherwise require cross-platform consistency, you’ll often want a random number generator that is repeatable, and guaranteed to be consistent across systems. In this situation, it can be a good idea to implement your own random number generator. It’s not as hard as you may think.

One of the simplest random number generator algorithms is the linear congruential generator algorithm. This algorithm uses a simple linear formula to generate values and is easily implemented in any language. The formula is simply:

x = (a*seed + c) % m

The multiplier (a), increment (c), and modulus (m) are constants that are chosen by you. Care must be taken when choosing these values. You’ll want parameters that result in a good period (eg the number of iterations before the generator repeats itself and returns to its initial seed). There are a lot of published values for these parameters. If you’re adventurous, you can also create your own. This paper describes a good criteria for choosing values and also lists a bunch of examples. This stackoverflow answer also briefly covers the criteria.

With the above formula (and a good set of parameters), you can generate a repeatable set of random numbers with a given seed. For example, in order to simulate the roll of a set of dice in Yahtzee, you would apply the formula with an initial seed and then use the generated random number as the seed to generate the next random number. Repeat until you have a random number for each of your six dice and use the modulus operator to convert those values to values ranging from 1 to 6 (ie the value shown on the dice).

In Python this formula could be written as:

import random

class RandomSequence(object):
    """Create a sequence of random independent numbers using LCG.
    """
    MODULUS = 4294967296
    MULTIPLIER = 1664525
    INCREMENT = 1013904223

    def __init__(self, seed=None):
        self.seed = random.randint(0, self.MODULUS) if seed is None else seed

    def next_seed(self):
        self.seed = (self.seed*self.MULTIPLIER + self.INCREMENT) % self.MODULUS
        return self.seed

    def next_random(self):
        return self.next_seed() / self.MODULUS

    def next_int(self, a, b):
        assert b-a
        return self.next_seed() % abs(b-a) + min(a, b)

If you require an objective-c version for your iOS game, there's an open source version on github written by Nick Lockwood.

In my upcoming multiplayer game, players compete against each other by trying to complete the same puzzle as fast as possible. The puzzles are generated randomly on the client, but I generate a seed value on the server (using the built-in Python random number generator). Each client, on both iOS and android, has a linear congruential generator that uses the seed value to generate a sequence of random numbers that is used when creating the puzzle. This way, the puzzles are guaranteed to be the same for the players. I also do some validation on the server side when a player submits their turn. The random numbers used in a player’s turn (eg a dice roll) are validated using the LGC implementation in Python.

I've been working hard to get my multiplayer game done, and I'll be announcing it here when it's done. You can also follow me on Twitter for updates. I'm @yargies.