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.


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
			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) {
		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.rect(curX, curY - clipHeight, Drawing.Constants.CellWidth, clipHeight);
		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.


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.


Mobile Performance & Quirks

Brace yourselves, this is going to be quite a ride.

Thursday I added a bit of code that lets the character move gradually towards a point that you click on the screen.
So far, I was moving the character with the arrow keys, which meant I couldn’t test much in mobile. I have been loading the page and watching it render, just to make sure it basically worked, and eyeing the FPS meter, but I couldn’t make it move.

Now that we can finally move on mobiles, I started experimenting with them a bit more…
And I found a good number of surprises:

TL;DR: Cell phones are awesome. And… they SUCK ASS. Read on, the details will be useful if you’re doing something like this

1) iPhone does not bubble up the click event on non-link elements.

Basically, tapping the canvas in iPhone didn’t do anything (I’m listening for clicks, on all other platforms, with window.addEventListener(‘click’))
I should’ve known about this, I read it in PPK’s blog, but that was a long time ago, I obviously didn’t remember.

PPK’s workaround works, adding an onclick to the canvas. I could also listen to clicks on the canvas itself instead of on the window.
The problem with that is that when I tap, the whole canvas goes a bit dark and then ligther again, “acknowledging” my click. That pretty much sucks ass.
On android, it’s worse, the whole thing is painted green. Green! Yuck. That’s easy though, I can resort to UA-sniffing and only do it for iPhone, but still not cool.

Fortunately one of the commenters in PPK’s blog figured out that it’s not that events don’t bubble; they just don’t bubble all the way up to body; but if you wrap the canvas in a div, and listen for clicks in it, it works, and nothing flickers. Works on Android and the desktop browsers too. Solved! Thank you PPK!

2) GetImageData performance is horrendous

Remember our cool lighting? It uses GetImageData and loops through all the pixels to make the sprites darker.

function DarkenCanvas(baseImage, ratio, toColor) {
	var tmpCanvas = document.createElement("canvas");
	tmpCanvas.width = baseImage.width;
	tmpCanvas.height = baseImage.height;
	var ctx = tmpCanvas.getContext("2d");
	ctx.drawImage(baseImage, 0, 0);
	var pixelData = ctx.getImageData(0, 0, tmpCanvas.width, tmpCanvas.height);
	for (var i = 0; i <; i+= 4) {[i] = toColor[0] + ([i] - toColor[0]) * ratio;[i + 1] = toColor[1] + ([i + 1] - toColor[1]) * ratio;[i + 2] = toColor[2] + ([i + 2] - toColor[2]) * ratio;
	ctx.putImageData(pixelData, 0, 0);
	return tmpCanvas

And in my Android HTC Desire S, it took 3 minutes to load the page. 3 fucking minutes!!!

Turns out, GetImageData doesn’t work too well on mobile. It’s not really GetImageData itself though, it’s the looping through the pixels that takes forever.
For comparison, my desktop browsers take 6ms, iPhone takes about 500ms, and Android takes about 4 seconds for each image.
5 sprites layers, 8 light levels…. You do the math.

Of course I didn’t expect this to be as fast as my PC, but considering how relatively fast everything else runs, I did not expect a 500x slowdown here…

One obvious solution here is to trade CPU for bandwidth. I can simply have the files pre-darkened in the server and load them already processed.
However, I’d rather not waste that bandwidth, and more than anything, processing on the client gives me HUGE flexibility. I can change the number of “lighting levels” by simply changing a constant, and the image files generate themselves.

On this one, I just gave up and asked.
It turns out that there *was* a simpler way, as I suspected, I just completely misunderstood how canvas compositing works.

Simply drawing a black semi-transparent rect with compositing mode “source-atop” does the whole trick.

I don’t know how fast or slow that is. The page went back to loading instantly, so I don’t care anymore (I know, I’d make a really shitty scientist)
Thank you Stack Overflow!

3) Viewports…

I saved the best for last… “mobile Webkit” is awesome for displaying webpages that are meant for bigger screens…
But to try and have a full-screen game, it’s a steaming pile of shit. Particularly on iPhone, where I spent 99% of my time trying to find a decent solution until I gave up and hard-coded the hell out of it. Piece of crap phone.

Let’s start from the beginning…
From the very first version of the engine, I added these meta tags:

<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1, user-scalable=no, target-densitydpi=device-dpi" />
<meta name="apple-mobile-web-app-capable" content="yes" />
<meta name="apple-mobile-web-app-status-bar-style" content="black-translucent" />

These are pretty much all I could find regarding making a cell phone viewport behave “the proper way” (ie. without any JS weird hacking).

I’m also setting, onLoad and onResize, the main canvas’s width and height to window.innerWidth/Height. That’s basically all you need to do for desktop browsers (and for the crappy experience i’m about to describe on cell phones which, technically, does work):

With those settings, this is what I’m seeing on my phones:

  • iPhone 4: portrait: reports 320×356. landscape: reports 480×208.
    In both cases: Wastes about 120px vertically with HUGE blue bars at the top and bottom. Sprites look very low-res (very shitty).
  • Android: portrait: reports 480×720. landscape: reports 800×400.
    In both cases: Wastes about 80px with a black bar at the top. Sprites look fucking awesome.
  • Android switching from portrait to landscape: reports 533×267. Wastes about 80px with a black bar at the top. Sprites look very low-res. It’s basically zooming in to about 150% for some reason. Also, it’s blitting about half the number of times per frame as in portrait, but frame rate is only 30% higher. Something’s wrong, it’s going too slow. I can pinch-zoom-out, and everything’s awesome again. Why the hell is it doing this?

So, basically, both phones are wasting half my screen, the iPhone is throwing away its beautiful Retina display, and Android is auto-zooming in when changing the orientation, plus it lets me zoom in even though I told it not to, and it zooms in on double click.
The default behavior is worse than shit, frankly.

So, let’s take these one by one, starting on the easier one…

Android’s zooming

With a bit of googling, it turns out this is an HTC Android issue, not Android in general. Apparently, non-HTC Androids do respect the “no zooming” directive. I didn’t really find a workaround, so what I’m doing is letting the user know that he’s zoomed in and he should zoom out. I still have the problem of zoom on double-tap, and I don’t know, yet, how much of a problem that’ll be. I’ll revisit this later if it becomes an issue. Bottom line, games will have to manage being zoomed in, most likely, and adapt correspondingly. If you’re doing a game where the user can zoom in, you just got that for free. You do need to adjust the number of pixels on the canvas, though, to not lose resolution (more on this below). It’s not pretty, but it sounds doable.

What I found, that is very useful, is how to detect this, and also how to figure out the ratios to correct for it. This is the code I’m using for this:

if (Window.deviceType == "android" && window.innerWidth != window.outerWidth) {
	// just show the "please zoom out sign"
	// but ratio between outerWidth and innerWidth, plus scrolling properties can let you correct.

Android’s top bar wastes screen

For the top bar that wastes screen, what we need to do is just scroll down. This implies making our page a bit taller than the window. “A bit” being exactly that bar’s height, or it’ll either stay partially visible, or some of our content will be off-screen.

I found that in android, this top bar’s height is the difference between window.outerHeight and window.innerHeight. This is simple, then:

Window.chromeVerticalSpace = 0; // All desktop browsers
if (Window.deviceType == "android") { Window.chromeVerticalSpace = window.outerHeight - window.innerHeight; }
elCanvas.width = window.innerWidth;
elCanvas.height = (window.innerHeight + Window.chromeVerticalSpace);

I’m also scrolling to the bottom of the page onLoad, to hide the top bar.

window.scrollTo(0, Window.chromeVerticalSpace);

Not exactly pretty, but gets the job done. I really want to see what happens with non-HTC androids, though, this may not work there…

iPhone’s wasted screen space

This is where the fun begins…

First I tried to find some other magical way of finding out how big the top bar is. I couldn’t.

So, I decided to hard-code it to 60px (trial and error gave me this number), and use the same solution as in Android.

This looked OK at first, but on closer inspection, particularly when changing orientation, it started to break in weird ways that I found no way to compensate for… Basically, if the page loaded on portrait, or on landscape, it’d show perfectly. However, as soon as I rotated the phone, it’d either be too tall in landspace, or too short in portrait (just *exactly* short in portrait, in other words, it took the exact height it needed to show the top bar at all times, with no scrolling possible).

This is *very* puzzling to me. Basically, the phone will give you some screen sizes for portrait/landscape, but when changing the orientation it seemed to give different ones. I tried setting the canvas to 1px by 1px to see if the canvas being there was affecting the window size, but that didn’t solve it. It does have something to do with it, if my canvas is 250×250 (and thus it fits always), I consistently get always the same screen and window sizes. But when I’m actually trying to maximize my canvas, it goes batshit crazy.

I don’t have the exact details at this point because I spent literally 4 hours trying crazy shit and rotating my phone, and by the time I was done I was ready to kill the moron responsible for this, so the details are a bit fuzzy now…

In the end, it left me with no choice. I just hard-coded the canvas size. This is the absolute shittiest solution in the planet if you ever want to do anything correctly, but I just lost it. Although there is a lot of very good information out there on the topic of mobile viewports (most of it thanks to PPK), I couldn’t find anything on having an element take up the whole screen consistently. I’m probably missing some really obvious option, but I just had had enough, and hard-coding an iPhone is “safe enough”, since there’s only one iPhone screen resolution (well, 2 really), and that’s not likely to change.

Fucking piece of shit phone.

var size = [320, 416]; // Default portrait
if (window.innerWidth > window.innerHeight) { size = [480, 270]; } // Default landspace

iPhone Homepage

Of course, if they bookmark your page in the homepage, then both the top and bottom bar disappear (due to the meta viewport), and you need to contemplate that as part of the hard-coding. Fortunately, there is a pretty property, if you know you’re on an iPhone:

if (window.navigator.standalone) {
	if (window.innerWidth < window.innerHeight) { size = [320, 480]; } // Fullscreen portrait
	else { size = [480, 320]; } // Fullscreen landscape

There’s also a bunch of nice things you can do to make the “homepage” experience better (better icon, splash screen, etc, etc)

The big problem with the homepage is that it runs ridiculously slow, because of the whole “no Nitro if you’re outside the sandbox” issue.
There’s pretty much fuck-all you can do about that, especially since even using things like PhoneGap you’ll have the same problem. This is very, very, very bad. Nothing to add there, though.

Retina display

Finally, the iPhone 4 lies to you about the screen size (backward compatibility, blah blah), and tells you it’s NOT a retina display. And there’s no way to coerce it into having the right dimensions/proportion. HOWEVER, you can exploit the fact that a canvas “size” and its element’s size don’t need to be the same. In other words, you can have more pixels in the canvas than the DOM element takes, and the contents get basically stretched. Fortunately, the iPhone reacts beautifully when you do this, by using all its nice, tiny pixels. Also fortunately, we at least have window.devicePixelRatio to detect Retina…

elCanvas.width = size[0];
elCanvas.height = size[1]; = size[0] + 'px'; = size[1] + 'px';
if (window.devicePixelRatio > 1) {
	elCanvas.width = size[0] * 2;
	elCanvas.height = size[1] * 2;
	Viewport.screenScalingFactor = 2; // Notify the viewport that screen coordinates are wrong

That final line is to let my “screen coords to map coords” method know that all the coordinates it’ll get are wrong and it has to correct accordingly.

So that’s it for today on mobile…
I can’t wait to get my hands on an iPad and see how bad it is…
Oh, and I need a non-HTC android to see how many of the things I call “Android” are just HTC specific.

The other big thing on phones is, obviously, performance. It’s horrendously slow right now (although faster than I would’ve expected before starting this whole project), but I have plans for that too.

Blocking Movement & Lighting

This was a fun update!

The first thing I needed to do was not allowing the character to walk anywhere. He has to respect walls, trees, and other “blocking” stuff.

Flags appear here for the first time. Each tile in the sprites has some flags associated to it. For blocking, we have “NonWalkable” (to block walking into a cell at all, for things like water), and “BlockWalkFromXX”, with XX representing the 4 iso directions (NE, NW, SW, SE). When the character changes cells, we check the flags of the 2 cells he moved between to see if they block movement.

This is straightforward for the 4 diagonal directions. For N, S, E, W, which happen if he’s just walking xactly through the vertex of a cell, we simply do 2 double diagonal checks. If one of those is permitted, it’s fine. For example, if going E, we try doing SE-NE, or NE-SE. If either of those work, we let him through.

// Check whether a character can actually change cells
Character.prototype.ValidateChangeToCell = function(curCell, newCell) {
	if (newCell.equals(curCell)) { return true; } // this shouldn't happen, but you can always walk within a cell
	if (newCell.x < 0 || newCell.x >= map.width || newCell.y < 0 || newCell.y >= map.height) { return false; } // If we're walking off-map, don't go there
	if (map.Cells[newCell.x][newCell.y].flags & CellFlags.NonWalkable) { return false; } // If the destination cell is not walkable, we just can't go there
	if (curCell.CircleDistance(newCell) > 1) { console.log("Non-adjacent!"); return true; } // I can't really validate if cells are non-adjacent
	var curCellFlags = map.Cells[curCell.x][curCell.y].flags;
	var newCellFlags = map.Cells[newCell.x][newCell.y].flags;
	switch (curCell.DirectionTo(newCell)) {
		case Direction.NE: if (curCellFlags & CellFlags.NonWalkFromNE || newCellFlags & CellFlags.NonWalkFromSW) { return false; }; break;
		case Direction.SW: if (curCellFlags & CellFlags.NonWalkFromSW || newCellFlags & CellFlags.NonWalkFromNE) { return false; }; break;
		case Direction.SE: if (curCellFlags & CellFlags.NonWalkFromSE || newCellFlags & CellFlags.NonWalkFromNW) { return false; }; break;
		case Direction.NW: if (curCellFlags & CellFlags.NonWalkFromNW || newCellFlags & CellFlags.NonWalkFromSE) { return false; }; break;
		// For non-diagonals, we test both possible diagonal paths. If neither works, return false
		case Direction.N:
			if ((this.ValidateChangeToCell(curCell, curCell.Move(Direction.NE, true)) && this.ValidateChangeToCell(curCell.Move(Direction.NE, true), newCell)) ||
				(this.ValidateChangeToCell(curCell, curCell.Move(Direction.NW, true)) && this.ValidateChangeToCell(curCell.Move(Direction.NW, true), newCell))) {				
			} else { return false; }
		case Direction.S:
			if ((this.ValidateChangeToCell(curCell, curCell.Move(Direction.SE, true)) && this.ValidateChangeToCell(curCell.Move(Direction.SE, true), newCell)) ||
				(this.ValidateChangeToCell(curCell, curCell.Move(Direction.SW, true)) && this.ValidateChangeToCell(curCell.Move(Direction.SW, true), newCell))) {
			} else { return false; }
		case Direction.E:
			if ((this.ValidateChangeToCell(curCell, curCell.Move(Direction.NE, true)) && this.ValidateChangeToCell(curCell.Move(Direction.NE, true), newCell)) ||
				(this.ValidateChangeToCell(curCell, curCell.Move(Direction.SE, true)) && this.ValidateChangeToCell(curCell.Move(Direction.SE, true), newCell))) {
			} else { return false; }
		case Direction.W:
			if ((this.ValidateChangeToCell(curCell, curCell.Move(Direction.NW, true)) && this.ValidateChangeToCell(curCell.Move(Direction.NW, true), newCell)) ||
				(this.ValidateChangeToCell(curCell, curCell.Move(Direction.SW, true)) && this.ValidateChangeToCell(curCell.Move(Direction.SW, true), newCell))) {
			} else { return false; }
	return true;

This was relatively straightforward, now for the fun part.


One fun thing we can do, which is really simple and pays off greatly, is darken the sprite sheets by processing them pixel-by-pixel and multiplying each color value by a ratio < 1.
If we progressively darken them and store the different "light levels", we can then pick, for each cell, from which of these levels to draw, and draw each individual cell darker or lighter.
Simply picking the light level through proximity to a light, we have some nice lighting.

The direct problem with this is, if for each cell we start trying to find the closest of all the lights in the map, drawing slows down considerably. To be fair, it was way less than I expected, it went from 61 FPS to 55 in my simple test, but still, that’s a lot of lost frames, and we can do better. Also, this doesn’t allow one of the best effects.

The position of the lights doesn’t change too often (the big exception is if the character himself holds a light, but still, it only changes when we change cells), so we can pre-calculate a “light map”, which just stores the pre-calculated light level for each cell in the map, and then simply refer to it when drawing.
The lightmap also lets us do something very cool, which i’ll get to in a sec.

To calculate the lightmap, we need to “project light” from each of the lights in the map. I want to do this by starting from the light, and “creeping outward” cell by cell, reducing the amount of light given in each step.
Processing a square centered on the light, and sized according to the “power” of the light is way faster, but it doesn’t let me do the cool thing I want to do.
So, starting from the light, I move in the 8 directions and put all those cells in a queue, which I process and for each of those cells, I put the 8 surrouding ones (that I haven’t already visited) in the queue too.

The result is that I’m always going from the center to the edges, the code is simple, and while the most efficient, still fast enough.
Calculating the whole lightmap for a 100×100 map with 12 lights takes about 0.6 ms.
That’s perfect.

And now for the cool part. Just like I have flags to block walking, I can have equivalent flags to block light passing through from cell to cell (for example, for the sprite of a tall wall). When spilling light from one cell to the next, I first check whether light “can walk” between those 2 cells, and if not, I don’t add that new cell to the queue.

The result is what I call “dungeon mode”. When you’re in a room, and there’s a narrow door leading to another room, only a sliver of your light passes through that door, giving a very realistic effect of holding a torch

And this is esentially the reason to do lighting by spilling from cell to cell, instead of the faster methods. This lets me very easily check for walls at each step, allowing this extra-cool effect almost for free.
Well, not free, the lightmap calculation jumps from 0.6 to 1.5ms, but it’s still more than fast enough. And if this becomes a problem, I can definitely make it better by only calculating the part that I need, instead of the whole map.

One caveat though… This doesn’t scale to huge maps and enormous amounts of lights…
I tried this in a 1,000 x 1,000 map with 10,000 lights, and it takes a full second to run.
Granted, you won’t have 10k lights, like, ever, but 1 second is very dire. If I ever need huge maps or too many lights, i’ll have to do something about this.

CalculateLightMap: function() {
	// Initialize the whole surface
	Drawing.LightMap = {};
	for (var x=0; x < map.width; x++) {
		Drawing.LightMap[x] = {};
		for (var y=0; y < map.height; y++) {
			Drawing.LightMap[x][y] = map.globalLightLevel;
	// Project light from each light
	for (var l=0; l < map.Lights.length; l++) {
		if (map.Lights[l].power > 0) {
			Drawing._ProjectLight(map.Lights[l].pos, map.Lights[l].power);
_ProjectLight: function(pos, power) {
	var alreadyProcessed = {}; alreadyProcessed[pos.x * 100000 + pos.y] = 1; // Store which cells I've been to already with this light
	var toProcess = [[pos, power]]; // And store which cells I need to light. This holds: cell, power to add
	while (toProcess.length > 0) {
		var c = toProcess.shift();
		var cp = c[0]; // cellPos
		Drawing.LightMap[cp.x][cp.y] = Math.min(Drawing.LightMap[cp.x][cp.y] + c[1], Map.Constants.LightingLevels);
		if (c[1] > 1) {
			for (var d = 0; d < 8; d++) {
				var newPos = cp.Move(d, true); // cp.Move takes a direction and moves in that direction. Directions are an enum from 0 to 7.
				if (Viewport.ValidateChangeToCell(cp, newPos, "Light")) {
					if (!alreadyProcessed[newPos.x * 100000 + newPos.y]) {
						alreadyProcessed[newPos.x * 100000 + newPos.y] = 1;
						toProcess.push([newPos, c[1] - 1]);
			} // go each of 8 directions
		} // If we have power to spill
	} // while (queue)

Final tip: When darkening the canvas, if instead of just multiplying for a ratio < 1, you make the pixels “tend” to some color that’s not black, you can create cool “fog” effects (white), or weird hellish environments (orange-red). It looks pretty good.

Characters! (and moving around)

I finally added characters. Characters are a bit special compared to the other layers we’re drawing, since we can have more than one per cell, and they can be manipulated directly from outside the map code. Objects will fall into this category too.

But now that we have a character moving around, we need to keep track of exactly which cell it’s stepping in. For this I needed to have a better way of determining which cell an offset from the center of another cell falls into. In other words, if the little guy is displaced 10px to the left and 10px up from the center of the cell, is he still in this cell?

I was doing this for scrolling the map, but that considered cells to be rectangular, which won’t work for our little fellas. We need to take into account the “diagonals”.
This is the kind of thought process I really enjoy doing, because I feel like my very limited knowledge of math is actually useful.

So this is pretty simple, just replace X in those formulas, and check whether Y is on the other side of the line. Easy!

And, we can use this for our character, and also for the viewport scrolling. Cleaner code FTW!

The other thing we want to do is scroll the viewport when the character is getting near the edges. This is really simple to do; we just need to define a “walkable area without scrolling”, and also a “ScreenToMap” function that is basically the exact opposite of MapToScreen (although the math is completely different and WAY simpler).

By the way… I love it when I write one of these functions and they just work at the first try. That is so not the common case when I’m doing math.

And now we have a guy that can walk on a scrolling map!

Next step: Blocking the walk! We really need to stop the whole walking through walls thing!

DOM Test

One of the ideas I’ve had from the beginning was, instead of drawing to canvas, using the browser rendering/layout engine instead. Basically, creating DOM elements for the map cells and setting CSS backgrounds for them…
That solves a bunch of problems, simplifies code in a lot of ways, and the browser’s pretty fast, being not written in JS…
I wasn’t really expecting this to work, but I did want to see what happened.

So… I made a little routine that, on load, would create one <div> for each map cell, inside of which is one <div> for each layer.
Each of these inner divs had as its background image the appropriate sprite file, with background-position to clip accordingly.
I draw each row, and each column, incrementing a counter and setting z-index to that counter, which automatically fixes all my ordering problems…
A bit of position math, and VOILA! It draws beautifully! It actually looks perfect, exactly like the canvas one. (I’m very pleaseantly surprised at this). So far so good.

Put all these divs inside one “map” div, to be able to move them all at once, and that inside a “viewport” div with overflow:hidden to kill the scrollbars…

A little code to move the map div around with the arrow keys…
Ah, there it is…
20 FPS scrolling the map around. Damn.

Well… I am creating about 13,000 DOM elements after all, and it’s positioning and reflowing all of them, probably… Maybe if I only create the ones I need to fill up the screen, and when you scroll I create/delete what I need/don’t need anymore…

The great attractiveness of the DOM system is that it basically solves all my invalidation problems. If you move the character around, it’ll take care of ordering, z-indexing, and it’ll only update the things that it needs to, magically, i just need to move the top/left properties of my character, and move him from cell to cell when he walks too far… It solves all the mouse events. And the viewport math. And backward compatibility to a lot more browsers. So let’s try the minimum viable thing…

I centered the map, and had the arrow keys move just one cell around, a little tree, instead of the whole map. That’s only 2 DOM elements, that has to fly!

20 FPS
Ok, so it’s probably reflowing everything everytime, even though it’s all position-absolute. Or at least redrawing everything. Or something…

Tiny window?
30 FPS

Let’s try Firefox…

Fine, canvas it is.
All in all, it was worth the experiment, given how little time it took to try it, and the big potential upside if it worked.
And it still *could* work, maybe, if instead of creating ALL the elements I just have the ones I need.
But that’s not cool anymore.

Oh, well, I still liked canvas more, it’s more fun to work like that, and it feels more “straightforward” than the DOM hackery, but this could’ve been good.

First running engine

A lot of progress today, nothing very interesting really.

I got the basic “engine” running, calculating which map cells it needs to draw to cover the whole screen, drawing them, with all their layers, and smoothly scrolling (so I don’t only calculate which cell should be at the center of the screen, I have pixel-level offsets).

It works in full page, automatically adjusts to the page size, just beautiful.

I also added one of my historical arch-nemeses to the code…. Mapping from screen coordinates to map coordinates (or, in other words, figuring out which cell the mouse is hovering over).
Just like 15 years ago, I tried to figure it out, I couldn’t, I searched for it, found it (much faster this time, there was no Google around back then), implemented it, it works, and no matter how hard I try, I cannot for the life of me understand exactly how it works.

I do get the idea… But I just can’t get to the point where I can derive the equations myself.
Which is partly why I have a mysterious “+1″ that I need, and I don’t know why, and it’s killing me inside, but without that, the result is off.
At least it’s “+1″ cell, and not “+7.243 pixels”… So the basics are OK, and it’s tremendously accurate along the edges…
But that +1 is just pure pain for me.

On another front, I haven’t done any performance work yet, although I can’t think of much to do without going to the BIG NEXT STEP, which is reusing the screen and invalidating what’s necessary, instead of redrawing the whole screen for every frame.

Even without optimizing anything, I’m still getting about 50 FPS running full screen (1920×1080) in my PC, and about 20 FPS in both iPhone and Android.
Not too bad for unoptimized code, but it’s not leaving me a lot of extra performance to take advantage of.
I’m going to use a profiler soon, and try to see if a few of the things I’m doing may be killing performance, however, it does look like 100% of the time spent is in blitting, so adding more logic shouldn’t make it much slower, as long as i’m not blitting more sprites to the screen per frame.

Having a larger map is also not a performance problem. It does consume a lot of memory, but it’s not slower at all.