-
January 13th, 2021, 09:34 AM
#1
How to generate a condition (true or false) based on possibilities?
Hello!
10 years into programming and I never ever had to use possibilities in conditional statements. Right now, I'm making a video game and I want my enemy to choose how to roam in the map based on some possibilities that are going to change at runtime based on the player's activity:
Code:
float RandomRoamPossibility = 0.8f; //The possibility that the enemy will roam to a random position into the map.
float RoamToPlayerPossibility = 0.1f; //The possibility that the enemy will roam to a location where a player is nearby.
float GoToNextTargetPossibility = 0.1f; //The possibility that the enemy will move to the next target, defined in the current target that the enemy is located right now.
So basically I want some functionality that will take as input these numbers and return true for only one of them! Also, the higher the number is, the more possible that this is what will
be returned as true:
Code:
/**
*The higher the possibility, the more likely is that that index will be returned!
*IMPORTANT: The array must sum to 1!
*@param possibilities An array of possibilities.
*@return The index of the possibility that was randomly chosen to be true.
*/
int GetAnswer(float possibilities[])
{
}
I googled it, but couldn't find anything and possibilities and statistics was actually my weak point in maths...
Last edited by babaliaris; January 13th, 2021 at 09:37 AM.
-
January 14th, 2021, 01:37 AM
#2
Re: How to generate a condition (true or false) based on possibilities?
Originally Posted by babaliaris
So basically I want some functionality that will take as input these numbers and return true for only one of them! Also, the higher the number is, the more possible that this is what will
be returned as true:
If you have the possibilities 0.8, 0.1, and 0.1 you think of them as three intervals,
1: 0.0 <= x < 0.8
2: 0.8 <= x < 0.9
3: 0.9 <= x < 1.0
Then you draw a random float x between 0 and 1, for example like this (the C++ 11 example is the best I think),
https://www.delftstack.com/howto/cpp...tween-0-and-1/
Finally, you check which interval x belongs to. That gives you one of the 3 possibilities.
Last edited by wolle; January 14th, 2021 at 01:41 AM.
-
January 14th, 2021, 03:08 AM
#3
Re: How to generate a condition (true or false) based on possibilities?
The link in my previous reply suddenly doesn't seem to work so I supply an example. It is based on the recipe: "Generating pseudo-random numbers" in Modern C++ Programming Cookbook, 2nd ed. by Marius Bancila,
Code:
#include <iostream>
#include <random>
void test() {
std::random_device seed{}; // random seed
auto gen = std::default_random_engine{seed()}; // default random number generator
auto distr = std::uniform_real_distribution<float>{0,1}; // statistical distribution
for (int i=0; i<10; ++i) {
float x = distr(gen); // random float between 0 and 1
std::cout << x;
if (x < 0.8f) { // assign interval
std::cout << " : 1";
} else if (x < 0.9f) {
std::cout << " : 2";
} else {
std::cout << " : 3";
}
std::cout << std::endl;
}
}
Last edited by wolle; January 14th, 2021 at 03:26 AM.
-
January 14th, 2021, 04:07 AM
#4
Re: How to generate a condition (true or false) based on possibilities?
Originally Posted by wolle
The link in my previous reply suddenly doesn't seem to work so I supply an example. It is based on the recipe: "Generating pseudo-random numbers" in Modern C++ Programming Cookbook, 2nd ed. by Marius Bancila,
...
Perhaps, this one will work?
https://books.google.de/books?id=8d_...6AEwCXoECAsQAg
Victor Nijegorodov
-
January 14th, 2021, 08:01 AM
#5
Re: How to generate a condition (true or false) based on possibilities?
I'm sorry I might have not explained the problem clearly. What I'm trying to do is something like those random balls pick up where you spin them in a bowl and then you choose one randomly.
Now imagine you have 50 blue balls and 2 red. Clearly, it is more likely to choose a blue ball. This is what I'm trying to achieve.
My algorithm should take a list of events (each one with a corresponding probability) and should return only one of them, in such a way that the event with the highest probability will be more likely to be returned.
Firstly I need a method that can return true or false in a random way based on a probability. In other words, the closer the probability is to 1 the more likely it to return true, false otherwise.
Luckily I found that at StackOverflow:
It's C# code but it's ok :
Code:
/*
* @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;
}
I also figured out an algorithm to do what I want (at least I think and it seems to work great).
The algorithm takes as input a list of events and what it does is looping through them and for each one of them does the following:
Code:
if ( Chance(currentEvent.probability) == false )
//remove this event from the list.
This keeps going until there is only one event left on the list and finally returns it.
In other words, because the Chance() is more likely to return false for probabilities closer to zero, then this means that events with probabilities closer to zero will be more likely to be removed
from the list. This means that it is more likely the one that will remain in the list and finally be returned by the algorithm will be the one with the highest probability!
This algorithm needs to adjust a little bit because there is a chance that all the items will be removed from the list or even worst the loop can keep going and the list gets never down to one item
but this can easily be fixed by adding a try condition. Though the last case is really unlikely to happen.
This algorithm seems to work pretty well:
Code:
/*
* @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;
}
Last edited by babaliaris; January 14th, 2021 at 08:06 AM.
-
January 14th, 2021, 11:30 AM
#6
Re: How to generate a condition (true or false) based on possibilities?
Originally Posted by babaliaris
Now imagine you have 50 blue balls and 2 red. Clearly, it is more likely to choose a blue ball. This is what I'm trying to achieve.
In this case, you have a total of 52 balls in the urn. The chance of picking a blue is 50/52, and a red is 2/52. The total probability is 50/52 + 2/52 = 52/52 = 1 (the ball will always be either blue or red). After you draw a ball, you check its color and then put it back into the urn again.
To simulate the above urn model with the algorithm I suggested, you generate a random float x between 0 and 1. Then check which of these intervals it belongs to
0.0 <= x < 50/52 : blue
50/52 <= x < 1.0 : red
Each time you repeat this you get a ball at random with a probability of 50/52 for blue and 2/52 for red. In the long run, 96,15% of all balls you draw will be blue and 3.85% will be red. The higher the probability of the color, the more often it will show up. For all I can see, it matches your goal perfectly:
"My algorithm should take a list of events (each one with a corresponding probability) and should return only one of them, in such a way that the event with the highest probability will be more likely to be returned."
It is just to substitute "event" with "ball color".
Last edited by wolle; January 15th, 2021 at 02:40 AM.
-
January 14th, 2021, 11:33 AM
#7
Re: How to generate a condition (true or false) based on possibilities?
Originally Posted by babaliaris
I'm sorry I might have not explained the problem clearly. What I'm trying to do is something like those random balls pick up where you spin them in a bowl and then you choose one randomly.
Now imagine you have 50 blue balls and 2 red. Clearly, it is more likely to choose a blue ball. This is what I'm trying to achieve.
My algorithm should take a list of events (each one with a corresponding probability) and should return only one of them, in such a way that the event with the highest probability will be more likely to be returned.
Firstly I need a method that can return true or false in a random way based on a probability. In other words, the closer the probability is to 1 the more likely it to return true, false otherwise.
Luckily I found that at StackOverflow:
It's C# code but it's ok :
Code:
/*
* @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;
}
I also figured out an algorithm to do what I want (at least I think and it seems to work great).
The algorithm takes as input a list of events and what it does is looping through them and for each one of them does the following:
Code:
if ( Chance(currentEvent.probability) == false )
//remove this event from the list.
This keeps going until there is only one event left on the list and finally returns it.
In other words, because the Chance() is more likely to return false for probabilities closer to zero, then this means that events with probabilities closer to zero will be more likely to be removed
from the list. This means that it is more likely the one that will remain in the list and finally be returned by the algorithm will be the one with the highest probability!
This algorithm needs to adjust a little bit because there is a chance that all the items will be removed from the list or even worst the loop can keep going and the list gets never down to one item
but this can easily be fixed by adding a try condition. Though the last case is really unlikely to happen.
This algorithm seems to work pretty well:
Code:
/*
* @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;
}
You're making it way harder than it needs to be. The solution Victor proposed does what you ask. He hardcoded values for .8, .9, etc. You'll need to use your computed probabilities sorted high to low.
Another approach using your probabilities above would be to create a 10 element int array. Insert a 1 (representing Random) eight times. Use a 2 indicating Roam and insert it once. Use a 3 indicating GoTo and insert it once. Use rand() % 10 to randomly select an array element.
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|