Save Games and All That

I have long postponed a task to improve Detour serialization. My use of the word may be a bit wonky, but I mean the business storing and restoring the game state. In case of Detour this also affects how you would initialize the navmesh too.

In pretty much all game projects I have participated in save games have been pretty much retrofitted into the game. It usually results a lot of stupid zombie coding and super long debugging sessions.

When I started thinking about Detour, I have tried to make decision which eventually will make the serialization implementation a bit simpler. That goes into how data is kept internally and what kind of data the API returns. For example there is no pointers, but handles instead.


Handles

Handles are simple abstraction which allows to keep track references to your data. The difference to a pointer is that handles can be invalidated, and you don't need to worry about someone having a reference to your data. The next time the data is accessed, the access will just fail, in which case the user should also invalidate the handle.

Usually in pointer based systems you use some sort of callback system, which tells the pointer owner that something has changed and you should remove the reference. Or it can result things like smart pointers or reference counting.

As the navigation data is solely owned by the navmesh, ref counting and smart pointers would not be a good choice. I also wanted the system to load the navmesh data as one contiguous chunk, which makes stuff like the usual ref counting not really a good choice.

Another good thing about the handles are that they can be stored in the disk as simple integers. These two facts: 1) simple handling of invalid references and 2) simple storing of returned data, make handles good choice when you need to pass handles to internal data through your API.


Detour Handles

Each detour handle contains three values: salt, tile ID, and polygon ID. Tile ID is simply an index to internal Detour tile array, polygon ID is index to a polygon within that time and salt is special ingredient which tells which version of tile we are using. The tile ref is constructed so that 0 (zero) value an be used as null handle.

Detour has fixed pool of tiles it reuses. Removed tiles are returned back to the pool and new tiles are allocated from the pool. Each of those tiles are identified by and index to the tile.

Every time a tile is removed the salt of that tile is incremented. This operation makes sure that if a tile changes, all handles which are pointing to the old data can be detected.

This also implies that if we save a dtPolyRef (the handle Detour uses) to disk when a save game is stored, we need to also restore the state of the Detour mesh when we restore a save game so that the handles are valid after save game is restored.


Saving Game State

The least information that needs to be stored on disk is the tile index and salt of each tile that we have in the current state of the navmesh. This allows the handles to survive the serialization. Additionally we may want to store the per polygon flags and areas too, as the API allows to change that too.

That is still piece of cake. But this is where things can get a bit complicated.

Pretty much every single game I've seen out there uses different way to load assets and even more so how they store and restore save games.

When save game is restored, some games load and initialize a full "section" of the game and then load a delta state on top of that. Some may first store the structure of the level and then load the assets that are needed.

While they both may sound like almost the same, the difference in load performance can be huge. The first, full section loading, allows us to place all the assets in such order that they are fast to load from disk, while the second method may be simpler if the world is allowed to change a lot but may and will result more fragmented loading, in which case seeking may kill your loading performance.

Streaming changes the game a bit too. I have never worked on a game which would have excessively used streaming. So I'm reaching out to you to have a bit better understanding of save game with streaming.

How do you handle asset loading and how do you restore the game state from a save-game?


Current Sketch

My current idea of how the API for serializing Detour navmesh looks something like this.

    dtNavMeshSerializer nser; 
    nser.storeDelta(navmesh); 
    fwrite(nser.getData(), nser.getDataSize(), fp);    

The serializer will create a contiguous clump of data which can be directly stored into disk. The process to restore the state is as follows:

    dtNavMeshSerializer ser; 
    if (!ser.init(data,dataSize)) 
        return false; 
    for (int i = 0; i < ser.getNavMeshResourceCount(); ++i) 
    { 
        const dtTileRes& tres = ser.getNavMeshResource(i); 
        navmesh->restoreTileState(tres.tileId, tres.stateData, tres.stateDataSize); 
    }    

This assumes that the structure of the navmesh has not changed in between. If the structure may change, you will need to load the tile data before restoring.

    dtNavMeshSerializer ser; 
    if (!ser.init(data,dataSize)) 
        return false; 
 
    dtNavMesh* navmesh = new dtNavMesh; 
 
    if (!navmesh->init(ser.getInitParams()) 
        return false; 
 
    for (int i = 0; i < ser.getNavMeshResourceCount(); ++i) 
    { 
        const dtTileRes& tres = ser.getNavMeshResource(i); 
        int dataSize = 0; 
        unsigned char* data = 0; 
         // Load data from disk.  
        if (!m_assetMgr.getNavmeshTileData(tres.resourceId, &data, &dataSize)) 
            return false; 
        navmesh->addTile(data, dataSize, false, tres.tileId, tres.tileSalt); 
         // Restore state  
        navmesh->restoreTileState(tres.tileId, tres.stateData, tres.stateDataSize); 
    } 

Note how the addTile looks different than currently. The tiles don't actually make any sense in random order, so in practice there is no need to pass the tile x and y coordinates when tile is added. This data can be stored in the tile header and acquired from there. Also not that tile ID and tile salt are also restored when tile is loaded to make sure the handles remain valid. That m_assetMgr is your custom asset manager, which will actually handle loading the navmesh data. This example also assumes that the asset manager handles allocating and releasing the data.

In case you use Recast to dynamically create the tiles you can use serializer to store the whole navmesh data too.

    dtNavMeshSerializer nser; 
    nser.storeAll(navmesh); 
    fwrite(nser.getData(), nser.getDataSize(), fp);

Restoring the state would look something like this:

    dtNavMeshSerializer ser; 
    if (!ser.init(data,dataSize)) 
        return false; 
     
    dtNavMesh* navmesh = new dtNavMesh; 
 
    if (!navmesh->init(ser.getInitParams()) 
        return false; 
 
    for (int i = 0; i < ser.getNavMeshResourceCount(); ++i) 
    { 
        const dtTileRes& tres = nser.getNavMeshResource(i); 
        navmesh->addTile(tres.tileData, tres.tileDataSize, true, tres.tileId, tres.tileSalt); 
    }

This code also restores the tile ID and tile Salt so that handles remain valid, but it does not store state, since the tile data already contains the state data too.


Conclusion

My ideas towards implementing the serialization are getting together. I'm requesting comments. Each game has unique requirements for storing save games and loading assets. There is no way I can please all, but I can try to make it little less painful for as many of you as possible.

Please, let me know if I overlooked some scenario with my sketch. And also please share how do you handle asset loading and how do you restore the game state from a save-game? If you don't want to share it here in my blog, feel free to mail it to me too!