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?
Best Answer
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
ifstatements 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.