Rendering three-dimentional array of tiles (as a tilemap)

Question

I'm trying to create 2d game engine in C++ using SDL2 (actually some code was migrated from SFML). I want to have a flexible multilayer tilemap that can store different types of tiles. My current version of this kind of map uses three-dimensional array of pointers to base class of tiles ("tilemap").

First of all - is it even a good approach?

I'm using pointers to make tiles polymorphic (eg. ground tile (tile_basic) has it's act number and texture id, but chest tile (tile_chest) has also a list of items in it). However scanning trough this array every time when I'm rendering my map would take a lot of time. So I'm scanning trough three-dimensional array of sprites (drawable objects) which is generated from the tilemap every time when new sprites are meant to be shown on the screen.

std::vector<std::vector<std::vector<mg::CompactSprite> > > sprites;

The first two dimensions are quite constant, they depend on the size of the application window. When moving the camera sprites move up to their size (width, heght) and when they are about to exceed this limit, their coordinates reset (x, or y, depending on which direction the camera is moving), getting it into simple words - I'm using modulo.

The problem is that this is terribly slow (~43ms with 23x18 map with only few layered tiles; using SDL2, similar results with SFML). I know I could render the whole visible area to the one image and just move that image and then render only new areas, but then I won't be able to make animated tiles without listing their coordinates, checking if they are in the visible area and then rerendering them which sounds bit overcomplicated, and I'm not quite sure if it'll really boost the rendering process.

---

So is there any better way to do this? Or I should change my approach?

Answer 1

What you have here is not a multidimensional array. What you have is a vector which references a bunch of vectors which reference a bunch of vectors which reference a bunch of objects.

The problem with these many layers of indirection is 1. that your CPU needs to jump through all these memory references each time it looks for a tile and 2. that these memory structures likely end up all over the place in RAM instead of in one block of memory. Why is that a problem? Memory locality!

But you can avoid this by using an actual multidimensional array mg::CompactSprite tiles[width][height][depth]. Arrays are always a contiguous block in memory. If you insist on using an std::vector instead of an array, create a single vector with a size of width * height * depth. You can then access individual tiles with tiles[tiles.x + y * width + z * width * height] (when this is too unreadable, you can easily build your own 3dArray-class around it which abstracts this away)

Another way to improve memory locality is to make your tile-class as small and simple as possible. Polymorphism is something I would avoid here. Anything not related to their appearance (like the content of a treasure chests) should be stored somewhere else.

When moving the camera sprites move up to their size (width, heght) and when they are about to exceed this limit, their coordinates reset

I am not sure if I understand this correctly, but it sounds to me like when you move the camera, you aren't moving the camera but instead move all the tiles, which implies that you iterate the complete array and overwrite the coordinates of every single tile. This is a bad idea, because it likely takes quite a lot of time to do that. A tile doesn't even need coordinates, because these are implied by its position in the array. What you should be doing is:

• calculate which tile index ranges are inside the viewport
• do a loop over the tiles which are inside these index ranges
• draw each tile with the position calculated from the camera position and the indexes of the tile