CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 7 of 7
  1. #1
    Join Date
    Jul 2017
    Location
    Greece
    Posts
    129

    Question 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.

  2. #2
    Join Date
    Feb 2017
    Posts
    620

    Re: How to generate a condition (true or false) based on possibilities?

    Quote Originally Posted by babaliaris View Post
    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.

  3. #3
    Join Date
    Feb 2017
    Posts
    620

    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.

  4. #4
    VictorN's Avatar
    VictorN is offline Super Moderator Power Poster
    Join Date
    Jan 2003
    Location
    Hanover Germany
    Posts
    20,097

    Re: How to generate a condition (true or false) based on possibilities?

    Quote Originally Posted by wolle View Post
    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

  5. #5
    Join Date
    Jul 2017
    Location
    Greece
    Posts
    129

    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.

  6. #6
    Join Date
    Feb 2017
    Posts
    620

    Re: How to generate a condition (true or false) based on possibilities?

    Quote Originally Posted by babaliaris View Post
    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.

  7. #7
    GCDEF is offline Elite Member Power Poster
    Join Date
    Nov 2003
    Location
    Florida
    Posts
    12,624

    Re: How to generate a condition (true or false) based on possibilities?

    Quote Originally Posted by babaliaris View Post
    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
  •  





Click Here to Expand Forum to Full Width

Featured