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:
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
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
// Reached the end of the table without finding an outcome
// Probably an error here, but let's fake it
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
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.
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.