Introduction to Loading and Saving

Home --> Programming Projects --> Fractal Block Engine --> Introduction to Loading and Saving

When does Loading and Saving Occur?

Loading occurs constantly as the player moves throughout the world. Whenever the player comes close to a chunk so that it is added to the active chunk tree, the chunk needs to be 1) procedurally generated and 2) all changes that have been previously made to the chunk must be loaded. These changes are stored in Chunk Changes Objects (CC Objects).
Saving only occurs when the user saves the game. So, all changes to the world must be buffered until the user chooses to save, at which time all these changes are saved to the filesystem. These changes are also stored in Chunk Changes Objects (CC objects).

So for example, if the player creates a stone block in a chunk, that will be stored in the CC object associated with the chunk. If the player moves far away from the chunk, the chunk will be destroyed (so that it is no longer in the "Active Chunk Tree"). However the CC Object will remain until the player saves the game. If the player exists without saving, all CC Objects are discarded and there is no saving.

Chunks, Chunk Changes Objects, and Chunk Files

Here is the process for adding a chunk into the active chunk tree:

The chunk is generated by the procedural world generation system.
We see if there is a "chunk file" in the filesystem associated to the chunk. This stores any changes that have been previously made to the chunk.
If the chunk file exists, we load it into a Chunk Changes Object (CC Object).
We merge the procedurally generated data with the CC object to create the final chunk.

Whenever a change is made to a chunk, the CC Object is updated immediately.

Here is the process for removing a chunk from the active chunk tree:

We simply delete the chunk.
We keep the associated CC Object until either
- the user saves the game (at which point it is flused to a chunk file), or
- the CC Object becomes irrelevant.

Why use Chunk Changes Objects (CC Objects)?

The reason we are using Chunk Changes Objects is so we only need to store and track CHANGES that have been made to a chunk, not the entire state of a chunk. This saves both time and space. However, it is significantly more complicated and harder to debug than a system where there are no CC Objects.

What would it look like to not have CC Objects? Well, when the player first visits a chunk it is is procedurally generated, but then once the player makes any change to the chunk the ENTIRE state of the chunk should be saved to a chunk file. Then, when the player comes back to this chunk, the saved chunk file should be loaded without the need to re-procedurally generate the chunk. Also, saving the entire state of a chunk is simpler than recording one change at a time and buffering them.

Although Fractal Block World uses CC Objects, this was a major headache for development. Someone making their own game should seriously consider if this is worth the added complexity.

Dirty vs Clean CC Objects

Suppose when adding a certain chunk to the active chunk tree, we see that there is an associated chunk file. We then create the CC Object from the chunk file then use that to generate the chunk. Suppose that no further change is made to the chunk. That is, the CC Object is not modified after it is created from the chunk file. Then when the player saves the game, there is no need to flush the CC Object to the chunk file (because the chunk file is up to date). That is, we are saying that every CC Object can have a dirty bit, and the CC Object only needs to be saved when this dirty bit is set to true.

Fractal Block World has gone back and forth on the use of these CC Object dirty bits. On the one hand it is not that difficult to program these dirty bits and it has a significant reward. On the other hand if not done correctly, there can be annoying bugs.

CC Object Revert Time

Every change (stored in a CC Object) that is made has a "revert time": the time at which the change will be reverted back to its original state. For example, creating a wood block might last for one hour, whereas creating a stone block might last for 10 hours. Many changes have a revert time that is at most one hour in the future. For example, damaging a monster to change its health will normally revert in an hour.

The revert time of a CC Object is the maximum revert time all all changes stored by the object. Chunk files simlarly have these revert times.

The loaded game time is the time of the game when it was last loaded. When the game is being played, we are able to remove chunk files whose revert time is less than the loaded game time.

We also could periodically open chunk files and remove from them changes that have reverted (even if the entire chunk file has not reverted). However, Fractal Block World does not do this.

A Puzzle

Suppose it is time to save the game, and there is a CC Object that is empty (it does not store any changes). Do we still need to save it?

Answer: Maybe! The issue is when there is a chunk file associated to the chunk. Then it is not good enough to simply not save the CC Object. Instead we need to REMOVE the chunk file.

This is something worth thinking about, and something to be careful about when designing the system.

Dormant Chunks

Suppose the player plays the game for minutes to hours without saving the game. There will be many thousands of CC Objects created. The most common of these CC Objects are the dormant ones.

A CC Object is dormant iff there is no chunk or chunk file associated to it. These are probably the CC Objects for chunks that the player has visited for the first time and has made changes to them. Many of these changes are short term.

There are two issues. One issue is that when it is time to save, processing all these dormant chunks will take time. The other issue is that storing all these dormant chunks in the mean time will take up a lot of memory.

Thus it makes sense to delete dormant CC Objects once they become irrelevant. Fractal Block World sorts all dormant CC Objects based on their revert time. Once a dormant CC Object's revert time is less than the current game time (not the loaded game time), we can delete the CC Object.

Precomputing Chunk Files

Once a chunk is removed from the active chunk tree, we still need to hold on to the associated CC Object. What we can do at the time when the chunk is removed is we can precompute the chunk file that would need to be saved later. This makes it faster when the user saves the game. This is what Fractal Block World does.

There is a draw back to this method of precomputing the chunk file. The issue is that the later were generate a chunk file, the more changes will have reverted and hence will not need to be saved.

Naming Chunk Files

We refer to a CC Object by its chunk path. This seems like the only sensible way to do it. Here is an example of a chunk path:

73a_8f5_421_c49.
Here the "73a" refers to the position (7,3,10), the 8f5 refers to the position (8,15,5), etc (we are using hexadecimal). Every position is of the form (x,y,z) where each of x,y,z is between 0 and 15 inclusive. Hence we can refer to each position as an integer between 0 and 4095 inclusive. Fractal Block Words stores every block path as a vector of such integers.

What should be the name of the chunk file that sores the data in the CC Object with the block path 73a_8f5_421_c49? We could simply call the file

"73a_8f5_421_c49.txt"
However the problem is that the names of these files can be extremely long. So instead we have each chunk file be named a "hashcode" of the chunk path, and inside each chunk file is the full path. The hahscode is a 4 byte unsigned integer. Here is how the hashcode of a block path is computed in Fractal Block World:

//The first 81 primes after one million.
//We actually only use the first 80.
int prime_table[] = {
    1000003, 1000033, 1000037, 1000039, 1000081, 1000099, 1000117, 1000121, 1000133,
    1000151, 1000159, 1000171, 1000183, 1000187, 1000193, 1000199, 1000211, 1000213,
    1000231, 1000249, 1000253, 1000273, 1000289, 1000291, 1000303, 1000313, 1000333,
    1000357, 1000367, 1000381, 1000393, 1000397, 1000403, 1000409, 1000423, 1000427,
    1000429, 1000453, 1000457, 1000507, 1000537, 1000541, 1000547, 1000577, 1000579,
    1000589, 1000609, 1000619, 1000621, 1000639, 1000651, 1000667, 1000669, 1000679,
    1000691, 1000697, 1000721, 1000723, 1000763, 1000777, 1000793, 1000829, 1000847,
    1000849, 1000859, 1000861, 1000889, 1000907, 1000919, 1000921, 1000931, 1000969,
    1000973, 1000981, 1000999, 1001003, 1001017, 1001023, 1001027, 1001041, 1001069};

//Gets the n-th prime after one million, looping around.
int GetPrime(int n) {
    if( n < 0 ) n = 0; //Should not happen.
    n = n % 80;
    return prime_table[n];
}

//The hashcode of a block path.
unsigned int GetHashcodeOfBlockPath(
    const vector<int> & path)
{
    int n = 0;
    long long total = 0;
    total += GetPrime(n++) * path.size();
    for(int i = 0; i < path.size(); ++i) {
        total += GetPrime(n++) * path[i];
    }
    return (total % 0xffffffff);
}

So then writing the hashcode in hexadecimal, a chunk file is named something like

"3f21ada6_1.txt".
What is the purpose of the "_1" at the end? This is in case there is a hash collision. If there are two chunk files with block paths with identical hashcodes, then "_1" and "_2" are used to distinguish the files. A hash collition is extremely rare.

Suppose we want to determine if there is a chunk file with a certain block path P. We first compute the hashcode of P and see if there is a chunk file with that name followed by "_X". If there is such a file, we must open it and start to read it to see if that path of the chunk file is P.

Not Literally Storing Each Chunk File in its own File

In an older version of Fractal Block World each chunk file literally was its own file on the filesystem. A problem with this is that playing the game for several hours, there are tens of thousands of files.

Instead, we can bundle chunk files together into one big file. The big file is broken into "pages" (of size 256 bytes). A chunk file is then stored in some number of pages inside the big file.

The Manifest

MORE!!! MORE!!! MORE!!! MORE!!!