The Resource Cache


Resource files need a resource cache. If your game has a tiny set of graphics and sounds small enough to exist completely in memory for the life of your game, you don't need a cache. It's still a good idea to use resource files to pack everything into one file; you'll save disk space and speed up your game's load time.

Most games are bigger. If your game is going to ship on a DVD you'll have almost five gigabytes to play around in, and I doubt your minimum RAM specification will require 5Gb. What you'll need is a resource cache—a piece of technology that will sit on top of your resource files and manage the memory and the process of loading resources when you need them. Even better, a resource cache should be able to predict resource requirements before you need them.

Resource caches work on similar principles as any other memory cache. Most of the bits you'll need to display the next frame or play the next set of sounds are probably ones you've used recently. As the game progresses from one state to the next, new resources are cached in. They might be needed, for example, to play sound effects for the first time. Since memory isn't available in infinite quantities, eventually your game will run out of memory, and you'll have to throw something out of the cache.

Caches have two degenerate cases: cache misses and thrashing. A cache miss occurs when a game asks for the data associated with a resource and it isn't there—the game has to wait while the hard drive or the CD-ROM wakes up and reads the data. A cache miss is bad, but thrashing is fatal.

Cache thrashing occurs when your game consistently needs more resource data than can fit in the available memory space. The cache is forced to throw out resources that are still frequently referenced by the game. The disk drives spin up and run constantly and your game goes into semi-permanent hibernation.

The only way to avoid thrashing is to decrease the memory needed or increase the memory requirements. It's rare that you'll get the go ahead to increase the memory requirements, so you're left with slimming down the game data. You'll probably have to use smaller textures, fewer sounds, or decrease the object or map density of your game to fix things.

Most of the interesting work in resource cache systems involve predictive analysis of your game data in an attempt to avoid cache misses. There are some tricks to reduce this problem, some of which reach into your level design by adding pinch points such as doors, elevators, or barren hallways. Some games with open maps, like flight simulators, can't do this. They have to work a lot harder. I'll show you a very simple resource cache so you can get your bearings. Then, I'll discuss why this problem generally gets its own programmer-and a good one.

For the sake of simplicity, I'm going to assume that the cache only handles one resource file. It's easy enough to make the modifications to track resources across multiple files. You'd need to attach a file identifier of some sort to each resource to track which resources came from which file. There's no need to create a monolithic file that holds all the game assets. You should just break them up into manageable chunks.

Resources might not exist in memory if they've never been loaded or if they've been thrown out to make room for other resources. You need a way to reference them whether they are loaded or not. You need a mechanism to uniquely identify each resource. A resource identifier for an iPac resource looks like this:

 struct IPacResource {    union    {       struct       {          short int m_folder;          short int m_resource;       };       int m_id;    };    IPacResource(int f=0, int r=0) { m_folder=f; m_resource=r; } }; 

For any resource in an iPac file, it is uniquely identified by combining the folder number and resource number into a single integer. Since iPac generates header files with enumerations for the folders and resources, you include the generated header file and declare a resource like this:

 #include "art.h"                   // This header is generated by iPac IPacResource r(ART_FOLDER, ART_PHOTOSHOP_32); 

A resource cache takes valid identifiers and returns pointers to the loaded resource. The top level API, Get(), usually returns a (void *), since the cache can hold anything:

 char *data =    (char *)cache.Get(IPacResource(ART_FOLDER, ART_PHOTOSHOP_32)); 

In a resource cache that manages multiple files, you would add a file identifier to the IPacResource structure. For speed use an integer that references an array of open resource files.

For the cache to do its work, it must keep track of all the loaded resources. A useful class, ResHandle, encapsulates the resource identifier with the resource data:

 class ResHandle {    friend class ResCache;                  // You'll see this in a minute protected:    IPacResource m_resource;    char *m_buffer;    unsigned int m_size; public:    ResHandle(const IPacResource & resource, int size, char *buffer);    ~ResHandle(); }; ResHandle::ResHandle(const IPacResource & resource, int size, char *buffer) {    m_resource = resource;    m_size = size;    m_buffer = buffer; } ResHandle::~ResHandle() {    if (m_buffer) delete [] m_buffer; } 

The ResHandle also tracks the size of the memory block. When the cache loads a resource it dynamically creates a ResHandle, allocates a buffer of the right size, and reads the resource from the resource file. The ResHandle class exists in memory as long as the resource caches it in.

A pointer to the ResHandle is inserted into two data structures. The first, a linked list, is managed such that the nodes appear in the order in which the resource was last used. Every time a resource is queried from the cache with Get(), the node in the least recently used list is removed from its current position and reinserted at the head of the list.

The second data structure, and STL map, provides a way to quickly find resource data with the unique resource identifier:

 typedef std::list<ResHandle *> ResHandleList;     // lru list typedef std::map<int, ResHandle *> ResHandleMap;  // maps identifiers to data 

Since most of the players are already on the stage, it's time to bring out the ResCache class, an ultra simple resource cache:

 class ResCache {    ResHandleList m_lru;    ResHandleMap m_resources;    IPacGameInterface *m_file;      // The resource file interface    unsigned int     m_cacheSize;   // total memory size    unsigned int     m_allocated;   // total memory allocated protected:    char *Allocate(unsigned int size);    void *Load(const IPacResource & r);    ResHandle *Find(const IPacResource & r);    void Free(void);    void *Update(ResHandle *handle); public:    ResCache(const unsigned int sizeInMb, const _TCHAR *iPacFile);    ~ResCache();    void *Get(const IPacResource & r); }; 

The first two members of the class have already been introduced; they are the LRU list and the STL map.

The IPacGameInterface class is an interface to the resource file, the nature of which is completely dependant on your game's data files. As far as ResCache is concerned, it only needs a few member functions:

 class IPacGameInterface {    // opens and closes the resource file    IPacGameInterface(const _TCHAR *iPacFile);    ~IPacGameInterface();    // finds the uncompressed resource size    int GetResourceSize(int folder, int resource);    // loads the resource into a pre-allocated buffer    int GetResource(int folder, int resource, char *buffer); }; 

Since the resource file is specific to each game, I won't waste time going over the details of writing code to make it work. I'm sure you can do that yourself. Let's concentrate on the guts of ResCache, starting with ResCache::Get() and working through the protected member functions:

 void *ResCache::Get(const IPacResource & r) {    ResHandle *handle = Find(r);    return (handle!=NULL) ? Update(handle) : Load(r); } 

ResCache::Get() is brain-dead simple: If the resource is already loaded in the cache, update it. If it's not there, you have to take a cache miss and load the resource from the file.

Finding, updating, and loading resources is easy. ResCache::Find() uses an STL map, m_resources, to locate the right ResHandle given a IPacResource. ResCache::Update() removes a ResHandle from the LRU list and promotes it to the front making sure that the LRU is always sorted properly. ResCache::Load() grabs the size of the resource from the file, allocates space in the cache, plugs the new resource into the cache, and reads the resource from the file:

 ResHandle *ResCache::Find(const IPacResource & r) {    ResHandleMap::iterator i = m_resources.find(r.m_id);    if (i==m_resources.end())      return NULL;    return (*i).second; } void *ResCache::Update(ResHandle *handle) {    m_lru.remove(handle);                    // REALLY REALLY SLOW!!!!    m_lru.push_front(handle);    return handle->m_buffer; } void * ResCache::Load(const IPacResource & r) {    // find the resource size    int size = m_file->GetResourceSize(r.m_folder, r.m_resource);    char *buffer = Allocate(size);    if (buffer==NULL)    {       return NULL;           // ResCache is out of memory!    }    // Create a new resource and add it to the lru list and map    ResHandle *handle = new ResHandle(r, size, buffer);    // Add the new handle to the STL data structures    m_lru.push_front(handle);    m_resources[r.m_id] = handle;    // read the resource from the file    m_file->GetResource(r.m_folder, r.m_resource, buffer);    return buffer; } 

Gotcha

The implementation of the LRU list as a naked STL list is a horrible choice, by the way. The call to m_lru.remove() in Update() has linear complexity, which is an ivy league way of saying that the more resources that exist in the list, the longer it will take to remove the ResHandle.

I considered a better method, but it bloated the example somewhat and made it harder to understand. I figured it would be just as good to leave the heinous abuse of STL <list> in there as an example to you all that abusing STL isn't a good idea!

Enough kid stuff. Here's ResCache::Allocate() and ResCache::Free():

 char *ResCache::Allocate(unsigned int size) {    if (size > m_cacheSize)    {       return(NULL);    }    // return null if there's no possible way to allocate the memory    while (size > (m_cacheSize - m_allocated))    {       // The cache is empty, and there's still not enough room.       if (m_lru.empty())          return NULL;       Free();    }    char *mem = new char[size];    if (mem)    {       m_allocated += size;    }    return mem; } void ResCache::Free() {    // find the oldest resource    ResHandleList::iterator gonner = m_lru.end();    gonner-;    ResHandle *handle = *gonner;    // remove the ResHandle from the LRU list and the map    m_lru.pop_back();    m_resources.erase(handle->m_resource.m_id);    // update the cache size    m_allocated -= handle->m_size;    // delete the resource    delete handle; } 

After the initial sanity check, the while loop performs the work of removing enough resources from the cache to load the new resource. If there's already enough room, the loop is skipped.

ResCache::Free() removes the oldest resource and updates the cache data members. The only thing you haven't seen you could write yourself, but I'll be nice and give you the constructor and destructor:

 ResCache::ResCache(const unsigned int sizeInMb, const _TCHAR *iPacFile ) {    m_cacheSize = sizeInMb * 1024 * 1024;           // total memory size    m_allocated = 0;    m_file = new IPacGameInterface(iPacFile, true); } ResCache::~ResCache() {    while (!m_lru.empty())    {       Free();    }    delete m_file; } 

Once you replace IPacGameInterface and IPacResource with the analogs to your game's data files you've got a simple resource cache. If you want to use this in a real game, you've got more work to do.

First of all, there's hardly a line of defensive or debugging code in ResCache. Resource caches are a significant source of bugs and other mayhem. Data corruption from buggy cache code or something else trashing the cache internals will cause your game to simply freak out.

A functional cache will need to be aware of more than one resource file. It's not reasonable to assume that a game can stuff every resource into a single file, especially since it makes it impossible for teams to work on different parts of the game simultaneously. Associate a file name or number with each resource, and store an array of open resource files in ResCache.

Best Practice

Consider implementing your own memory allocator. Many resource caches allocate one contiguous block of memory when they initialize, and manage the block internally. Some even have garbage collection, where the resources are moved around as the internal block becomes fragmented. A garbage collection scheme is an interesting problem, but it is extremely difficult to implement a good one that doesn't make the game stutter. Ultima VIII used this scheme.

That brings us to the idea of making the cache multithread compliant. Why not have the cache defrag itself if there's some extra time in the main loop, or perhaps allow a reader in a different thread to fill the cache with resources that might be used in the near future? This is a likely solution for games with an open map, and the game will constantly cache new resources in and out of the game. Games that use closed maps or pinch points may get away with a single threaded version.

It's also not unusual to use separate resource caches for different resources such as textures, objects, and sounds. This is especially true for textures, since they can exist in two different kinds of memory: video memory or system memory. A good texture cache needs to take that into account.




Game Coding Complete
Game Coding Complete
ISBN: 1932111751
EAN: 2147483647
Year: 2003
Pages: 139

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net