World Design and Cache Prediction

Perhaps you've just finished a supercharged version of ResCache—good for you. You're not done yet. If you load resources the moment you need them, you'll probably suffer a wildly fluctuating frame rate. The moment your game asks for resources outside of the cache, the flickering hard disk light will be the most exciting thing your players will be able to watch.

First, classify your game design into one of the following categories:

• Load Everything at Once: This is for any game that caches resources on a screen-by-screen basis or level-by-level. Each screen of Myst is a good example, as well as Grim Fandango. Most fighting and racing games work under this model for each event.

• Load Only at Pinch Points: Almost every shooter utilizes this design, where resources are cached in during elevator rides or in small barren hallways.

• Load Constantly: This is for open map games where the player can go anywhere they like. Examples include flight simulators, massively multiplayer games, and action/ adventure games like Grand Theft Auto: Vice City.

The first scheme trades one huge loading pause for lightning fast action during the game. These games have small levels or arenas that can fit entirely in memory. Thus, there's never a cache miss. The game designers can count on every CPU cycle spent on the game world instead of loading resources. The downside is since your entire playing area has to fit entirely in memory, it can't be that big.

Shooters like Halo on the Xbox load resources at pinch points. The designers add buffer zones between the action where relatively little is happening in the game. Elevators are perfect examples of this technique. The CPU spends almost no time rendering the tiny environment inside the elevator, and uses the left over cycles to load the next hot zone. The player can't change his or her mind in the middle of the trip until the elevator gets to the right floor.

Best Practice

These buffer zones will exist in many places throughout the game, providing the player with a brief moment to load weapons and rest happy trigger fingers. The designers at Bungie took advantage of this and placed a few surprise encounters in these buffer zones, something that always made me freak out when I was playing Halo.

Hallways are another good example of buffer zones. If you ever wondered why the Master Chief in Halo spends a lot of time in abandoned hallways it's because the Xbox is busy loading the next section of the map. The bigger the map, the longer the hallway. It's a great design conceit because the player is moving, making it feel like the action is still there. Even better, the folks at Bungie were wise enough to use the hallways to set the tone for the next fight with Covenant forces or The Flood—sometimes it was as simple as painting the walls with enemy blood or playing some gruesome sound effects.

Best Practice

Don't make the player read a bunch of text in between levels just to give yourself time to cache resources. Players figure this out right away, and want to click past the text they've read five or six times. They won't be able to since you've got to spend a few more seconds loading resources and they'll click like mad and curse your name. If you're lucky, the worst thing they'll do is return your game. Don't open any suspicious packages you get sent in the mail.

Open mapped games such as flight simulators, fantasy role playing games, or action/ adventure games have a much tougher problem. The maps are huge, relatively open, and the game designers have little or no control over where the player will go next. Players also expect an incredible level of detail in these games. They want to read the headlines in newspapers or see individual leaves on the trees, while tall buildings across the river are in plain view. Players like that alternate reality. One of the best games that uses this open world design is Grand Theft Auto: Vice City.

Of these kinds of games, the third person over-the-shoulder camera like you see in Ultima or Diablo is the easiest to handle. The viewable area may be small, but very densely populated with detail.

Ultima VII used a simple approach. The main map was broken into segments approximately 16 meters square as shown in Figure 8.9.

Figure 8.9: Ultima VII's Main Map.

Enough area was cached in to keep the game rendering smoothly. When the player walks across the map, the areas behind the player are cached out to make room for new areas in the direction of travel. Every time the player walked across a map boundary, the game froze for half a second. This pause wasn't a fatal flaw by any means, since the year was 1992, and players were willing to accept a little frame stutter in exchange for the densely populated world. Solving the frame stutter would have been non-trivial in Ultima VII's single threaded environment.

Modern operating systems have more options for multithreading, especially for caching in game areas while the CPU has some extra time. Use the players direction of travel to predict the most likely areas that will be needed shortly, and add those resources to a list that is loaded on an ad hoc basis as the cache gets some time to extra work. This is especially beneficial if the game designers can give the cache some hints, such as the destination of a path or the existence of a mountain pass, if it is clear that the player is likely heading in a predictable direction. These map elements almost serve as pinch points like the hallways in Halo, although players can always turn around and go the other direction.

Best Practice

Create your cache to load multiple resources at one time, and sort your cache reads in the order in which they appear in the file. This will minimize any seeking activity on the part of the drive's read head. If you're resource file is organized properly, the most used resources will appear close together at the beginning of the file. It will then be probable that resource loads will be accomplished in a single read block with as few seeks as possible.

If you want to find out which resources are used most frequently, you should instrument your build. That's a complicated way of saying you'll create a debug build with special code that creates a log file every time a resource is used. Use this log as a secondary data file to your resource file packing tool. The most used resources should sort to the beginning of the file, and attempt to exist as a contiguous block.

The maximum map density should always leave a little CPU time to perform some cache chores in open map game designs. Denser areas will spend most of their CPU time on game tasks for rendering, sound, and AI. Sparse areas will spend more time preparing the cache for denser areas about to reach the display. The trick is to balance these areas carefully, guiding the player through pinch points where it's possible, and never overloading the cache.

If the CPU can't keep up with cache requests and other game tasks, you'll probably suffer a cache miss and risk the player detecting a pause in the game. Not all is lost, however, since a cache miss is a good opportunity to catch up on the entire list of resources that will be needed all at once. This should be considered a worst case scenario—because if your game does this all the time it will frustrate players.

A better solution is a fallback mechanism for some resources that suffer a cache miss. Flight simulators and other open architecture games can sometimes get away with keeping the uncached resource hidden until the cache can load it. Imagine a flight simulator game that caches in architecture as the plane gets close. If the game attempts to draw a building that hasn't been cached in then the building simply won't show up. Think for a moment what is more important to the player: a piece of architecture that will likely show up in 100ms or so anyway, or a frustrating pause in the action.

Best Practice

It's a good idea to associate a priority with each resource. Some resources are so important to the game that it must suffer a cache miss rather than fail to render it. This is critical for sound effects, which must sometimes be timed exactly with visual events such as explosions.

The really tough open map problems are those games that add level of detail on top of an open map design. This approach is common with flight simulators and action adventure games. Each map segment has multiple levels of detail for static and dynamic objects. It's not a horrible problem to figure out how to create different levels of detail for each segment. The problem is how to switch from one level of detail to another without the player noticing. This is much easier in action/adventure games where the player is on the ground and most objects are obscured from view when they flip to a new level of detail.

Flight simulators don't have that luxury. Of all the games on the market, flight simulators spend more time on caching continuous levels of detail than any other non-rendering task. Players want the experience of flying high enough to see the mountains on the horizon and diving low enough to see individual trees and ground clutter whiz by at Mach 1.

This subject is way beyond the scope of this book, but I won't leave you hanging. There is some amazing work done in this area, not the least of which was published in Level of Detail for 3D Graphics by D. Luebke, M. Reddy, J. Cohen, A. Varshney, B. Watson, and R. Huebner. They also have a web site at: http://lodbook.com/.