- Home /
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 :-)
Hi, you could use a k-d tree to store the tiles, this could help optimize the unused/empty space and is fast to access.
Answer by _met44 · Apr 01, 2015 at 02:53 PM
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...
Thanks a lot for thorough explanation!
Based on your suggestion, I’ve made my on TileData class, and used it in a simple 3d grid:
private TileData[,,] tileDataGrid = new TileData[1024, 1024, 5];
I’m retrieving all layers within a “2d range” (exactly the size of the viewport) like this:
public void ActivateTiles (int tileX, int tileY, int width, int height) {
for (int x = tileX; x < tileX + width; x++) {
for (int y = tileY; y < tileY + height; y++) {
for (int z = 0; z < amountOfLayers; z++) {
if (tileDataGrid[x,y,z] != null) {
// Instatiate...
}
}
}
}
}
This is working fine in the editor, but I am eventually targeting mobile - so I’m looking for a way to store it better.
The problem with the array solution is, that a foreground layer, only holding a couple of cloud-tiles like this:
01233456789
0
1
2
3
4 ccccc
5 ccccc
6
Takes up this memory, with . representing null-cells:
01233456789
0xxxxxxxxx
1xxxxxxxxx
2xxxxxxxxx
3xxxxxxxxx
4xxxxccccc
5xxxxccccc
6
Is there a datatype in c#, where I can retrieve a 2d range (preferably as simple as above), but without having to store all the null-cells?
If the kdtree or dictionnary(X) of dictionnary(Y), that you mentioned, can do it, I would love a deeper explanation or a sketchy example! :-)
Thank you very much so far!
Hey man sorry i wrote you a super long detailled answer and lost it thanks to this sh*tty site, super frustrating :s
Anyways I'll try to give you the core idea with the little patience I have left:
Forget about complex data structure like trees, you don't need them
Forget about unused space, at least for a start. Assets are compressed and chunks of data with identical value respond well to compression so unless you face a memory issue at some point don't think about it just yet.
Try the Dictionnary of Dictionnary method i was mentionning, it'll be easy to code and work with in general, and should get the job done
The method goes like this:
Choose a chunk size, like 10x10 tiles, and make prefabs/scriptableObjects/text asset (which ever is more convenient to you) for each chunk
Poll tiles based on player viewport: if player sees 20 horizontal tiles and is at position [30,62] you only need tiles from 20 to 40 on the X axis. Note that if you memorize the currenty $$anonymous$$/max of X & Y you'll only need to load/unload the difference when moving and not the entire viewport...
When polling for a tile, let's say at location [42,58], divide each index by chunk size you picked so with a chunk size of 10 your chunk index would be [4, 5]
Check if this entry exist in dictionnaries and if not load the corresponding chunk from resources and add it to the dictionnary
Once you have loaded the required chunk poll it for the local coordinates of your tile, so in our example it would be [2, 8]
Don't forget to clean up unused chunks based on viewport of the player
summary:
GetTile(x, y)
| GetChunk(x / chunkX, Y / chunkY)
| GetChunkTile(x % chunkX, y % chunkY)
Let me know if it helps :)
Cheers
Your answer
Follow this Question
Related Questions
How do i make a level editor for a 2d platformer game? 0 Answers
Unity 2D tiles and grid 1 Answer
Check if object is on grid 1 Answer