Using random numbers with a bias

Question

I appear to be awful at describing the question so I'll try and describe the problem.

I want to add a random amount of heads to my creatures but I want to be able to determine several things. a) The minimum number of possible heads b) The maximum number of possible heads c) The probability of the number being high/low within the above values.

So i could add heads like so: addHeads(5, 10, 0.5); // should produce creatures with "around" 7.5 heads but they could have anywhere from 5 to 10.

So random number generation isn't the problem, but controlling and actually using them in a game is. :D

Answer 1

One way to do it is to apply a power function: $$f(x) = ax^p+b$$

Start with a random number \$x\$ in [0, 1] and then raise it to the power of some positive number \$p\$. Powers < 1 will bias upward, i.e. the numbers will be more likely to be higher than lower within [0, 1], and powers > 1 will bias downward. Then use multiplication (\$a\$) and addition (\$b\$) to shift the range of numbers from [0, 1] to your desired range. In pseudocode:

function random(low, high, bias)
{
    float r = rand01();    // random between 0 and 1
    r = pow(r, bias);
    return low + (high - low) * r;
}

// Examples:
random(5, 10, 1.0);  // between 5 and 10, average is 7.5
random(5, 10, 0.5);  // between 5 and 10, average is somewhere around 8.5
random(5, 10, 2.0);  // between 5 and 10, average is somewhere around 6.5

Here's a plot of the second example:

On the horizontal is the initial random number in [0, 1] and on the vertical is the output. You can see that something like 75% of the initial range is mapped to values higher than 7.5, and 25% of the initial range is mapped below 7.5. So the result is that numbers generated by this function are more likely to be higher.

Answer 2

The usual answer will be some code that can tweak the random number distribution to give you the properties you want. I'd suggest instead working backwards:

1. first decide what distribution you actually want and draw it out
2. calculate the “cumulative distribution” which is the sum of the function in step 1
3. choose a random number from the cumulative distribution
4. look up the number from the original distribution you drew

This way you don't ever actually need to find a function (like power or logarithm) that matches your desired behavior. You can directly model your desired behavior.

How do you implement this? You can approximate step 1 with a table. For step 2 you add the values in the table. For step 3 you pick a random number from 0 to the sum in the cumulative table. Then for step 4 you look for the corresponding entry in the cumulative table.

I don't yet have a great description of this technique, but I've written a little bit in the “Designing your own distribution” section of this page.

This approach probably won't work for everything but I mention it because tables are nice for designers to edit, and the designer is not limited to existing mathematical functions but instead can choose any arbitrary wacky shape. For example, if you decide that a prime number of heads should be unusually rare, that's easy to write in a table, but it might be harder to find a mathematical function that fits that shape.

Answer 3

I have a harvest system implemented in my game that utilizes rejection sampling. Each item has a weighted chance of being produced. It's easy to assign weights to certain items and get one randomly using that weighted chance. This is similar to your situation, except you don't have harvest items, you have number of heads. So, you'd first assign a weighted chance to each head count value for the values you want.

So we have # of heads : weighted chance

5 heads:2
6 heads:4
7 heads:3
8 heads:1
9 heads:2
10 heads:1

The weighted chance values don't have to add up to anything specific, but you should know that they are going to be relative to each other.

Then we go through and make a list of them all:

ArrayList<ProducedItemInfo> tmpList = new ArrayList<ProducedItemInfo>();
    int totalChance = 0;
    for (HeadWeightPair hwp: headWeightPairs) {
        if(conditionsMetFor(hwp)) {
            totalChance += hwp.weightedChance;
            tmpList.add(hwp);
        }
    } //add up the total weight and create a list of the available options
      // at this stage, you could have conditions that would preclude certain options
      // for example, you could check the size of the creature and
      // not allow high numbers of heads
      // if you'll never have conditions, just generate this list once and keep it
    //now we go through removing a random value from the totalChance
    // if one of the items is less than the total, we return that item
    if (totalChance > 0) {
        int rand = randomInt(totalChance);
        for (HeadWeightPair hwp: tmpList) {
            if (rand < hwp.weightedChance) { return hwp.headCount; }
            rand -= hwp.weightedChance;
        }
    }

It's log(n) if you have a pre-compiled list (if you don't have conditions you can do that).