How can I spawn items based on probabilities?

Question

I'm working on a game where I want to choose which object to spawn based on probabilities. Assuming the decision to spawn the object has been done by some other process, I'd like the object with the highest probability to have a higher chance of being spawned. An object with 50% spawn probability should spawn more often than an object with 15% spawn probability. I also need to account for instance where a game object has the same spawn probability

GameObject 1 .50 
GameObject 2 .25
GameObject 3 .25 

How can I implement this logic?

Answer 1

There are different ways of doing this. Here I am giving two ways of getting a weighted game object. The first one is easy but not a good practice and has a lot of issues. I have commented on the code so that you can easily understand. If you have any confusion feel free to tell me here.

using System.Linq;
public class RandomObject
{
  public GameObject randomObj;
  public int priority;

}

public class CumilativeSelection
{
  public List<RandomObject> objectList;
  System.Random rnd = new System.Random();
// This logic is straught forward but might not be currect always (Not a good choice)
// 1. You pick a value from 1 to 10 (or may be 1 to 100 whatever)
// 2. Probability of having 1 is 1/10, 2 is 1/10 and so on (Uniform Destribution) .So the
//    Probability of having 1 to 4 is (1/10 + 1/10 + 1/10 + 1/10) = 0.4 or 40%
// 3. Now you can spawn on a particular object with a 40% of probability.
void EasyRandom() 
{

    int val = rnd.Next(1, 10);
    if(val<2)
    {
        //10% probabilty of coming to this block
        //Spawn an object which has 10% probability
        //1/10 = 0.1
    }
    else if (val < 6)
    {
        //50% probabilty
        // 1/10 + 1/10 + 1/10 + 1/10 + 1/10 + 1/10 = 5/10 = 0.5
    }
    //And so on
}


// This logic is called the Cumilative Destribution Function. More accurate and a bit
// complex. To learn more go to link: http://www.vcskicks.com/random-element.php This 
// guy had made the explanation really easy. My logic is kind of similar to him with a few 
// variation.

GameObject GetObjectWithMaxProb()
{
    int totalWeight = objectList.Sum(t => t.priority); // Using LINQ for suming up all the values
    int randomNumber = rnd.Next(0, totalWeight);

    GameObject myGameObject = null;
    foreach (RandomObject item in objectList)
    {
        if(randomNumber < item.priority)
        {
            myGameObject = item.randomObj;
            break;
        }
        randomNumber -= item.priority;
    }
    return myGameObject;
}

So, what we are basically doing here is picking a random value between zero and the total weight. Then, just checking which of the item has more priority than the random number just generated and return that game object. I have tested the second function with unity and it did a great work giving the object with most probability. I have uploaded the full project to github if you want to check. https://github.com/Shubhra22/WeightedRandom.git

Answer 2

In genetic programming, this is called the roulette selection function/algorithm. Here's one way to implement it:

int selectFromRoulette(double[] weight, Random rng) {
    double total = 0;
    double amount = rng.nextDouble();
    for(int a=0; a<weight.length; a++){
        total += weight[a];
        if(amount <= total){
            return a;
        }
    }
    return -1;
}

The above code takes an array of mutually exclusive probabilities (weights) and randomly selects one of them. If the probabilities sum up to less than 100%, there's a chance than none of them will get selected - in that situation, the method will return -1. It assumes that the sum of the probabilities doesn't exceed 100%. Also, keep in mind that testing for equality of floating numbers is error prone, so you probably don't want this exact solution if you're making casino games.

Answer 3

Yes. This is quite similar to how you do what is called a "weighted average".

Your rand() function needs to be able to take a range as floats, many do not.

OTOH, if your probabilities are always going to be percentages, consider storing them as unsigned integers instead. Once upon a time, that would have been a no-brainer, but these days floating point operations are cheap and memory access is expensive. Why when I was your age...

OTOOH, if your language frees you from such concerns, then never mind that crusty ol guy sitting in my chair.

Answer 4

Since your probabilities sum up to 1, you can basically loop through the objects adding the previous probability to the probability to select the object (this basically generates a probability density function). More clearly:

r = U(0,1) // random value drawn from a uniform distribution
if r <= p_1 // if the random value is smaller than the probability to call object 1
    obj = 1 // call object 1
else if r <= (p_1 + p_2) // else, compute probability to call object 2, and check if it applies
    obj = 2
else if r <= (p_1 + p_2 + p_3) // else compute probability 3...
    obj = 3

Since r is uniformly distributed, you will have the right proportion of object 1, 2 and 3.

Of course, in code, you would probably have a vector of gameObjects with their corresponding probabilities (make sure the probability vector sums to 1).

Example (in c#):

GameObject[] myGoArray = new GameObject[]{go1,go2,go3};
float[] myAssociateProb = new float[]{.5f,.25f,.25f};

float r = Random.Range(0f,1f);
GameObject selectedGo;
float currentProb = myAssociateProb[0];
for(int i = 0; i < myGoArray.Length; i++){
    if(r <= currentProb){
        selectedGo = myGoArray[i];
        break;
    }
    currentProb += myAssociateProb[i + 1];
}