2

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 WeightedValue

public 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 : 2534
  • Item 2 : 2078
  • Item 3 : 1774
  • Item 4 : 1436
  • Item 5 : 1188
  • Item 6 : 990

If 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.

  • 2
    if you have weights of 1,1,2,3 what you should do is roll a 1d7. Then on a roll of 1 select item1, on a roll of 2 select item2 on a roll of 3 and 4 select item3 on a roll of 5, 6 and 7 select item4. You're over-complicating this. – Pieter B Sep 21 '16 at 6:57
  • 1
    Mandatory RNG illustration: cdn.ablebits.com/_img-blog/random-generator/… – Kromster Sep 21 '16 at 8:38
7

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 empty
roll = dice roll in [0, sum)
table-position = 0
for item in list:
  table-position += item.weight
  if roll < table-position:
    return item.value
assert unreachable

The 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).

  • An excellent answer, thank you. Also worth noting is that this solution runs a bit faster, to the tune of ~17ms faster than my solution over 100,000 selections with the same input. – Magic Marbles Sep 21 '16 at 17:51
  • 1
    @MagicMarbles Good to hear. If you have many items that do not change often, you can speed this up by pre-calculating the dice range for each item and doing a binary search over a sorted list (not sorted by their weight, but by their dice range). This drops the complexity from O(n) to O(log n), but I wouldn't bother for less than 20 values. – amon Sep 21 '16 at 17:57
0

Another way of doing randomness would be a deck of cards. If you fill the deck with 5 raining cards, and 10 cloudy cards, and 25 sunny cards, then you shuffle the deck. Each time you select a weather type draw the next card in the deck. You are guaranteed to have the correct ratios. After you have drawn all the cards in the deck reshuffle so that the order is different next time.

  • 2
    This solution guarantees that you will see each card exactly once for each stack of 40 cards. That is not random. In particular, we already know what the 40th card must be if we can count cards. A card that was already drawn can not be drawn again until the deck is reshuffled, meaning that the probability of subsequent cards depends on the cards already drawn. Only the first card is as random as the underlying random number generator. – amon Sep 21 '16 at 6:38
-1

So, that doesn't really work. Maybe another way?

public T Roll(){
        if(weightSum <= 0.001){
            return null;
        }
        if(!isSorted){
            Sort();
        }

        T val = null;
        while(val == null)
        {
            WeightedValue<T> wv = weightedList.get(dice.nextInt(weightedList.size()));
            //System.out.println("Weight: " + wv.Weight());
            if(dice.nextFloat() <= (wv.Weight() / weightSum)){
                val = wv.Value();
                break;
            }

        }

        return val;
    }

Here I randomly select an item from the list of WeightedValues and roll against it's pass chance. Lets see what the results are for a Group with 6 items with the same weight, doing 10,000 rolls:

  • Item 1 : 1737
  • Item 2 : 1615
  • Item 3 : 1676
  • Item 4 : 1638
  • Item 5 : 1667
  • Item 6 : 1667

This looks much better! Over 100,000 rolls it's even closer to an equal spread:

  • 1 : 16618
  • 2 : 16589
  • 3 : 16876
  • 4 : 16656
  • 5 : 16679
  • 6 : 16582
  • Testing further, with a group that has weights of 1, 1, 2 and 3. The item with a weight of 3 was selected 43,009 times out of 100,000 rolls. That works out to being selected about 43% of the time. Given that the ideal chance would be 3 in 7, or 42.8~% that's close enough. – Magic Marbles Sep 20 '16 at 22:03
  • I've checked the math and this solution is correct, i.e. yields values with the correct probabilities. However, it is not guaranteed to terminate (no problem in practice), and will visit an expected number of n - 1 values before it throws an appropriate dice value. See my answer for a version that manages with a single dice throw, and has simpler probabilities. – amon Sep 21 '16 at 7:18
  • 2
    You are really over-complicating this. – Pieter B Sep 21 '16 at 7:24
  • As is the way of a naive solution I suppose. Math isn't my strong suit so I tend to over think things when it comes to topics like probability in particular. – Magic Marbles Sep 21 '16 at 17:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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