A number of years ago I worked on an open world game that got cancelled. Despite it not being released, I learned a few things.
If you try to make a game where the player can walk around a large world without loading screens, chances are that the whole world won’t fit in memory at once.
Since it can’t all fit in memory at once, as the player moves around you are going to have to unload old chunks of the world to make room for the new chunks that the player is about to enter.
To simplify the problem, it’s really common to break the world up into a grid, and keep a radius of tiles loaded around the player at any one time.
In the above you can see that 9 tiles are kept in memory. If the player crosses the boundary to the cell to the left, we unload the cells on the right (red cells) and load new cells in on the left (green cells).
The idea is that we keep a border of cells loaded around the player at all times so that they never see the edge of the world, but we don’t have to keep the whole world in memory at the same time.
The size of the cells can vary depending on the actual needs of your game. If you can travel very quickly in your game, you may need larger cells.
Instead of just having 9 large cells loaded at any one time, you may instead opt to have smaller cells but have more layers of them loaded at any one time. The below has 2 layers of cells loaded around the player, so has to keep 5×5 = 25 cells loaded at any one time. This can give you more granularity if you need it.
The number of cells you have to keep in memory when keeping N layers of cells loaded around the player is 
1 layer means 9 cells, 2 layers mean 25 cells, 3 layers mean 49 cells, 4 layers mean 81 cells and so on.
This isn’t the only way to arrange your world tiles though. You can also make it so every row of tiles is offset by half a tile from the one above it. That gives you a setup like this:
With this setup, keeping a single layer of cells loaded around the player takes only 7 cells instead of 9. That might not sound like much, but that means that your memory budget is 129% of what it was the other way.
Alternately, it means you can keep your cells at the same quality level but only have to load 78% as much stuff from disk as the player moves around the world.
For keeping N layers of cells around the player you need to keep 
1 layer means 7 cells, 2 layers mean 19 cells, 3 layers mean 37 cells, 4 layers mean 61 cells.
Here’s a table to show you how the regular grid compares to the half offset grid for cell counts. The savings do get better with more layers, but not very quickly.
Overall, this is a pretty cool technique that is pretty low cost if you do this early in the project. Once you have a lot of content divided into a regular grid, it can be a challenge to move over to this half tile offset grid.
Some Notes From Readers
@chrispewebb said that an issue he’s faced when going this method is having T junctions on LODed terrain, but that skirts should be able to help there.
@runevision pointed out that while the memory requirements are lowered, so is the shortest distance (radius) from the player to data that isn’t loaded. One idea to deal with this if it’s a problem could be to use smaller cell sizes and to do more layers to make up for it.
The blog at the bottom of the sea 
You can achieve a similar effect by using a Euclidean radius to get a circular area of loaded tiles rather than a square grid shape. The corner tiles are sqrt(2) further away from the player than tiles directly to the north/east/south/west and can be dropped. Simply computing the distance from the tile center to the player could be the metric for loading a tile. Using this metric, the number of tiles is (PI/4)*(2N+1)^2, which is close to 78% of the square tile count. I would guess that the half grid offset also approaches a ratio of PI/4 for large enough N, but I haven’t done the math.
LikeLike
I thought this was a good article but my thoughts ran to how much of the memory would need updating when a player moves. For the regular grid with N layers, horizontal or vertical moves need 2N+1 blocks and diagonal moves need 4N-1 blocks to be updated. For the Half Offset Grid, it is always 2N+1 blocks, regardless of direction moved. This is a good thing because it makes it easier to create smooth game play when you don’t have to worry about updating different numbers of blocks depending on the player’s move. That said, the Half Offset Grid never reaches the peak efficiency of the Regular Grid but it is always better than the worst case in the Regular Grid.
Layers Regular Grid X or Y Diagonal Half Offset Blocks
1 3 X 3 = 9 3 33% 5 56% 7 3 43%
2 5 X 5 = 25 5 20% 9 36% 19 5 26%
3 7 X 7 = 49 7 14% 13 27% 37 7 19%
4 9 X 9 = 81 9 11% 17 21% 61 9 15%
5 11 X 11 = 121 11 9% 21 17% 91 11 12%
6 13 X 13 = 169 13 7.7% 25 15% 127 13 10%
7 15 X 15 = 225 15 6.7% 29 13% 169 15 8.9%
This table shows the number of layers, Regular Grid arrangement and total blocks, blocks updated for X or Y moves (number and percent of total), blocks updated for diagonal moves, and the total for Half Offset followed by number and percentage of updated blocks. It looked like it was aligned when I typed it in but I suspect it my look crooked once I post it.
From looking at this chart, it would seem that the more layers you have, the smaller the percentage needing update. There is another advantage to having many layers in that you can allow the player to roam among several blocks without update. For example, if I have a 15 X 15 Regular Grid that gets loaded when you start and only gets updated when the player leaves the central 5 X 5 block area. When updating like this, there is a choice whether to update only enough blocks to keep the player in the center 5 X 5 or whether to update enough blocks to place the player in the center block. In the latter case a priority for which block to update is suggested by the layers; load the blocks closest to the player first.
I’m sure you could allow a player a 19 block roaming area within a 169 block Half Offset Grid. One of the reasons I suggest a roaming area is to prevent excessive updating when a player frequently crosses into another block and returns.
LikeLike
What I do is add a bit of hysteresis by using a different block depth/distance for creating and deleting blocks. For example, blocks are created when they’re within 5 block widths of the player, and deleted when they’re at 6 block widths. This means that a player can walk back and forth within a block and no other blocks are created or deleted. It’s more complex and takes a bit more memory, but may work well depending on the situation.
LikeLike
Saw something similar today when researching this topic. Insomniac Games used a similar technique in Sunset Overdrive, except they used circles with a radius. https://www.gdcvault.com/play/1022268/Streaming-in-Sunset-Overdrive-s
LikeLike
Pingback: hikari – Terrain Mesh Generation | devfault