I've made an algorithm that takes as input a list of events and returns the only one that occurred (The algorithm makes sure that only one event will occur and the one with the highest probability should be more likely to occur).
The way that it works is by looping through the events, checking each event if it occurred and if not it removes it from the list until there is only one event left. Because the events with probabilities closer to 0 are more likely to be removed, then it is more likely that the one that is left is actually the event with the highest probability.
Because there is a chance that the loop will never terminate, or take a lot of iterations until it does, I stop the loop if a number of tries have been reached. This is actually a really rare situation but I must make sure the algorithm won't starve my game framerate.
Also if anyone knows a better way to achieve this, I'm listening!
I've done some tests and it seems to be working pretty great!
Results (Right-click the image below and open it in a new tab to see it better):
using System.Collections.Generic;
using UnityEngine;
public class Probability
{
private static readonly System.Random m_Rand = new System.Random();
/*
* @param probability The probability to check for a chance.
* @return True or False. The closer to 1 the higher the chance to return true.
*/
public static bool Chance(float probability)
{
//Make sure the probability is in the range [0,1].
if (Debug.isDebugBuild)
Debug.Assert(probability >= 0 && probability <= 1, "Probability must be a number in [0,1]");
return (float)m_Rand.NextDouble() < probability;
}
/*
* @param probabilities A List<KeyValuePair<string, float>> with the value representing the probability.
* @return The key (string) of the probability that occured.
*/
public static string OnlyOneWillOccur(List<KeyValuePair<string, float>> probabilities, int tries = 10)
{
//Logging stuff.
if (Debug.isDebugBuild)
{
//Empty array assert.
Debug.Assert(probabilities.Count > 0, "There is no point using this method with an empty list.");
//Check the number of tries.
Debug.Assert(tries >= 10 && tries <= 40, "Tries should be in the range of [10,40] for better performance.");
//In debug build, check if the probabilities sum up to 1.
float sum = 0;
foreach (KeyValuePair<string, float> pair in probabilities)
sum += pair.Value;
Debug.Assert(sum == 1, "The sum of the probabilities must be equal to 1");
}
//Clone the original probabilities list.
List<KeyValuePair<string, float>> probabs = new List<KeyValuePair<string, float>>(probabilities);
//Number of tries. If foreach #1 does not get a Chance() that produces
//false, then current_tries should be increamented!!!
int current_tries = 0;
//Loop until you reached all the tries or the probabilities array has only one item.
while (current_tries < tries && probabs.Count > 1)
{
//To be removed helper list.
List<KeyValuePair<string, float>> toBeRemoved = new List<KeyValuePair<string, float>>();
//Just a flag.
bool shouldIncreaseTry = true;
//foreach #1
foreach (KeyValuePair<string, float> pair in probabs)
{
if (Probability.Chance(pair.Value) == false)
{
toBeRemoved.Add(pair);
shouldIncreaseTry = false;
}
}
//Increase the number of tries.
if (shouldIncreaseTry)
current_tries++;
//If all the items are going to be removed from the probabs list.
//Reset the algorithm and increase the tries counter.
if (toBeRemoved.Count == probabs.Count)
{
current_tries++;
probabs = new List<KeyValuePair<string, float>>(probabilities);
continue;
}
//Remove all the toBeRemoved key-value pairs from the probabilities.
foreach (KeyValuePair<string, float> pair in toBeRemoved)
{
//Make sure the probabilities won't go empty!!!
if (probabs.Count == 1)
break;
//Remove the next item.
probabs.Remove(pair);
}
}
//Only one item in the list.
if (probabs.Count == 1)
return probabs[0].Key;
//THE FOLLOWING SHOULD BE REALLY RARE TO HAPPEN.
//More than one items in the list. Return one randomly.
else if (probabs.Count > 1)
return probabs[m_Rand.Next(0, probabs.Count)].Key;
//This line should never be reached!!!
if (Debug.isDebugBuild)
Debug.Assert(false, "This line should never be reached. The code above should make sure that there is at least 1 item in the probabs array!");
return null;
}
}
