Random numbers with a weighted chance.

I have a list of object that I want to instantiate randomly, but I also want a higher chance to instantiate the first in the list.

As the game level progresses, I want the higher chance to move to the end of the list.

In other words, my list contains objects that are classed as easy to hard in order and I want to instantiate the easy ones at the start of the level but let them get harder as time progresses.

This list will have up to 50 objects in it, but that count will probably go up a little before the end of the project.

Can anyone suggest a good way to do this?

 

I've implemented this very functionality in my asset Make It Random.

To avoid just arrogantly plugging my asset, here's the core bit of the algorithm, so that you can get going yourself.

Code (CSharp):

1. public int GetRandomWeightedIndex(int[] weights)
2. {
3.     // Get the total sum of all the weights.
4.     int weightSum = 0f;
5.     for (int i = 0; i < weights; ++i)
6.     {
7.         weightSum += weights[i];
8.     }
9.  
10.     // Step through all the possibilities, one by one, checking to see if each one is selected.
11.     int index = 0;
12.     int lastIndex = elementCount - 1;
13.     while (index < lastIndex)
14.     {
15.         // Do a probability check with a likelihood of weights[index] / weightSum.
16.         if (Random.Range(0, weightSum) < weights[index])
17.         {
18.             return index;
19.         }
20.  
21.         // Remove the last item from the sum of total untested weights and try again.
22.         weightSum -= weights[index++];
23.     }
24.  
25.     // No other item was selected, so return very last index.
26.     return index;
27. }

To use the function, you just need an array of weights that is equal in size to the number of items you want to select from. It will return an index that you can use to access the selected item.

To summarize/explain the algorithm, you first figure out the weight of all the possibilities summed together. Then you start with the first index and ask, "Out of all the possibilities, how probable is this first index?" That probability is the weight of the first index, divided by the weights of all untested possibilities (including the one currently being checked).

To check that probability, just generate a value greater than or equal to 0, and strictly less than the total untested weights, and if the result is strictly less than the weight of the item being tested, then the check passes and that item should be selected.

If not, then you consider that item to be tested, subtract its weight from the sum of total untested weights, and move on to the next item.

If you manage to make it to the very last item, then the total untested weights will be equal to the weight of that last item. The probability is then of course 100% that the last item will be checked. I wrote my loop above so that it avoids this last useless check, and always returns the last item if it gets that far.

Note that I used integer weights in the above example. The overall concept will work with any other numeric type, but because Unity's Random class selects from float ranges that include the upper bound, it won't be exactly accurate unless you write your own method of getting a random float that excludes the upper bound.

(Side note: I just did a search and quickly discovered an alternate method which is even better if you can guarantee that your array of weights is sorted, as it only requires generating a single random number. Time for me to add a to-do for updating my randomization library with that option!)

 

If you don't mind me asking, why do you generate a new random for each element/index?

Here is an old post where we discuss weighted random selections:
https://forum.unity3d.com/threads/making-random-range-generate-a-value-with-probability.336374/

You should be able to accomplish it with only one random number generated.

Rewritten to match your interface:

Code (csharp):

1.  
2. public int GetRandomWeightedIndex(int[] weights)
3. {
4.     if(weights == null || weights.Length == 0) return -1;
5.  
6.     int t;
7.     int i;
8.     for(i = 0; i < weights.Length; i++)
9.     {
10.         if(weights[i] >= 0) w += weights[i];
11.     }
12.  
13.     float r = Random.value;
14.     float s = 0f;
15.  
16.     for(i = 0; i < weights.Length; i++)
17.     {
18.         if (weights[i] <= 0f) continue;
19.      
20.         s += (float)weights[i] / total;
21.         if (s >= r) return i;
22.     }
23.  
24.     return -1;
25. }
26.  

Or with floats, to allow for infinite probability:

Code (csharp):

1.  
2. public int GetRandomWeightedIndex(float[] weights)
3. {
4.     if(weights == null || weights.Length == 0) return -1;
5.  
6.     float w;
7.     float t;
8.     int i;
9.     for(i = 0; i < weights.Length; i++)
10.     {
11.         w = weights[i];
12.         if (float.IsPositiveInfity(w)) return i;
13.         else if(w >= 0f && !float.IsNaN(w))t += weights[i];
14.     }
15.  
16.     float r = Random.value;
17.     float s = 0f;
18.  
19.     for(i = 0; i < weights.Length; i++)
20.     {
21.         w = weights[i];
22.         if (float.IsNaN(w) || w <= 0f) continue;
23.      
24.         s += w / total;
25.         if (s >= r) return i;
26.     }
27.  
28.     return -1;
29. }
30.  

 

The algorithms above are the general way to do a weighted selection. For the specific purpose you mention in the OP though, a moving bell-curve might be more what you're looking for. The biggest question would be:
Should there always be a (low) chance to get any item, like getting item 50 at the very start of the level, or should it be a limited range (which moves over time)?

In the latter case, something like:

Code (csharp):

1. // Bell curve centered on zero that ranges from -19 to +19
2. int curve = Mathf.Random(0,20) + Mathf.Random(0,20) - 19;
3. int result = Mathf.Clamp(difficulty + curve, 0, results.Length-1);

Where difficulty is a number that rises from 0 -> 50 over the course of the level. The clamp will produce a lot of the first/last item when you're near that end of the scale; to avoid that you could re-randomize instead if it falls outside the range.

 

Honestly, because my mind got stuck on a single track, and I failed to think a little more carefully or research more fully.

There are other issues that I see a lot that bug me in terms of minute details. For example, in your code you used Random.value (which includes the upper bound of 1.0f), and then used a less-than-or-equal comparison to do the probability checks. Those aspects combined mean that there is a very tiny bias towards the earlier indices, even if all the weights are identical. Hardly relevant for the vast majority of games I know, but these are the things that keep me up at night, overlooking the stupid inefficiency of my overall algorithm. Now I will definitely be updating the weighted random selection in my asset to correct this oversight, so I thank you!

And Errorsatz makes an excellent point that the problem at hand might actually benefit more from a convenient and automatic shaping of the distribution curve, rather than having to manually specify the weights of every item for every level.

 

If you need a distribution curve, I'd highly recommend setting up an AnimationCurve, and using it to design your curve in-editor (that might also be a feature your asset could benefit from, @AndyGainey). Very simple, and very effective for a variety of situations where you want a two-axis curve.

 

Totally agree, that really annoys me as well.

It's why in the code that I actually use, which can be found in the link, I implement my own IRandom interface that supports either the Unity random (with the range fixed) as well as Microsoft's Random, and any custom ones that could be implemented.

 

This. Animation curves are surprisingly versatile. They are my go to for any data transformations where the underlying model does not fall into an obvious equation. Its pretty easy to set up a curve that converts input from Random to input on your specified distribution curve. If you use a cumulative probability curve the math is just a single line.

Code (CSharp):

1. public AnimationCurve cumulativeProbability;
2.  
3. public int GetRandomItem (int noOfItems){
4.     return noOfItems * (int)cumulativeProbablity.Evaluate(Random.value);
5. }

The advantage of this system is you never have to explicitly calculate probabilities for each item. It also does not care how many items you have. You can just draw a vague curve weighted towards the beginning, and see what happens. If it doesn't feel right, you can drag a few key frames around and try again.

You could go one step further and use a set of animation curves to drive the key frames on your cumulative curve. Thus changing the distribution over time. This is slightly more complex, but its still the same idea.

 

Thanks for all the replies.

I don't know why I didn't think of using an animation curve before now, I do it all the time in maya. I guess I don't think of unity as an animation package and so forgot all about animation curves.

Thanks again, I have a few ideas to play with now.

 

This is the easiest solution
Unity Best Practices:Weighted Randomizer - Part1

 

where does total come from? You've not declared it, passed it in, or calculated it

 

This thread is a bit old... so I'm not sure exactly, but I probably wrote that in notepad, or even directly here in the browser as I often do.

And looking at it, total is probably supposed to be 't'.

 

Fixed the errors. Should be pastable now without any issues!

Code (CSharp):

1. public int GetRandomWeightedIndex(float[] weights)
2.         {
3.             if (weights == null || weights.Length == 0) return -1;
4.  
5.             float w;
6.             float t = 0;
7.             int i;
8.             for (i = 0; i < weights.Length; i++)
9.             {
10.                 w = weights[i];
11.  
12.                 if (float.IsPositiveInfinity(w))
13.                 {
14.                     return i;
15.                 }
16.                 else if (w >= 0f && !float.IsNaN(w))
17.                 {
18.                     t += weights[i];
19.                 }
20.             }
21.  
22.             float r = Random.value;
23.             float s = 0f;
24.  
25.             for (i = 0; i < weights.Length; i++)
26.             {
27.                 w = weights[i];
28.                 if (float.IsNaN(w) || w <= 0f) continue;
29.  
30.                 s += w / t;
31.                 if (s >= r) return i;
32.             }
33.  
34.             return -1;
35.         }

 

in foreach loop there should be line
weightSum += i;
NOT weightSum += weights; !!!!!

 

? No, that doesn't make any sense. Are you sure you understand the idea behind the algorithm? weightSum should be the sum of all weights, not the number of weights.