Weighted Probabilities with Integers for Game

Question

The idea here is to pick a skill at random for the player each round. Four skills will be chosen, they are all random, and the same skill can repeat multiple times.

The player has a skill level for each ability. The higher the skill level, the greater the chance that the skill will be chosen.

Rather than use floats and percentages, I have created this solution based on ranges and integers. The readability of the code is what I am concerned with here. Does it make sense from looking at it? Would more comments help, or should I use a different approach?

I am using this in a libGDX game, so I am limited to Java 6.

private Ability getRandomAbility() {
    final Map<BZRange, Ability> abilityRanges = new HashMap<BZRange, Ability>();
    int count = 0;
    for (Ability ability : this.skillLevels.keySet()) {
        int abilityLevel = this.skillLevels.get(ability);
        BZRange abilityRange = new BZRange(count, count + abilityLevel);
        abilityRanges.put(abilityRange, ability);
        count += abilityLevel;
        //increase the count by an extra one so that the ranges dont overlap
        count++;
    }

    int randomNumber = this.random.nextInt(count);
    for (BZRange range : abilityRanges.keySet()) {
        if (range.contains(randomNumber)) {
            return abilityRanges.get(range);
        }
    }

    return null;
}

Here is the BZRange class, it is very simple:

public class BZRange {

    private int low;
    private int high;

    public BZRange(int low, int high){
        this.low = low;
        this.high = high;
    }

    public boolean contains(int number){
        return (number >= this.low && number <= this.high);
    }
}

Answer 1

You can accomplish this without your BZRange class and without the additional HashMap.

You could in theory cache the total skill level value, as I have a feeling it isn't changed very often.

private Ability getRandomAbility() {
    // `sum` can be a cached value, or computed by summing `this.skillLevels.values()`.
    int sum = this.getTotalSkillLevels();

    int randomNumber = this.random.nextInt(sum);
    for (Entry<Ability, Integer> entry : this.skillLevels.entrySet()) {
        int abilityLevel = entry.getValue();
        randomNumber -= abilityLevel;
        if (randomNumber < 0) {
            return entry.getKey();
        }
    }
    return null;
}

Let's say that you have the ability skills 4, 3, 5. The sum is 12 which means that an integer from 0 to 11 (inclusive) is generated.

• If that value is 0, 1, 2 or 3 (four different values) the first skill will be chosen.
• If it is 4, 5, or 6 the second skill will be chosen.
• Finally, if it is 7, 8, 9, 10, or 11 then it will pick the last skill.

No need for a BZRange class, just need for some simple maths.

Answer 2

You can add the final modifier for your BZRange fields since this class is immutable - this makes the definition (slightly) clearer. :)

//increase the count by an extra one so that the ranges dont overlap

At first, I thought this was an odd comment to read, but then I realize this is just because your contains() implementation is a bound-inclusive comparison... If BZRange is only used purely for this computation, perhaps you can consider changing the contains() implementation to exclude the upper bound hmms?

As for the logic itself... I did a quick search and uncovered not one, but two Stackoverflow suggestions for using a TreeMap and its ceilingEntry() or floorEntry() methods, so you may want to consider that. The gist is:

private Ability getRandomAbility() {
    int offset = 0;
    TreeMap<Integer, Ability> abilityMap = new TreeMap<Integer, Ability>();
    for (Entry<Ability, Integer> entry : this.skillLevels.entrySet()) {
        abilityMap.put((offset += entry.getValue()), entry.getKey());
    }
    // edit: added 1 offset as well for adjustment
    return abilityMap.ceilingEntry(1 + this.random.nextInt(offset)).getValue();
}

Answer 3

On to of hjk's superb answer, a few lesser points.

Iterate over map entries rather than keys + lookup

When iterating over a map, if you need both the keys and their corresponding values, then instead of iterating over the keys and then looking up the corresponding values with get calls, it's better to iterate over the entries, so that you can save the lookups.

Your should apply this technique to the loops that iterate over skillLevels and abilityRanges maps, because they both need the corresponding values, not only the keys.

Arrange condition elements in numerical order

Instead of this:

    return (number >= this.low && number <= this.high);

When you have multiple numeric conditions, it's slightly more readable to arrange the elements in their numeric increasing order, like this:

    return (this.low <= number && number <= this.high);