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.

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.

• javascript
• html
• canvas

4 Answers 4

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-puting anything.

Alternatively you could prepute 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 pute 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 es to hit testing. It is paratively extremely fast to pute 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.

The mon solution in traditional game development is to build a click mask. You can re-render everything onto a separate off-screen canvas in a solid color (the rendering should be very quick). When you want to figure out what was clicked on, you simply sample the color at the x/y co-ordinate on the off-screen canvas. You end up building a color-->obj hash, akin to:

var map = {
      '#000000' : obj1
    , '#000001' : obj2
    , ...
};

You can also optimize the rendering to the secondary canvas to only happen when the user clicks on something. And using various techniques, you can further optimize it to only draw the part of the canvas that the user has clicked on (for example, you can split you canvas into an NxN grid, e.g. a grid of 20x20 pixel squares, and flag all of the objects in that square -- you'd then only need to re-draw a small number of objects)

HTML5 Canvas is just a drawing plane, where you can set different transforms before calling each drawing API function. Objects cannot be created and there is no display list. So you have to build these features yourself or you can use different libraries available for this.

http://www.kineticjs./

http://easeljs./

A few months before I got interested in this and even wrote a library for this purpose. You can see it here : http://exsprite.. Ended up facing a lot of performance issues, but because of lack of time I couldn't optimize it. It was really interesting, so waiting for some time to make it perfect.

I believe the ments should suffice. This is how I determine user intention in my 2d isometric scroller, currently located at http://untitled.servegame.

var lastUp = 0;
function mouseUp(){
    mousedown = false; //one of my program globals.
    var timeNow = new Date().getTime();
    if(mouseX == xmouse && mouseY == ymouse && timeNow > lastUp + 100){//if it was a centralized click. (mouseX = click down point, xmouse = mouse's most recent x) and is at least 1/10th of a second after the previous click.
        lastUp = new Date().getTime();
        var elem = document.elementFromPoint(mouseX, mouseY); //get the element under the mouse.
        var url = extractUrl($(elem).css('background-image')); // function I found here: http://webdevel.blogspot./2009/07/jquery-quick-tip-extract-css-background.html

        imgW = $("#hiddenCanvas").width(); //EVERY art file is 88px wide. thus my canvas element is set to 88px wide. 
        imgH = $(elem).css('height').split('p')[0]; //But they vary in height. (currently up to 200);

        hiddenCanvas.clearRect(0, 0, imgW, imgH); //so only clear what is necessary.

        var img = new Image();
        img.src = url;                          
        img.onload = function(){
            //draw this elements image to the canvas at 0,0
            hiddenCanvas.drawImage(img,0,0);

            ///This putes where the mouse is clicking the element.
            var left = $(elem).css('left').split('p')[0]; //get this element's css absolute left.
            var top = $(elem).css('top').split('p')[0];
            offX = left - offsetLeft; //left minus the game rendering element's absolute left. gives us the element's position relative of document 0,0
            offY = top - offsetTop;
            offX = mouseX - offX; //apply the difference of the click point's x and y
            offY = mouseY - offY;


            var imgPixel = hiddenCanvas.getImageData(offX, offY, 1, 1); //Grab that pixel. Start at it's relative X and it's relative Y and only grab one pixel.
            var opacity = imgPixel.data[3]; //get the opacity value of this pixel.

            if(opacity == 0){//if that pixel is fully transparent
                $(elem).hide();
                var temp = document.elementFromPoint(mouseX, mouseY); //set the element right under this one
                $(elem).show();
                elem = temp;
            }

            //draw a circle on our hiddenCanvas so when it's not hidden we can see it working!
            hiddenCanvas.beginPath();
            hiddenCanvas.arc(offX, offY, 10, 0, Math.PI*2, true); 
            hiddenCanvas.closePath();
            hiddenCanvas.fill();


            $(elem).css("top", "+=1"); //apply something to the final element.

        }
    }
}

In conjunction with this:

<canvas id="hiddenCanvas" width="88" height="200"></canvas>

Set the CSS positioning absolute and x = -(width) to hide;