In the continued development of my Ludum Dare game, Ninja Flare, and also future projects I realize that I will most likely follow some form of tile based map representation, just like so many other platform games do.  I have therefore been spending one hell of a lot of time trying to find the most robust solution that I can to handle and resolve collisions in a tile map. In many conventional implementations, an object that can collide is limited to be the same size as a single tile in the map, however I want my colliding objects to be of arbitrary size.  The problem as I see it is actually not trivial to solve and I have burned through many many pages in my sketch book devising ideas for how to tackle such a problem.  I want the most robust solution I can find, although I don’t feel i need to go as far as using swept collision methods, since that would on the face of it add another level of complexity entirely.  So far I have created a small framework to let me implement various solvers, and test their robustness.  The above picture is a screen shot from this framework, and shows a few things of interest.  The very light blue solid rectangles represent walls, or blocking tiles in the map. The dark outlined rectangle in the lower middle is the object that is being tested for a collision and the lighter blue outlined rectangles surrounding it highlight the tiles that were examined when trying to determine an intersection.  The outlined red squares that surround some of the tiles highlight any of these that intersect with the object being tested.  It is these intersecting tiles that I am interested in when determining how to resolve an overlap.

Part of the current solution that I am exploring involves a pre-processing step to the tile data. This is acceptable for me since anything that avoids computation at run-time, is a bonus, and the pre-processing is extremely fast and simple.  Sub regions of the map could be reprocessed at run time if the map data changes, so it will not be a hindrance in that respect.  The computation that is performed performed in this stage examines each tile and decides what direction that tile could push an obstacle back out of a collision.  It is rational that a tile cant push an object into another tile, since that is not a valid resolution.  These vectors are represented in the above picture by dark blue lines near the perimeter of each tile.  These vectors are stored in the map data as an encoding of bits, one for each of the four directions possible.

This is the current stage I have reached, and I am now working on the final solver using all of the data I have so far extracted about the collision, and the simplification of data in the pre-processing step.  When I have reached something robust enough I will post the solution I have found, and provide a full tutorial of my findings.  I am interested however how other engines have solved this problem so I may also examine other engines.