Thinking Fast

This post looks at the problem of entities with a nextthink rate higher than the framerate (inspired by a func_ post that I’ve lost in the meantime). The Quake engine guarantees 10 fps, anything more frequent risks lagging behind when framerates drop. Obviously rendering at 10fps can never draw a 20fps animation correctly; our goal for today is to have a 0.05 nextthink entity execute its think function 20 times in 1 second, running multiple times in a single frame when necessary. This results in dropped frames in an animation; a health regeneration function benefits more by reaching the correct total. The plan is to do something like
while(self.nextthink < time + frametime) self.think();
but the details of Quake’s timekeeping present some pitfalls.
This article was updated on 11th April to correct which ranges of time the Quake engine runs think frames in.

Today we’ll use the following QuakeC think function most of the time

void() regen =
{
    self.health = self.health + 1;
    self.nextthink = time + 0.06;
}
Aside: 10fps minimum
You may ask what it means for Quake to have a 10fps minimum. Normally, Quake uses the length of real time passed during the calculation of one frame as the amount time is increased by at the next frame. This means game time moves at real time rates. However, the engine will never increase time by more than 0.1s in one go. If frames take longer than that to produce, game time is in effect slower than real time.

The Quake engine does a few surprising things with respect to time and think functions. We will build up a model of how think and time interact by imagining we’re developing a new engine called “Tremble”, and discover how Quake fixes the issues we encounter. The starting point is an engine with a time value which increases each frame by the same amount frametime. The engine looks each frame for any entities whose nextthink value is < time + frametime (so will expire before the next frame starts), and runs their think function. Imagine we trigger a entity to initially run the regen think function when time = 1, and frames occur every 0.05s (20 fps). Here is a table of the entity’s change over subsequent frames, plus whether its think function ran.

time thinks? nextthink health
1.00 yes 1.06 1
1.05 yes 1.11 2
1.10 yes 1.16 3
1.15 yes 1.21 4
1.20 yes 1.26 5
1.25 yes 1.31 6
1.30 yes 1.36 7

The Tremble engine is now a whole tic of health ahead of where it should be, as the window between time in one frame (against which nextthink is set) and time + frametime in the next frame (which it is tested against) is actually double 0.05, and the function never fails to run. If we changed our code to end with self.nextthink = self.nextthink + 0.06 we’d get

time thinks? nextthink health
1.00 yes 1.06 1
1.05 yes 1.12 2
1.10 yes 1.18 3
1.15 yes 1.24 4
1.20 yes 1.30 5
1.25 no 1.30 5
1.30 yes 1.36 6

Now exactly 6 thinks run (note that we skip on the 6th frame because the inequality test is strict). Let’s leave this problem with a potential solution, and look at another issue the Tremble engine has. Take the following think function and kick it off when time = 1.

void() echo =
{
    dprint("LOOK AROUND YOU");
}
time thinks? nextthink
1.00 yes 1.00
1.05 yes 1.00
1.10 yes 1.00
1.15 yes 1.00

The effect is captured on video for your enjoyment. Basically, our Tremble engine will keep running a function if it doesn’t set nextthink in the future. It doesn’t seem right that functions would need to opt-out of running every frame; we need some way to prevent thinks repeating if they aren’t requested.

The Quake engine solves this by setting nextthink = 0 BEFORE the function runs. Although it fixes the problem at hand, we now cannot use our fix to the earlier problem of dropped thinks. There is a surprising innovation in the Quake engine at this point – it lies to the QuakeC about what the time is. More specifically, it sets time to the value that nextthink held before it was wiped – moving the clock forward temporarily to the moment the think was supposed to occur. That way, code in the form self.nextthink = time + 0.1 behaves like the “fixed” QuakeC in our Tremble Engine examples. Also note that the engine is only changing the time value, it doesn’t e.g. interpolate moving entities to future positions

Now both of the problems we identified with the Tremble engine are resolved, and the solutions seem satisfactory, although if you were told the behaviour out of the blue you would more likely think it odd. It is worth pondering how odd the resulting world is now entities thinking on the same frame don’t agree on what the time is. Our plan to run a while(self.nextthink < time) loop as a fix to our motivating problem now has a hole in it: we can’t see what the actual time is! Let’s import the fixes into the Tremble engine, and run an entity with a 0.06 think period in a 10 fps server (the new column realtime indicates the “true” server time, while the time column is what the QuakeC sees):

realtime time thinks? nextthink
1.00 1.00 yes 1.06
1.10 1.06 yes 1.12
1.20 1.12 yes 1.18
1.30 1.18 yes 1.24
1.40 1.24 yes 1.30
Aside: zero nextthink
While it works, it’s not immediately clear why Quake uses nextthink = 0 to indicate that a think function has expired. One might consider just strictly checking if nextthink is between the current server time and the time of last frame; an earlier nextthink indicating that the think already expired. The example just above is the reason not to do this, notice how a fresh nextthink was set on the last line, yet realtime is ahead of it. Strict checking would cause this entity to freeze.

Notice how the realtime and the time columns diverge, and the think time are retreating further into the past. The final adjustment we need to make to the Tremble engine is to limit how far the engine is willing to lie – never to tell an entity it’s earlier than the time of the last frame (thanks to spike for explaining this detail so I could update the article.).

If we want to run multiple thinks to smooth this out we need to access the true server time. One way to accomplish this is through modifying the startframe function. The engine doesn’t need to lie to startframe and time is set equal to the engine’s real time before the function is called. Add a new global float called realtime, and set realtime = time in startframe. Now any think function has access to the real time as well as their “think time”, which is the information we need to actually set up the plan from the beginning of the article. What follows is the simplest pattern to attempt multiple thinks, which would need to be applied anywhere a function sets nextthink intervals less than 0.1.

void() regen =
{
    self.health = self.health + 1;
    self.nextthink = time + 0.06;
    if (realtime + frametime > self.nextthink)
    {
        time = self.nextthink;
        self.nextthink = 0;
        self.think();
    }
}
realtime time thinkcount nextthink health
1.00 1.00 2 1.12 2
1.10 1.12 2 1.24 4
1.20 1.24 1 1.30 5
1.30 1.30 2 1.42 7
1.40 1.42 2 1.54 9
Aside: should we bother?
There is an argument that the days in which Quake players fear dropping to 10 fps are long gone, and 20 fps can be all but assumed. However, the techniques in this article are just as applicable to higher rates of thinking (e.g. hipnotic rotations think 50 times a second). The Quake engine also has a maximum frame rate of 72fps, so ultra-high rates can only be achieved like this.

It might be tempting to extract this boiler-plate code out into a separate function. However if not done carefully this may lead to excess stack use and a crash, as seen in a previous post. For the present task, there is a very good way to avoid any runaway stack use, but that’s for a future post. Until then!

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s