2
\$\begingroup\$

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?

\$\endgroup\$

2 Answers 2

3
\$\begingroup\$

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.

\$\endgroup\$
7
  • \$\begingroup\$ i like the idea of that non-functional tile (AKA dumb piece of rock) managing thing. i did kind of same thing for handle effect on my old project. which instead of make object per effect, make one object and store needed info (time, location, direction etc) than one effect object can handle a list of effects. -- so as i follow your advise as i can and re planning my work, should it be instead of just storing, array will store tile visual info(tile type) and tile's function type which indicate what storage you should find to needed object? \$\endgroup\$
    – HM Ham
    Dec 21, 2018 at 12:31
  • \$\begingroup\$ @HMHam I am not sure if I understand you correctly. What I would suggest is that you have a 2d array of integers representing a world chunk. Then you have an array of TileType objects with one entry per type and the array indexes matching the integers in the world chunk. So there is only one object which represents the rock TileType. So if you need the texture of the tile at coordinates x:y you would do texture = tileTypes[chunk.tiles[x,y]].texture; \$\endgroup\$
    – Philipp
    Dec 21, 2018 at 12:44
  • \$\begingroup\$ Sorry since English is not my first language it would been hard to understand what i said. and yes i got that tile type idea. but i was not sure for handling Functional objects which has custom data-structure or behavior. i thought whenever that kind of object created, read there Function type and store as type. and instead of just put texture type, put function type either. than when i need to access that block, i can do with <inventory = ObjManager->GetStorageByType(E_Chest)->GetInventory(x,y)>. but i am not sure that is the best way and hope to hear if you have a better idea \$\endgroup\$
    – HM Ham
    Dec 21, 2018 at 14:12
  • \$\begingroup\$ @HMHam How many of these "functional objects" are you going to have compared to the number of "non-functional" objects? \$\endgroup\$
    – Philipp
    Dec 21, 2018 at 14:32
  • \$\begingroup\$ for now, Liquid , Storage , Crafting , Stationary weapon (like mortar or missile) kind of things. but after i kind of finish the project i want to add Wiring or Transporting (like conveyor) system too. \$\endgroup\$
    – HM Ham
    Dec 21, 2018 at 16:24
1
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ i read how minecraft handle world data once, didn't understand all but i understand that data structure start as whole world and keep cut area by area until it sizes as 16*16*16 block size. so i thought at last, there would be some arrays holding small area's data. -- few days ago i saw the 'unreal engine grid tutorial' and in the tutorial i saw he was 'Linking' the object with grid. when object is placed, it mark as "Occupied" on there location's grid data. and since you said Object is not a cell, he's way would better than put pointers in array \$\endgroup\$
    – HM Ham
    Dec 21, 2018 at 12:01
  • \$\begingroup\$ but the question is, if i use Linking way to handle place-able objects, i need to store pointers at arrays too or if i don't store pointer, i thought it will take much CPU to find the placed object at certain location or by given information. so i wonder that linking method will be more efficient than store in array which you can find object so fast if you know the index. \$\endgroup\$
    – HM Ham
    Dec 21, 2018 at 12:08
  • \$\begingroup\$ You can keep objects in a KD-tree if you like, but for "few hundred" it's not unlikely that brute force is just as good as everything. You'll most likely visit them all each frame anyway, so no issue. There's no link to store, really. The cell where an item is in doesn't need to know that item. If you do store this, you'll again have to provide 8 bytes of storage per cell, which is just what you want to avoid. \$\endgroup\$
    – Damon
    Dec 22, 2018 at 13:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .