c++ - Optimizing a simple 2D Tile engine (+potential bugfix) -

preface

yes, there plenty cover here... i'll best keep well-organized, informative , straight-to-the-point possibly can!

using hge library in c++, have created simple tile engine.
, far, have implemented following designs:

• a ctile class, representing single tile within ctilelayer, containing row/column information hge::hgequad (which stores vertex, color , texture information, see here details).
• a ctilelayer class, representing two-dimensional 'plane' of tiles (which stored one-dimensional array of ctile objects), containing # of rows/columns, x/y world-coordinate information, tile pixel width/height information, , layer's overall width/height in pixels.

a ctilelayer responsible rendering tiles either or partially visible within boundaries of virtual camera 'viewport', , avoid doing tiles outside of visible range. upon creation, pre-calculates information stored within each ctile object, core of engine has more room breathe , can focus strictly on render loop. of course, handles proper deallocation of each contained tile.

---

issues

the problem facing boils down following architectural/optimization issues:

1. in render loop, though not rendering tiles outside of visible range, still looping through of tiles, seems have major performance impact larger tilemaps (i.e., thing above 100x100 rows/columns @ 64x64 tile dimensions still drops framerate down 50% or more).
2. eventually, intend create fancy tilemap editor coincide engine.
   however, since storing two-dimensional information inside 1 or more 1d arrays, don't have idea how possible implement sort of rectangular-select & copy/paste feature, without major performance hit -- involving looping through every tile twice per frame. and yet if used 2d arrays, there less more universal fps drop!

bug

as stated before... in render code ctilelayer object, have optimized tiles drawn based upon whether or not within viewing range. works great, , larger maps noticed 3-8 fps drop (compared 100+ fps drop without optimization).

think i'm calculating range incorrectly, because after scrolling halfway through map can start see gap (on topmost & leftmost sides) tiles aren't being rendered, if clipping range increasing faster camera can move (even though both move @ same speed).

gap gradually increases in size further along x & y axis go, eating half of top & left sides of screen on large map. render code shown below...

---

code

// // [allocate] // pre-calculating tile information // - rows/columns   = map dimensions (in tiles) // - width/height   = tile dimensions (in pixels) // void ctilelayer::allocate(uint numcolumns, uint numrows, float tilewidth, float tileheight) {     m_ncolumns = numcolumns;     m_nrows = numrows;      float x, y;     uint column = 0, row = 0;     const ulong ntiles = m_ncolumns * m_nrows;     hgequad quad;      m_tilewidth = tilewidth;     m_tileheight = tileheight;     m_layerwidth = m_tilewidth * m_ncolumns;     m_layerheight = m_tileheight * m_nrows;      if(m_tiles != null) free();     m_tiles = new ctile[ntiles];      for(ulong l = 0; l < ntiles; l++)     {         m_tiles[l] = ctile();         m_tiles[l].column = column;         m_tiles[l].row = row;         x = (float(column) * m_tilewidth) + m_offsetx;         y = (float(row) * m_tileheight) + m_offsety;          quad.blend = blend_alphaadd | blend_colormul | blend_zwrite;         quad.tex = htexture(nullptr); //replaced sake of brevity (in engine's code, used globally allocated texture array , did random tile generation here)          for(uint = 0; < 4; i++)         {             quad.v[i].z = 0.5f;             quad.v[i].col = 0xff7f7f7f;         }         quad.v[0].x = x;         quad.v[0].y = y;         quad.v[0].tx = 0;         quad.v[0].ty = 0;         quad.v[1].x = x + m_tilewidth;         quad.v[1].y = y;         quad.v[1].tx = 1.0;         quad.v[1].ty = 0;         quad.v[2].x = x + m_tilewidth;         quad.v[2].y = y + m_tileheight;         quad.v[2].tx = 1.0;         quad.v[2].ty = 1.0;         quad.v[3].x = x;         quad.v[3].y = y + m_tileheight;         quad.v[3].tx = 0;         quad.v[3].ty = 1.0;         memcpy(&m_tiles[l].quad, &quad, sizeof(hgequad));          if(++column > m_ncolumns - 1) {             column = 0;             row++;         }     } }  // // [render] // drawing entire tile layer // - x/y          = world position // - top/left     = screen 'clipping' position // - width/height = screen 'clipping' dimensions // bool ctilelayer::render(hge* hge, float camerax, float cameray, float cameratop, float cameraleft, float camerawidth, float cameraheight) {     // calculate current number of tiles     const ulong ntiles = m_ncolumns * m_nrows;      // calculate min & max x/y world pixel coordinates     const float scalarx = camerax / m_layerwidth;  // how far (from 0 1, in world coordinates) along x-axis within layer     const float scalary = cameray / m_layerheight; // how far (from 0 1, in world coordinates) along y-axis within layer     const float minx = cameratop + (scalarx * float(m_ncolumns) - m_tilewidth); // leftmost pixel coordinate within world     const float miny = cameraleft + (scalary * float(m_nrows) - m_tileheight);  // topmost pixel coordinate within world     const float maxx = minx + camerawidth + m_tilewidth;                        // rightmost pixel coordinate within world     const float maxy = miny + cameraheight + m_tileheight;                      // bottommost pixel coordinate within world      // loop through tiles in map     for(ulong l = 0; l < ntiles; l++)     {         ctile tile = m_tiles[l];         // calculate tile's x/y world pixel coordinates         float tilex = (float(tile.column) * m_tilewidth) - camerax;         float tiley = (float(tile.row) * m_tileheight) - cameray;          // check if tile within boundaries of current camera view         if(tilex > minx && tiley > miny && tilex < maxx && tiley < maxy) {             // is, draw it!             hge->gfx_renderquad(&tile.quad, -camerax, -cameray);         }     }      return false; }  // // [free] // gee, wonder does? lol... // void ctilelayer::free() {     delete [] m_tiles;     m_tiles = null; } 

---

questions

1. what can done fix architectural/optimization issues, without impacting other rendering optimizations?
2. why bug occurring? how can fixed?

---

thank time!

optimising iterating of map straight forward.

given visible rect in world coordinates (left, top, right, bottom) it's trivial work out tile positions, dividing tile size.

once have tile coordinates (tl, tt, tr, tb) can calculate first visible tile in 1d array. (the way calculate tile index 2d coordinate (y*width)+x - remember make sure input coordinate valid first though.) have double loop iterate visible tiles:

int visiblewidth = tr - tl + 1; int visibleheight = tb - tt + 1;  for( int rowidx = ( tt * layerwidth ) + tl; visibleheight--; rowidx += layerwidth ) {     for( int tileidx = rowidx, cx = visiblewidth; cx--; tileidx++ )     {         // render m_tiles[ tileidx ]...     } } 

you can use similar system selecting block of tiles. store selection coordinates , calculate actual tiles in same way.

as bug, why have x, y, left, right, width, height camera? store camera position (x,y) , calculate visible rect dimensions of screen/viewport along zoom factor have defined.