Repeatable Random Numbers with xorshift+ (JS)

Like most languages, JavaScript has a random number generator: Math.random(). It’s not the best, but it’s good enough for many purposes, including some we’ve seen before. Like the RNGs of most languages, though, Math.random() has its drawbacks. Of these drawbacks, one is very important for game developers: there’s no way to seed! Why is this bad? That cuts to the very heart of random number generation on computers.

True randomness is hard to come by. On a computer, you have a few ways of creating it, such as noise circuits or measurements of user input. This randomness (entropy) is then converted by code into something usable, such as numbers or bits. On Linux and similar systems, there is a special file, /dev/random, that provides access to the random data. Some programming languages then allow developers to use the data through mechanisms like C++’s std::random_device.

All well and good, right? As long as your source has enough randomness, you can generate all the numbers you need. But, contrary to thermodynamics, a computer’s entropy can run out. When that happens, /dev/random stops working, waiting until it can conjure up enough random bits to meet your needs. Other systems fare no better.

Fortunately for us, games don’t often need true random numbers for gameplay. (Authentication and encryption are a different story.) So we can get away with something that only looks random. That’s good for us, because there are plenty of algorithms out there that can make a convincing string of numbers, including Math.random(). Technically, they aren’t “true” random numbers, and they all have a weakness that can allow someone with enough data to guess the next numbers in the sequence. But that very predictability comes in handy for game development. Starting from a little bit of data (from one number to a few, depending on the algorithm used), we get a whole set of numbers, billions of them or more. That starting data is the seed.

Most languages that I’ve used allow you to set the seed on the RNG. C, for example, has the srand() function, while Python provides random.seed(). But JavaScript doesn’t have this. Instead, the RNG is seeded for you when your program/app/page loads, and it will be different every time. Usually, that’s not a problem.

Sometimes, though, you need the predictable sequence that comes from using a seed. Procedural generation is one notable example. Look at Minecraft: a whole world can be created from a simple string of text. Obviously, there’s randomness injected in the process, but it’s made on-demand. Think how hard it would be to store the whole world after creating it. But, if you only had JavaScript’s RNG, you wouldn’t have much of a choice.

There are better RNG implementations out there. Indeed, many have written JS versions of them. Here’s my attempt at the popular algorithm known as xorshift+.

module.exports = (function() {
    // xorshift128+ requires 128 bits of state (we'll seed later)
    var state = new Uint32Array(4);

    // Scaling factor (2^32) to convert Math.random floats into integers
    var MAXINT_PLUS_1 = Math.pow(2,32)

    // Pre-fill the state array (can later be seeded)
    // This is required because xorshift can't have state of all zero
    for (var i = 0; i < state.length; i++) {
        state[i] = Math.random() * MAXINT_PLUS_1;
    }

    // A saved random number, since we're returning 32-bit numbers
    var saved;

    return {
        // Seeds the internal RNG.
        seed: function(s) {
            if (s === 0 || s == null) {
                // Can't use a zero seed (maybe throw an exception?)
                return;
            }

            // TODO Handle various types of arguments (just numbers/arrays for now)
            if (typeof s === 'number') {
                // Use only the lowest 32 bits right now
                state[0] = s >>> 0;
            } else if (s.constructor && s.constructor.name === 'Uint32Array') {
                for (var i = 0; i < state.length; i++) {
                    if (s[i] !== undefined) {
                        state[i] = s[i];
                    } else {
                        state[i] = 0;
                    }
                }
            }
        },

        // Returns a random float between 0 and 1 (exclusive),
        // with 32 bits of precision.
        random: function() {
            // If we already have a saved number, return it,
            // also clearing it for later use.
            if (saved != null) {
                var temp = saved;
                saved = null;
                return temp / MAXINT_PLUS_1;
            }

            // x = s[0]
            var x = new Uint32Array(2);
            x[0] = state[0];
            x[1] = state[1];

            // y = s[1]
            var y = new Uint32Array(2);
            y[0] = state[2];
            y[1] = state[3];

            // s[0] = y
            state[0] = y[0];
            state[1] = y[1];

            // (a): x ^= x << 23
            var xl23 = new Uint32Array(2);
            xl23[0] = x[0] << 23;
            xl23[1] = (x[1] << 23) & (x[0] >> 11);
            x[0] ^= xl23[0];
            x[1] ^= xl23[1];

            // (b): x ^= x >> 17
            var xr17 = new Uint32Array(2);
            xr17[1] = x[1] >>> 17;
            xr17[0] = (x[0] >>> 17) & (x[1] << 19);
            x[0] ^= xr17[0];
            x[1] ^= xr17[1];

            // (c): x ^= y ^ (y >> 26)
            var yr26 = new Uint32Array(2);
            yr26[1] = y[1] >>> 26;
            yr26[0] = (y[0] >>> 26) & (y[1] << 6);
            x[0] ^= y[0] ^ yr26[0];
            x[1] ^= y[1] ^ yr26[1];

            // s[1] = x
            state[2] = x[0];
            state[3] = x[1];

            // return x + y
            var retval = new Uint32Array(2);
            retval[0] = x[0] + y[0];
            retval[1] = x[1] + y[1] + (retval[0] < x[0]);
            saved = retval[1];
            return retval[0] / MAXINT_PLUS_1;
        }
    };
})();

I’ve written it as a Node.js module, but you can easily adapt it to a browser environment by changing module.exports on line 1 to window.xorshift or whatever you like. Whether it’s attached to the global window (browser) or loaded with require() (Node), the function creates an object with two methods: random() and seed(), both of which are explained below.

This isn’t a perfect implementation, and it does have a limitation that the original doesn’t have. This is because of JavaScript’s number handling, which might best be termed as “special”. JS only really has 64-bit floats for numbers, unless you do even more TypedArray contortions than I did here. So I had to compromise by making the random() function output numbers between 0 and 1 with 32 bits of resolution. Each run of the algorithm creates 64 bits of randomness, so I split that into two numbers, saving the second for the next call to the RNG. Changing the function to return integers instead of floats is easy enough: remove the two divisions by MAXINT_PLUS_1.

The whole reason for making this thing was to have a predictable RNG for JavaScript. That’s what the seed() function does. Pass in a single 32-bit integer or a typed array of them, and it will seed the algorithm using that. (One good way to extend this would be to use a hash such as MD5 to allow strings and other objects. That’s why the “TODO” comment is there.) If you don’t, it will use a few numbers generated from Math.random().

Another benefit of this (or any similar RNG) over the stock implementation is that you can create more than one, each tied to its own seed. This means that, for example, you can have your world generator running off a different sequence than your AI. You would then only have to save the seed for the world RNG, while the AI RNG gets reseeded when you reload the game. This would prevent players from, say, repeatedly reloading to get a good outcome of a battle in a strategy game.

As usual, I didn’t make the algorithm; I only wrote the code in this post. You can use it for whatever purpose you like, but I’m sure there are better implementations out there. I didn’t check, mostly because I wanted to try my hand at writing it first. It’s good practice.

Until next time, have fun!

2D Grid Movement with Kinematic Bodies (Godot)

Movement on a grid is common in many games, especially 2D games. In one of my current projects (a “falling blocks” game), this particular problem came up: how do you get grid-based (or discrete) movement on the X-axis while retaining free, continuous movement on the Y-axis? Specifically, I’m using the Godot engine, but the same principle should carry over to any game engine or development environment.

Movement in 2D

Many 2D game engines offer physics systems, and they all tend to be pretty similar (probably because most of them use Box2D under the hood). While your game may be all about sprites, the physics code works with bodies and shapes. Roughly speaking, bodies represent the “mass” of your game objects, while a body’s shapes outline its area. When two bodies’ shapes overlap, there’s a collision, which is handled however your game is supposed to: kill an enemy, take damage from a bullet, etc.

Depending on the specific engine, you have a few different kinds of shapes available. Godot, for example, lets you assign rectangles, circles, lines, “capsules” (like a rectangle with rounded caps on each end), and general polygons. If these aren’t enough, you can combine multiple shapes on a single body. Of course, most 2D engines work this way, so you probably already knew all that.

For bodies, you again have options. Walls and other immobile obstacles are usually static bodies (i.e., they don’t move), and interactive elements are often rigid bodies fully under the influence of physics. The player character, in many engines, is a third type of body, the kinematic body, which causes collisions and stops when it hits a static body, but isn’t affected by forces or friction or, indeed, any physics at all. Once again, though, you already know all of this, because that’s how most 2D physics engines work.

The Setup

For this specific problem, I’m using a kinematic body to represent each falling block. Attached to that body is a sprite (the default Godot icon, for this post) and a collision shape, as you can see in this screenshot:

KinematicBody2D scene tree

(In Godot, there are separate classes for 2D and 3D physics objects, so we have to use KinematicBody2D and CollisionShape2D.)

The kinematic body is the basic object representing each block, the sprite is its appearance, and the collision shape defines its area. Simple enough. Now, what we want to happen is this: move the sprite in two different ways. On the Y-axis, the block should fall down continuously, moving through every point on its way to the bottom. On the X-axis, however, we want the block to “jump” from one position to another, because the blocks have to stack perfectly.

I’ve also set up a scene to use as a base. It’s nothing much, just walls on either side and a floor on the bottom of the screen:

Scene tree for walls and floors

When all this is done, we’ll have a sprite falling from the top of the screen until it hits the “wall” at the bottom. At any point after it appears, you can click and drag it to move it from side to side, and it will stay on a grid, something like this:

Grid movement

Making the Body

We can make the body/sprite/shape combination as follows:

  • The KinematicBody2D is the root node. The only property I changed was reducing the collision margin (Collision > Margin in the Inspector window) to 0.001, the lowest it can go. You don’t actually need to do this for the example, but it may help if you have a problem with collisions detected when bodies aren’t really touching. (There’s also a script attached to this node, but we’ll get to that.)
  • The Sprite is our image. Load the icon.png file that’s included with every Godot project, and you can leave pretty much everything else as is.
  • The CollisionShape2D node, as you might expect, is our collision shape. Due to the way Godot works, we need to define the shape of the shape, which you can do under CollisionShape2D > Shape in the Inspector. Create a new RectangleShape2D in the menu, and set its X and Y extents to something a little less than 32:

RectangleShape2D Properties

(The logo image is 64×64 pixels in size, and extents are measured from the center. If we set the extents to exactly 32, then some blocks might be considered colliding when they really aren’t. That’s because of the collision margin I mentioned above. You can even like 31.999 if you like, and that may work better than 31. Honestly, I’m not sure at the moment.)

The Code

Now that we have all that out of the way, we come to the real meat of the post, the code. Add a new script to your KinematicBody2D node. I named mine gridmove.gd, but you can call it whatever you want. Anyway, here’s the code:

extends KinematicBody2D

# Our accumulated motion on the X axis
var xaccum

# Track if we're dragging a sprite
var mouse_down

# These are the width and height of the sprite
var twidth
var theight

# A default fall speed (like gravity, but velocity instead of acceleration)
const STARTING_SPEED = 100.0

# A velocity vector that we'll use for calculations below
var velocity = Vector2()

func _ready():
    # This object will use input and fixed-timestep physics
    set_process_input(true)
    set_fixed_process(true)

    # Initialize our variables
    xaccum = 0
    twidth = get_node("Sprite").get_texture().get_width()
    theight = get_node("Sprite").get_texture().get_height()
    mouse_down = false
    velocity.y = STARTING_SPEED

func _fixed_process(delta):
    # The object will fall until it hits the bottom of the world or another object
    var motion = velocity * delta

    # Test if we've accumulated enough movement to "jump" one grid square,
    # If we have, then we'll add that much movement to our motion vector.
    if abs(xaccum) > twidth:
        motion.x = twidth * sign(xaccum)
        xaccum -= twidth * sign(xaccum)
    else:
        motion.x = 0

    # Move the object as much as possible
    motion = move(motion)

    # If we're colliding (with the wall or another object), 
    # then we need to modify our motion vector.
    # See the Godot wiki for how and why this works:
    # https://github.com/okamstudio/godot/wiki/tutorial_kinematic_char#problem
    if is_colliding():
        var n = get_collision_normal()
        motion = n.slide(motion)
        move(motion)

    # If the mouse button has been released,
    # we can stop worrying about motion on the X axis
    if not mouse_down:
        xaccum = 0

func _input(event):
    # Create a rectangle covering the entire sprite area
    var gp = get_global_pos()
    gp.x -= twidth/2
    gp.y -= theight/2
    var gr = Rect2(gp, Vector2(twidth, theight))

    # If the left mouse button is pressed while over the object,
    # all we do is set our state variable. If it's released anywhere,
    # we clear that same variable.
    if event.type == InputEvent.MOUSE_BUTTON and event.button_index == 1:
        if gr.has_point(event.pos):
            mouse_down = event.pressed
            get_tree().set_input_as_handled()
        elif mouse_down and not event.pressed:
            mouse_down = false

    # If the user drags while holding the left mouse button,
    # that's our signal to start accumulating motion.
    if event.type == InputEvent.MOUSE_MOTION and mouse_down:
            xaccum += event.relative_x
            get_tree().set_input_as_handled()

The comments tell you most of what’s going on in the code itself. Basically, what we’re doing is “saving up” the motion on the X-axis until it’s enough to move by one grid “square”, which is the width of the logo sprite. The xaccum variable holds how much motion we’ve saved, and we check it each frame (technically, each physics update period, which isn’t necessarily tied to the frame rate). If we’ve saved up enough, then we move the sprite, deducting that motion from our accumulated value.

The added wrinkle is due to gravity, as you can see at the top of the _fixed_process function. Blocks in this particular scene fall at 100 pixels per second, and then they might move on the X-axis. With a vector, we can represent both of these motions, as in line 44, but then we have a problem. Kinematic bodies, remember, can cause collisions when they move, and the move() method stops when the body collides with another, as explained in the wiki article linked on line 49, which also shows how to use the slide() method to change the motion vector.

Spawning the Blocks

The following script should be added to the root Node of the other scene (the one where we defined the walls and floor). All it does is spawn a new block (body, sprite, and shape) whenever you press Space.

extends Node

var block

func _ready():
    set_process_input(true)
    randomize()
    block = load("res://block.xscn")
    spawn(randi() % 10)

func _input(event):
    if event.type == InputEvent.KEY and event.is_pressed() and event.scancode == KEY_SPACE:
        spawn(randi() % 10)

func spawn(column):
    var node = block.instance()
    var tex = node.get_node("Sprite").get_texture()

    # Add 1 to the column value for the left wall,
    # add 0.5 because positions are relative to the center of an object
    var spawn_x = (column + 1.5) * tex.get_width()
    node.set_pos(Vector2(spawn_x, tex.get_height() / 2))
    add_child(node)

Most of this is basic Godot engine stuff like creating a node instance. We do add a hint of uncertainty by spawning each new block in a random grid column.

Conclusion

There’s a lot more that can be done with this code, and it’s probably not bug-free. There may even be a better way of going about this particular problem. If so, I’d love to hear about it! Also, even though I used Godot for this example, the same pattern will work anywhere you have 2D physics, from big names like Unity, to Phaser and other “simpler” engines. You might even be able to adapt it to work in 3D, but I haven’t really tried. Let me know what you come up with, and have fun!

Random Number Distributions (JS)

Last week, I talked about a method for choosing random values within a set, one of the many uses for random numbers in a game. This time, I’ll go deeper into the notion of probability distributions, and how you can make use of them in game development and other kinds of programming. A word of warning: this post will have code (usually Javascript) and might use a lot of math!

Simply Random

The uniform distribution is the one you already know. It’s behind all the simple RNG functions we saw before, like C’s rand() or Javascript’s Math.random(), and it’s what you get when you roll a single die: every number has an equal chance of coming up. In math terms, if there are n possibilities, then the chance of getting any specific one is 1/n. Couldn’t be simpler, really. For most game uses, this is your main tool, and the “weighted set” from the other post is a handy add-on.

The Bell Curve

I mentioned the bell curve and the normal distribution last time, but here I’ll go into a little bit more detail. The bell curve, of course, is often an early introduction to the world of statistics and terms like “standard deviation”, and (as we saw in the other post) it’s what you start getting when you roll more and more dice at a time.

Obviously, that’s one way to get a normal distribution: roll a bunch of dice and add them together:

var dieRoll = function() { return Math.floor(Math.random() * 6) + 1; }
var bellCurveRoll = 0;
for (var i = 0; i < 10; i++) {
    bellCurveRoll += dieRoll();
}

This gives us something close (though not perfect): random numbers will range from 10 to 60, with 35 being the most common. If we need something better (i.e., more accurate), we’ll need to delve into probability theory. Don’t worry, it’s only a short dive.

Side Quest

The mean might be familiar to you, since it’s not much more than another name for “average”. For a normal distribution, the mean is the center point of the curve, the part where it’s at its highest.

Less familiar is the standard deviation, although you may remember that from high school or early college. It’s important in a lot of stats-based fields, because it measures how “clustered” a group of data points is.

Now, for a set of data, you can calculate the mean and standard deviation. That’s pretty much how things like grading curves work: you take the data and make a distribution that fits. For RNGs, however, we have to work backwards. Instead of calculating the mean and standard deviation for the data, we choose them at the start, and our RNG uses them to provide the proper distribution of values. For the normal distribution, this means that about 68% of the values will be within 1 standard deviation of the mean, 95% within 2, and 99.7% within 3. (By the way, the standard deviation is usually identified in math by the Greek letter sigma: σ. “3-sigma” confidence, then, is 99.7% likelihood that something is true. “Six sigma” encompasses everything within 6 standard deviations of the mean, or about 99.9999998%; it’s not quite “one in a billion”, but it’s pretty close.)

Back to Normal

So, knowing all this boring math, you can start getting your random numbers. Here’s one way of doing it in Javascript:

function normalDistribution (mu, sigma) {
    var u1 = Math.random();
    var u2 = Math.random();

    var z0 = Math.sqrt(-2.0 * Math.log(u1)) * Math.cos(Math.PI*2 * u2);
    var z1 = Math.sqrt(-2.0 * Math.log(u1)) * Math.sin(Math.PI*2 * u2);

    return z0 * sigma + mu;
}

This uses a method called the Box-Muller transform to generate a random number on a bell curve. (The astute reader will notice that the function actually generates two random numbers, but throws one of them away. If you like, you can make a better function that stores the second value and returns it as the next random number.) The two parameters are our mean (mu, because it is often written as the Greek letter μ) and the standard deviation (sigma). The Wikipedia link above explains the theory behind this method, as well as giving links to other ways, some of which might be faster.

Exponential Randomness

Normal distributions have their uses, and they’re about as far as most people get in studying randomness. But we won’t stop there. We’ll move on.

Next up is the exponential distribution. This one isn’t that hard to make in code:

function expoDistribution (lambda) {
    return -Math.log(1.0 - Math.random()) / lambda;
}

But you might wonder if it’s really useful. Well, as it turns out, it does come in handy sometimes. Basically, the exponential distribution can be used anywhere you need a “time between events” type of randomness, like random events firing in a strategy game.

The lambda parameter is what’s called a “rate parameter”, and it’s intimately related to the mean; in fact, it’s the reciprocal: the exponential distribution’s mean is 1 / lambda. But what does it mean? Let’s take an example: say you’re making a game where special power-ups appear, on average, twice every minute. Using the above function with lambda as 2, the result would be the time (in minutes) until the next power-up. (The mean would then be 1/2, or 30 seconds, which makes intuitive sense.)

Pareto, Principle, and Power

If you’ve ever heard of the “Pareto Principle” or the “80-20 rule”, then you’ve got a head start on learning about the Pareto distribution. The general idea is thus: there are a few with a lot, and a lot with a little. “The top 20% control 80% of the wealth” is the most common way to state this particular idea, but a random distribution with these properties can be surprisingly useful in games. Here’s the code:

function paretoDistribution (minimum, alpha) {
    var u = 1.0 - Math.random();
    return minimum / Math.pow(u, 1.0 / alpha);
}

We have two parameters we can control this time. minimum is the lowest possible value that can be returned, while alpha controls the “shape” of the distribution. (Generally, higher values of alpha have a faster drop-off, meaning that lower values have higher probability. The “80-20” distribution has an alpha of log(5) / log(4), or about 1.161.)

The Pareto distribution isn’t just used for wealth, though. Anywhere you have a “long tail”, it might be what you’re looking for. Random city sizes (or star sizes, for an interstellar game) follow a Pareto distribution, and it might be a good way to model “loot drops” in an RPG; less powerful objects are far more common than the Ultimate Sword of Smiting, after all.

In Closing

These aren’t all that’s available, but the four distributions I’ve shown are probably the most useful for programmers, especially game developers. As before, I didn’t originally come up with any of this; it’s all been known since before I was born. Some code is converted from Python’s extensive random module, specifically the functions random.expovariate() and random.paretovariate(). The code for the normal distribution is my Javascript conversion of the Box-Muller transform example at the Wikipedia link above. (By the way, if you want me to post examples for a different language, just ask!)

A lot of people already know all this material, and there are plenty of other sites detailing them better than I can, but I hope that this is enough to get you interested.

Weighted Random Choices (JS)

In programming, we often need to generate random numbers, especially for games. Almost any game will use at least some kind of random number generator (RNG), and most need lots of them to drive the AI, make new levels, and so on.

Any programming language worth using (for games, anyway) will have some way of making an RNG. C has rand(), Javascript has Math.random(), and so on. Game engines usually add in their own ways, like Unity’s Random.value, constructed out of the base provided by whatever language they’re written in. All of these work in basically the same way: you ask the RNG for a value, and it gives you one. Usually, it’s a floating-point number between 0 and 1, which is good if that’s what you need.

Beginners starting out in game development quickly learn how to turn the float value from 0 to 1 (not so useful) into a number in the right range (more useful). The code for rolling a regular, six-sided die usually looks something like this (in Javascript):

var roll = Math.floor(Math.random() * 6) + 1;

It’s a pretty standard technique, and many languages and game engines now have functions that do this for you. And, again, if that’s what you need, then it’s perfect. Sometimes, though, it’s not what you need. This post is for one of those times. Specifically, the case where you need to choose one value from a list.

Simple Choices

When you simply need to pick a single value out of a list (array, vector, whatever), that’s easy. All you’re really doing is the same thing as rolling a die:

var index = Math.floor(Math.random() * array.length);
var choice = array[index];

In effect, we’re choosing a random array index. Easy. Like rolling a die, it gives you an equal chance for each possible value. (If your array contains the numbers from 1 to 6, then you’ve just created a less efficient method of rolling a die.)

Harder Choices

Not everything has an equal probability, though. (Statistics as a science wouldn’t exist if it did. Whether that’s a good or bad thing depends on the way you look at it, I guess.)

Some things can be approximated with the die-rolling method above. Lotteries, for example, work the same way, as do raffles. For some games, that may be all you really need. But other games require more from their RNGs than this.

Take the case of rolling multiple dice. Anybody who has played a role-playing game, or craps in a casino, or even Monopoly knows that, while every number on a die has an equal chance of popping up, things get more complicated when you add more dice. With two dice, for example, a total of 7 is more common than a 2 or 12, because there are more ways to roll numbers that add up to 7: 1+6, 6+1, 2+5, 5+2, 3+4, and 4+3. Add more dice, and the numbers get bigger, the range gets wider, but the idea stays the same: numbers “in the middle” are more likely than those on the outside. (Due to what’s called the central limit theorem, the more dice you roll, the more the graph of possible outcomes starts to resemble a bell curve.)

Rolling a lot of dice is impractical, even on a computer. The probabilities aren’t always so nice and neat that a bell curve works. Maybe you need to choose from a set where the ends are more common than the middle, or a list with a weird distribution of frequencies like the letters in English text. (One out of every eight letters, on average, is E, but Z is over a hundred times less common.) A word game, for instance, would certainly need to do something like this.

Now, there are plenty of different ways of generating random numbers based on frequencies. Here, I’m only going to describe what I think is the simplest. First, we need a problem. Let’s say you’re making a word game that, for whatever reason, uses the letter tiles from Scrabble. (You probably wouldn’t be making an actual Scrabble game, because some people or lawyers might not like that, but we’ll say you’re using the letter frequencies.) Looking at that link, you can probably see that just using random choices won’t help you. We need something different.

First things first, let’s define the set we’re choosing from (note the space at the end, which represents the blank tiles):

var letters = ['a','b','c','d','e','f','g','h',
    'i','j','k','l','m','n','o','p','q','r','s',
    't','u','v','w','x','y','z',' '];

Since this is an uneven distribution, we need some way of representing each probability. In this method, we do this by “weighting” each value. We’ll store these weights in their own array:

var weights = [9, 2, 2, 4, 12, 2, 3, 2,
    9, 1, 1, 4, 2, 6, 8, 2, 1, 6, 4,
    6, 4, 2, 2, 1, 2, 1, 2];

In this case, the sum of all the weights is 102 (100 letters, 2 blanks). Therefore, the ratio of each weight to that sum is the frequency of the letter. (For example, there are 12 E tiles, so E’s frequency is 12/102, or about 11.8%.) That’s the key to this method. Basically, we do something like this:

function randomLetter() {
    var totalWeight = 0;

    for (var w in weights) {
        totalWeight += w;
    }

    var random = Math.floor(Math.random() * totalWeight);

    for (var i = 0; i < letters.length; i++) {
        random -= weights[i];

        if (random < 0) {
            return letters[i];
        }
    }
}

(Obviously, in a real game, we’d need something much more robust, with better error handling, etc., but this is enough to illustrate the point. Also, this isn’t normally how I’d write this function, but I’ve simplified for the same reason.)

The function works by picking a random number from 0 up to the sum of the weights. We then use that as an “index”, but not directly into the array. Instead, we count down from our chosen number, each time subtracting successive weights, until we go below zero, where we produce the corresponding letter.

Let’s say that our random number is 15. We go through the weights array, starting with 9. Subtracting 9 from 15 leaves 6, so we keep going, down by 2 to 4, then by 2 again to 2, then by 4 down to -2. That’s below zero, so that’s where we stop, returning 'd'.

This method isn’t just limited to choosing letters. You can use it anywhere you need a biased sample. Think of a game that has five different types of enemies, each with different chances of spawning. Set up a list of enemy types, another holding their appearance frequencies, and the same method will give you waves of bad guys.

(Note: I’m not claiming credit for any of this. It was all figured out a long time ago, and certainly not by me. I’m not even the first to write about it online. But it’s definitely something beginners should learn, and I hope to post more little “tutorial” articles like this in the coming months, because we were all young, once.)