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