Fixtures for your Redis Database

Another week, another gem!

This time, you’ll be able to test your code that interacts with Redis much more easily and consistently, by resetting your Test Redis DB to a known state at the start of each test.

RedisFixtures is, as its name says, Fixtures for your Redis DB. If you are using Redis as more than a cache (and if you’re not, you absolutely should, Redis is awesome!), you’ll want to have a consistent initial database state for your tests.

RedisFixtures will run at the start of each of your tests, flush your test Redis DB, and load the data from the Fixture into it.

As for generating this fixture, if you’re using FixtureBuilder, then it couldn’t be easier. Simply call RedisFixtures.save_fixtures and the end of your factory block, and you’re in business!

If you’re using any other gems to generate your fixtures, basically do the equivalent thing for them.

RedisFixtures is compatible with Minitest, and I’ll be adding support for RSpec soon. If you’re using RSpec and would like to have fixtures for Redis, get in touch!

Happy testing!

SmsSafe – MailSafe for SMS – Send SMS safely in your apps!

So, after a very long blogging hiatus, I’m coming back, with a completely different approach. Ruby Gems!!

Over the last few years I’ve been working on some very very interesting projects, and as part of those I developed a lot of functionality that is quite general purpose, and that I’ve been extracting into gems, for my own future self, of course, but I’m also blogging about them in the hopes that they will help you.

On today’s installment: SmsSafe!

If you’ve every sent emails with Rails, you’ve probably encountered MailSafe, that beautiful gem that allows you to test your app safely, knowing you will never email actual customers with crap, test data, or worse. Both Watu and Msty had this need to send SMS, and being used to MailSafe, I felt very unhappy without having a similar safety net, especially on Msty, where accidentally sending out SMS during a load test of the system could easily mean a few thousand dollars in carrier fees.

Seeing this, I cut my Gem-making teeth by blatantly stealing stemps’s idea, and building what is essentially MailSafe for SMS.

The idea is quite simple. You add the gem to your Gemfile, and then add this to your config:

    SmsSafe.configure do |config|
      config.internal_phone_numbers = ['+12223334444', '+447111222222']
      config.intercept_mechanism = :redirect
      config.redirect_target = '+12223334444'
    end
 
    SmsSafe.hook!(:action_texter) # or :twilio or :nexmo

The way this works, just like MailSafe, is you set a whitelist criteria, to which SMS can go, and for everything else, a redirection strategy and address. Anything that isn’t going to the whitelist, you can choose to ignore (simply drop it), redirect to a different number (probably your own), or redirect to e-mail instead, for a less annoying debugging alternative.

The usual cases:

  • For development, you’ll whitelist nothing and then redirect everything to your phone / email. That way, when you are testing workflows that send SMS, you do get them.
  • For staging, you can whitelist the numbers of everyone in the dev team… Or you can have a testing phone in the office that receives all SMS…
  • The whitelist can be either a string, an array of strings, a regex, and most interestly a Proc, which lets you do custom logic. For example, on our “beta testing” environment, we wanted our testers to be able to sign up (for which they needed a verification SMS), but not be able to SMS other people. This simple Proc solved that, using the “reference” field to filter based on the message “type”. You can also use a Proc for the redirection address, so you can vary who ends up receiving the SMS / email using any logic you may need.
        SmsSafe.configure do |config|
          config.internal_phone_numbers = Proc.new do |message| # Return true if it can go out, false if it needs to be intercepted
             message.original_message.reference.start_with?("phoneverif")
          end
          config.intercept_mechanism = :discard
        end
  • For load / stress testing, you’ll turn off SMS sending completely. However, this will throw off your timings, since SMS sending is most certainly not instantaneous. To compensate for this, you can set a :discard_delay property to be the average response time of your SMS provider, which will give you a more realistic benchmark.

SmsSafe works by hooking into either the ActionTexter, Twilio or Nexmo gems. However, only ActionTexter has hooks that allow for interception (that I suggested via Pull Request for this very gem, and they graciously accepted). ActionTexter also provides functionality for switching to a “test” SMS provider in your test environment, allowing you to inspect the messages that would’ve been sent, so I strongly recommend you use it in your project.

Twilio and Nexmo are hooked via monkeypatching, unfortunately. If you use any other SMS gem or provider, and you’d like to use SmsSafe, please either submit a PR, or just let me know and I’ll try to add it, I’d love to see adoption for SmsSafe!

Blog’s out of order

So… I started this blog to document my experiments and learnings during the process of writing my isometric game engine in Javascript. As such, it’s served its purpose, and I believe most of the information here is still relevant and applicable, but with my recently found job at Watu, I haven’t had time to update the blog and probably won’t for quite a while. See you on the next experiment!

Better performance testing

My latest problem to solve was performance, particularly on the algorithm that calculates lighting, and the tools I had were severely lacking, so when I made a tweak somewhere, it wasn’t completely clear whether it made things better or didn’t make a difference.

The main problem here was that, to assess performance, I had my general visual impression of “how fast it went”, which is of course flawed, and an FPS counter, which oscillates a lot, so not much help there either. To make matters worse, different scenarios have different effects on performance. Standing still is considerably faster than moving around close to the screen center, which is ridiculously faster than having to scroll; the FPS counter oscillates like crazy, and it’s hard to get a good measure of performance differences.

After thinking about this for a while, I found a workaround that’d let me be a bit more scientific in my measurements. Basically, I’d have the character automatically follow a certain walking path once the engine loaded, and I’d time how long it took to do that. This is also not 100% exact, as there is a setTimeout with 0 delay between frames, which can make things vary, but it’s reasonably realistic, and if I let it run a few times, I can get a decent measure, much more scientific than what I had so far at least.

I obviously also can use my timing function from the beginning of my experiments, where I turn the engine off, and just run one function in a loop thousands of times and time it, and I’m going to do that in some cases, but I also want to have a way to measure performance of “the whole thing”.

Coding that was reasonably simple, and I intentionally coded it in a way that is easy to “add it on” to the existing code (God, I love Javascript). That way, I can add it to older versions of the code, and check whether some of the changes I made (particularly the ones where I was following the profilers, which made my code somewhat uglier) actually made a difference, and whether that difference is big enough to justify the uglier code.

In the table below, you’ll find the results of running all the relevant versions of the code, in each of the browsers I’m testing. You’ll notice I made “lighting on” and “lighting off” tests. Lighting off means that the global light level is the maximum, in which case the code knows it doesn’t need to care about darkening stuff, and it completely bypasses all the lighting and lightmap calculations. I did this because I believe the lighting code is part of the performance problem, and I want to measure to what extent.

Times with lighting

Version Desktop Chrome Desktop Firefox Laptop Chrome Laptop Firefox HTC Desire S Portrait HTC Desire S Landscape iPhone 4 Portrait
1 24954
+-26
23264
+-80
38934
+-106
44639
+-298
91412
+-3945
90239
+-495
176235
+-3842
2 13577
+-114
8026
+-47
34776
+-174
28582
+-149
75171
+-1257
75891
+-1342
133525
+-1643
3 13655
+-104
7985
+-48
35336
+-98
29336
+-42
74852
+-362
83093
+-146
131648
+-865
4 14889
+-66
19095
+-205
38262
+-248
35366
+-72
92587
+-386
100320
+-326
189879
+-1482
5 14817
+-49
17039
+-240
38533
+-217
34861
+-79
90699
+-608
180984
+-2326
6 14922
+-46
17842
+-192
38716
+-207
36049
+-146
94242
+-1103
201195
+-1992

Times without lighting

Version Desktop Chrome Desktop Firefox Laptop Chrome Laptop Firefox HTC Desire S Portrait HTC Desire S Landscape iPhone 4 Portrait
1 24313
+-37
21117
+-190
37905
+-172
38476
+-91
62009
+-507
64704
+-552
96330
+-296
2 12877
+-126
5585
+-240
34577
+-270
24609
+-62
47220
+-217
53905
+-739
65196
+-690
3 12829
+-117
5795
+-267
34513
+-270
23971
+-66
47460
+-171
52511
+-292
65979
+-1485
4 14090
+-65
10828
+-185
37473
+-183
29390
+-240
68764
+-286
115799
+-493
5 13995
+-64
9154
+-204
36726
+-139
29172
+-140
66950
+-552
109763
+-599
6 14029
+-66
9141
+-229
36394
+-254
29408
+-93
66718
+-250
110656
+-1570

(I’m sorry for the holes, testing this took forever, so I didn’t finish all the “landscape” versions)

Versions of the code:

  • Code1: First version that included following a walking path. Includes lighting, right before doing delta drawing.
  • Code2: First version with delta drawing, incompletely done (would pan the existing canvas, and draw invalidated cells, but wouldn’t invalidate the new cols/rows when scrolling, nor the lightmap). It’s not useful to compare against Code 1, because it’s very incomplete, but it’s useful to compare to the next several versions, as I add things one by one, to see how long each of those take.
  • Code3: As part of delta drawing, I had to adjust the viewport to the screen better, to be able to draw only a few columns/rows when scrolling. This is that change, I included this version of the code to see how much that change had impacted performance. Verdict: Not much really.
  • Code4: Delta drawing: Invalidate new columns/rows that show up while scrolling, to “fill the black gaps at the borders”
  • Code5: At one point I started playing around with the Chrome and Firebug Profilers, and I made a bunch of tweaks to the code based on where I was finding bottlenecks. These basically made the code a bit uglier, and inlined a few things, to gain performance. At the time, I wasn’t sure how effective they were. Verdict: More effective than I thought.
  • Code6: The final missing change for delta drawing to be done 100%: When the lightmap changes, invalidate the cells whose lighting changed. This was a good hit to performance, now I need to figure out if it’s finding which cells to invalidate, or actually having to draw more cells that makes the impact. That’s pretty easy to figure out.

Hardware:

  • Desktop: Quad-core i7-2600 @ 3.4 GHz, 8 Gb RAM, running at 1920×1080 (both Firefox and Chrome results shown)
  • Laptop: Three year old Dell laptop: Core 2 Duo @ 2.00Ghz, 3Gb RAM (both Firefox and Chrome results shown)
  • Android: HTC Desire S, 768 MB RAM, Android v2.3.3 (480×720)
  • iPhone: iPhone 4, running inside Safari (not standalone app) (640×832)

Interesting things to note:

  1. First of all… How did I not have this before? I feel so idiotic. Just as I was running the tests, giving cursory glances to the data, I started seeing so many obvious patterns emerge I wanted to kick myself. Having a standard performance benchmark to run in all your devices (and actually running it all the time) is way more fundamental than I would’ve expected, mainly because performance-wise, browsers are way more different than I expected.
  2. Comparing equal to equal, lighting vs non-lighting: Lighting doesn’t take a lot of time for Chrome, but it does take a lot of time in Firefox, and it takes a huge amount of time in the cell phones. This was a big red-herring for me, and the main reason why not having this test framework before was a huge mistake. When I did lighting, I was checking out how it affected performance, but just in Chrome, and since it was really fast, the price I was paying in render time was absolutely worth it to get the gorgeous effect. Testing in other browsers shows I have considerably less leeway when it comes to what I can do in the lighting department, I really need to improve that.
  3. The performance gains from the first stage of delta drawing (which was thoroughly incomplete, and by far the fastest version of it) were incredibly bigger in my desktop (for both Chrome and FF) than in all the others. In the worst case (the iPhone), it is actually a bit slower than just drawing the whole frame every time. I’m not sure what this means. Probably the performance ratio in the iPhone of blitting against the extra JS processing I need to do on invalidated cells is completely different than in Chrome in my desktop. (Which would mean blitting in my desktop is stupidly slow compared to JS processing, it could be…). I’m going to keep delta drawing anyway since it’s stupidly fast if you’re not scrolling, and I can work on improving the performance of the code I’m running every frame, but this was a big disappointment to find out.
  4. The little tweaks I made based on the profiler indications were a nice win. Not in Chrome, and I now know that my computer was the worst possible choice to run the profiler on, but the tradeoff of performance vs slightly uglier code definitely paid off. I’ll be doing considerably more of this, if I can. By that I mean… In my computer, I took the profiler as far as I could, until it started giving me stupid, incorrect data. Hopefully running it in my laptop will give me new useful information.

The main thing I got out of all this is: A lot of things I tested whether they made a difference or not, and didn’t, only didn’t make a difference in Chrome, or in my beast of a computer, and they do make a big difference in other browsers/platforms.

For example, I had a bunch of constants to turn things on/off (for testing/debugging purposes), like drawing FPSs, drawing Viewport Data, etc. This meant a bunch of “if we should do x, do it”, where it didn’t do anything. Just checking the flag, in Chrome, didn’t make any difference at all, so I never bothered with it. When I removed those checks, my test runs in iPhone without lighting went from 110s to 93s. That’s a pretty fucking big change, where as in Chrome the difference was absolutely zero.

The part that sucks is that this means I need to revisit pretty much *all* my assumptions, everything, from the beginning. All the little benchmark tests I made for “unit things” need to be re-run, in all platforms.

Shit.

The second big thing I learned is that lighting is stupidly fast in my computer, and stupidly slow in all the others. That’s cool, it wasn’t written to be fast initially, it was written to be somewhat elegant and I never revisited that because it seemed fast enough (in my computer). I’ll be working *a lot* on that now.

The upside is, obviously, that it’s pretty obvious I’ll be able to squeeze some good amount of extra performance out of these…


So the moral is… Different devices / browsers are not just a matter of faster or slower. Some things will be faster or slower relative to other things. In my desktop, it seems like JS execution is stupidly fast compared to drawing to screen. In the cell phones, it’s exactly the opposite. Things that didn’t make any difference at all in my computer had dismal differences on the mobiles.

So benchmark in all the devices. All time time. Every time.

Performance problems

It’s time to really get into performance improvements. I did a bunch of performance experiments before I started, and I sanity-checked a thing or two while I was going, but I never really did serious work on the codebase, always counting on invalidation drawing to solve all my problems.

It didn’t.

Time to roll up the sleeves…

The first stop was obviously playing around a bit with the Chrome and Firefox profilers. I did some inlining of simple functions I was calling a lot. This did improve the performance of the caller routines, in theory, according to the profilers. However, since FPS oscillate a lot when scrolling, and max out at 250 when standing, the effect is not very visible. It seemed to be somewhat visible in mobile, but it wasn’t huge. Or maybe it was wishful thinking.

Also, after the first few improvements, the profilers started giving me weird data.

Chrome is telling me most of the time (20% of the total, with the other 80% belonging to “(program)”) is spent in a function that barely does anything. If I wrap the contents of that function into another function, with “(function() {})();”, the inner function uses almost zero time, as I’d expect, and the outer one still reports 20% (“self” time, not “total”). If I comment out the contents, it still takes 20% of the time, and it’s not even being called that much, compared to others… So that doesn’t make any sense.

Firefox was giving me reasonable data at first, but when I turned on lighting, I get a tremendous slowdown with the profiler on (which I didn’t get without lighting, and also turning on lighting didn’t slow the code down almost at all without the profiler), and it’s reporting times that are clearly off compared to the “profiler off”.

And the ones I wanted the most, the profilers for Android and iPhone, well… They don’t seem to exist, so not much help there…

Now, Chrome and Firefox run more than fast enough, but in the Android and iPhone, it not only runs slower, but it’s visibly obvious that the lightmap calculation is a problem. The lightmap gets recalculated every time a light source changes cells (or changes power), and since the character holds a “torch”, it happens every time you cross a cell boundary. On cell phones, there is a very clear pause when that happens. If you walk a long straight line, you see the character literally stop and stutter every time it passes from one cell to another.

So the lightmap calculation is heavy. This doesn’t surprise me, given that I made the simplest possible implementation of it, and it’s not exactly written in the fastest possible way. What does surprise me is that after making it, I did check how it impacted performance (in Chrome), and it didn’t. At all.

But without a profiler in mobile, untrustable profilers in desktop, and a fluctuating FPS meter as my only measure of performance, it’s kind of hard to make improvements. I made a bunch of little changes, and I have no idea whether they actually made a difference or not. Sometimes it seems they did, sometimes it doesn’t… It’s very frustrating and it feels very hit and miss.

My general feeling at this point is of disappointment (given, mainly, that my magic card didn’t work as I expected). We’ll see what happens, but it seems HTML5 games with a lot of screen action are still not as viable as I expected on mobile. I’ll have to keep experimenting.
Puzzlers and the like should be very viable, I believe, though, and these are the types of games I’m most interested in anyway. So we’ll see…

One thing I did, at this point, was Google around for other “HTML5 games”, to see if at least other people had been able to do cool looking, kind of intensive games in HTML5 that’d work fast enough on my mobiles.
I didn’t find anything even remotely close to what I’m trying to do. Nothing. At all. It’s either tech demos, crappy looking stuff, very, very basic things, or Flash. Lots and lots of Flash that for some reason says it’s “HTML5″
That’s both encouraging and discouraging.

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!

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 < pixelData.data.length; i+= 4) {
		pixelData.data[i] = toColor[0] + (pixelData.data[i] - toColor[0]) * ratio;
		pixelData.data[i + 1] = toColor[1] + (pixelData.data[i + 1] - toColor[1]) * ratio;
		pixelData.data[i + 2] = toColor[2] + (pixelData.data[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];
elCanvas.style.width = size[0] + 'px';
elCanvas.style.height = 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; }
			break;
		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; }
			break;
		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; }
			break;
		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; }
			break;
	}
 
	return true;
}

This was relatively straightforward, now for the fun part.


Lighting!

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…
Perfect!

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
Ugh
Ok, so it’s probably reflowing everything everytime, even though it’s all position-absolute. Or at least redrawing everything. Or something…
Damn

Tiny window?
30 FPS

Let’s try Firefox…
8 FPS

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.