javascript - Pixel perfect 2D mouse picking with Canvas

Question

I'm writing a 2D game in html5 using Canvas which requires mouse click and hover events to be detected. There are 3 problems with this: detections must be pixel-perfect, objects are not rectangular (houses, weird-shaped UI buttons...), and it is required to be fast and responsive. (Obviously brute force is not an option)

So what I want to ask is how do I find out which object the mouse is on, and what are the possible optimizations.

P.S: I did some investigation and found a guy who used QuadTree here.

Answer 1

I have a (dated) tutorial that explains the concept of a ghost canvas which is decent for pixel-perfect hit detection. The tutorial is here. Ignore the warning about a newer tutorial, the newer one does not use the ghost canvas concept.

The idea is to draw the image in question to an in-memory canvas and then use getImageData to get the single pixel of the mouse click. Then you see if that single pixel is fully transparent or not.

If its not fully transparent, well, you've got your target.

If it is fully transparent, draw the next object to the in-memory canvas and repeat.

You only have to clear the in-memory canvas at the end.

getImageData is slow but it is your only option if you want pixel-perfect hit detection and aren't pre-computing anything.

Alternatively you could precompute a path or else an array of pixels with an offset. This would be a lot of work but might be faster. For instance if you have a 40x20 image with some transparency you'd compute an array[40][20] that would have true or false corresponding to transparent or not. Then you'd test that against the mouse position, with some offset, if the image is drawn at (25, 55) you'd want to subtract that from the mouse position and then test if the new position is true when you look at array[posx][posy].

That's my answer to your question. My Suggestion? Forget pixel-perfect detection if this is a game.

Seriously.

Instead make paths (not in canvas, in plain javascript code) that represent the objects but are not pixel perfect, for instance a house might be a square with a triangle on the top that is a very close approximation of the image but is used in its stead when it comes to hit testing. It is comparatively extremely fast to compute if a point is inside a path than it is to do pixel-perfect detection. Look up point in polygon winding number rule detection. That's your best bet, honestly.