Help me optimize

This is the drawing method of my tile engine.
The point is, when a button is pressed (left,right,up,down) the x and y offsets are changed. if the offsets are changed the map is updated and goes through the 3 nested for loops. If the offsets have not been changed then that last draw will be redrawn. So when idle I get 999+ fps when I move the map the fps goes down to about 55 because of the expensive content of the 3 nested for loops. I know that somehow I need to get rid of the if statements and the multiplies in the loops but I can't think of how I would do it.
Any help is appreciated.

Code:

---

int CMap::DrawMap(SDL_Surface *dest_surf, SDL_Surface *src_surf){
  SDL_Rect dest;
  SDL_Rect src;
  int y,x,lyr;
 
  /* previous offsets */
  static int pre_x_offset = -1;
  static int pre_y_offset = -1;
 
  /* Checks if map needs updating */
  if(x_offset != pre_x_offset || y_offset != pre_y_offset){
    for(lyr=0;lyr<LAYERS;lyr++){
      for(y=0;y<y_tiles;y++){
        for(x=0;x<x_tiles;x++){
         
          dest.x = (x * TILESIZEX) - x_offset;
          dest.y = (y * TILESIZEY) - y_offset;
         
          /* Does not draw outside the display_size box */
          if(dest.x > display_size_x) continue;
          if(dest.y > display_size_y) continue;
          if(dest.x < -32) continue;
          if(dest.y < -32) continue;
         
          /* The source coordinates of the tile map */
          src.x = MAP[lyr][y][x].xpos;
          src.y = MAP[lyr][y][x].ypos;
          src.w = TILESIZEX;
          src.h = TILESIZEY;
         
          /* Blit one tile at a time to a buffer */
          SDL_BlitSurface(src_surf, &src, buf, &dest);
        } 
      }
    }
  }
  /* Nullify dest rect blit buffer to destination surface*/
  dest.x = 0;
  dest.y = 0;
  SDL_BlitSurface(buf, NULL, dest_surf, &dest);
 
  /* Updates previous offsets */
  pre_x_offset = x_offset;
  pre_y_offset = y_offset;
  return 0;
}

---

Only loop through the region that you're currently *needing* to render. Figure out where the start and end x/y coordinates are for your screen's bounding box and then relate that to the closest tile in your map and then start the loop from there, completely ignoring all other tiles.

So you mean instead of updating the whole map, just update the screen. It sound's so simple but I never would have thought of it.

I've done this, but I'm not sure if I have calculated it properly because my fps are still about the same. I whipped it up really quickly.

Code:

---

  int y,
      x,
      lyr,
      scr_x_low = x_offset / TILESIZEX,
      scr_y_low = y_offset / TILESIZEY,
      scr_x_hi  = x_offset + display_size_x / TILESIZEX,
      scr_y_hi  = y_offset + display_size_y / TILESIZEY;
     
  /* previous offsets */
  static int pre_x_offset = -1;
  static int pre_y_offset = -1;
 
  /* Checks if map needs updating */
  if(x_offset != pre_x_offset || y_offset != pre_y_offset){
    for(lyr=0;lyr<LAYERS;lyr++){
      for(y=scr_y_low;y<scr_y_hi;y++){
        for(x=scr_x_low;x<scr_x_hi;x++){
          dest.y = (y * TILESIZEY) - y_offset;
          dest.x = (x * TILESIZEX) - x_offset;
  .
  .
  .

---

Yup, exactly. Probably one of the easiest optimizations to make.

Here is how I did it:
All my tiles are stored in a vector (just contains the texture and some flags).
Then I use 2 functions to update the map, 1 ScrollX function and 1 ScrollY function. In these functions all I do is update betwean which tiles I should draw (which tile is in top left, top right, bottom left).

Then in the drawing function I just draw the tiles based on these numbers. This does not involve nested for-loops or anything, the only thing is a single for loop in the drawing-method.

Ok I'll have to go have have a think about how I am going to do it. Back to the pen and paper I think :) Thanks for the help.

Shakti and I have talked about this forever. There is a super fast way to draw tiles and a super slow way. The for-loop is the super slow way.

What is the difference between displaying tiles and displaying a scrolling tilemap?

1. Starting tile image changes.
2. ScrollX and ScrollY determine which tile you are 'starting at'
3. RowCounter determines which row you are on.

So here is how you do it normally.

Start at grid(0) in the upper left corner of the screen and render tiles and increment the starting offset until you reach or go beyond the right side of the screen. Then add WidthOfMap to RowCounter and add that value into your starting offset be it 0 or whatever. Keep doing this until the whole screen is rendered, or until you overrun the tile map bounds.


So it comes down to 3 increments instead of 3 fors.

Thanks Bubba, it's really late right now so I will read your post again tomorrow but it does make sense.

sand_man, you might want to try using a larger background bitmap that you scroll with. When the player scrolls within the large background bitmap, it'll be fast because you won't need to to even look at the map indices; you'll just adjust the offset portion of the background bitmap and blit. But when the scroll goes beyond the large background bitmap, you'll have a problem: you'll have to redraw the map onto the large background bitmap. OK, when this redraw happens, there'll be some choppyness. You might be able to detect when the surface is about to redraw and do it in a thread.


Also, think about eventually changing SDL_BlitSurface. There's an undocumented function in one of SDL's include files that doesn't check for the screen border. You'll crash the program if you draw outside, but you ought to get more speed because for most of your pixels you know their niside the screen.

I did have a larger bitmap but I just changed this because I wanted to blit directly to the screen instead of an intermediate surface. Then I realised that to check if the map needs updating that I would need an intermediate surface to revert to if no updating is needed. The intermediate surface I'm using now however is the same size as the screen where as before the surface was the entire size of the map which slowed it down quite a bit. I haven't had any time to sit and think about this but hopefully I'm able to use Bubba and Shakti's technique without too much more trouble. But having a larger surface than the screen is out of the question.

Having a larger surface than the screen eats memory unnecessarily. Video memory is still a precious resource and at most you will get a 2048 x 2048 map because that is the absolute maximum size of any texture on any card to date....I think.

You must use tiles.

Quote:

---

Having a larger surface than the screen eats memory unnecessarily. Video memory is still a precious resource and at most you will get a 2048 x 2048 map because that is the absolute maximum size of any texture on any card to date....I think.

---

The video memory backbuffer the screen will pan on will be something like 1024*1024. In most cases, he'll be able to scroll smoothly on a 640x480 screen; he's using a video memory blit from the background. But when the visible region he's panning on intersects the backbuffer border, he must then redraw the tiles onto the backbuffer. This redraw is slow but he may might be able to do it faster using a fairly large system memory bitmap and blitting portions of the syxtem memory bitmap onto the video memory bitmap. Occasionally he'd have to reach back on his tiles and blit them on to his system memory bitmap. But because this redraw would only rarely occurr, he could probably arrange for it on his map.

How can you say this redraw is slow? Each tile is simply 2 triangles. Most normal 3D scenes have way more triangles than this tile map would ever have. In fact it would be safe to say with a tile size of 10x10 you could overlay and alpha blend hundreds of layers of tile maps before you noticed a degradation in performance - depending on how well your card handles alpha-blending and multi-texturing.

One tile map will only have about 2000 to 4000 triangles in it. On 1024x768 with a tile size of 16x16 your tile results are: 64x48.

Total tiles on screen at any one time: 64 * 48 = 3072
Total triangles for one tile map: 3072*2 = 6144
Total number of vertices - using non-indexed, non - cached vertex buffers - 3072 * 4 = 12288.

These numbers are quite small in relation to what a modern 3D game throws at the video card to render one entire scene. You will probably have to slow the game down just to play it using the tile method. And 16x16 tiles are very small on 1024x768 so it would be ludicrous to even use tiles that small.

This method will not cause any performance problems, even if you implement it half-assed.

Quote:

---

How can you say this redraw is slow? Each tile is simply 2 triangles. Most normal 3D scenes have way more triangles than this tile map would ever have.

---

The SDL_Blit call reduces to a check to see if the source rect and destination rect are valid and then calls SDL_BlitFast. SDL_BlitFast eventually makes the directdraw somewhere. So, SDL doesn't yet use 3d hardware acceleration and I'm sure there's some slow up there. And of course my video card is kind of slow, too.

Quote:

---

And 16x16 tiles are very small on 1024x768 so it would be ludicrous to even use tiles that small.

---

He'd probably use 20x20 for a 640x480 or 800x600 screen, I guess.

Actually I'm using 32x32. I am currently writing this uwing SDL (obviously) but only because I know it pretty well now. After I get more in depth I will change the gfx routines to OpenGL.