Layered Tile Engine - Ideas about optimization?

Started by Khris, Thu 20/05/2010 11:23:24

Previous topic - Next topic

Khris

So, as some of you may know, I'm currently in the process of trying to replicate Chrono Trigger's tile engine.
It uses four layers combined with two zPlanes and a priority mode for every tile to give the impression of having much more layers.
Basically, I have two layers of ground tiles, stored in map-sized DynamicSprites, one holding the base floor, the second one holding details or foreground objects.
Then there's two sprite layers, one for each zPlane. Those contain the character sprites, either in full or with their sprite being distributed among them tile by tile. These layers are also stored in DynamicSprites, but they are redrawn every game loop.

When it comes to drawing the screen, I loop through every tile, determine the order of the layers depending on its priority flags, then compose the final tile and draw it to a fifth DynamicSprite.
After the loop, this DynamicSprite is cropped and displayed.

Here's the relevant portions of code:

Code: ags
DynamicSprite*t;

void _compose_tile(int x, int y, DrawingSurface*d1, DrawingSurface*d2, DrawingSurface*d3, DrawingSurface*d4) {
  DynamicSprite*temp;
  DrawingSurface*ds = t.GetDrawingSurface();
  ds.Clear(Game.GetColorFromRGB(255, 0, 255));
  temp = DynamicSprite.CreateFromDrawingSurface(d1, x, y, tiledims, tiledims);
  ds.DrawImage(0, 0, temp.Graphic);
  temp = DynamicSprite.CreateFromDrawingSurface(d2, x, y, tiledims, tiledims);
  ds.DrawImage(0, 0, temp.Graphic);
  temp = DynamicSprite.CreateFromDrawingSurface(d3, x, y, tiledims, tiledims);
  ds.DrawImage(0, 0, temp.Graphic);
  temp = DynamicSprite.CreateFromDrawingSurface(d4, x, y, tiledims, tiledims);
  ds.DrawImage(0, 0, temp.Graphic);
  ds.Release();
  temp.Delete();
}

void _str_vs::ReDraw(bool update_guis) {
  if (!this.maploaded) return;
  
  DrawingSurface*rds = Room.GetDrawingSurfaceForBackground();
  rds.DrawingColor = this.bgc;
  rds.DrawRectangle(this.x, this.y, this.x+this.w-1, this.y+this.h-1);
  
  DynamicSprite*map = DynamicSprite.Create(this.tw, this.th, false); // holds final map
  DrawingSurface*ds = map.GetDrawingSurface();
  ds.Clear(0);
  ds.DrawingColor = 15;
  t = DynamicSprite.Create(tiledims, tiledims, false);
  
  // update character layers Z1&Z2
  this.DrawCharTiles();
  
  // draw all layers together
  DrawingSurface*l1 = L1.GetDrawingSurface();
  DrawingSurface*l2 = L2.GetDrawingSurface();
  DrawingSurface*z1 = Z1.GetDrawingSurface();
  DrawingSurface*z2 = Z2.GetDrawingSurface();
  
  int x, y, i, zp, zm;
  int xx, yy;
  while (y < mapheight) {
    x = 0;
    while (x < mapwidth) {
      i = y * mapwidth + x;
      xx = x*tiledims;
      yy = y*tiledims;
      zp = Tile[i].zplane;
      zm = Tile[i].zmode;
      
      if (zp == eZplaneN) {
        if (zm == 0)      _compose_tile(xx, yy, z1, l1, l2, z2); // (Z1 sprites below ground)
        else if (zm == 1) _compose_tile(xx, yy, l1, z1, z2, l2); // (high ground above all sprites)
      }
      else if (zp == eZplane1) {
        if (zm == 0)      _compose_tile(xx, yy, l1, l2, z1, z2); // (all ground below sprites)
        else if (zm == 1) _compose_tile(xx, yy, l1, z1, l2, z2); // (high ground above Z1 sprites)
      }
      else if (zp == eZplane2) {
        if (zm == 0)      _compose_tile(xx, yy, z1, z2, l1, l2); // (all ground above sprites)
        else if (zm == 1) _compose_tile(xx, yy, z1, l1, z2, l2); // (ground over sprite)
      }
      else if (zp == eZplaneT) {
        if (zm == 0)      _compose_tile(xx, yy, l1, z1, l2, z2); // (all ground above sprites)
        else if (zm == 1) _compose_tile(xx, yy, z1, z2, l1, l2); // (all ground above sprites)
      }
      
      ds.DrawImage(xx, yy, t.Graphic);
      if (zm) ds.DrawPixel(xx+1, yy+1);
      
      x++;
    }
    y++;
  }
  ds.Release();
  t.Delete();
  
  // canvas change to reflect viewscreen size and offset
  map.ChangeCanvasSize(this.w, this.h, this.ox, this.oy);
  rds.DrawImage(this.x, this.y, map.Graphic);
  rds.Release();
}


I can already think of two methods of optimizing this:

- Only draw the part of the map that's actually visible on-screen. This is part of my to-do list anyway.

- When I redraw the sprite layers, I loop through all tiles that contain part of a sprite. I could mark them, then skip unmarked ones inside _compose_tile.

The thing is, given that the screen will show around 300 tiles, I'll be in the range of over a thousand DynamicSprite.CreateFromDrawingSurface and DrawingSurface.DrawImage commands each loop, even with those optimizations.

I can't think outside of the box any longer, so I'm glad for any input on this. :)

EDIT:
I've actually just thought of another way immediately after writing this.
There's no need to redraw tiles without sprites, so I could skip redrawing those every loop using flags marking tiles as dirty for the whole map.

Jim Reed

#1
Quote from: Khris on Thu 20/05/2010 11:23:24
There's no need to redraw tiles without sprites, so I could skip redrawing those every loop using flags marking tiles as dirty for the whole map.
CodeJunkie made this happen in my tile engine, and made the framerate went really up. I can share the source if you need it.

http://www.filedropper.com/agsrpg

abstauber

But don't these tiles have to be redrawn anyway, as soon as the maps scrolls?

Monsieur OUXX

Secondary question.

In terms of brute performance, what do you think would go faster, for a tiled scrolling?
1/ Using GUI controls (1 control per tile) and fiddle with the positions of each control,
OR
2/ Redraw the (dirty) tiles manually?

I'm not asking about technical limitations like "the GUIs are always on top" or "there are only 30 controls per GUI". Just brute performance.
 

Monsieur OUXX

Quote from: Khris on Thu 20/05/2010 11:23:24
I can't think outside of the box any longer, so I'm glad for any input on this. :)



About the optimization questions you raised, I can think of several things, from the easiest to the ones that require a bit of refactor :

1/ Is the "ds.Clear(Game.GetColorFromRGB(255, 0, 255));" really required?
I couldn't figure that out from your code, but if it's not, then drop it, my guess is that it's not a low-cost function.

2/ Do you really need to create and destroy "t" at each redraw?
I couldn't figure that out from the code either. But, just like for Clear, this type of allocation might be expensive. Test it in a loop with no other instructions. If it turns out to be expensive, then always re-use the same "t".

3/ Copy-paste the body of the  "_compose_tile" function where it's called, each time it's called.
It's dirty! But it saves width*height (several hundereds of) function calls, and function calls can be a bit expensive, as I've shown in some performance tests I've done a while ago. If you don't want to do that, at least try not to pass paramaters. Use global variables instead. I had also shown that the function call's speed is proportional to the number of parameters. It's DIRTY too, but you're designing a function where speed is critical --> You decide.

4/ Keep an index of the tiles contained in each layer and zPlanes.
Do you get me? Instead of saving what is the zPlane for each tile, instead, make a list of tiles contained in each zPlane.
This needs a (bit of) refactor.
Why would you do that? Because, then, it saves all the time spent on evaluating "if..then..else" in each iteration of the double-loop.
--> Instead you'll call the double-loop once for each zPlane, and there WON'T be any "if..then..else" in the double-loop (i.e. no time wasted on comparing the conditions).


Oh, and the dirty tiles thing is ABSOLUTELY essential.
But, as abstauber remarked, it'll be ruined if you scroll. Well, there is a way to reduce the impact, but I'm too lazy to explain ;-)
 

RickJ

Using your current method I wonder if it wouldn't be more efficient and easier to just to do a wholesale copy of the section(s) of the background that is to be reused instead of reconstructing it from tiles every time?  For example to scroll right you would just copy the background minus the left column of tiles and redraw on the background at the left margin.  Then the only thing left to do is draw the column of tiles on the right hand side of the background.

This could perhaps be further optimized by using a background that's twice the size of the viewport.  Scrolling is accomplished via AGS scrolling room feature.   It's not necessary to reconstruct the background each game cycle.  Construction of the background outside the viewport can be distributed over multiple game cycles.   As in the DemoQuest Looping room example, when the viewport reaches the right/left edge of the background it is set to the opposite side of the background.   So for our purposes here it means that a copy of the current background must be at that location.   This can be accomplished using the above wholesale copy method or spiting it into a number of operations distributed over a number of game cycles. 

Hope this helps ;)

Khris

Thanks for the input so far guys, much appreciated!

I quickly implemented two flags for each tile that basically track character movement and prevent tiles that don't change from being redrawn over and over again.
Somehow this works as long as I don't scroll; when I do, the screen hoes haywire with tiles being drawn at weird in between locations.
I don't get what's wrong because the code that draws the on-screen part of the map is completely separate from the rest and shouldn't be affected at all; well, I'll let it be for tonight.

Oh my, no it isn't. I completely forgot that I crop the map sprite to display the screen, no wonder it messes stuff up.
I'm using a second sprite and it works just fine now.

Jim Reed:
Thanks, I couldn't get the game to scroll though. Anyway, doing this is mostly about reinventing the wheel, but it can never hurt to see how other people did it ;)

Monsieur OUXX:
Some nice ideas there; I'll deal with them as soon as I experience a noticeable lag.

RickJ:
Currently I keep a sprite holding the complete map in memory, redrawing only the parts of it that have actually changed between loops, then display a cropped version of it according to the scrolling offset and viewport size.
That's more or less what you were suggesting, I take it? Although apart from the "only redraw what changed" part, that's how I did it when I first posted here. :)

Jim Reed

Aye, I forgot, my game doesn't scroll, sorry.

Shane 'ProgZmax' Stevens

The way my old tile engine worked was that it would render all the tiles for the screen PLUS an additional outline of tiles outside the screen to prevent 'popup'.  Having coded it in dx7 years ago the rendering was quite fast even with 4 tile layers, 6 parallax backgrounds and vector-determined tile shapes (they could be anywhere from 3-8 sides as I recall).  Obviously if you move into large resolutions you'll eventually reach slowdown without further optimizations like partial redraws and such, and I haven't tried it on ags so I can only imagine there's going to be a pretty significant performance hit trying to do the same thing here.  Honestly, if you're this serious about coding a chrono trigger engine I'd recommend you go with c++ and some game libraries as you'll have a much easier go of it as far as performance optimizations and features (and it's clear you have the interest and the skill to do so).


Monsieur OUXX

Quote from: Khris on Thu 20/05/2010 23:12:54
RickJ:
Currently I keep a sprite holding the complete map in memory, redrawing only the parts of it that have actually changed between loops, then display a cropped version of it according to the scrolling offset and viewport size.
That's more or less what you were suggesting, I take it?

RiskJ actually explained what I wrote I was too lazy to explain  ;D
He's not suggesting exactly what you're writing. His method is much more universal.
- Just like you, the part of the map he actually draws (once and for all) is larger than the viewport.
- however, he doesn't necessarily draw the *whole* map. He only draws the parts of the map that surround the viewport and might need to be quickly displayed. Cleverly, he suggest to keep track, within the hidden drawingSurface, of what should be eventually displayed where on screen, so that the map's hidden drawingSurface is almost never redrawn.

So, at each frame, what's displayed on screen is:
   1/ mostly the viewport, plus
   2/all the surrounding bits that have been drawn (calculated) in the "background".

It's not very clear but it would need a drawing to explain  ;D
 

SMF spam blocked by CleanTalk