How should I store world data in a 2D grid sandbox game?

Question

I'm just a beginner game developer and working on my own first project (beyond copying other games for learning skills).

Because I really like sandbox games (like Minecraft, Rimworld, Terraria etc..), I am trying to make a 2D grid-based sandbox game.

For now I am building a plan for my game's base architecture, and I'm having an issue managing world data (for more specifically, handling Block/Tile Data).

In a sandbox game, you can easily place or remove some blocks (or tiles) as you like. So you need to store it in some kind of storage and sort it so that you can access these blocks easily.

So I thought I should make an Array that holds pointers to Tile Class instances, and the index in the array corresponds to the grid's index. I started writing code based on this idea.

But here is the problem: since not every tile's size is 1x1, some may take 2x3 blocks. If i just put this object's pointer in the array, there are 6 identical pointers stored in single array.

I think that may not the best way to handle tile data.

I thought there might be some way to handle tile data better than to just put a pointer in array.

So how should my game handle multi-grid-cell sized block (or tile) data?

Answer 1

But here is the problem, since not every tile's size is 1x1, some may take 2x3 block size. and if i just put in Array this object's pointer, there is 6 same pointer will store in single array.

Don't treat the 2x3 block as one tile. Treat it as 6 different kinds of tiles with the specific behavior that when you add or remove one of them, you also add/remove the other 5 of the group. That will really cut down on the corner-cases you need to handle.

I also agree with Damon: Do not represent each block with a full-blown pointer to an object. That's going to cause an overhead which is non-negligible in this case.

Tiles which do not need an unique state (like a dumb piece of rock) do not need an own object. All rock-tiles can share the same object. You can represent them with an integer representing the type-ID. Use the shortest type of integer which still fits as many tile-types as you have (1 byte if you stay under 255 tile types, 2 byte if you stay under 65535). So for example, if you need the texture of the tile at coordinates x:y of the current chunk you would do

texture = tileTypes[chunk.tiles[x,y]].texture;

This will also make your serialization and deserialization a lot easier. Writing and reading a 2d array to/from files is rather simple. But if you need to come up with a scheme so serialize your tile class, it gets a lot more complicated. A fast and solid serialization system is important for infinite world games like Minecraft, because they suspend those parts of the world which are outside of the sight range to hard drive and load them when the player returns.

For those kind of tiles which do have unique state (like chests, signs or smelters in Minecraft), each of these tiles will require an own object to hold its state and handle its interaction logic. The tiles should still be represented as integers in the map chunk array. But their tile-specifc data should be stored in separate data-structures which serves as a lookup table to link tile-coordinates to tile-specific state objects.

Which data-structure would be appropriate for this purpose depends on how many of them you have. When you expect to have about as many functional as non-functional objects, then it might make sense to store their states in another 2d array with the same dimensions as the map chunk (with the entries which map to non-functional tiles holding null values). When you want to be able to handle a few hundred functional tiles per chunk, then you might want to use a binary tree or hashtable to map coordinates to states. When you are only expecting a single-digit number per chunk, you can just store them in a list in which you perform a linear search when you need to.

Answer 2

There are two major things to keep in mind with that kind of game: Memory and cache. While that sounds simple, you could write a bookshelf full of books about this.

Memory is O(N²) or O(N³) respectively in that kind of game, so you are being kinda desperate from the start because you're fighting giants.

If you can get away using one byte of storage per cell (requiring a table lookup or similar) instead of 8 bytes for a pointer, you will want to do that. This not only cuts down memory requirements, but it also increases how many cells will fit into cache.

Next, objects are not cells (even though they may look alike). Up to a maximum number of objects is stored outside the grid (object with properties and position). Terraria, which you named as an example, stores around 400 objects maximum (drop more, and the oldest one disappears). This is not perfect, but it is rarely a problem and it "works".

Similarly, enemies (or NPCs) are heavily pruned away. What isn't visible doesn't exist (reverts to a minimum or even a default state) and is not simulated.

Also, you will want to prune away as large as possible unused areas as soon and efficiently as you can. Lastly, you will also want to make sure that what belongs together is together.

Which leads to... spatial subdivision algorithms, of which there exist a couple different ones. Minecraft uses, if I am not mistaken (not 100% sure) a sparse octree. Hierarchical grids may be another option. Different algorithms have different pros and cons, you may even want to combine several.

In 2D you might still get away with storing the whole world in an array (though that's very sub-optimal cache-wise, you spend a lot of game logic in looking at nearby cells so what's close should be stored close together). In 3D, you have pretty much no choice but to rigorously prune away huge regions of unused space, as for example with a sparse tree. Otherwise there's simply no way you can store a world of any serious size in memory.