Invalidation drawing

As I mentioned in the closing of my last post, performance is OK in desktops, but horrible in cell phones.
That’s ok though; I always, from the very beginning, was planning a change that was going to change performance completely. This is my big ace up the sleeve, so it better work. If it doesn’t, we’re screwed…

In short, it’s what I call “invalidation drawing”.

Basically, instead of clearing the screen for each frame and redrawing it completely (which takes about a thousand blits in a mobile size screen), I keep track of which map cells have changed (or are “invalidated”), and redraw only those, leaving the rest alone.
This dramatically reduces the amount of blitting necessary, but it has a bit of extra cost dealing with the whole “invalidation” thing.

Some things that we need to keep in mind, which add processing overhead:

  • The most obvious issue with this is scrolling. When you scroll, you take the whole canvas and make one huge blit of its entire contents, displaced a bit. That’ll leave a “hole” in the side you’re scrolling to (not actually a hole, it’ll actually keep the current contents of that area), so we need to “invalidate” all the cells involved in redrawing that area.
  • Another obvious problem is that if the character is standing on a cell, and in the one right to the South of it there’s a tree covering him, then when you redraw the cell the character is in, you need to also redraw the cell to the south of that one. And if the one to the south of that one also has a tree, you need to keep drawing down and down and down. This adds the complexity of checking whether you need to draw or not, plus the added overhead of drawing all those extra cells.
  • If lighting is enabled, any time the level of light of a cell changes, that cell needs to be invalidated.
  • If the edges of the map are visible, when scrolling there will be crap left as a side effect, since we’re not explicitly clearing them up. Even if we do clear the “hole” by drawing a black rect, when for example the character walks along the map border, even without scrolling, the part of him that’s “out of the grid area” is left there forever, instead of being covered in black.


Assuming that most of the time is spent drawing to the screen, which I believe is pretty safe to say, then the overhead added by all of this should be considerably smaller than the gains of drawing much less.

The only potential flaw I see in that reasoning is that our most under-priviledged browsers in terms of CPU also have the smaller screens. A small screen is good when you’re drawing the whole screen, since there’s less blitting required. At the same time, however, this drawing method is at its slowest when scrolling, since you need to draw whole columns or rows to cover the gaps, and in a small screen, a few columns are a large percentage of the screen. Add to that the fact that, in a small screen, you’re always scrolling, plus the computation overhead, the gains may not be so big… We’ll find out…

How it works

First of all, we have an array of InvalidatedCells (with a Point object for each cell).
We need to fill this array to know what to draw:

  • In each tick, we take the cells where each of the characters are, and add them to the array (we do this in Character.Tick). I’m assuming all characters change something in every frame; they either move, their animation frame changes, etc. This is pessimistic, but probably accurate most of the time.
  • Since a character typically “overflows” to the top of his Cell, we also invalidate the 3 cells above (NW, N, NE) the character. In reality, each sprite has a new property indicating how many cells to the North it covers (at least partially). We use this property to determine how far North to invalidate, in case we have a very tall Boss.
  • If a character changes cells while moving, we add the Cell he left, and the one he entered (plus the 3 to the top of each).
  • If it’s the main character, and his move makes the screen scroll, we not only flag that we need to recalculate the Viewport parameters, we also store how much we scrolled in each direction. All this so far is handled by the Character class itself
  • When we need to recalculate the lightmap, we keep a copy of the old one. After recreating it, we compare both, and any Cell that has changed its light level is added to InvalidatedCells.
  • At the time of drawing each frame, if the screen has scrolled, we blit the whole screen canvas onto itself, with an offset, and then we invalidate several whole rows at the top/bottom, or columns at the left/right, so that the gaps will be redrawn.
  • Something important to note… Because of the “black areas” that will show if the map border is visible, I may be invalidating cells that are technically off the map. They may have negative X/Y coordinates, or have X/Y larger than the map’s width or height. More on this in a while.

At this point, we have a list of cells that we need to redraw because they have changed somehow. The list is un-ordered. Some of these cells may be duplicate. Some may be off the map. And some may have another cell to the south that has something tall that covers this cell partially.
So we need to pre-process this array before we start actually drawing.

An important insight to keep in mind is that, if cell (1,1) is invalidated, and cell (2,2) (the one immediately to the south) has a tree, we don’t really need to redraw (2,2) completely, we just need to redraw the part of (2,2) that is covering (1,1). By doing this, and not redrawing all of (2,2), we save ourselves from also having to re-draw (3,3) if it also has a tall tree that covers (2,2). This idea is crucial, because otherwise, we can end up cascading south and redrawing pretty much the whole screen if we’re in a dense forest.

The easy way to solve this in canvas (and it’s fast enough, according to my tests), is to set a clipping area to the bounding rect of (1,1), and just redraw (2,2) completely. That way, only the part of the screen we need to update is affected.


So, we have our array.
First thing we do, we sort it, because we do need to draw in order. We can draw “horizontal lines” (moving East), or diagonals (moving SE or SW), as long as we draw “from back to front”. So sorting by either first X and then Y or viceversa just works.
We then go over the sorted array and we remove the duplicates. Once sorted, this is much faster, by comparing each item to the previous one, rather than having a hash of which cells we’ve already found. We do create that hash anyway, as we’ll use it later, but not having to check it now makes this way faster.

Now, for the fun part… For each cell left in the list, we need to check if there are cells to its South that we need to partially redraw.

First of all, when we loaded the map and went through the sprite sheets, we stored how tall is the tallest sprite (not in terms of pixels, but in terms of how many cells to the North it affects). This basically tells us, for each cell we’re redrawing, how far South we need to look to see if another cell affects it. This is important to keep in mind: having one ridiculously tall sprite will make rendering of everything slower, even if you never use it. So sprite sheets need to be designed accordingly, and if in one map we’re not using tall sprites, leave them out of the definitions.

So, we have our cell, and we know that our tallest sprite affects 4 cells to the North (given how iso works, it doesn’t have to be very tall for that to happen). We need to check, starting from our cell, the height of all sprites in each of the 4 cells to the South of this one, plus the ones to the NE and NW of those, since those overlap over half of our cell and may need redrawing too.

For each of *those*, we first check if they are already in our “hash of cells we already have in InvalidatedCells”. If we already have it, we know we’re going to redraw it completely anyway, so don’t bother. If it’s not in the hash list, and it has something tall enough to bother our cell, then we store this as an “affected cell”, associated with the original cell we were redrawing.

Example:

Here, the dark red cells are the ones that get “spontaneously” invalidated, because something happened. When processing the map, we need to look at the light green cells (4 sets of them, because that’s how tall our tallest sprite is) to see if something’s tall enough to bother. For the guy on the left, nothing is. For the guy on the right, there’s a tree (blue) that’s tall enough to affect the cell where the character is. Below that tree, there is another tree, but this one isn’t tall enough, so we ignore it.

When processing this invalidatedCells array, we’ll end up with the cell that holds the blue tree attached to the cell that has the character on the right, as one of the “affected cells”, a part of which we need to redraw once we redraw the actual invalidated cell where the character is.

The cells marked light green are the ones that we need to examine when processing the cells the characters are on. When processing the 3 cells above those, which for out algorithm are exactly the same as those two, we examine a few more cells that I’m not marking here for clarity (but following the same pattern).


To sum up, our pre-processing function receives an array of { x: int , y: int } structures, and it returns an array of { x: int, y: int, affectedCells: array[{x,y}] }

With this at hand, drawing the map is now quite simple.

For each cell in this new array…

  • We calculate where the bounding rect of this cell lies in the screen.
  • If it’s way off the screen (which can perfectly happen, if an NPC moves at the other end of the map), we ignore it.
  • If it’s outside the map, it means the borders of the map are visible, and we need to clear an area with black. We simply draw a “black tile”, which is just a “black diamond” cell to cover whatever was in that area
  • If it’s inside the map, we just use our regular “DrawCell” method.
  • Finally, for either case, if according to our pre-processing we have Affected Cells to redraw, we set a clipping area where this cell is, and we call DrawCell for each of the affected cells.

Piece of cake.

In case that didn’t make any sense at all, here’s the code:

 
// Takes all the invalidated cells, sorts them in the right drawing order,
// and finds what other pieces of cells to the south need to be drawn
_ProcessInvalidatedCells: function() {
	var invCells = Drawing.invalidatedCells;
	var newInvalidatedCells = [];
	var alreadyFound = {};
 
	invCells.sort(function __sortInvalidatedCells(a, b) {
		if (a.x == b.x && a.y == b.y) { return 0; }
		if (a.x > b.x && a.y < b.y) { return 1; }
		if (a.x < b.x || a.y < b.y) { return -1; }
		return 1;
	});
 
	for (var i = 0, l = invCells.length; i < l; i++) {
		if (!invCells[i].equals(invCells[i + 1])) { // Filter duplicates
			newInvalidatedCells.push(invCells[i].clone());
			alreadyFound[invCells[i].x * 100000 + invCells[i].y] = 1;
		}
	}
 
	// Check which cells below these ones we need to redraw too (with the right clipping)
	// Find cells below these, which are not in the list to redraw already, that are tall enough to affect us
	for (i = 0; i < newInvalidatedCells.length; i++) {
		var affectedCells = [];
		var centralCell = newInvalidatedCells[i].clone(); // We need to look at the 3 cells below. We make 3 cell objects, in the right "formation", and we move them all South in each step.
		var sideCellNE = centralCell.MoveNEClone(); // We also only clone once we found we need to draw
		var sideCellNW = centralCell.MoveNWClone(); // This is considerably faster than having one and moving it and cloning all the time
 
		for (var h = 1; h <= map.maxCellHeight; h++) {
			centralCell.x++; centralCell.y++; // centralCell.MoveS() inlined
			if (!Viewport.InMapPoint(centralCell)) { continue; }
 
			sideCellNE.x++; sideCellNE.y++; // sideCellNE.MoveS() inlined
			if (!alreadyFound[sideCellNE.x * 100000 + sideCellNE.y] && sideCellNE.x >= 0 && sideCellNE.y >= 0 && map.Cells[sideCellNE.x][sideCellNE.y].cellHeight >= h) { affectedCells.push(sideCellNE.clone()); }
 
			sideCellNW.x++; sideCellNW.y++; // sideCellNW.MoveS() inlined
			if (!alreadyFound[sideCellNW.x * 100000 + sideCellNW.y] && sideCellNW.x >= 0 && sideCellNW.y >= 0 && map.Cells[sideCellNW.x][sideCellNW.y].cellHeight >= h) { affectedCells.push(sideCellNW.clone()); }
 
			if (!alreadyFound[centralCell.x * 100000 + centralCell.y] && map.Cells[centralCell.x][centralCell.y].cellHeight >= h) { affectedCells.push(centralCell.clone()); }
		}
 
		newInvalidatedCells[i].affectedCells = affectedCells;
	}
 
	return newInvalidatedCells;
},
 
DrawMapDelta: function() {
	// (removed a bunch of code, unrelated to this post)
 
	// Sort the invalidated cells we need to draw, and check which other cells we need to also refresh because of these
	var invCells = Drawing._ProcessInvalidatedCells();
 
	var firstCell = Viewport.firstCell.clone(); // Index of the Cell at the top/left of the screen
	var firstCellPos = Viewport.firstCellPos.clone(); // Position of that Cell in pixels
 
	// NOTE: When referring to the position of a cell, the Y coordinate is the bottom of that cell, not the top, because the top
	// can be different depending on how tall the sprites in that cell are (whereas nothing can overflow to the bottom, so the bottom is fixed)
 
	for (var i = 0; i < invCells.length; i++) {
		var curCellIndex = invCells[i];
 
		var curX = firstCellPos.x + (curCellIndex.x - firstCell.x) * Drawing.Constants.HalfCellWidth - (curCellIndex.y - firstCell.y) * Drawing.Constants.HalfCellWidth;
		var curY = firstCellPos.y + (curCellIndex.x - firstCell.x) * Drawing.Constants.HalfCellHeight + (curCellIndex.y - firstCell.y) * Drawing.Constants.HalfCellHeight;
 
		// If off-screen, get out
		if (curX < -Drawing.Constants.CellWidth || curX > Viewport.screenWidth ||
			curY < 0 || curY > Viewport.screenHeight + Drawing.Constants.CellHeight * 2) {
			continue;
		}
 
		if (Viewport.InMapPoint(curCellIndex)) {
			var curCell = map.Cells[curCellIndex.x][curCellIndex.y];
			Drawing.DrawCell(ctx, curCell, curCellIndex, doLighting, lightLevel, curX, curY, true);
		} else {
			curCell = { cellHeight: 0 };
			Drawing.DrawBlackTile(ctx, curX, curY);
		}
 
		if (curCellIndex.affectedCells.length == 0) { continue; }
 
		//---------
		// Draw the pieces of cells below this one.
		// Set clipping area
		var clipHeight = (curCell.cellHeight + 1) * Drawing.Constants.CellHeight;
		ctx.save();
		ctx.beginPath();
		ctx.rect(curX, curY - clipHeight, Drawing.Constants.CellWidth, clipHeight);
		ctx.clip();
 
		for (var j = 0; j < curCellIndex.affectedCells.length; j++) {
			var affCell = curCellIndex.affectedCells[j];
			var dX = (affCell.x - curCellIndex.x) * Drawing.Constants.HalfCellWidth - (affCell.y - curCellIndex.y) * Drawing.Constants.HalfCellWidth;
			var dY = (affCell.x - curCellIndex.x) * Drawing.Constants.HalfCellHeight + (affCell.y - curCellIndex.y) * Drawing.Constants.HalfCellHeight;
 
			Drawing.DrawCell(ctx, map.Cells[affCell.x][affCell.y], affCell, doLighting, lightLevel, curX + dX, curY + dY, true);
		}
 
		ctx.restore(); // Kill clipping area
		//---------
 
	} // for (invalidatedCells)
 
 
	Drawing._ResetInvalidation(); // Clear the invalidatedCells array
},

Some notes about the process

The first problem I found trying to make this work was that my viewport calculations weren’t exactly awesome.

Basically, I just made them a bit wasteful, just guaranteeing that I’d cover the whole screen by adding a few extra rows/columns, because it was easier and I’m lazy, and that was fine when drawing the whole screen, we just waited a few blits.

Turns out, if the Viewport makes you draw too far out of the screen, when you try to scroll and you invalidate “the first n columns to the left”, you have to draw A LOT of columns, because the first one you draw is way off-screen. And this pretty much negates a lot of the advantages of delta-drawing.

And what’s worse, sometimes the first one is not so off, becuase it depends a lot on the size of your screen, and where you are centering the map, so you can’t just have a few less columns and be done, the whole calculation needs to be rethought.

Once I did that, and the Viewport was fitting tighter around the screen, I found out I wasn’t being a bit wasteful. On a cell-phone screen, where this was worst, I saved up to 17% of blits when drawing full screen. In my HTC, that alone gave me 4 extra FPS!. And of course, when drawing only deltas, and scrolling, this saved about 40% of blits, because I now need to draw only 3 columns. Huge win.

Results

Performance on the desktop absolutely shot up. From 60 FPS maximized, it went straight to 250 when standing still, 210 when running around not scrolling, and about 100 when scrolling. It’s important to note that 250 FPS is the absolute maximum you can get in Chrome when doing setTimeout with 0 delay, so in reality this number is higher, but I can’t know how high.

As for mobile performance, while it’s much better, it still leaves a lot to be desired. I’m not quoting FPS increases because they fluctuate a lot, and it’s very hard to measure, but with lighting on (lighting impacts a lot), while scrolling (which happens all the time in a tiny screen), I get about 14 FPS. With lighting off, I get a pretty consistent 20-30 FPS, which is good enough, with 40-60 FPS if not scrolling.

All in all, this change was a huge win. It gave me as much of an increase as I expected on the desktop, but it wasn’t the magical card that I was expecting it to be. There is still a lot of work to do.

Damn!

4 comments

  1. I see a lot of interesting articles on your website.
    You have to spend a lot of time writing, i know how to save you
    a lot of time, there is a tool that creates unique, SEO friendly articles in couple of seconds, just type
    in google – k2 unlimited content

  2. I actually prfeer the top right, probably because it does look like a school book from the 1970s! It is intriguing, with all those different types of map. I like the other two but the picture of the man in the mac is a bit old-fashioned – it would be better if the person did not look so 1950s (putting even the 1970s textbook to shame!). Maybe it could even be a woman.I do think that all three are a bit “fussy”, though, I think they could come up with something a bit cleaner and more modern in design. But – they are all nice, I am just nitpicking.

  3. Wan

    In acquired diosrders of granulopoiesis it is not uncommon to see eosinophils in which some granules have basophilic staining characteristics. These are immature granules, sometimes termed Pro-eosinophilic granules*. Such cells are increased in frequency in CGL, eosinophilic leukaemia and certain categories af AML, in which eosinophils are part of the leukaemic clone, particularly cases of AMML with eosinophilia associated with inversion of chromosome 16. . But recent evidence has shown, that in some patients with CLG there are also hybrid cells with a mixture of granules of eosinophil type and baosphil type. Nice photo thank You very much.

  4. Agree that it may be time to go back to the drawing board to dgsien a cover that is less cluttered and has a cleaner look.These days artists are doing a lot with graphic dgsien and there is such a huge selection of fonts that much is possible.

Leave a Reply

Your email address will not be published. Required fields are marked *

*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre lang="" line="" escaped="" highlight="">