Data structure for random outcome from a hit probability table

The basic idea of a hit-table is carried over from pen & paper role playing games. You roll a die or a number of dice representing your ability to attack an opponent. Your opponents defense is relative to your ability to attack: if you can roll higher than their defensive ability, then you hit them; if not, you miss.

Games started out with simple implementations and mechanics got more complicated as (e.g.) later editions of the rulebooks were published and players/customers desired a more realistic combat experience.

So conceptually, a hit table may look something like this:

Roll    Outcome
1-5     Miss
5-15    Dodge
16-20   Parry
21-80   Hit
81-100  Critical Hit

World of Warcraft calls this an attack table, but I haven't found a good resource which discusses a good data structure for this. The best implementation I have come up with so far is a linear traversal of an ordered list of the relative outcomes, which makes the decision algorithm O(n), where n is the number of possible outcomes. The psuedo-code for this comes out to be:

var result = randome.next(0, hittable.maxvalue)

foreach outcome in hittable
    if result < outcome.max_value
        return outcome

// Reached the end of the table without finding an outcome
// Probably an error here, but let's fake it
return hittable.last

A typical combat in (most) modern games has many, many attacks that go to the hit-table for determination, as well as many possible outcomes. It is not hard to imagine this lookup becoming a serious bottleneck in terms of processing time. I remember the algorithm of a bucket sort from my Comp. Sci. coursework and have been enamored with the idea of finding a datastructure which would allow for a O(1) lookup of random number values. What would such a datastructure look like?

I can imagine how it could work with a one-liner query in SQL, but something tells me that would be adding a whole lot of overhead for a not-true O(1) solution.

SELECT name FROM hittable
WHERE hittable.min_roll < RAND() AND RAND() < hittable.max_roll

This is just a notion that popped into my head because "it's a hitTABLE, so why not store it in a table". Note: the above query also would not work because the two calls to rand would return random numbers.

Edit: MMORPGS have also implemented something similar for Loot Tables, which determines what you get from winning a battle (by looting the corpse of the defeated foe). This is complicated by having multiple potential outcomes for each random result, e.g.

Roll    Outcome
1-5     Nothing
5-15    Some Gold
16-20   An Item
21-80   Some Gold and An Item

81-100  Lots of Gold and TWO Items

In a game the size of World of Warcraft, you could have thousands of players looting the same monster in any given second, so again a strong argument can be made for finding the very fastest way to perform lookups of this manner.

Answer

This is called weighted randomization (or "discrete distribution selection"), and there are two good data structures to represent it:

• A partial-sum tree (my name, as I don't think it has a good name)


• Walker's Alias Method

Both are described quite nicely in this blog post.

---

If you are coding in C#, I've implemented them both in an easy-to-use weighted randomizer library for C# here. You can find the documentation here.

Using it, your code would look something like this:

enum AttackOutcome { Miss, Dodge, Parry, Hit, CriticalHit };
...
//Create the randomizer
IWeightedRandomizer randomizer
    = new StaticWeightedRandomizer();

//Add the items, and their associated weights

randomizer.Add(AttackOutcome.Miss, 5);
randomizer.Add(AttackOutcome.Dodge, 10);
randomizer.Add(AttackOutcome.Parry, 5);
randomizer.Add(AttackOutcome.Hit, 60);
randomizer.Add(AttackOutcome.CriticalHit, 20);

...

//Later, randomly pick an item.  This can be done as many times as you'd
//like; it's O(1), so it's super-fast no matter how many items you add!

AttackOutcome outcome = randomizer.NextWithReplacement();
switch(outcome)
{
    case AttackOutcome.Miss: 
        ...etc.
}