Programming - Random Weighted Selection

For Cupcake Escape (which is now playable again), I used a weighted system for selecting random objects off a list. By that I mean each object from the list can have different probabilities.

Suppose we have the following objects we want to summon.

Cookie
Pie
Turkey
Cranberry
Bran muffin
Natto
 
The way that is done is by first assigning each object a number from 0-100 and then creating a sum using each object's number. Then you basically divide each object's number by the sum in order to get a percentage. That percentage is your object's probability of spawning. You don't necessarily have to divide within your program, but I did it for the sake of human understanding using floats. However, I do not recommend using floats, as they take up more memory than ints do. Not to mention keeping track of floats is a pain... So I would recommend just sticking to ints.


Cookie - 100
Pie  - 50
Turkey - 50
Cranberry - 25
Bran muffin - 25
Natto - 10

Group Sum - 260

(It's fine to use the above set of information for the next part of the algorithm)

 Approximate probabilities

Cookie -38.5%
Pie  - 19.2%
Turkey - 19.2%
Cranberry - 9.6%
Bran muffin - 9.6%
Natto - 3.9%

Note that these items are ordered in accordance to weight/probability. You don't necessarily need this to be ordered. I just have them in order for the sake of being organized.

So you have your probabilities and associated objects stored somewhere. I used an array in my game. The next part is to randomly spawn those objects in accordance to the probabilities assigned to your objects. So first you need to generate a random number within the range of 0 and the sum we previously calculated. That random number represents your selection choice.

To figure out what you need to spawn, you now need to go through the array and check against your generated number.

To do this, you go through the array. You also need a temporary variable to keep track of were you are in the array so far. So the way this works is that you check each item in the array from smallest to largest. You add the current probability to the temporary variable and check if your variable is bigger than your generated number. If your generated number is bigger, you move to the next item in your array and add it to your temporary variable. If your generated number is still bigger, you do it again. When your temporary variable is finally bigger than your generated number, you simply return the object you just added and you have your selection!

For example... let's say our generated number is 159. This int was randomly chosen from a range of
0 and 260 (or 261 if non inclusive) using an RNG.

We have our temporary variable int SumSoFar (set to 0) and we start with Natto, because it's the smallest and the first item in the array. Natto has a probability of 10, so SumSoFar is 10. Since our random number is 159, SumSoFar is smaller, so we move onto the next item.

Add Bran Muffin
SumSoFar = 35
35 < 159

Add Cranberry
SumSoFar = 60
60 < 159

Add Turkey
SumSoFar = 110
110<159

Add Pie
SumSoFar = 160
160 !< 159

Return Pie


So why does this work?

Suppose you have your range laid out on a line

NBBBCCTTTTTPPPPPKKKKKKKKKK


All you are doing is picking one of the letters above. Each letter represents one of your possible choices. The number of letters represents the probability of picking that letter. Suppose you randomly pick a spot on the line and you are looking from left to right. Every range to the left of where your finger fell is not below your finger. The range that is below your finger is your selection choice. No matter where your finger falls in the range of K for example, it will still be K. Your finger did not fall in the ranges of P, or T, or C, or B or N, because your finger already went past all of them. However, your finger did not pass the range of K. Your finger fell within the range of K. So, because your finger went past the end of all previous ranges, but did not pass the end of range K, you landed on K. This is the principal which the algorithm above works on and is the reason why it works.

Some Things to Note

Because of the loop involved, it might be difficult to use this weighted probability selector during run time if your selection group is large. The reason being is because this loop will run on one frame, and if the delay is big enough because your group is large, you will pay for it in your frame rate. I cannot necessarily say this explains why my game stutters a little bit (it might be because of my factory setup), but it can certainly be a negative factor in theory. So limit your selection pool size.

When you are creating your sum, do that loop on awake or before the player has control. Calculate it, and do not set the sum manually because this allows for flexibility. If your designers want to tweak the weight/probability because something was appearing too often, they can simply change that number and you don't have to go back into your code to change anything. It's convenient for everybody!