How do I handle specific tile/object collisions?

Question

What do I do after the bounding box test against a tile to determine whether there is a real collision against the contents of that tile? And if there is, how should I move the object in response to that collision?

I have a small object, and test for collisions against the tiles that each corner of it is on.

Here's my current code, which I run for each of those (up to) four tiles:

// get the bounding box of the object, in world space
objectBounds = object->bounds + object->position;  
if ( (objectBounds.right >= tileBounds.left) && 
     (objectBounds.left <= tileBounds.right) && 
     (objectBounds.top >= tileBounds.bottom) && 
     (objectBounds.bottom <= tileBounds.top))
{
    // perform specific test to see if it's a left, top , bottom 
    // or right collision. If so, I check to see the nature of it 
    // and where I need to place the object to respond to that collision... 
    // [THIS IS THE PART THAT NEEDS WORK]
    //
    if( lastkey==keydown[right] && ((objectBounds.right >= tileBounds.left) && 
                                   (objectBounds.right <= tileBounds.right) && 
                                   (objectBounds.bottom >= tileBounds.bottom) && 
                                   (objectBounds.bottom <= tileBounds.top)) )
    {
        object->position.x = tileBounds.left - objectBounds.width;
    }
    // etc.

Answer 1

What I do in my 2D engine, is that I define a Polygon type property (called CollisionPolygon) for all classes that represent collidable objects. My Polygon type is basically just a list of lines. (More precisely, line sections. Each line is defined by its 2 end points.) You have to define the edges of the collision polygon of your objects manually once. If you have only a couple of objects to be tested for collision, you can use complex polygons with 100+ edges and it won't affect the performance drastically. If you have hundreds of objects, than you should stick to 4-12 sided polygons, just in case.

The next step is to implement the Point-in-Polygon algorithm. Since you didn't state which programming language or framework do you use, here's a sample implementation:

https://stackoverflow.com/questions/217578/point-in-polygon-aka-hit-test

Then you create another method, using Point-in-Polygon, that tests if two Polygons are colliding (if any of Polygon A's edges is inside Polygon B, then it's a collision).

NOTE: You have to do it both ways (it is possible, that A has none of its edges in B, but B has one or more of its edges in A). Also note, that depending on the velocity of the objects, and your game's refresh rate, you might miss some collisions! Imagine two needle-like polygons crossing each other's path at high velocity. At time T1, they have no overlapping areas. At time T2, they intersect, but none of them have edges in the other one. This will not be detected with the Point-in-Polygon method. If this seems to be a problem in your engine, you will have to do some more research.

Finally, implement your own way of handling actual collisions. It really depends on what you want to do... In my engine, I always store the previous position of the object, and reset the colliding objects' positions to it whenever a collision occurs. I also calculate the inertia of the two objects (velocity * mass), multiply it with an arbitrary <1 value ("energy loss"), and calculate the new velocities of the colliding objects, using good old primary school physics.

I recommend defining an interface for all of these (ICollidable, for example), that contains the following: CollisionPolygon property (type: Polygon), BoundingRectangle property (type: Rectangle), bool CollidesWith(ICollidable otherObj) method.

Then your collision detection will be basically this: 1. For every ICollidable on the scene, do the BoundingRectangle test with all the other objects. 2. If two objects' bounding rectangles collide, then do the polygon-based collison test. 3. If the polygon-based test is also positive, then register the collision (perhaps by storing indexes of the two objects). 4. Once all the objects have been tested for collisions, go through the registered collision instances, and do your "OnCollision" stuff. In my engine, this is where I sum up all the inertia changes for a given object, and then apply the changes.

Answer 2

This explanation is a working solution, but it's not the most optimal.

You can build a mask for the tile and also the object it collides with ... these may be pre-computed along with the bitmap you draw, but sometimes the mask is made up of non-zero pixels. So where a pixel is color 0, you don't considder it to be part of the object or part of the tile. So, by using pixel color 0, you remove the need to build a seperate mask. Now, where a bounding box collision has occured, you want to create a mask-collision box that encompasses both the tile and object (this is in an offscreen buffer). For any pixel where both masks collide ... that is, a pixel is visible on both masks, you have a collision.

What to do from here ... you could bounce the object back in the direction it came from, (which makes a collision feel "sticky"), or you could have another mask with collision actions stored in it ... essentially saying "If you collide with this pixel, move in this direction".

You can optimise this approach by several ways ... 1) Using a preset color to use as the masks, meaning you don't need to build seperate masks for collision 2) when building the mask collision box, it only needs to encompass either the tile OR the object, and then you draw to that box using clipping, just like when drawing to the screen. 3) If your mask is a bitmap array, you could use the number 1 to indicate that this pixel is collidable, and 0 for not being collidable, and then you only need to perform a LOGIC AND of the two masks together, and any non-zero value means a collision occured. 4) If you are using paletised bitmaps, you could see if you could get away with only 127 colors in your bitmap, and allocate 1 bit in the colors to the mask, thereby combining method 1 and 3. 5) If you have managed to implement methods 2 and 4, you might realise that you don't actually need to draw to a collision box, but can perform inline collision testing.