How can I select an enemy to act next, biased toward smaller enemies?

Question

Suppose there are X number of enemies in the game. They all have to attack one by one. Each enemy is picked randomly, and can be of Y size.

How can we attain biased randomness in such a way that small enemies are attacking more often than big ones?

My current algorithm is "pick any random enemy" no matter the size, and I'd like to improve on this.

Answer 1

Try accounting for larger enemies multiple times, then drawing one from them. For instance let's say you have 6 enemies, two of them are medium, one is large and the other 3 are small. Then you'd have a list similar to

small A, small B, small C, medium A, medium A, medium B, medium B, large A, large A, large A

If you pick one of these random, then you'll obviously have a larger chance to pick large A, than small a

Answer 2

Let's say the size-values are as follows:

small  = 3;
medium = 2;
large  = 1;

In this situation, you could add all size-values of your enemies together to calculate a biased random. For Example:

smallUnitsTotal  = 4; // => 12 points total (4 * 3)
mediumUnitsTotal = 2; // =>  4 points total (2 * 2)
largeUnitsTotal  = 1; // =>  1 points total (1 * 1)
totalPoints = (12 + 4 + 1)= 17 points total

Now you can just pick a random number (r) between 1 and 17. If r <= 12, a random small enemy attacks. If r > 12 && <= 16, a medium unit attacks and otherwise, the large unit attacks.

Hopefully this helps!

Answer 3

I'd be tempted to handle it like a raffle. Every time an attack slot comes around, everyone gets a number of raffle tickets according to their attack frequency. Then you do a random draw from those tickets, and deduct tickets from the winner. Everyone else keeps their tickets for the next draw, so someone who hasn't been picked in a while will gradually become more likely to get their turn.

Enemy SelectAttacker(List<Enemy> enemies) {
    float totalWeight = 0f;
    float weightAdded = 0f;
    float greatest = float.negativeInfinity;

    // Hand out raffle tickets to everyone in line to attack.
    foreach(var enemy in enemies) {
        // GetAttackRate can change value depending on the character's state,
        // like returning 0 if stunned / out of range, or a boosted value if enraged.
        float weight = enemy.GetAttackRate();

        weightAdded += weight;
        enemy.accumulatedAttackWeight += weight;
        greatest = Max(greatest, enemy.accumulatedAttackWeight);

        totalWeight += Max(enemy.accumulatedAttackWeight, 0f);
    }

    // Contingency: if the enemies who were holding all the raffle tickets died,
    // and everyone remaining is in attack debt, fast-forward a few rounds' worth.
    if(greatest <= 0f) {
        float advance = (Floor(-greatest / weightAdded) + 1) * weightAdded;
        totalWeight = 0f;
        foreach(var enemy in enemies) {
            enemy.accumulatedAttackWeight += advance;
            totalWeight += Max(enemy.accumulatedAttackWeight, 0f);
        }
    }

    // Choose a winner.
    float random = Random() * totalWeight;    
    totalWeight = 0f;    
    foreach(var enemy in enemies) {
        totalWeight += Max(enemy.accumulatedAttackWeight, 0f);
        if(totalWeight > random) {
            // Penalize this enemy proportionate to the crowd still waiting.
            // This keeps the total number of tickets in circulation controlled.
            enemy.accumulatedAttackWeight -= weightAdded;
            return enemy;
        }
    }

    // Fallback, only hit in the event of invalid input 
    // (like NaNs / negative attack rates)
    return enemies[0];
}

A few neat things about this approach:

• Enemies can have fractional attack weights (in case this enemy really needs to attack 2.3 times as often as that other one), without blowing up all your weights to multiples of a common divisor.

  All of these weights are relative, so two enemies with GetAttackRate returning 3 will (on average) attack as often as each other, three times as often as an enemy with GetAttackRate returning 1, and half as often as an enemy with GetAttackRate returning 6, no matter the composition of the battle group.

• This method scales linearly to any number of enemies, and the overhead remains constant no matter how disparate your weights (compared to drawing cards from a deck, where an enemy that attacks 10 times as often as another needs 10x the storage in the deck)

• You can easily vary the attack selection priorities dynamically based on enemy states or other factors. We don't need to do much grooming of the selection data as enemies join, change state, or die.

• Enemies that have attacked a lot recently tend to go into an "attack debt" with negative tickets held, limiting runs of the same enemy being chosen.

Answer 4

This can be handled by a straight forward reverse weighting.

Assign enemy size 'Y' as a numeric value (ex. 1-4). Choose a ceiling value 'Z' that is greater than the largest possible value of 'Y' (The greater the difference between 'Z' and the highest 'Y' value will result in the least difference in attack frequency)

Provide each enemy with a weighting value of 'Z' - 'Y'.

Create a list of enemies with each having a number of entries equal to their weighting value.

Calulate the sum of all all weighting values and generate a random number between 1 and the sum.

Use this to pick an index from the list and that is the monster that attacks this turn.

There are numerous optimisations that can be applied to this, but this will give the functionality you have requested.

Answer 5

What I did was a straight-forward algorithm for biased randomness or weighted probability.

Getting sum of weights.Weight is nothing but the prioririty given to an object.In my case the smaller the enemy the bigger the weight.

for(int i=0; i < value.size; i++) {
  weight_size = weight_size + value.get(i).getInt("weight");
}

Getting random weight from 0 to total weight.

double random_weight = Math.random() * weight_size;

Calculating which to choose based on weight.Loop on the objects until random weight is less than the weight of the object.

    for(int i=0; i < value.size; i++) {
        if (random_weight< value.get(i).getInt("weight")) {
            return value.get(i);
        }
        random_weight -= value.get(i).getInt("weight");
    }

Simple yet effective.