Game Design/theory, Loot Drop Chance/Spawn Rate

Question

I have a very specific and long-winded question for you all. This question is both about programming and game-theory. I recently added spawnable ore to my Turn Based Strategy Game: http://imgur.com/gallery/0F5D5Ij (For those of you that look please forgive the development textures).

Now, onto the enigma that I have been contemplating. In my game, ore is generated each time a new map is created. 0-8 ore nodes are generated per level-creation. I already have this working; except it only generates "Emeraldite" at this point, which brings me to my question.

How would I, the programmer, make it so nodes have specific rarity? Consider this short mockup which is not actually game data:

(Pseudo Chances that a node will be one of the following)

Bloodstone 1 in 100
Default(Empty Node) 1 in 10
Copper 1 in 15
Emeraldite 1 in 35
Gold 1 in 50
Heronite 1 in 60
Platinum 1 in 60
Shadownite 1 in 75
Silver 1 in 35
Soranite 1 in 1000
Umbrarite 1 in 1000
Cobalt 1 in 75
Iron 1 in 15

I want to make it so that a generated node could be, theoretically, any of the above, however, with the odds also considered. I hope that question is clear enough. I have been trying to wrap my head around this, and even tried to write out a few if statements with randoms, however, I keep coming up empty handed.

Basically, I just want you guys to see my issue, and hopefully provide me with some insight on how I could approach this in a dynamic kind of way.

If any clarification is needed, please ask; sorry again if this was convoluted.

(I am adding C# as a tag only because that is the language I am using for this project)

Answer 1

I'd first represent the probability of each loot type as a simple number. A probability in pure mathematics is conventionally expressed as a floating point number in the range 0 to 1, but for efficiency, you can use integers in any (large enough) range (each value is the 0-1 value multiplied by the maximum (which I'm calling MaxProbability here)).

e.g. Bloodstone (1 in 100) is 1/100 = 0.01, or MaxProbability * (1/100).
     Copper (1 in 15) is 1/15 = 0.06667, or MaxProbability * (1/15).

I'm assuming that 'Default (Empty Node)' means the probability of none of the others. In this case, the simplest way is not to define it - you get it if none of the others are chosen.

If 'Default' was included, the sum of all these probabilities would be 1 (i.e. 100%) (or MaxProbability, if using integers).

The 1/10 probability of 'Default' in your example is actually a contradiction because the total of all those probabilities is not 1 (it's 0.38247619 - the sum of the probability as calculated in my examples above).

Then you would choose a random number in the range 0 to 1 (or MaxProbability if using integers), and the chosen loot type is the first one in the list such that the sum of the probabilities of it and all previous ones ("cumulative probability") is greater than the random number.

e.g.

MaxProbability = 1000   (I'm using this to make it easy to read).
     (For accurate probabilities, you could use 0x7FFFFFFF).

Type                 Probability  Cumulative
----                 -----------  ----------
Bloodstone             10            10              (0..9 yield Bloodstone)
Copper                 67            77    (10+67)   (10..76 yield Copper)
Emeraldite             29           105    (77+29)
Gold                   20           125    etc.
Heronite               17           142
Platinum               17           159
Shadownite             13           172
Silver                 29           200
Soranite                1           201
Umbrarite               1           202
Cobalt                 13           216
Iron                   67           282

Default (Empty Node) 7175          1000   (anything else)

e.g. If your random number in the range 0 to 999 (inclusive) was 184 (or anything in the range 172 to 199), you would choose "Silver" (the first one with cumulative probability greater than this).

You could hold the cumulative probabilities in an array and loop through it until you find one higher than the random number, or reach the end.

The order of the list does not matter. You chose a random number only once per instance.

Including 'Default (Empty Node)' in the list means that the last cumulative probability will always be MaxProbability and the loop that searches it would never go past the end. (Alternatively, 'Default' can be omitted, and you choose it if the loop reaches the end of the list.)

Note that choosing a random number for each one in turn, e.g. a 1/10 chance of 'Bloodstone', then a 1/15 chance of Copper if not Bloodstone, skews the probabilities towards the earlier items: The actual probability of Copper would be (1/15) * (1 - (1/10)) - 10% less than 1/15.

Here's code to do it (the actual choosing is 5 statements - in the method Choose ).

using System;

namespace ConsoleApplication1
{
    class LootChooser
    {
        /// <summary>
        /// Choose a random loot type.
        /// </summary>
        public LootType Choose()
        {
            LootType lootType = 0;         // start at first one
            int randomValue = _rnd.Next(MaxProbability);
            while (_lootProbabilites[(int)lootType] <= randomValue)
            {
                lootType++;         // next loot type
            }
            return lootType;
        }

        /// <summary>
        /// The loot types.
        /// </summary>
        public enum LootType
        {
            Bloodstone, Copper, Emeraldite, Gold, Heronite, Platinum,
            Shadownite, Silver, Soranite, Umbrarite, Cobalt, Iron, Default
        };

        /// <summary>
        /// Cumulative probabilities - each entry corresponds to the member of LootType in the corresponding position.
        /// </summary>
        protected int[] _lootProbabilites = new int[]
        {
            10, 77, 105, 125, 142, 159, 172, 200, 201, 202, 216, 282,  // (from the table in the answer - I used a spreadsheet to generate these)
            MaxProbability
        };

        /// <summary>
        /// The range of the probability values (dividing a value in _lootProbabilites by this would give a probability in the range 0..1).
        /// </summary>
        protected const int MaxProbability = 1000;

        protected Random _rnd = new Random((int)(DateTime.Now.Ticks & 0x7FFFFFFF));    


        /// <summary>
        /// Simple 'main' to demonstrate.
        /// </summary>
        /// <param name="args"></param>
        static void Main(string[] args)
        {
            var chooser = new LootChooser();
            for(int n=0; n < 100; n++)
                Console.Out.WriteLine(chooser.Choose());
        }           
    }
}

Answer 2

You could rewrite all chances so that they use the same divisor (e.g. 1000), your chances then become

• Bloodstone 10 in 1000
• Default(Empty Node) 100 in 1000
• Gold 20 in 1000

Next, create an array of a 1000 elements, and fill it with
10 Bloodstone elements,
100 Empty elements,
20 Gold elements,
etc.

Finally, generate a random number between 0 and 1000, and use that as the index into the element array, this will give you your random element.

You might have to play with the chances a bit, since you'll probably want all 1000 array elements to be filled, but this is the general idea.

edit its not the most efficient implementation (at least in terms of memory usage, its running time should be good), but I chose this since it allows for a concise explanation that doesn't require a whole lot of math.