Designing a probability table

Question

I'm prototyping a game in where the user taps a button and a item randomly appears.

    Object A = 10% chance of discovery
    Object B = 15% chance of discovery
    Object C = 12% chance of discovery etc... totalling 100%

Over the progression of the game, the user may increase the odds of finding certain objects, for example increasing Object A's probability from 10% to 15%.

I'm wondering if anyone can suggest an efficient design or function for running through probabilities and returning an object.

At first I considered just randomly generating a number from 1 to 100, and then using a series of if/else if statements, but this seems tedious and not very malleable for updating item probabilities. Also, should I store the probabilities in and NSDictionary?

Any suggestions appreciated. I'm writing in Objective-C. Thanks

score 4 · Accepted Answer · edited May 23 '17 at 10:25

The simplest design would be to have a NSMutableDictionary (mutable since you need to update it) in this fashion

NSMutableDictionary * probabilityTable = @{
    @"objectA" : @0.10, // the @ converts the number to a `NSNumber` (NSDictionary accepts only objects)
    @"objectB" : @0.15,
    @"objectC" : @0.12
};

and so on.

Then in order to retrieve a probability

probabilityTable[@"objectA"];

and for updating it

probabilityTable[@"objectA"] = @0.16;

EDIT

For extra joy, you can use the objects themselves as dictionary keys. In order to do so, make those objects subclasses of a class MyObject (I'm assuming that you will have different classes for different object categories). Such class must conform to the NSCopying protocol and implement the isEqual and hash methods.

For more info on how to conform to NSCopying: Implementing NSCopying

For more info on how to implement isEqual and hash: Best practices for overriding isEqual: and hash

After you do it, you use the object itself for retrieving its probability and update it, turning the above code in something like

// initializing 
NSMutableDictionary * probabilityTable = @{
    objectA : @0.10,
    objectB : @0.15,
    objectC : @0.12
};

// retrieving
probabilityTable[objectA];

// updating
probabilityTable[objectA] = @0.16;

EDIT 2

If you wanna get fancy, you could also write an assertion to check that the sum of probabilities is always 1. The check would look like

float sum = 0;
for (NSNumber * n in probabilityTable.allValues) {
    sum += n.floatValue;
}
NSAssert(sum == 1.0, @"Sum of probabilities must be 1.0");

You can easily think of bundling this check in a method and call it every time you modify the probability table

Makes sense programmatically, the only issue I see is updating, which would also require you to update every other object's probability so that the total still equals 100%, and that those objects' change in probability is weighted correctly. — user339946, Apr 07 '13 at 17:28
That's intrinsic in the problem, in the sense that unless you provide some smart default for updating the other values, the "system" won't know how to balance the update. You may decide to have some automatic behavior (redistribute the difference between all the other objects) and wrap the `update` call providing such behavior. — Gabriele Petronella, Apr 07 '13 at 17:31

score 1 · Answer 2 · answered Apr 07 '13 at 17:08

Are the objects unique? If so, create a bag that holds all the objects

NSArray *legendarySwords=....

and just remove an arbitrary element from that array.

If the objects are not unique -- you've got a vending machine that dispenses as many of each object as the player can afford -- take your array

@[ 0.10, 0.15, 0.12 ...]

and construct the cumulative probabilities

@[ 0.10, 0.25, 0.37 .... 1]

Now, generate a single random number [0,1]; the first element in the array <= the random number gives you the choice.

But this will be a pain for maintenance. A nicer solution would populate a bunch of objects with relative probabilities:

NSThing *canteen=[[NSThing alloc] initWithCost: 10 abundance: kCommon];

NSThing *magicArrow=[[NSThing alloc] initWithCost: 100 abundance: kRare];

NSInventory *inventory=[NSInventory inventoryFor: @[canteen, magicArrow, ...];

Then construct your probability arrays from the inventory. Need to make arrows kVeryRare for play balance? You only need to change the magicArrow, and your probability arrays will be updated automatically. Otherwise, you're bound to have problems eventually.

Aneesh · Answer 3 · 2014-08-17T04:58:18.117

I had the same problem as you, and stumbled upon this very helpful link.

The code in the link is written in ActionScript 3, so here is my objective-c converted code. I

- (MyObject *)getWeightedRandomObject
{
    int weightsCounter =  0; // sum of the current weights added

    // get the total weight of all the obstacles
    for (MyObject* object in objectsArray)
    {
        weightsCounter += object.spawnWeight;
    }

    int random = arc4random_uniform(weightsCounter) + 1; // random int from 1 to total weight inclusive.
    weightsCounter = 0;

    // pick the weighted object
    for (MyObject* object in objectsArray)
    {
        weightsCounter += object.spawnWeight;

        if (random < weightsCounter)
        {
            return object;
        }
    }

    return [objectsArray lastObject]; // only the last object will be remaining at this point
}

To be certain that this algorithm worked, I created three objects with a spawnWeight of 60, 30, and 10, and called this method 1000 times. I ran the test about six times, and every single time the spawn percentages were almost spot on. You might want to customize the above code a bit to fit your needs, but the logic of the algorithm is tested and works.

Enjoy!

Designing a probability table

3 Answers3