Faster Canvas Picking - HTML5 Game Development Insights - page 70

Basic Picking with Bounding Boxes
Since your SpriteInstance object supports both position and size information, the most straightforward way
to determine what sprite has been picked is to test the given point against the bounding box of the sprite. In this
simplistic model of picking, all that's needed is a simple loop over all the sprites in the scene, and to test which of their
bounding-boxes intersect with the given x,y point on the canvas (given from the mouse); see Listing 5-6.
Listing 5-6. Find the desired sprite by looping through all instances, and determining which one contains the XY pair.
Note that this function returns the FIRST instance it finds
function findClickedSprite(x,y)
{
//loop through all sprites
for(var i =0; i < spriteInstances.length; i++)
{
var sp = spriteInstances[i];
//pick is not intersecting with this sprite
if( x < sp.pos.x || x > sp.pos.x + sp.size.w || y < sp.pos.y || y > sp.pos.y + sp.size.h)
return sp;
}
return null;
}
In Listing 5-6, you're completely ignoring z-ordering and complex depth stacking, and just returning the first
sprite that contains this selection point. Don't worry; we'll get to that later.
Caveats
As mentioned, the brute-force, bounding-box method of picking is quite effective for scenes with low object count.
However, once the number of objects in your scene increases, this technique will quickly reveal performance
problems, especially on underpowered devices. Another particular issue is scene depth complexity—that is, how many
overlapping sprites you have. Once you start adopting more aggressive versions of depth complexity, you'll quickly
find that this method is unacceptable to user input and expectations, and you'll need a more fine-grain solution.
Faster Picking via Bucketing
Let's say you're building a complex app and you have thousands of images in flight when a user clicks. You'll quickly
see that the performance burden lies in the inner loop of the sprite-to-point collision test, and although a simple
bounding-box test will be the quickest to implement, you still end up touching a lot of items that aren't even remotely
near the point in question.
The solution to this is to introduce a spatial acceleration structure to your canvas. This data structure organizes/separates
your sprites spatially, such that you speed up spatial tests by only referencing items that are reasonably co-located.
There's lots of variants for SAS (for example, scene graphs, bounding volume hierarchies, quadtrees, and octrees),
each having a unique set of pros, cons, and trade-offs, the analysis of which is outside the scope of this section.
For your purpose, you will use a very simplistic 2D binning algorithm, which will divide your canvas into a grid of
cells (of fixed sizes); each cell will contain a list of objects that touch that cell, allowing a sprite to be listed in multiple
cells (see Figure 5-2 ).