# 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.

• This table is so tiny that it's not worth spending more than 10 seconds thinking about. Use whatever data structure (or just code) is easiest. – congusbongus Aug 6 '13 at 0:13
• The example given is far from exhaustive. Also, the loot tables are under similar load constraints, on the whole, and are orders of magnitude larger. You're right from the perspective of an initial deployment, but from a long term scalability standpoint, I couldn't disagree more. – Patrick M Aug 6 '13 at 0:16
• How big can a loot table be, can you give an example of one that is orders of magnitude larger? Even a table with 100 elements can be traversed in relatively no time at all. The comment about the thousands of players is a red herring - in a game the size of WoW, thousands of players could be doing many other things in a given second, what makes you think the loot table is worth considering over those other things? Also, determining loot is not latency sensitive at all; if you really had to you can predetermine it and apply when the monster is killed. – congusbongus Aug 6 '13 at 1:49
• You're giving yourself away on the comment of Loot not being latency sensitive. WoW went through a whole era (year+, multiple major patch cycles) where you would frequently lose the ability to loot because the loot window would basically time out. You'd go to loot your kill, your character would kneel down, the window would pop up and nothing would be in it. You could close the window, but your character would never stand up and you couldn't loot another monster until you logged out and back in. This was particularly bad for the skinning profession, who couldn't gather skins before looting. – Patrick M Aug 6 '13 at 3:42
• Also, say you predetermine the loot. Well, you've not solved the problem, you've just moved your bottleneck to a different part of the code. Servers go down? Well you'd better be prepared to wait a while for pre-rolling & looking the loot table results of all 100k+ creatures in the entire world. – Patrick M Aug 6 '13 at 3:44

## 6 Answers

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<AttackOutcome> randomizer
= new StaticWeightedRandomizer<AttackOutcome>();

//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.
}

• I should have known to search for answers in terms of dice and rolls and gambling terms. Thank you for the links and especially the library. – Patrick M Aug 6 '13 at 13:25

You're overthinking it. Let's be real for a second here. What you're doing is creating a log flow that is essentially:

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


This is as simple as it gets and your pseudocode can be directly translated into code. You are simply not going to be able to go do better than one if statement check, which, by the way, is negligible in terms of processor time unless you are telling me you have thousands or even tens of thousands of hit entries?

If you do indeed have ten thousand entries, or, better yet, you've profiled your code to check that this has become a problem then you can speed it up somewhat by performing a modified binary search. The only thing you will need to change from the standard algortithm that can be googled is that you want the first entry that is more than or equal to your 'roll'. Let me know if you need me to make some pseudocode but it should be pretty trivial to write.

• +1 for profiling the code: yes, I am over-thinking it. I ask because I want to know, not because I need to know (strictly speaking, at the juncture etc.) – Patrick M Aug 6 '13 at 4:02

If the tables are stable (don't change), you can get an O(1) sampling via the Alias Method. It almost certainly isn't worth the trouble if the tables are smaller, though.

The basic idea is to split up your range into a series of N buckets of uniform weight, with each bucket containing exactly 2 weighted option. You can select one of the N buckets with the usual uniform random number generation techniques. Then you can pick one of the two items in the chosen bucket with another random number. Two random numbers and you get an answer, fairly accounting for weight, every time.

The trick is a preparation step that makes the buckets. You need to do a pass to find the average weight of all buckets. Then you do a pass to split all your items into small values (items with a weight below average) and large items (at or above average). Then you repeatedly pop one item from each list, put the small item into the next bucket, and then put in the large item such that it fills up the average. Subtract the "used up" amount from the large item. If the new value is below average, add it to the small list, otherwise the large. Each bucket contains the two items in it and the weight of the small item that was added to it.

Say we have:

A 0.5
B 1.2
C 0.9
D 1.4


The total weight is 4.0, the average is 1.0. We have a small list containing:

A 0.5
C 0.9


and a large list containing

B 1.2
D 1.4


We take the first item from each, A and B. We put A in the first bucket, which now has a weight of 0.5. We still need 0.5 to hit the average, so we put in B and subtract that 0.5 remainder from it's weight. We now have a weight of 0.7 for B. This is below the average, so we put B in the small list, giving us:

Small
-----
C 0.9
B 0.7

Large
-----
D 1.4

Buckets
-------
A,B  0.5


Now we pop one from each list, giving us C and D. We put C in the next bucket, for a total weight of 0.9. We still need 0.1 to hit the average, so we put in D and subtract 0.1 from its weight. That gives us a new weight for D of 1.3. That is over average, so we put D back into the large list. Now we have:

Small
-----
B 0.7

Large
-----
D 1.3

Buckets
-------
A,B  0.5
C,D  0.9


We take one of each (there only is one of each) and we get B and D. We put B in the third bucket which only has a weight of 0.7 now. We need 0.3 to fill up to average, so we put in D and subtract 0.3 from its weight, giving us 1.0. That's at average so we put it in the large list, giving us:

Large
-----
D 1.0

Buckets
-------
A,B  0.5
C,D  0.9
B,D  0.7


We now have no more small items. If you are out of small items, then either you are also out of large items or you have exactly one large item at a weight equal to average (as in our example). If you don't have one of these two cases, your implementation is wrong. We put this final large remaining item equal to average weight into it's own final bucket. Our buckets are now:

Buckets
-------
A,B  0.5
C,D  0.9
B,D  0.7
D,-  1.0


That's four buckets. To choose one of our weighted oppions, we get a random number [0,N) where N is the number of buckets (4). Say we got 2. That's the third bucket containing B,D 0.7. We now get another random number from [0.0,Avg) where Avg was our average weight (1.0). Say we get 0.465. That's less than the pivot weight of 0.7 in that bucket, so we pick that bucket's small item, which was B.

We can keep doing this over and over and over. Choose two random numbers and get a properly weighted result. No looping or iteration. O(1) lookup for the generated table.

There are variations of the initial processing algorithm to make the table generation much more efficient should you have a situation where the table might change in unpredictable ways during play. If the table changes frequently, you're better off with an O(log(N)) binary search of a sorted running-sum table. In such a table using the above example, you'd have:

A   0.5 = 0.0+0.5
B   1.7 = 0.5+1.2
C   2.6 = 1.7+0.9
D   4.0 = 2.6+1.4


This table needs a single O(N) pass to generate. You need the sum of weights and that running sum for each item. Choose a random number in [0,Sum). Do a binary search to find the smallest running sum that is still greater than or equal to the random number. A binary search on four items is unlikely to be faster than a linear search but it scales better for larger tables obviously (not as well as O(1), but the preprocessing step is much cheaper for this method than an alias table).

• Interesting approach. It sounds on the face of it to be similar to the bucket sort. I don't like the requirement of multiple random numbers for each determination, but the wiki article points out that your initial random call can be partitioned into bit-widths small enough accommodate the size of the alias table, which could be an overall improvement on the number of RNG calls made. Also, since it only requires O(n) setup time, you only need to perform n lookups before you come out ahead, making it really clear where the tipping point is. +1 – Patrick M Aug 6 '13 at 4:25
• Actually, the hittable from my psuedocode requires O(n) set up time as well, so I'm having a hard time to see where this isn't a win (except for complexity, dev time & maintenance time). – Patrick M Aug 6 '13 at 4:28
• The linked SO question has an improvement over my naive implementation: You don't need to pre-build the whole hit table if you know the sum of the weights in advance. Instead, compare the sum of the weights against the random number and stop when you go over the value. – Patrick M Aug 6 '13 at 4:38
• Pulling two random numbers is really really cheap with any sane PRNG, you're worrying about a problem you aren't having. Doing the bit tricks is fine so long as you fully understand what you're doing; not all random number generators distribute their randomness to all bits fairly, so you might end up subverting the algorithm if you try to get too clever. The hittable from your question is a variation of the binary search (especially if you go the SQL route). Also recall that notation like O(N) is very academic; there's a very real difference in practice between complexity XN and YN. – Sean Middleditch Aug 6 '13 at 5:42

based on how small these hit table usually are, I guess O(n) won't hurt. I mean how big can N be? in your example it's 5, I mean there are 5 possible outputs, and iterating over them won't take that much time. But strictly speaking about O notation you can reduce it to O(logN). here is the idea:

you can think of hit table as a list of numbers. since all the possible random values are covered exactly with 1 outcome, we can rest assured if we find the smallest number bigger than the input value we can determine the outcome. converting your example we'll have something like this:

1<--Miss-->5<--Dodge-->15<--Parry-->20<--Hit-->80<--Critical Hit-->100

these numbers (1,5,15...) are very unlikely to change during game play, in fact they usually are determined during game balancing, and set by the game designer. so it can just store them as a sorted list.

The last key to O(logN) algorithm is binary search. Most languages already have it implemented in their core library. so we just pair key values with outcome, and search between the keys for that specific key. What ever key is found, you simply have to return it's respective value.

here is a sample code in C++:

std::map<int, std::string> hitTable;

void initializeHitTable()
{
hitTable = "Miss";
hitTable = "Dodge";
hitTable = "Parry";
hitTable = "Hit";
hitTable = "Critical";
}

string getHitTableOutCome(int value)
{
std::map<int, std::string>::iterator searchResult;
searchResult = hitTable.upperBound(value);
/*
upperBound will return the smallest key-value pair in
the table which is not smaller or equal compared to
the input value. it means hitTable.upperBound(2) will
return (5, "Miss"). note that hitTable.upperBound(5)
results in (15,"Dodge"). also note that std::map always
stores the keys in ascending order, and upperBound uses
binary search to find it's result.
*/
if (value < 1 || searchResult == hitTable.end())
return "value is out of table);
/*
either if our input value is is below 1 or above 99
we don't have any entry in our hit table to match it.
the first condition is pretty obvious, and the second
one means there is no entry larger than value in our
hitTable
*/
else
return searchResult->second;
/*
searchResult is a key-value pair. And
searchResult->second, it the value assign to that
specific key.
*/
}

• The binary search idea is good, but you (and other commenters) are right to point out that the table would have to be large to realize any gain. You could get to O(1) here by densely populating the array (i.e. for(i=0; i < misschance; i++) hittable[i] = "Miss" - large room for optimization, espeically with c-style malloc/realloc calls). The trade off is that if you need 5 digits of precision, then your array becomes large and more expensive to construct or reallocate. I'm hoping there's a sweet spot generic approach between expensive to construct & expensive to traverse, i.e. both cheap. – Patrick M Aug 6 '13 at 3:53

You can try the following (in Python):

# coding: utf-8
hittable = {(1,5): "miss", (6,15):"dodge", (16,20):"parry", (21,80):"hit", (81,100):"critical hit"}
@memoize
def hash(x):
for i in hittable.keys():
if x in range(i,i+1):
return i
import random

for i in range(10):
x = random.randint(1,100)
print x, hittable[hash(x)]


For @memoize, use some memoization decorator.

This, however, boils down to just having the mapping of each of the attacks to the outcome (with O(1) access).

Without memoization, you have just slightly more convenient access to the values (with O(n) access), as the looping is hidden in the hash function.

• Memoization is an interesting approach - it essentially builds a lookup table on top of an arbitrary function, which would get any weighed randomization lookup implementation down to O(n) compute time after each input in the range had been called once. – Patrick M Aug 6 '13 at 13:30
• @PatrickM down to O(1) actually – Michael Pankov Aug 6 '13 at 16:50
• yep... typo. We were already at O(n) :-P – Patrick M Aug 6 '13 at 17:33

What you could do is either use an array of the critical points, and then use an enum for the index that you retrieve based on this. Alternatively, you could use else-if statements chained together. I feel that an enum would be the best final data structure (containing miss, dodge, parry, hit, critical hit) as it can allow you to have stronger typing in the end.

• The enum idea is interesting. But that would seem to require the critical points being static. The point of using a data structure at all (as opposed to a hard coded round-robin system) is that the variables are not static: they can change over the course of time and the data structure chosen should help that goal, not hinder it. – Patrick M Aug 6 '13 at 0:18
• Not necessarily. I said that the result of the attack would be the enum; the way you get to that can be dynamic. The else-if statements could be checked against a variable, and you could change the array values to whatever you want. It would also be pretty easy to iterate over the array and check the value against the next highest one with a while loop. – PixelArtDragon Aug 6 '13 at 0:22