Search Unity

  1. Megacity Metro Demo now available. Download now.
    Dismiss Notice
  2. Unity support for visionOS is now available. Learn more in our blog post.
    Dismiss Notice

Random Number Generator

Discussion in 'Scripting' started by smittywerbenjagermanjensensen, Dec 6, 2021.

  1. smittywerbenjagermanjensensen

    smittywerbenjagermanjensensen

    Joined:
    Sep 16, 2021
    Posts:
    20
    How would I go about doing a random number generator in this way. Basically there are three variables and a percentage chance that something would happen based on how big the variables are. Like if two variables value was 5 and one was 10 the one that was 10 would be more likely to happen in percentage chance. It would have be not determinant on the specific numbers but on how big the numbers are in relation to each other. Im still new and dont really know how to do this.
     
  2. lordofduct

    lordofduct

    Joined:
    Oct 3, 2011
    Posts:
    8,513
    If you're saying you want to calculate the odds for each entry based on some 'weight'.

    ...

    Well I went to go look for some threads from years ago where I talk about this very thing.

    BUT, instead, it turns out Unity has created an article in their documentation all about it:
    https://docs.unity3d.com/2019.3/Documentation/Manual/RandomNumbers.html

    You want the section about "Choosing Items with Different Probabilities".

    Note that even though they describe it with numbers adding up to 100... that doesn't actually matter. Since they sum up all the probabilities, then calculate from that. It all works out in the end.

    Basically it'll sum 5 and 10 making 15. Then it'll take a random value from 0-15. Then it will find which entry it fits in the range of. Resulting in a 33% chance for the 5, and a 66% chance for the 10.
     
    ritesh_khokhani likes this.
  3. smittywerbenjagermanjensensen

    smittywerbenjagermanjensensen

    Joined:
    Sep 16, 2021
    Posts:
    20
    Code (CSharp):
    1.     float Choose (float[] probs) {
    2.  
    3.         float total = 0;
    4.  
    5.         foreach (float elem in probs) {
    6.             total += elem;
    7.         }
    8.  
    9.         float randomPoint = Random.value * total;
    10.  
    11.         for (int i= 0; i < probs.Length; i++) {
    12.             if (randomPoint < probs[i]) {
    13.                 return i;
    14.             }
    15.             else {
    16.                 randomPoint -= probs[i];
    17.             }
    18.         }
    19.         return probs.Length - 1;
    20.     }
    21.  
    This seems to be what I want but how would I put in multiple variables. Like if the variables names were a b and c. I don't really know how I would write it again im still fairly new
     
  4. exiguous

    exiguous

    Joined:
    Nov 21, 2010
    Posts:
    1,749
    Just search the AssetStore for "weighted random". There are 4 free solutions. Use one of these for fast results.

    If you want to do it yourself and/or learn:
    Usually you would have some kind of class or struct which has some absolute and relative value, a cumulative relative value and the "thing" you want to retrive (fe an item). Then you add instances of this class/struct to your list and give them an abs value and the item. When you have added all of them you iterate the list and sum the abs values up (this can already be done while adding the elements to the list). Then you iterate again and divide the abs value of each entry by the sum of all abs values. You store this in relative value of each entry. And you sum those relative values up to the current item and store this in cumulative value.
    When you need a weighted random thing you just generate a random value fe 0.73. and iterate until the random number is between the "borders" of an entry.

    Example of the algorithm:
    A = 20,
    B = 50,
    C = 10,
    sum = 80
    A rel = 20/80 = 0.25
    B rel = 50/80 = 0.625
    C rel = 10/80 = 0.125 (those relative values should sum up tp 1!)
    A cum = 0.25
    B cum = 0.875
    C cum = 1
    Check wether your random number is between 0 and Acum -> return A
    Check wether rand val between Acum and Bcum -> return B
    Check wether rand val between Bcum and Ccum -> return C
    So with our example random value of 0.73 we would choose B since it is between 0.25 and 0.875.

    So you probably want some class as "manager" to handle a list of those weights and items. Which returns one item with a given 0-1 number etc.. Also keep in mind that you need to recalculate sum, rel values and cumulative relative values when you add or remove items from this list.

    Hope that helps.
     
    ritesh_khokhani likes this.
  5. Rand_D

    Rand_D

    Joined:
    Oct 24, 2017
    Posts:
    44
  6. Bunny83

    Bunny83

    Joined:
    Oct 18, 2010
    Posts:
    3,913
    Well, the first algorithm just does the most simple and straight forward: "replace processing power with memory" approach. While it is true that a single roll would have a constant time, it has several limitations. It highly depends on the number of elements in your weighted list and what the extreme values for the weights are. If you allow weight values like 1000 and weights like 0.0001, your lookup array would need 10 million elements, even for just two elements. Yes, a lookup table can be more efficient if you have a really large number of elements (100+) and the weights are in a relative close range. Since the idea of the approach is to divide the fair range into equal buckets which represent the smallest weight, this would not scale well, if arbitrary weight values are allowed. A lot of games (thinking of minecraft or any mods) often allow extremely low weights for rare items but quite high weights for common things. This would waste a lot of memory.

    The last one mentioned is essentially the same as the linear approach, just optimised with a binary search. Yes, you can do that, but again it only matters if you really have a lot of elements which a relatively high number of the highest probability. This may sound confusing but let me explain. Just for the sake of argument, lets assume the largest weight has 50%, the second largest weight has 25% and the remaining 25% are all the remaining smaller weights (in case of 100 elements that would be 98 relatively small weights). So the linear algorithm would in 75% of the time return in just one of two steps. So a binary search wouldn't much improve the average case here. However if all those 100 items have the same probability of just 1%, the linear algorithm would of course vary from O(1) up to O(n).

    Of course it depends on how you would implement the binary distribution for your search. You can split up the number of elements in equal buckets, in that case the average runtime would be worse than the linear approach in the case of a few high valued weights. It's also possible to seperage the whole range into equal buckets and doing an ordinary binary search across the whole weight range. Though this would not result in a balanced binary tree if the weights are heavily different.

    Sure, as I said, if the number of elements is really high, implementing a binary search would probably improve the average runtime, but makes the best runtime worse and the worst runtime better. Though I wouldn't consider implementing a binary search if I only have about 100 items to choose from. Especially if this is just for something like loot generation. To stick with MC: If it's about ore distribution I may consider using a binary search or lookup table. If extreme values are necessary, you have really a lot values to choose from and you need high performance, you can also use a hybrid system by using a two or more staged lookup table. So the last smallest bucket in the first LUT would cover all the small values in a seperate LUT. This may cut a single 1M LUT into two with about 1k elements.

    There simply is no go-to solution that fits all needs perfectly.
     
    Yoreki and orionsyndrome like this.
  7. orionsyndrome

    orionsyndrome

    Joined:
    May 4, 2014
    Posts:
    3,070
    I'd only add that for the drops a lookup isn't a satisfying solution. Many of the reasons are already stated by Bunny.

    And if you need it for some kind of generation, you can probably prebake entire distribution.

    So in either case, you don't really want a lookup. Maybe there are other cases I cannot think of at the moment where this pays of. But you can always make simple weight-based distribution trees and play with the Pareto principle, where high probability items take 80% of the pie, and then recursively slice off the remaining 20%, nesting smaller and smaller chances in a manner that is easy to implement and design.

    My algorithm of choice is a linear search, because it's not the search algorithm that needs love, but the distribution model itself. You can always design the model to guarantee "the fate to be decided" in no more than X iterations, the evaluation of which is typically almost as fast as the actual number generation. So why bother?
     
    Bunny83 likes this.
  8. Rand_D

    Rand_D

    Joined:
    Oct 24, 2017
    Posts:
    44
    I do agree with Bunny in that there is no solution to fit all needs. Also want to add to the discussion a case that where a pre-init LUT can be a better choice compare to linear search. Think of when a player chooses to open 100 chests in one go(like those cs:go case opening stream). Assume the weight of each item in each chest stays the same, then for every chest the linear search needs to run again. Compare to a LUT when you only need to init it once in memory, and then just select item in O(1) per chest. Also if the selection is performed by server, I do think it might benefit to go for LUT.
     
  9. orionsyndrome

    orionsyndrome

    Joined:
    May 4, 2014
    Posts:
    3,070
    I agree with that use case, but that's still not a one-size-fits-all. The actual approach is thus very situational.
    In other words, if in some cases a LUT is obviously better, while at the same time it's easy to imagine a scenario in which rebuilding a LUT would be an overkill, the whole discussion is moot. It's akin to whether one should use a list or a dictionary. Is one better over the other? If the answer is "it depends", then we can talk about it for ages, and never agree with each other, unless we manage to grasp the higher domain, in which both are equally legit solutions each with their own strengths and weaknesses.