Sunday, July 4, 2021

Revisiting the Chunking Engine

Last August, I wrote a post about my tilemap chunking engine.  The initial design involved loading 9 chunks of map data around the player, C0 being the chunk the player is on at any given moment.

9 Chunks Around Player

As the player moves around the map, loaded chunks that fall outside this list of 9 need to be saved and unloaded.  Back then I was concerned about figuring out how to unload the adjacent chunks beyond this list of 9 around the player.  Here was my thinking and approach.
"As the player moves around, there is a constant check against the player position and the id of the chunk that is two chunks away from the player's position.  Those need to be saved, then unloaded.  Currently, the check is very precise at exactly 2 chunk sizes away from the player."
The implementation required code that calculated up to 21 chunks at a time.  After coding this approach, I recall how frustrated I was that chunks would get missed when I dragged the player around the map from within Unity's Scene view at runtime.

Recently, it dawned on me that my original design had a very serious flaw.  Any player teleportation code I might add in the future would render my chunk unloading method totally useless.  In that use-case, every chunk outside of the player's new 9 chunks would need to be unloaded, including the previous 9 chunks the player was whisked away from.  It was at that moment I realized I was looking way to narrowly at the problem and the solution was embarrassingly simple.  That is what I wish to share with you in this post.

The chunk engine needs to manage three lists of chunk ids and perform three actions against those lists.  In my engine, a chunk is defined as a 25x25 tile section of the tilemap.  When I create the Perlin-based tilemaps, I store each chunk's tile data in a JSON file, using the filename to indicate the chunkid and tilemap it belongs to (I have multiple tilemaps).  

The first list to manage is the list of chunks that are loaded into memory.  This list must always include the current 9 chunks around the player.  My first method is named CheckChunksToLoad(int direction) in which I pass a direction value in each Update cycle.  I start with 0, the player's chunk, and rotate clockwise from C0 to C8 as shown above.  Using a switch statement, each cycle is responsible for one thing, checking to make sure the chunk at the direction is loaded in memory.  When my direction = 9, it is reset to 0, and the cycle repeats.

The second list to manage is the list of currently loaded chunks EXCEPT the 9 around the player's current position.  For this, I have a second method named CheckChunksToUnload() which creates a new List<int> chunkIdListToKeep.  It builds the current list of 9 chunks that must remain in memory.  Next,  it updates the third list to manage, which is the chunks that must be unloaded.  Elegantly, one line of code updates this list once I know which chunks to keep.

_chunksToUnloadList.AddRange(_loadedChunkIdList.Except(chunkIdListToKeep).ToList());

The third method is responsible for unloading a single chunk from the _chunksToUnloadList, and it does so with each Update().  It is aptly named UnloadAChunk().  This method, which is 15 lines of code, is so much simpler than trying to calculate 21 chunk ids.  If the _chunksToUnloadList.Count > 0, it means a chunk needs to be unloaded.  So, it grabs the first chunkId from the list and calls the method which saves the changes to that chunk and updates the JSON file.  That method also clears the chunk from the tilemaps and frees up memory.  Once this is done, the method ends with two very important lines which removes the chunkId from both managed lists.

_loadedChunkIdList.RemoveAll(i => i == chunkId);

_chunksToUnloadList.RemoveAll(i => i == chunkId);

There are several advantages to the new approach.  I only ever need to calculate the chunkIds of the 9 chunks around the player.  Every other chunk on the map gets cleaned up.  The engine runs faster and provides chunk cleanup regardless of how I manage the player's position.  It just works.

I will leave you with some calculations you might find useful if you are working with a tilemap and need to identify chunks to unload.  

int chunkId = _chunksToUnloadList.First();

int maxChunksWide = _ms / _cs;

int yVal = chunkId / maxChunksWide;

int unloadChunkAtY = (_cs * yVal);

int xVal = chunkId - (yVal * maxChunksWide);

int unloadChunkAtX = xVal * _cs;

The above calculations allow you to determine the 0-based x (horizontal) and y (vertical) coordinates of the first tile in each chunk of the tilemap where the first tile is the bottom-left tile in the chunk and the chunks start in the bottom-left corner of the tilemap.  The _ms variable is the width of the tilemap assuming the tilemap is square.  The _cs variable is the width of a chunk in number of tiles.  As an example, if you have a tilemap that is 125x125 tiles, with each chunk being 25x25, you will have the following sample data.

chunk 0:  y=0, x=0
chunk 1:  y=0, x=25
chunk 2:  y=0, x=50
chunk 3:  y=0, x=75
chunk 4: y=0, x=100
chunk 5: y=25, x=0
...
chunk 24: y=100, x=100

For the curious, I do not use the tile palette or rule-tile system in Unity.  I coded my own rule-tile system which essentially does the same thing (don't ask why).  This means my chunk engine does not (yet) have the ability to handle chunk edge-tile rules which would blend the tiles properly at the chunk edges.  This is something I am aware of and will address in the future.  Likely, the solution will involve loading an extra tile around each chunk so the engine knows what tile exists beyond the edge of the chunk.  But that is another backlog item for the future.  

I hope you found this post interesting.  Please feel free to leave comments.  Thanks for reading along.

Until next time...

No comments:

Post a Comment

Feel free to leave a comment. All comments are moderated.