2D collision detection

Question

Let's assume I'm using this character.

_{(source: iconbug.com)}

How would you implement collision detection for it? Using a bounding box doesn't seem to be a good approximation, because the bird's shape is nowhere near a square.

I was thinking of having a sort of quad tree data structure inside the object that represents portions of the image. Each leaf could be either false (in case it covers the white/transparent space outside the bird) or true (in case it represents an area of the bird i.e. beak, eye etc). Then somehow test the only obstacle in the scene for collision with the bird.

But my problems in my approach are:

1. I don't know how to initialize the quad tree.
2. Once the quad tree is initialized, I'm not sure how to traverse & use it once the obstacle is within the coordinates of the image.

How would you do collision detection with non-squarish characters?

LE: The other approach I've seen was to use multiple bounding boxes. For example I'd have one or a few bounding boxes for the beak, then a few of them for the hair or the tail. But it can get tedious. If this is a valid approach in my case, how would I generate those bounding boxes? I doubt I'd have to have them hardcoded in my program.

LE2: I care about fairly precise collisions. I can't imagine how a single bounding box or circle can at least approximate decently that shape, so this approach won't work.

Answer 1

Circle collider. Good enough for it I would say unless you're doing something fancy with certain parts being affected by physics or the colliding looking unnatural, and even if you need to split it up into several parts I have one thing to say to you:

Don't overcomplicate it.

You don't need a full quad tree structure for this. Just have several boxes or circles in a straight array, and then intersect with all of them. This can't possibly be performance critical enough and you won't gain that much from using a quad tree.

Answer 2

A two step check process

On the first step, you check the bounding box, and if there is no collision there, then the test is over. If there is collision, you move over to the second pass

On the second pass, if you want more precision, and you want a true pixel perfect solution, then you can do just that, a pixel perfect check pass

Since your image is a PNG (or any other file format that contains an alpha channel) this would be rather easy

1. Calculate the intersection area between that one object in the scene and the bird, generating a simple rectangle of intersection on both images
2. Within that intersection, check that each pixel has an alpha value > 0 in BOTH images
3. If any such pixels exist, you got your collision. Otherwise no

If you look at your images alpha channel, you can see how it already has all the information you might need for pixel perfect collision

Pixel perfect collisions are usually expensive, so doing a rough estimate at first with a bounding box or a more detailed collision figure (Like the one Anko suggested) may save you some precious time

The "finer" detailed collision bounding box Anko suggested:

PS: If your image has a halo, an effect or other non-0 alpha channel around it that you don't want to collide with, the algorithm threshold can easily be adjusted to accommodate that

Answer 3

I would use a circle for the body and a single rectangle for the beak, but that's just my opinion. Overcomplicating your collision geometry can slow down your app though, you're practically doubling (or more) the number of characters on-screen.

Answer 4

Maybe you could use some kind of wonky polygon/edge collider.

Not sure exactly how this would work, but:

two objects: object 1: the bird (o1), object 2: the thing that might hit the bird (o2)

1) Define a bounding shape that is a polygon that fits closely to the first object (o1) in question.

2) Get the edges of o1, o2 that could conceivably collide without could conceivably collide without o2 passing through o1 or vice versa.

With the position and size of the shape (o2) you could probably isolate edges (of o1) which can't conceivably be hit, whether it's becauses they are "behind" another edge (of o1) which is closer to o2. If you had a right triangle whose hypotenuse faced up and right and a rectangle approaching it straight on (with the long side along the x-axis) then you can tell which edges to omit because they're beginning and end y values are both either above or below the rectangle.

3) Determine if one of the points on an edge of o2 is the same as a point on any of the edges of o1 that you selected in step 2.

this concept probably works best for colliding polygons (i.e. things with clear edges), but maybe you can treat a circle as one long edge (e.g. if o2 was a circle).