Best way to choose random element from weighted list

Question

I want to create a simple game. Every so often, a power up should appear. Right now the different kinds of power ups are stored in an array.

However, not every power up should appear equally often: For instance, a score multiplier should appear much more often than an extra life.

What is the best/fastest way to pick an element at random from a list where some of the elements should be picked more often than others?

Answer 1

If by "best" you actually mean "fastest", then by far the fastest way (although not nearly the most efficient way) is to choose a multiplier that makes all of the weights integers, at least to whatever precision you care about, and then store that many copies of each in one large array.

For example, if you assign "score multiplier" a weight of 80%, and "extra life" a weight of 20%, then create a 5-element array with 4 references to the "score multiplier" object/variable and 1 reference to the "extra life". Then generate a random number between 1 and 5 and pick from the corresponding index. Distribution doesn't matter.

In practice, unless you've got tons of memory and a very slow CPU, this is a waste of memory. It's far, far simpler and more efficient to write a bunch of if statements comparing a random number to a low/high bound, and if the number of possible items isn't that big (let's say less than 10?) then it shouldn't be that hard to maintain.

If you've got hundreds or thousands of possible items/power-ups/whatever then this is no longer a very maintainable solution. In that case the best option I know of is to maintain a sorted list of tuples with the key as the minimum weight; you don't need to store the maximum as that's implied by the next item. For example [ [0, scoreMultiplier], [80, extraLife], [95, invincibility] ]. Then you can do a binary search on this list to find the appropriate item corresponding to a random number in O(log N) time.

Answer 2

Just a simple weighting system would work. Create a 100 index array, and things that happen 1 time in 100, appear in only 1 spot, while things that appear 1 time in 5 appear in 20 spots. Generate a random number between 1 and 100, and the event that happens is the one in that index of the array.

This is how they compute loot tables for RPGs. You can also generate a list of events that store their probability range internally, so instead of having a large array filled with redundant entries, you can have a smaller two dimensional array that stores an event, along with the numeric range in which it occurs.

Answer 3

If the weight is a percent of times the item should be selected (say 1-100), what about going through the list and assigning each item a 'check' equal to the sum of its weight plus the previous weights. Then take a random number between 1-100 (i.e., a standard random number between 0 and 1, multiplied by 100, tweaked so as to be a non-zero integer), and choose the first item whose 'check' value is greater than or equal to the random value?

So, if there are three elements "A" with weight 25%, "B" with weight 50%, and "C" with weight 25%, the 'score' values are: A=25 (25+0), B=75 (50+25), C=100 (25+75). A random number of 12 would select A (since 12 <= 25). Any random number from 1-25 selects A. Any random number of 26-75 selects B. Any random number between 76-100 selects C.

Would this work?

Possibly this is the same as suggested by Aaronaught -- to be honest I wasn't sure exactly what he or she meant by

write a bunch of if statements comparing a random number to a low/high bound