I'm trying to devise a way to create a 'loot table' for an RPG, mostly to see if it can be done.I'm partly inspired by old D&D style tables, which would list a range of values for each item on the table (i.e. 0-20 weather is clear, 21-50 weather is raining, 51-99 weather is cloudy) and you would roll a dice to see where you fall on the table.I'd like to do this without a bunch of If/Elses, as I might want to construct tables from data stored in a file or database.So I went with weighting the values on the 'table'. Higher weights would mean a higher chance of that value being selected. Sum all the weights, and then divide each individual weight by the sum to get a chance of passing. If the weights are 1, 1, 2, and 3, then the weight of 3 should have about a 3/7 chance of being selected.SO here's what I came up with:public class WeightedRandomGroup<T> {    private Random dice = new Random();    private List<WeightedValue<T>> weightedList = new ArrayList<>();    private float weightSum = 0;    boolean isSorted = false;    public void Insert(WeightedValue<T> wv){        weightSum += wv.Weight();        weightedList.add(wv);        isSorted = false;    }    public T Roll(){        if(weightSum <= 0.001){            return null;        }        if(!isSorted){            Sort();        }        T val = null;        while(val == null)        {            for(WeightedValue<T> wv : weightedList)            {                //System.out.println(Weight:  + wv.Weight());                if(dice.nextFloat() <= (wv.Weight() / weightSum)){                    val = wv.Value();                    break;                }            }        }        return val;    }    private void Sort(){        Collections.sort(weightedList, comparator);        isSorted = true;    }    private Comparator<WeightedValue<T>> comparator = new Comparator<WeightedValue<T>>(){        public int compare(WeightedValue<T> w1, WeightedValue<T> w2){            if(w1.Weight() > w2.Weight())                return 1;            else if (w1.Weight() == w2.Weight())                return 0;            else                return -1;        }    };}And WeightedValuepublic class WeightedValue<T> {    private T value;    private float weight;    public WeightedValue(int weight, T value){        this.weight = weight;        this.value = value;    }    public float Weight() { return weight; }    public T Value() { return value; }}The procedure is to go through each weight and 'roll' to see if we can roll under it's pass chance. The list is sorted so we start with the lowest weights and move up to the highest weights and we keep going through the list until we roll under one of the items pass chance.Those who've done discrete maths or the like will probably see an issue, which I'm going to show now:Given a table where every value has an equal weight, this is how many times each item is selected when rolling (out of 10,000 rolls):Item 1 : 2534Item 2 : 2078Item 3 : 1774Item 4 : 1436Item 5 : 1188Item 6 : 990If everything has an equal weight, then everything should have a fairly close number of hits, but clearly this is not the case with Item 6 being rolled less than half as often as Item 1 or Item 2!Which makes sense. If we have 4 items with an equal chance, then using my above code we roll against a 25% chance for the first item. If that fails, we roll for 2, then if that fails 3, and so on. This means we have a 75% chance to try to roll for the second item. a ~56% chance to roll for the third item and a 42% chance to roll for the 4th item. (if I did the math right)I'll post what I came up with to fix this, but I'm interested in if there's a better way to 'roll a dice' on a table.
Programming a Truly Fair Weighted Random Dice Roll
random
Your problem is that you roll the dice multiple times to select an item. This is entirely unnecessary, and turns your simple loot table where each item has a range of dice values to a loot decision tree which introduces dependent probabilities. Instead, we roll the dice once to get a value in the range [0,sum), then iterate through all items until you have found the matching item.Pseudocode:assert list is not emptyroll = dice roll in [0, sum)table-position = 0for item in list:  table-position += item.weight  if roll < table-position:    return item.valueassert unreachableThe advantage of this solution is that it's simple, the weight corresponds linearly to selection probability, you don't need to sort the list, and most importantly: it is guaranteed to terminate in O(n).