less than 1 minute read

I have been working on a game where enemy characters must select a target seemingly at random but such that the distribution of selected targets is balanced. Initially I had come up with a randomization algorithm with weighted values for each target but this became cumbersome and much too complex.

Then I remembered the scheduling algorithms from my Operating Systems class. In particular, the lottery scheduling algorithm.
\

// assume a queue of targets
int total = 0;

for (Target t : targets) {
   t.tickets = 5;
   total += t.tickets;
}

// generate a random number from 0 to total
for (Target t : targets) {
   randNum -= t.tickets;
   if (randNum <= 0) {
      targets.reenqueue(t);
      return t;
   }
}

The queue structure is critical to ensuring proportionality in target selection. Also, targets can be given a higher amount of tickets if bias is needed.

Leave a comment