How to: Weighted Random Selections
A few months ago I wrote about our latest asset context, Drop Tables. Drop Tables, like Loot Boxes, use a weighted rarity system to determine which asset(s) you are rewarded. Since building these features, I have been asked by several developers to outline the method I used to randomly select an asset based on predefined weighting. While I would like to take all the credit, I actually used a method I read about several years ago that was really smart. Since I can’t find the post any longer, I’ll attempt to explain it in my own words.
The goal I had was to create a system that selected a random asset from a list where each asset has been provided a number weight. Assets with a higher weighting should be selected more frequently, but not completely block assets with a lower weighting from being selected.
While there were several ways to approach and possibly solve this task, I had to also consider that LootLocker users might have hundreds of assets in a Loot Box and therefore I needed a system that could scale easily. For example, one solution could be to list all assets multiple times based on the weighting number: for example if the `Pirate Hat` asset had a weight of 3 and the `Pirate Hook` had a weight of 1, the list would look like this:
- Pirate Hat
- Pirate Hat
- Pirate Hat
- Pirate Hook
Randomly selecting from this list would deliver the expected results in that the `Pirate Hat` would be selected 3 out of 4 times. But when you have 100 different assets and 100 different weights you’re suddenly selecting from a list of thousands - if not tens of thousands - of assets and the game has to wait much longer for a response. This is no good.
The solution I ended up using for this system sounds more complicated at first but is ultimately more performant. This is how it works:
- Add together all of the weights for all assets in the list
- Pick a random integer between 1 and the product from Step 1
- Loop over the assets in your list, starting at any asset you wish, and subtract that asset’s weight from the number selected in Step 2
- If the result of this is less than or equal to zero, then great we have a winner! If not, take the result and subtract the next asset’s weight from it.
- Keep repeating this process until the result is less than or equal to zero. Whatever asset you end up on when your result is less than or equal to zero is your winner.
Here’s a diagram that hopefully explains it more clearly.
The idea behind this method is that the random number we pick in Step 2 is getting lower every time we iterate over another asset (if the result isn’t ≤ 0), meaning that eventually an asset will always be selected and it’s most likely to be one with a high weighting.
So, there you have it - an explanation of how the weighted random system for our Loot Boxes work, and mostly our Drop Tables. They do get a little more complicated because we have concepts such as Roll Count and support for dropping multiple items though. But that’s a story for another blog post. If you have any questions or feedback, feel free to reach out via our Discord or tweet me directly.