Accelerating per-pixel collisions in Canvas

UPDATE: At some point this demo broke and I haven’t yet had the time to get it to work again.

For the impatient ones:
Main demo HTML:
index.xhtml

I think the code could be interesting for people working on highly interactive content for decent browsers (yes, that excludes InternetExplorer. There’s no way to work around this short of offering Canvas as a plugin).

The only way so far to use per-pixel collisions with Canvas is using getImageData, which has a terrible overhead and I thought I could accelerate the whole thing by using bitmap functions to pre-filter the data. Right now it is meant for colliding a map with a sprite, but with a bit of work it could also be used to colliding two sprites. Basically it works like this:

  1. Calculate size of the rotated and scaled sprite.
  2. Create a canvas of this size
  3. Load the map file and blit it to that canvas.
  4. Load the sprite and blit it to the same canvas, keeping only parts where the previous content and the sprite overlap.
  5. Scale the canvas down to 1/16 of it’s original size) (technically 1/256 should also work, but it seems that the scaling starts skipping pixels then).
  6. Convert the downscaled image to a pixel array.
  7. Check the alpha channel of the pixel array. If any pixel has an alpha value >0, we have a colission.

Using this optimization my PC (1.8Ghz) is able to calculate around 3000 16×16 sprite collisions per second, which should be plenty for any normal game.

I’ve written a little demo, where 100 Tentacles invade my hometown (Mannheim). With 100 collisions, there’s even time for a fancy cloud shadow effect 🙂 . Note that they don’t collide with each other. While this is possible (actually, the code is already in there, you just have to remove the comments) it slows the whole thing down with little noticeable effect.

So far I’ve tested it in today’s Minefield build and Opera 9.50. While it does work in Opera, it’s too slow for practical use. In Minefield it works with or without tracing, but with negligible difference as most work is done natively by the image functions anyway. Safari fails totally for me, but then again Safari never worked properly on my system anyway (I can’t get to the error console. Yes I have the menu enabled, but when I select it, nothing happens).

The source for the main classes is GPLed, but the main file intentionally isn’t, because the map image is provided by GoogleMaps and so only licensed under “fair use”. Likewise, the tentacle is a redrawn character from Day of the Tentacle.

GPLed sources:
$js.js
CanvasCollision.js
Entity.js
Crowd.js
main.js

Main demo HTML:
index.xhtml

The individual images used in this demo:
map_walkable.png

map.png
clouds.png
sprite.png