Hello - 

I recently started designing a tile-based game, but I'm not exactly sure what would be the best method for storing my tiles in the map that will be displayed. I understand that most maps are a simple 2D array with each dimension representing the different axes (x, y), but my game has massive quantities of tiles that need to be displayed at once (I don't have an exact number, but I know it will be over 60x30, which is 1800 at once). I'm fairly certain that the aforementioned construct will be too simple and costly for my needs. I'm also looking to delve into simple procedural generation in the future, meaning I want my method of storage to be able to be easily modified/populated. The best analogy of a game I could give for reference is Terraria, since it has both procedural generations and a bunch of tiles.

To simplify, my question is basically:

What would be an efficient way to store a map with large amounts of tiles (in the thousands), while still allowing the construct to be populated relatively easily?

Thanks for any input/help.

A 2D array is usually more than sufficient for 2D map storage and iterating through it. As long as you're not falling into any performance anti-patterns (e.g. drawing the entire map instead of just the screen, not walking the layers/cols/rows in memory-order, failing to batch draw calls, etc.) Draw efficiently, iteration is not going to be your bottleneck.

Back in the day we were drawing 320x240 screens with ~450 tiles (1 dense layer + 2 sparse layers) using software blitters at 60fps on 66mhz 486s, albeit at 8-bit color.

What's often more useful is chunking the whole map into regular sections, either so that you can stream them from disk or just to keep memory use down if it's a concern on your platform -- but that approach ultimately only amounts to a 2D array of map sections, which themselves are 2D arrays of tiles. Even something like a quad-tree is likely over-thinking a 2D game. There's an article floating around about optimizing minecraft-like cube storage, where they looked at various more-complicated storage schemes like RLE arrays and compressed octrees -- the conclusion was that plain old 3D arrays were the winner anyway, and I think Minecraft world sections are (or were) something like 32x32x256. Drawing performance comes from how they generate and optimize draw calls from this simple storage, not coming up with any sort of clever storage.

2 hours ago, Ravyne said:

What's often more useful is chunking the whole map into regular sections, either so that you can stream them from disk or just to keep memory use down if it's a concern on your platform -- but that approach ultimately only amounts to a 2D array of map sections, which themselves are 2D arrays of tiles. 

So are you saying that I could use a 3D array to store the map, with the added dimension being the chunk being referred to, and that each chunk has its own cartesian planes?

There are different ways to store it, but in a 3D array, the extra dimension would be the map sections. If you have a large map, and you cut that up into, say, 64x64 tile squares (which is your first two dimensions), then you can think of the 3rd dimension as if you picked up all those sections stacked them up, each section has a place in that stack, which is your third dimension. Up to this point, you just have all the sections themselves defined, but not how each section makes up the larger map.

What you need is a way of relating those sections in the larger 2D space of the map. One way is another 2D map -- think of it like a tilemap within a tilemap, only the outer tilemap contains map sections. When you draw, the sections might be 1024 pixels apart, and tiles might be 16 pixels apart. You'd find which few sections are on screen, where their corner is, and draw the tiles within it relative to it's corner, then you move over 1024 pixels where the next section is, and then draw it's tiles. Your drawing loop is now nested four levels deep, rather than two. You can have a single 4D array, or a 2D array (the section map) and many smaller 2D arrays (the section tilemaps) -- and you might collect the section tilemaps together as a single (now 3D) array, or not.

Now, really, if you want to think about streaming a very large map, is that you don't have to have all the sections in memory. Just the ones that are on-screen and a few nearby so that the player never sees them loading. In that arrangement, you'd not have a 4D array, or even a 3D array of map segments. You'd have a 2D array that's the map of sections, and each of those would be a pointer (or reference) to the small tilemap for that section. You load only the tilemaps for sections nearby, on demand, and you can free the tilemaps of far away sections as needed.

If that's not clear, feel free to ask again. But do keep in mind that all this complication might be unnecessary. This streaming sort of set up really only benefits you if tilemap memory use is high, or if loading the entire large map all at once is noticably slow.

You can tile an infinite plane with rectangular chunks and load them on demand:

• implement rendering of the part of a chunk that intersects the current screen viewport (clipping, at most, part of the tiles along two adjacent sides).
• If a chunk is the same size as the screen, at most 4 chunks in a rectangular tiling have a visible portion: draw their visible portions.
  With smaller chunks you'd have more overhead (and 1800 tiles represent a small tilemap, there's no reason to go lower resolution), while with larger chunks the worst case of 4 chunks would be the same.
• Meanwhile, load or generate procedurally in another thread or in pauses adjacent chunks within a certain distance from the viewport, and discard chunks outside another (bigger) distance from the viewport.
• In the simplest case, you can keep the whole map in memory (in chunks) and "load" chunks implicitly into cache memory upon access.
  Note that with a simple 2D array layout the cache only needs to contain 4 chunks at a time, with 25% utilization at worst, rather than a very sparse portion of very large arrays)

You're stressing about a number of tiles that a Super Nintendo can handle...

I currently have a 100x100 tilemap with 2 layers (one for the tiles and one for the characters) I can draw at once with absolutely 0 performance issues. I think I can push 1000x1000 no issues (at this point they become individual pixels so wtv), modern rendering pipelines are really hard to bottleneck and a 60x30 array is trivial.