Random Entities from Find()

Our aim today is to select a random entity from a collection, so that each entity has an equal chance of being selected. A very simple aim, to which we’re adding the twist that we don’t know how many entities there are in the collection ahead of time. In Quake coding this is actually a very common situation: we don’t have the luxury of arrays that we can query the size of. The two kinds of collection we frequently encounter are linked lists – like the one returned by findradius, and collections returned one entity at a time by the find function. Today’s technique can be used with either, in the example code I’ve elected to use find. We’ll start with our outer loop, pretty standard stuff, where we define a few variables we will need.

local entity candidate;
local entity selection;
local float counter;
for(candidate = find(world, classname, "monster_ogre");
    candidate != world;
    candidate = find(candidate, classname, "monster_ogre"))
{
  //code to follow
}

So we’re using a for loop to cycle through each candidate in the map – this time I’m looking for all the ogres. Our plan is that after the loop completes, the selection variable will contain the randomly chosen ogre. The counter will be useful inside the loop, lets go and see how:

//this is the code inside the loop
counter = counter + 1;
if(random()*counter <= 1)
  selection = counter;

That’s it! The odds are 1 in counter that the test random()*counter <= 1 is true. In other words, for the nth ogre candidate, we switch our selection to it with probability 1/n. The rest of the time we stick with the ogre we already had. In the next two paragraphs I’ll outline the maths that makes this work, feel free to skip them if you trust me!

Imagine that we already know that the function selects from lists of k ogres with equal probabilities. What happens when we add one more ogre on the end of the list? Before we get to the new ogre, the algorithm is unchanged, so we’ve fairly chosen one of the first k ogres. From above, we switch to the new ogre with probability 1/(k+1), which is the desired probability (our list is now k+1 ogres long). We stick with the ogre from the first k, (originally chosen with probability 1/k) over the remaining k/(k+1) of the time, resulting in a total probability of 1/k * k/(k + 1) = 1/(k+1) as well!

Adding one more ogre to the list preserves the fairness, but is it fair to begin with? Let’s examine the code in the simplest case, when there is exactly one ogre. In our first and only pass through the loop, counter increases from 0 to 1. We then ask if random()*1 is less than 1: it always is. So we select that ogre with 100% probability, job done! But if the algorithm is correct for 1 ogre, by the above paragraph it’s still correct when we add one more. Now it’s correct for 2 ogres, so the first paragraph says it’s correct for 3. Repeat this for 4, 5, 6…up to any number of ogres! This is an example of a mathematical argument known as induction.

Welcome back. It’s worth examining what the code does if the collection is empty. Luckily it’s easy to check that it returns world – but you must be aware that this can happen in your subsequent code, or you might end up modifying world and crashing the server. The importance of this increases when you consider adding a filter to your results – perhaps we only want to randomly select among the ogres who have an enemy currently. We can modify the loop as follows:

//this is the code inside the loop
if(candidate.enemy == world)
  continue;
counter = counter + 1;
if(random()*counter <= 1)
  selection = counter;

We’re using the continue keyword in accordance with the previous article on removing nested loops. The important thing is to only update counter if the entity passes our filter, otherwise the probabilities go wrong.

That’s about all for this article, but I’m gonna leave you with an interesting alternative on how to write the loop we began with:

local entity candidate;
local entity selection;
local float counter;
while(candidate = find(candidate,classname,"monster_ogre"))
{
  //inner loop code here
}

PRO: We only define the find function once. This helps avoid errors if in future we have to change the code to something like find(candidate, class, "ogre") – there are two places this needs changing in the original and we run the risk of forgetting one.

CONS:It’s a bit harder to understand, and we use an assignment in the conditional, which generates a compiler warning. We’re doing it intentionally here: the value assigned to candidate is then used in the conditional test for the loop, ending it as soon as we assign world. This setup is the reason assignment in a conditional is allowed, but whether it’s worthwhile is debatable…