Search Unity

Understanding andeeeee's Randomising/shuffling library

Discussion in 'Scripting' started by rayfigs, Sep 4, 2015.

  1. rayfigs

    rayfigs

    Joined:
    Feb 8, 2009
    Posts:
    41
    Hi, I was looking for an example on how to generate weighted random values via a script. In my findings I found andeeeee's Randomising library which seems like it would do what I want but I just don't understand how to assign weighted values to the sample method.

    I see that Sample accepts two properties a float array and a float, if I had 3 values 1,2,3 and wanted 1 to have 90% probability of showing and 2 with 5% and 3 with 5%, what would that look like?

    The link to the library is:
    http://forum.unity3d.com/threads/randomising-shuffling-library.29977/

    The full script is:

    Code (CSharp):
    1. using UnityEngine;
    2. using System.Collections;
    3.  
    4. public class RandFuncs {
    5.  
    6. //    Return an array of integers containing the numbers from zero to num.
    7.     public static int[] Indices(int num) {
    8.         int[] result = new int[num];
    9.        
    10.         for (int i = 0; i < result.Length; i++) {
    11.             result[i] = i;
    12.         }
    13.        
    14.         return result;
    15.     }
    16.    
    17.  
    18. //    Uniform random number, 0..1 range.
    19.     public static float Rnd() {
    20.         return Random.value;
    21.     }
    22.    
    23.  
    24. //    Random integer in the range first..last-1.
    25.     public static int RndRange(int first, int last) {
    26.         return Random.Range(first, last);
    27.     }
    28.  
    29.    
    30. //    As above, but the start of the range is assumed to be zero.
    31.     public static int RndRange(int last) {
    32.         return Random.Range(0, last);
    33.     }
    34.  
    35.  
    36. //    Random shuffling of the supplied integer array.
    37.     public static void Shuffle(int[] ints) {
    38.         int temp;
    39.        
    40.         for (int i = 0; i < ints.Length; i++) {
    41.             temp = ints[i];
    42.             int swapIndex = RndRange(ints.Length);
    43.             ints[i] = ints[swapIndex];
    44.             ints[swapIndex] = temp;
    45.         }
    46.     }
    47.    
    48.  
    49. //    Sum of the values in the supplied integer array.
    50.     public static int Sum(int[] ints) {
    51.         int result = 0;
    52.        
    53.         for (int i = 0; i < ints.Length; i++) {
    54.             result += ints[i];
    55.         }
    56.        
    57.         return result;
    58.     }
    59.    
    60.  
    61. //    Sum of the values in the supplied float array.  
    62.     public static float Sum(float[] floats) {
    63.         float result = 0f;
    64.        
    65.         for (int i = 0; i < floats.Length; i++) {
    66.             result += floats[i];
    67.         }
    68.        
    69.         return result;
    70.     }
    71.    
    72.  
    73. //    Choose an integer at random, according to the supplied distribution.
    74.     public static int Sample(float[] distro, float total) {
    75.         float randVal = total * Rnd();
    76.        
    77.         for (int i = 0; i < distro.Length; i++) {
    78.             if (randVal < distro[i]) {
    79.                 return i;
    80.             }
    81.            
    82.             randVal -= distro[i];
    83.         }
    84.        
    85.         return distro.Length - 1;
    86.     }
    87.    
    88.  
    89. //    As above, but calculate the total too.
    90.     public static int Sample(float[] distro) {
    91.         float total = Sum(distro);
    92.         return Sample(distro, total);
    93.     }
    94.  
    95.  
    96. //    Sample several items without replacement.
    97.     public static int[] SampleRemove(int maxNum, int numSamples) {
    98.         int[] result = new int[numSamples];
    99.         int numNeeded = numSamples;
    100.        
    101.         for (int numLeft = maxNum; numLeft > 0; numLeft--) {
    102.             float chance = (float) numNeeded / (float) numLeft;
    103.            
    104.             if (Rnd() < chance) {
    105.                 result[--numNeeded] = numLeft - 1;
    106.             }
    107.            
    108.             if (numNeeded == 0) {
    109.                 break;
    110.             }
    111.         }
    112.        
    113.         if (numNeeded != 0) {
    114.             result[0] = 0;
    115.         }
    116.        
    117.         return result;
    118.     }
    119.    
    120.  
    121. //    Make a string representation of an integer array.  
    122.     public static string Dump(int[] ints) {
    123.         if (ints.Length == 0) {
    124.             return "<Empty>";
    125.         }
    126.        
    127.         string result = ints[0].ToString();
    128.        
    129.         for (int i = 1; i < ints.Length; i++) {
    130.             result += ", " + ints[i].ToString();
    131.         }
    132.        
    133.         return result;
    134.     }
    135.    
    136.  
    137. //    Make a string representation of a float array.  
    138.     public static string Dump(float[] floats) {
    139.         if (floats.Length == 0) {
    140.             return "<Empty>";
    141.         }
    142.        
    143.         string result = floats[0].ToString();
    144.        
    145.         for (int i = 1; i < floats.Length; i++) {
    146.             result += ", " + floats[i].ToString();
    147.         }
    148.        
    149.         return result;
    150.     }
    151. }
    152.  
    153.  
    154. //    Class to perform fast sampling without replacement from a distribution. This
    155. //    has a linear time preprocessing step that is performed before sampling
    156. //    takes place.
    157. public class FastSample {
    158.     float[] distro;
    159.     int[] aliases;
    160.     float mean;
    161.    
    162.    
    163.     public FastSample(params float[] initDistro) {
    164.         distro = new float[initDistro.Length];
    165.         float total = 0f;
    166.        
    167.         for (int i = 0; i < distro.Length; i++) {
    168.             distro[i] = initDistro[i];
    169.             total += distro[i];
    170.         }
    171.        
    172.         Debug.Log(string.Format("Distro: {0}", RandFuncs.Dump(distro)));
    173.  
    174.        
    175.         mean = total / (float) distro.Length;
    176.        
    177.         Debug.Log(string.Format("Mean: {0}", mean));
    178.        
    179.         int[] sep = new int[distro.Length];
    180.        
    181.         int shortMarker = 0;
    182.         int tallMarker = sep.Length - 1;
    183.        
    184.         for (int i = 0; i < distro.Length; i++) {
    185.             if (distro[i] < mean) {
    186.                 sep[shortMarker++] = i;
    187.             } else {
    188.                 sep[tallMarker--] = i;
    189.             }
    190.         }
    191.        
    192.         Debug.Log(string.Format("Sep: {0}", RandFuncs.Dump(sep)));
    193.         tallMarker++;
    194.        
    195.         Debug.Log(string.Format("Tall marker: {0}", tallMarker));
    196.  
    197.        
    198.         aliases = new int[distro.Length];
    199.        
    200.         for (int i = 0; i < (sep.Length - 1); i++) {
    201.             int curr = sep[i];
    202.             float shortfall = mean - distro[curr];
    203.             int firstTall = sep[tallMarker];
    204.             distro[firstTall] -= shortfall;
    205.             aliases[curr] = firstTall;
    206.            
    207.             if (distro[firstTall] < mean) {
    208.                 tallMarker++;
    209.             }
    210.         }
    211.        
    212.         aliases[sep[sep.Length - 1]] = sep[sep.Length - 1];
    213.     }
    214.    
    215.    
    216.     public int Next() {
    217.         float rndVal = RandFuncs.Rnd() * (float) distro.Length;
    218.         int slotNum = Mathf.Min(Mathf.FloorToInt(rndVal), distro.Length - 1);
    219.         float fracPart = (rndVal - (float) slotNum) * mean;
    220.        
    221.         if (fracPart < distro[slotNum]) {
    222.             return slotNum;
    223.         } else {
    224.             return aliases[slotNum];
    225.         }
    226.     }
    227. }
    And the method I think I need is:

    Code (CSharp):
    1. /    Choose an integer at random, according to the supplied distribution.
    2.     public static int Sample(float[] distro, float total) {
    3.         float randVal = total * Rnd();
    4.        
    5.         for (int i = 0; i < distro.Length; i++) {
    6.             if (randVal < distro[i]) {
    7.                 return i;
    8.             }
    9.            
    10.             randVal -= distro[i];
    11.         }
    12.        
    13.         return distro.Length - 1;
    14.     }
    15.    
    If I submit an array to the method, how will the weighted value be assigned to the various elements? I'm sure it has something to do with the fact that the method is static and I don't fully understand what that means. Any help with understanding how to get this to work would be helpful.

    Many thanks,
    Reinaldo