Have huge grid data in a way so a 2d range can be pulled effectively?

I’m creating a 2d game, with a huge tilebased world. The grid is made up of 16x16px tiles. The grid also has a layer dimension: A couple of background graphics layers, a couple of action layers (game logic, collision, more) and a foreground graphics layer.

With a 1024*1024 grid and say 5 layers thats 5242880 tiles. So for performance reasons, I can’t have the whole world active at once - I can’t even create a GameObject for each tile to activate/deactivate.

So I think I need a solution where the underlying, layered griddata is stored in a way, so I blazingly fast can pull e.g.:

GetTiles (int minX, int maxX, int minY, int maxY)

This method could be called by the camera, based on what’s visible. The return value is used to create gameobjects and place them correctly.

My first idea was to store each layer in a 2d array. But e.g. the foreground graphics layer is rarely used. So that 2d array would mostly hold nulls, which is quite a waste, right?

My second idea was having a Tile class, where each Tile holds an gridX-, gridY- and layer value. And then have an array of all tiles in the game. Problem is, that then I would have to iterate through the whole list with something like:

if (x > minX && x < maxX && y > minY && y < maxY)

…which would create a framerate hiccup.

So my question is: What’s the best way to store a lot of layered grid data, so I quickly can pull a 2d range?

I’m a quite experienced front-end programmer, but I barely know anything about storing larger chunks of data or other back-end’ish stuff.

I’m not expecting a ready-to-use-coded solution… but any starting points, explanation of key concepts or reads/tutorials on this subject is most wellcome! I really don’t know where to start… Thanks in advance :slight_smile:

Hello, as you said there are 2 aspects to take into consideration:

  • Storing data
  • Retrieving it

1/ Storing data
Can be done with a simple 2D array if your target platform has enough memory, for example on PC even 100 bytes per tile your 1024*1024 grid * 5 layers would be only 500MB and that is easily supported by all your potential users nowadays, it’s clearly the fastest to both create and performance-wise so go for it if you can.

If you’re targeting a low RAM platform like mobile or arduino for example you’ll have to spend a bit more time on this.

You can think of several ways to proceed but base idea is to offer the same feature as the basic array (poll data at XY coordinates) and behind the scene you have something like the suggested kdtree or simpler, dictionnary(X) of dictionnary(Y) that you load from resources and a way to unload distant chunks.

I won’t go too much into details because it also depends a lot on how you create your world.

2/ Retrieving data
No need to loop through everything, you know the size of the viewport (like, 20 horizontal tiles by 14 vertical ones) so you only have to monitor the player’s movement and when the min/max values of the currently displayed X & Y aren’t matching anymore you poll the data grid for the new tiles and release the unused ones !

I hope it’s clear enought, let me know if you need some more explanations…