Terrarium: A focus on game loops and scheduling
We've talked about the Terrarium game loop quite a bit in the past, mainly through channels that no longer exist (the GDN Forums). The primary reason we focused attention on the game loop was to help creature authors understand the order of processing in order to optimize the way their creatures would interact with the world. At this time some authors were discovering internal game functions that were helping them gain a slight edge over the rest of the community. This lead us to release as much internal information as we could without actually releasing the source code.
So what does the game loop in the Terrarium look like? Well, we have a single method linked to a timer control, and we run our method in direct response to the timer's event getting fired. This can be a bit dangerous, since we are dependent on the processing of WM_TIMER messages which can be backed up in the processing queue. Some extra code is added to make sure our code isn't re-entered while we are still processing (still dangerous on a multi-proc machine, since we don't use thread-safe code). Each time the code is called it increments a special tick counter. Each game tick is actually comprised of 10 smaller engine ticks where the engine does it's processing. Ideally we operate at a frequency of 1 game tick every half second and therefore 1 engine tick every 1/20th of a second. Each engine tick also links to a rendering tick, so our effective rendering rate is 1/20th of a second. You won't even realize the refresh is this slow, because the screen is refreshing at 60hz or 60 frames per second irregardless of whether or not we update our screen buffer (which is why games that render at 200 fps are ignorant since you only see a handful of those frames anyway).
So a game loop semantically looks like this:
GameTick() {
tickCount++;
Engine.Tick(tickCount);
Graphics.Render(tickCount);
}
That is pretty easy. You have your engine code (internal processing, AI, running creatures), and your rendering code. The rendering code in our case isn't really linked to the engine all that closely, since we are rendering game state from approximately a second before. This affords us the ability to have an immutable source for rendering, and allows us to interpolate movement between the previous location (previous state) and current location (current state) so that we can render 10 frames of animation with only a single displacement value.
I'm going to get off the graphics engine and talk just about the game engine for now. The only important note for the graphics engine is that the first frame rendered after setting a new state takes exceptionally longer than the rest of the frames. This means that our 1st frame of every 10 has the ability to throw off our real-time scheduling since it can take more than 1/20th of a second, then the rest of the frames compensate for this because they take a much shorter amount of time. We could have fixed this, but it wasn't a huge concern at the time.
So every 1/10th of a tick our game engine does some work. Since this work is broken into 10 separate calls into the engine, we also have to try and load balance our processing into those 10 calls. We did this through hand-tuning, which in retrospect wasn't very smart. Our basic tick operation becomes a switch statement dependent upon the tick counter. If you could visualize for a moment, it might look something like this:
switch(tickCount%10) {
case 0:
case 1:
case 2:
case 3:
case 4:
// Do creature processing
CreatureScheduler.AllowCreaturesToProcess();
break;
case 5:
// Do first part of engine stuff
break;
case 6:
// Do second part of engine stuff
break;
// etc.... through case 9:
}
So 0 through 4 aren't that hard. We run 1/5th of the creatures each time and the tuning or time allowed per creature is balanced such that only the right amount of time should be taken. If a creature is naughty and goes over we punish it harshly and it probably doesn't get the chance to do the same thing over. You may see some hick-ups in the Terrarium at times, and this is why. Creatures are allowed to be naughty at times and when they do it elongates our tick timings.
The larger amount of work is done in cases 5 through 9. All of the engine processing is done here. Certain functions take a while, others are almost instantaneous. All of the scheduling is hand-tuned so that the layout of the various processing functions within the ticks was done based on profiling done before release. Say what? Yep, there is no actual scheduler running real timings and running as many tasks as possible within a given time frame. Could we have fixed this one? Heck yeah, but again, the game runs good enough as is. I tend to agree with this in most cases, especially when the cool aspect of the Terrarium isn't its game loop, but rather its ability to host creature code.
So how could things change? Well, several things need to change. First, if the graphics engine can't render the first frame in 1/20th of a second, then we need to do some extra work to make that possible. The reason this particular render can take longer than 1/20th of a second is because we pre-render a bunch of helpful surfaces. Namely, the current background, any plants (caching the plants gets a huge perf benefit), and any dead creatures (another huge benefit). We could rewrite the graphics engine to load balance the rendering of these staging surfaces over multiple calls maybe? That would probably be best. In most cases we can render this frame on a decent machine in less than 1/100th of a second, and only in the worst case scenario does it go longer, so if it does, we should allow skipping one frame of animation or maybe even two, and then skip as many game engine ticks as required. As long as we get our work done before the end of the half second tick, we should be fine right? Right!
Our new GameTick looks something like this:
GameTick() {
// We could also use some real-time sync'ing...
tickCount++;
DateTime end = DateTime.Now.AddMilliseconds(50);
Graphics.Render(tickCount);
// Skip if this is the first frame that takes a good
// deal of time. If other frames take longer then
// too bad.
if ( DateTime.Now > end && (tickCount % 10 == 0)) {
// Throw some code in to protect against larger than half
// second renders of a frame.
int maxTicks = 9 - (tickCount % 10);
int ticksToIncrement = Math.Min(maxTicks, ...); // work out how many ticks we need to skip
tickCount += ticksToIncrement;
end = end.AddMilliseconds(ticksToIncrement * 50);
}
// Tell it the tick since the 10th tick is important and it will have to
// finish any high priority processing irregardless of how long it takes
//
Engine.Tick(tickCount, end);
}
The next big change is going to be to the Engine.Tick method. Rather than tuning functions that process things we now have to implement a simple task queue. The task queue holds all things that need to happen sorted in some way by the order in which they should happen. Each creature that needs to be executed, for instance, will be added and processed. In the case that creatures don't use a lot of time, the 5 ticks we used to use, might be downgraded to a single tick for instance. All of that processing the engine does over 5 ticks? It might be possible for that to happen in one tick as well. What this does is ensure that any of the old portions of the game engine that might have accidentally gone over 1/20th of a second will now be compensated for by all of the operations that run much faster than 1/20th of a second, hopefully smoothing out any speed issues that we used to see.
The game engine will always know if this is a new tick because it always gets to process the 10th tick each round. So we can have a flag that tells us to set up our queue. Note we'll have two queues. One for creatures and one for engine events. The way this works is that creatures are processed until none are left. Then we roll up all of our events into a second queue that will be processed by the engine so long as it has time or if it is playing catch-up. The code might look like this:
if ( (tickCount % 10) == 9 ) {
// Makes our other processing easier
end = DateTime.MaxValue;
}
// Make a decision as to what needs processing
if ( processCreatures ) {
while(CreatureScheduler.ProcessNextCreature() && DateTime.Now < end) { }
if ( CreatureScheduler.Done ) {
processEvents = true;
processCreatures = false;
}
}
if ( processEvents && DateTime.Now < end) {
TaskScheduler.AddEvents(RollUpEvents());
processEvents = false;
processEngine = true;
}
if ( processEngine && DateTime.Now < end) {
while(TaskScheduler.ProcessNextTask() && DateTime.Now < end) { }
if ( TaskScheduler.Done ) {
processEngine = false;
}
}
if ( (tickCount % 10) == 9 ) {
processCreatures = true;
processEvents = false;
processEngine = false;
}
That isn't a bad game loop. When we first enter, we'll make sure this isn't the last tick in a run. If so, we make sure everything gets processed. We run through creatures first, until we run out of time, or are done, and then we have logic to move the process along. We move to rolling up events (which I'm assuming is fast), and then finally onto processing those events. Note the events have to already be ordered, so if we used the current Terrarium system, we'd simply push things onto the queue the same way we have the processing functions ordered. If we added a few more variables we could also do first time into tick processing, etc... And I think we'd have to add those for the current Terrarium implementation, but that isn't hard. We could also throw in a good deal of asserts to make sure the game loop is operating properly and to ensure that we don't get out of sync in any way since we are using basic boolean flags as our transition logic. Heck, imagine if we rolled up our events before the creatures were done? That might really suck resulting in some events being processed twice or some of our creatures not getting their events processed by the engine. Even worse, the engine code might start running before all of the creatures are finished (though the timing logic would prevent most of this). These are bad scenarios and asserts would prevent them.
Thanks for sticking through my examination of a game loop. I realize that you don't have the Terrarium loop at your fingertips as reference, but you will soon enough, so I don't feel bad talking about it and wetting your appetite. The loop could definitely process a bit better, as I've pointed out and be a little bit more resilient to timing problems. I'll answer any questions you might have about game loops and scheduling, so feel free to post comments. I'll also make sure the code gets fixed if there are any issues. Do note that this code is really just basic pseudo-code though, since I have tried to compile it and it is extremely incomplete. Enjoy!