26

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)

14
  • 5
    A random collection of if statements with randoms that I already shamefully swept aside.
    – Krythic
    Sep 23, 2014 at 9:14
  • 2
    You should share some code you've tried. That helps to solve your issues faster
    – Ghasem
    Sep 23, 2014 at 9:15
  • 14
    Also is this not better suited for gamedev.stackexchange.com instead of directly stackoverflow? As it correlates directly to game programming and also a bit game theory
    – Thomas
    Sep 23, 2014 at 9:16
  • 1
    Your stats don't add up -- you have indicated that 90% of the time you want a non-empty node .. but the chances of the ores do not add up to 90% Sep 23, 2014 at 12:57
  • 3
    This is actually called the fitness proportion/roulette wheel selection - en.wikipedia.org/wiki/Fitness_proportionate_selection
    – DanDan
    Sep 23, 2014 at 18:09

8 Answers 8

21

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());
        }           
    }
}
10
  • It was extremely hard to choose, but you did offer a coding solution, and a great explanation, therefore I choose you as the answer. However, I really wish I could accept more than one person. Still, you went above and beyond the call. Thank you.
    – Krythic
    Sep 24, 2014 at 3:38
  • 2
    10..76 should yield Copper, not 10..77. The solution is virtually the same as others, but I dislike the programming sample. It is very easy to define lootTypes/lootProbabilities in wrong order and difficult to astually check the probabiltiy of a single item (really, try to quickly tell me what is the probability of Gold?). And it requires a spreadsheet to generate the values!
    – Dariusz
    Sep 24, 2014 at 5:44
  • @Dariusz I am taking the source he provided and rewriting it fix these things. In fact, I am mish-mashing everyones opinion together, in a way.
    – Krythic
    Sep 24, 2014 at 6:37
  • @Krythic post your code after you've finished, so we can grumble at it :)
    – Dariusz
    Sep 24, 2014 at 6:45
  • @Dariusz Already finished it. imgur.com/gallery/2LLMdnR still working on it right now though. Unfortunately it became proprietary the moment I hit build. (There is a playable demo there if you're interested though) Oh, and the source code is obfuscated, sorry. =P
    – Krythic
    Sep 24, 2014 at 6:49
18

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.

12
  • So consider each one with the maximum? That makes a lot of sense actually. It is kind of reversed, but I could see it working.
    – Krythic
    Sep 23, 2014 at 9:25
  • What about nodes that have the same rarity? In other words, if two nodes have a 1 in 60 chance of being said node?
    – Krythic
    Sep 23, 2014 at 9:32
  • @Krythic They'd follow each other as normal. Also note that your 1 in 60 chance is forced to become a 17 in 1000 chance with this method: 1000 * (1/60) = 16.667. Sep 23, 2014 at 9:42
  • @Krythic As ipi says, you fill 17 of your array elements with element A, and then the following 17 array elements with element B. The order of the elements in your array doesn't matter, its the number of occurences that determines the odds. Sep 23, 2014 at 9:59
  • 1
    Thinking on this for a while, this sounds like a really good idea. The code is pretty simple. Memory usage isn't really that bad. Speed is based on the way arrays are handled by the compiler. Once the array is created, speed wise it is fast since all that is happening is a reading a array element and passing that value to the creation factory. To optimize beyond that would probably make the code more complex (not by much) and probably be a series of comparisons before the selected element is found. You will spend more time game balancing than this will run in development + CPU time.
    – BPugh
    Sep 23, 2014 at 18:03
10

First of all, specifying the the default-empty node's probability is unnecessary. The other probabilities should be defined in such a way, that the empty node is created if no other type is created.

How to do this and ensure the generation probabiltiies are equal to those you specified? In short:

  • convert the probabilities to a floating point (it's a value with a common divisor of 1)
  • sum all probabilities and check if they are < 1
  • write a class which will store the all the probabilities
  • write a function which will get a random node based on those probabilities

For your example:

Bloodstone 1 in 100 = 0.01
Copper 1 in 15 ~= 0.07
Emeraldite 1 in 35 ~= 0.03
Gold 1 in 50 = 0.02
Default = 0.87

Now the class can be implemented in at least two ways. My option consumes much memory, does the computations once, but it also rounds the probability values which may introduce some error. Note, that the error depends on the arrSize variable - the larger it is, the smaller the error.

The other option is as in Bogusz's answer. It is more precise, but required more operations per each generated element.

Option suggested by Thomas requires a lot of repeatable code for each option hence is not versatile. Shellshock's answer will have invalid effective probabilities.

Astrotrain's idea to force yourself to use the same divisor is virtually the same as my own, though the implementation would be slightly different.

Here's a sample implementation of my idea (in java, but should be ported very easily):

public class NodeEntry {

    String name;
    double probability;

    public NodeEntry(String name, double probability) {
        super();
        this.name = name;
        this.probability = probability;
    }

    public NodeEntry(String name, int howMany, int inHowMany) {
        this.name = name;
        this.probability = 1.0 * howMany / inHowMany;
    }

    public final String getName() {
        return name;
    }

    public final void setName(String name) {
        this.name = name;
    }

    public final double getProbability() {
        return probability;
    }

    public final void setProbability(double probability) {
        this.probability = probability;
    }


    @Override
    public String toString() {
        return name+"("+probability+")";
    }

    static final NodeEntry defaultNode = new NodeEntry("default", 0);
    public static final NodeEntry getDefaultNode() {
        return defaultNode;
    }

}

public class NodeGen {

    List<NodeEntry> nodeDefinitions = new LinkedList<NodeEntry>();

    public NodeGen() {
    }

    public boolean addNode(NodeEntry e) {
        return nodeDefinitions.add(e);
    }

    public boolean addAllNodes(Collection<? extends NodeEntry> c) {
        return nodeDefinitions.addAll(c);
    }



    static final int arrSize = 10000;

    NodeEntry randSource[] = new NodeEntry[arrSize];

    public void compile() {
        checkProbSum();

        int offset = 0;
        for (NodeEntry ne: nodeDefinitions) {
            int amount = (int) (ne.getProbability() * arrSize);
            for (int a=0; a<amount;a++) {
                randSource[a+offset] = ne; 
            }
            offset+=amount;
        }

        while (offset<arrSize) {
            randSource[offset] = NodeEntry.getDefaultNode();
            offset++;
        }
    }

    Random gen = new Random();

    public NodeEntry getRandomNode() {
        return randSource[gen.nextInt(arrSize)]; 
    }

    private void checkProbSum() {
        double sum = 0;

        for (NodeEntry ne: nodeDefinitions) {
            sum+=ne.getProbability();
        }

        if (sum >1) {
            throw new RuntimeException("nodes probability > 1");
        }

    }



    public static void main(String[] args) {
        NodeGen ng = new NodeGen();
        ng.addNode(new NodeEntry("Test 1", 0.1));
        ng.addNode(new NodeEntry("Test 2", 0.2));
        ng.addNode(new NodeEntry("Test 3", 0.2));

        ng.compile();

        Map<NodeEntry, Integer> resCount = new HashMap<NodeEntry, Integer>();

        int generations = 10000;
        for (int a=0; a<generations; a++) {
            NodeEntry node = ng.getRandomNode();
            Integer val = resCount.get(node);
            if (val == null) {
                resCount.put(node, new Integer(1));
            } else {
                resCount.put(node, new Integer(val+1));
            }
        }


        for (Map.Entry<NodeEntry, Integer> entry: resCount.entrySet()) {
            System.out.println(entry.getKey()+": "+entry.getValue()+" ("+(100.0*entry.getValue()/generations)+"%)");
        }
    }

}

This makes sure the probabilities are actually uniform. If you checked for the first node spawn, then the other, then the other - you would get wrong results: nodes checked first would have increased probability.

Sample run:

Test 2(0.2): 1975 (19.75%)
Test 1(0.1): 1042 (10.42%)
Test 3(0.2): 1981 (19.81%)
default(0.0): 5002 (50.02%)
3
  • And this includes the probabilty of equal-rarity nodes? In other words if two nodes have the same rarity?
    – Krythic
    Sep 23, 2014 at 9:35
  • @krythic yes it does; I've just edited it to have a better test.
    – Dariusz
    Sep 23, 2014 at 9:38
  • Let me look into this, implement it, and test it. I will get back to you tomorrow and likely accept your answer if all goes well.
    – Krythic
    Sep 23, 2014 at 9:40
4

I think that it is easy to understand how it works. (Cobalt, 20: means 1 of 20 -> 5%)

Dictionary<string, double> ore = new Dictionary<string, double>();
Random random = new Random();

private void AddOre(string Name, double Value)
{
    ore.Add(Name, 1.0 / Value);
}

private string GetOreType()
{
    double probSum = 0;
    double rand = random.NextDouble();

    foreach (var pair in ore)
    {
        probSum += pair.Value;
        if (probSum >= rand)
            return pair.Key;
    }
    return "Normal Ore";  //Reaches this point only if an error occurs.
}

private void Action()
{
    AddOre("Cobalt", 20);
    AddOre("Stone", 10);
    AddOre("Iron", 100);
    AddOre("GreenOre", 300);

        //Add Common ore and sort Dictionary
        AddOre("Common ore", 1 / (1 - ore.Values.Sum()));
        ore = ore.OrderByDescending(x => x.Value).ToDictionary(x => x.Key, x => x.Value);

    Console.WriteLine(GetOreType());
}

Edit:

I add section "Add Common ore and sort Dictionary".

6
  • 2
    Why would you divide by 1000 and then multiply by 1000 again? Double is floating-point, so you will only lose precision with multiplication. And you should NEVER initialize the Randomizer on each call - this will be horribly slow and potentially worse random numbers than otherwise!
    – Falco
    Sep 23, 2014 at 12:09
  • I think you could even use the right probabilities in the AddOre Method - so pass 1.0 / 20 right there...
    – Falco
    Sep 23, 2014 at 12:11
  • Thank you for your improvements. I felt it too complicated, with such simple matter. Sep 23, 2014 at 12:15
  • That's a good algorithm and is roughly an equivalent to mine. It is more complex, since you do computing for each random ore type, but the results will be accurate.
    – Dariusz
    Sep 23, 2014 at 12:17
  • Indeed, it will work slower than your version. I admit that I did not pay attention to the speed - my mistake. The whole algorithm can be slightly improved by sorting the dictionary, and the most likely types of rocks placed at the beginning. This will reduce the number of iterations of the loop. Sep 23, 2014 at 12:31
3

I recently had to do something similar, and I ended up with this generic "spawn generator".

public interface ISpawnable : ICloneable
{
    int OneInThousandProbability { get; }
}

public class SpawnGenerator<T> where T : ISpawnable
{
    private class SpawnableWrapper
    {
        readonly T spawnable;
        readonly int minThreshold;
        readonly int maxThreshold;

        public SpawnableWrapper(T spawnable, int minThreshold)
        {
            this.spawnable = spawnable;
            this.minThreshold = minThreshold;
            this.maxThreshold = this.minThreshold + spawnable.OneInThousandProbability;
        }

        public T Spawnable { get { return this.spawnable; } }
        public int MinThreshold { get { return this.minThreshold; } }
        public int MaxThreshold { get { return this.maxThreshold; } }
    }

    private ICollection<SpawnableWrapper> spawnableEntities;
    private Random r;

    public SpawnGenerator(IEnumerable<T> objects, int seed)
    {
        Debug.Assert(objects != null);

        r = new Random(seed);
        var cumulativeProbability = 0;
        spawnableEntities = new List<SpawnableWrapper>();

        foreach (var o in objects)
        {
            var spawnable = new SpawnableWrapper(o, cumulativeProbability);
            cumulativeProbability = spawnable.MaxThreshold;
            spawnableEntities.Add(spawnable);
        }

        Debug.Assert(cumulativeProbability <= 1000);
    }

    //Note that it can spawn null (no spawn) if probabilities dont add up to 1000
    public T Spawn()
    {
        var i = r.Next(0, 1000);
        var retVal = (from s in this.spawnableEntities
                      where (s.MaxThreshold > i && s.MinThreshold <= i)
                      select s.Spawnable).FirstOrDefault();

        return retVal != null ? (T)retVal.Clone() : retVal;
    }
}

And you'd use it like:

public class Gem : ISpawnable
{
    readonly string color;
    readonly int oneInThousandProbability;

    public Gem(string color, int oneInThousandProbability)
    {
        this.color = color;
        this.oneInThousandProbability = oneInThousandProbability;
    }

    public string Color { get { return this.color; } }

    public int OneInThousandProbability
    {
        get
        {
            return this.oneInThousandProbability;
        }
    }

    public object Clone()
    {
        return new Gem(this.color, this.oneInThousandProbability);
    }
}

var RedGem = new Gem("Red", 250);
var GreenGem = new Gem("Green", 400);
var BlueGem = new Gem("Blue", 100);
var PurpleGem = new Gem("Purple", 190);
var OrangeGem = new Gem("Orange", 50);
var YellowGem = new Gem("Yellow", 10);

var spawnGenerator = new SpawnGenerator<Gem>(new[] { RedGem, GreenGem, BlueGem, PurpleGem, OrangeGem, YellowGem }, DateTime.Now.Millisecond);
var randomGem = spawnGenerator.Spawn();

Evidently the spawn algorithm was not considered critical code so the overhead of this implementation was of no concern when compared to the ease of use. Spawns were run on world creation and it was easily more than fast enough.

2

Astrotrain already gave my answer but since I coded it up already I'll post it. Sorry for the syntax, I work mostly in Powershell and that is the context currently in my mind. Consider this psuedo code:

// Define the odds for each loot type
//           Description,Freq,Range
LootOddsArray = "Bloodstone",1,100,
"Copper",1,15,
"Emeraldite,"1,35,
"Gold",1,50,
"Heronite",1,60,
"Platinum",1,60,
"Shadownite",1,75,
"Silver",1,35,
"Soranite",1,1000,
"Umbrarite",1,1000,
"Cobalt",1,75,
"Iron",1,15

// Define your lookup table. It should be as big as your largest odds range.
LootLookupArray(1000)

// Fill all the 'default' values with "Nothing"
for (i=0;i<LootLookupArray.length;i++) {
    LootOddsArray(i) = "Nothing"
}

// Walk through your various treasures
for (i=0;i<LootOddsArray.length;i++)
    // Calculate how often the item will appear in the table based on the odds
    // and place that many of the item in random places in the table, not overwriting
    // any other loot already in the table
    NumOccsPer1000 = Round(LootOddsArray(i).Freq * 1000/LootOddsArray(i).Range)
    for (l=0;l<NumOccsPer1000;l++) {
        // Find an empty slot for the loot
        do
            LootIndex = Random(1000)
        while (LootLookupArray(LootIndex) != "Nothing")
        // Array(Index) is empty, put loot there
        LootLookupArray(LootIndex) = LootOddsArray(i).Description
    }
}

// Roll for Loot
Loot = LootLookupArray(Random(1000))
0

Use Random.Next http://msdn.microsoft.com/en-us/library/2dx6wyd4(v=vs.110).aspx:

Random rnd = new Random();

if (rnd.Next(1, 101) == 1)
    // spawn Bloodstone
if (rnd.Next(1, 16) == 1)
    // spawn Copper
if (rnd.Next(1, 36) == 1)
    // spawn Emeraldite

The minimum value should always be 1, the maximum value is the odds of spawning the item + 1 (minValue is inclusive, maxValue is exclusive). Always test the return value for 1, e.g., for Bloodstone there is a 1 in 100 chance that the randomly generated number is 1. Of course, this uses a pseudo random number generator, which should be good enough for a game.

1
  • 8
    This solution makes each following if less probable by a factor depending on the probabilities of the previous ifs. If you run a check on results of this algorithm for a large enough number of tries, you will see that the probabilities significantly differ from the defined.
    – Dariusz
    Sep 23, 2014 at 12:16
0

A slightly different approach to Astrotrains idea would be that instead of an array to use if statements . The upside is then that you need less memory, the downside that it will need more cpu time to calc the value of the node.

Thus:

Random rnd = new Random();
var number = rnd.next(1,1000);

if (number >= 1 && number <10)
{
  // empty
}
else
{
  if (number >= 10 && number <100)
  {
     // bloodstone
  }
  else
  {
     //......
  }
}

Also a downside to this variant comapred to the array variant is that this one takes more place codewise at the location where you use it and is more prone to errors / corrections (try to add something inside it you need to update all variants).

Thus this here is metnioned for completeness sake but the array vairant (memory usage aside) is less prone to the problems that the if variant has.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.