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

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?

• What does your profiler say about where your bottleneck is? we could guess, but considering that we haven't even got your whole sourcecode (no, please don't post it) we would likely guess wrong. So please run the game with profiling enabled and tell us what it says. Apr 10, 2016 at 18:50
• It uses around 13MB of RAM, CPU (1 core) is on full (no sleeping), without displaying the map the "game" loop executes in ~1ms. Most memory is consumed by some undertemined types (SDL stuff?). The tilemap is about 231KB. Apr 10, 2016 at 19:06
• @AlexandreVaillancourt Sorry about that. English is not my native language. I've tried my best to explain what I mean without giving a code, because it's huge and splitted into multiple files. If you could point me the parts which you don't understand, or which you think might need some polishing, I could try to explain them better. You can always edit my question if you want and I would be really grateful if you could make some parts more clear. Apr 10, 2016 at 20:58
• just add a break or two. Apr 10, 2016 at 21:08
• Philipp's tip is the right one. What does your profiler says? Visual Studio 2013 and up comes with a profiler; you can use that to check where is the most time spent. Apr 10, 2016 at 21:54

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
• Thanks for answer. So I'm not using sprites anymore, just rendering stuff with SDL_RenderCopy. I'm using 2-dimensional dynamic array (not vector). I tried using 1-dimensional, but since the number of layers isn't constant and it varies on different coordinates it wasn't possible to properly calculate coordinates having only single array index. So now the second dimension is to store all the tiles in certain coordinate which is calculated from first dimension. It's much faster, but still I'm not quite sure if it's fast enough. Rendering one frame takes about 2ms but sometimes it's even 14ms. Apr 11, 2016 at 20:25
• @Mohrcore 14ms per frame = 71 frames per second. That's more than enough. Apr 11, 2016 at 20:45
• Oh, sorry, didn't think of that simple calculation while posting my comment. There will be also some game logic that will take some time but I guess it'should be ok for now. But I was asking because I noticed that the map still doesn't move smoothly. I know that this question isn't really related to the original one but is the std:clock() a good way to measure time? I'm using it when moving camera and when rendering frames (I've noticed that if I don't give some time between rendering frames the performance drops dramatically. I suspect that the CPU is giving the GPU instructions too fast). Apr 11, 2016 at 21:25
• OK, neverming, it was a matter of startup. The slowdown only occured at startup, so it's not the matter of clock. Apr 12, 2016 at 15:41
• @Mohrcore std::clock only measures the CPU time spent on the current process, not the actually elapsed real-time, so it can get you wrong results. More accurate timers are supplied by the std::chrono library. Apr 12, 2016 at 15:59