Thus far my enemies and powerups have been spawned with more or less equal probabilities. This has meant that some of the more powerful options have spawned in greater numbers than wanted. Today I will remedy that.
It took me some thinking and searching, but I found the best option for me to be something that is called roulette wheel selection or fitness proportionate selection. Don’t be alarmed with the names, the algorithm itself is quite easy.
But before I introduce it, I have to introduce an auxiliary method with which I will calculate the sum of all the weights. The summing method itself is straight forward. All I have to do is to go through all of the weights and add them together. For these cases foreach loop is perfect, because it goes through every item in an array. Another good thing about this one is that, if I change the size of the weight arrays the method will still work. I called the method WeightsSum, at least it’s descriptive… The method takes the weight array as input and returns the integer sum of all of the weights.
I haven’t implemented any form of a check to see if the array is empty, null or the sum is zero. Usually this is a bad practice, but in this case the arrays are hard coded, cannot be changed during runtime, and I will not use zero valued weights. That is why I haven’t done any error checks, still one has to be mindful of this.
Now then what are the weights? The weights indicate how often I want that particular powerup or enemy to spawn. However they are not direct probabilities, that means that their sum does not equal to 1.0 or 100, or at least it doesn’t have to equal one of those two options. Also with this method I don’t have to normalize the weights, mostly due to the relaxed condition of weights not being real probabilities.
Still this doesn’t mean that the method wouldn’t work, it just means that there is one step less in the process. Other benefit is that if I ever change the weights or add new ones for new powerups or enemies, I don’t have to go through all of them to see whether or not the normalized sum is 1.0.
Higher the weight value, the more likely the corresponding powerup or enemy is to be chosen. If there are two or more weights with equal values, then one among those will be randomly chosen. Every item that has a zero valued weight will not be chosen.
I chose the weights first by assigning them the values that I thought were good, then after few test runs I refined them to be closer to what I wanted the spawn rates to be. The comments above the arrays are for me to remember which weight corresponds with which powerup or enemy.
Then to the actual method for selecting the random powerup or enemy. The method is called RouletteSelector and it takes the weight array and the sum of the weights as input. Once it is done, it returns the index value of the chosen item.
First the method picks a random number between zero and the sum of all the weights. Now this has to be a half-open interval from the sum side, that is [0, sum) or [0, sum[ depending on which notation you prefer.
Then it goes through the weight array in a for loop. If the random number is less than the weight at the current index value, then this index value will be returned. On the other hand if it is not less than the weight, the current weight will be subtracted from the random number and then the loop will continue on to the next index value.
Those who are familiar with this method could be wondering will this work the same as the usual way of comparing a partial weight sum to the random number and selecting the one index value where the partial sum is equal to or more than the random number.
The answer is yes, this will work the exact same way. The only differences are that I don’t have to introduce another variable to store the partial sum, the comparison is less than operation which would eliminate possible round-off errors, and instead of addition there is subtraction.
The last issue to consider is, what happens if for some reason the random number is picked from a closed interval of [0, sum]? If the random number is less than the sum, it works exactly the same as before. So the issue is when the random number equals to the sum. As an example lets use weights [1,1,1] and the random number is then 3.
When the code is executed in the first round it checks if 3 is less than 1, the weight at index 0. Since this is not true, the code will subtract the weight from the random number, thus 3 becomes 2.
The same thing happens next round, 2 is not less than 1, so the random number reduces to 1. Then comes the last round, the index value is 2 at the moment. Because the comparison is less than, it will make the argument in the if statement false since 1 is not less than itself, then the weight will be subtracted from the random number and as this is the last element in the array the for loop will come to an end without finding any index value to return.
This is an important thing to remember if you implement this, the other one is the subtraction. In my case, I use the Random.Range for integers which is exclusive from the larger numbers side, that is it is a half-open interval of [x,y), when x < y.
That is how you can implement the roulette wheel selection method for your needs of selecting items with different probabilities at random. And as you can see the more probable ones spawn most often, yet all of the items will spawn eventually.