Canvas pixel collision detection

So… a fair number of people arrive here looking for how to detect when a pixel/object/thing has collided with something else.

I’ll add more information in the future but in the interim, the quick and dirty advice I can provide:

Given p = x, y where this is the point your trying to determine if it intersects another… the best place is to start with bounding box logic.  Regardless of what shape your object is, if wrap it in an invisible box boundry, it’s relatively trivial to do:

box upper left origin is bX, bY off size sizeX, sizeY.   If p.x greater then bX and p.x less then bX + sizeX AND p.y greater then bY and p.y less then bY + sizeY   you’re inside the bounding box and it’s highly likely your point has or will soon be colliding with an object.

That’s pretty much it and is perfect if you don’t mine lagging the crap out of whatever is running this logic.    To make these collision checks performant, you need to make the computer do less work.   For two dimensional space, my personnel research has led me to the Quad tree structure ( wikipedia article ).  I’ve got a brute force / naive implementation prototyped  @ here & here but as of 2011 March 9th it is not finished and needs some more work.

Basically Quad tree’s provides a super quick way for you to determine if there is any other objects in relative space to an entity.  Doing a quick lookup, if there’s nothing nearby then you can skip the bounding box checks and then the stupidly expensive perimeter intersection checks.

Full library is here and like most of my pet projects is heavily undocumented and completely absent of unit-testing.

One thought on “Canvas pixel collision detection

  1. Pingback: Canvas tag: Collision detection & pixel decay - Refactored scope

Comments are closed.