Pseudo random proportional scheduling in games.
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