Game Design/theory, Loot Drop Chance/Spawn Rate
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
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());
}
}
}