CollisionHandler explosion logic

I've been thinking a lot about the collision, and I'd like to share with you my findings.

Without any sort of optimization, collision detection could work this way : take the list of game entities, start with the first one, and check if it collides with any entity in the rest of the list. Then take the second entity and check if it collides the the rest of the list. This is simple but inefficient. Indeed we are sometimes checking if an entity situated at the top left of the map is colliding with an entity at the bottom right of the map.

So instead of using brute force, we can use some sort of culling. So instead of checking for collision against all entities, we are going to reduce the number of candidates on which we need to check for collisions. This is called the broad phase collision detection.

In order to do that, we first need some sort of spatial partitioning. There are several options, but I would opt for an easy one to implement : a grid. The grid has squares the size of a tile (how convenient! ;) ). Each square holds one piece of information regarding the "static" geometry. Basically the square will know if it's empty, or if there's a wall or an explosion. I call these "static" geometry, because they exist only at positions filling exactly one tile. There's never an overlap of one of these object over 2 tiles (2 grid squares).

Now for our moving entities, we chose to reference their position by their bottom-left corner. Because our entities are the size of a tile, when we move them, they can only overlap a maximum of 4 adjacent squares. So for each moving objects, we can just check 4 squares.

What about collision among moving entities (or I would even broaden a bit by saying collision among entities which are not static, so don't take exactly one tile) ?

I found out that a good solution is to use the same grid we just designed for static objects, to hold information about our other objects. Each square of the grid contains an empty list. When a non-static entity reference position (bottom-left corner) enters that square, we had a reference to that entity in the list. Once the moving object reference position moves out of that square, we remove its reference and add it to the newly entered square.

With this setup, we are now able to do the following : take the list of all non-static entities (ie. dwarves, monsters, power-ups, bombs). For each of them, you look in the map for 5 squares : the square where the reference position of the entity is, and the following adjacent cells : right, bottom-right, bottom, bottom-left.

In the "center cell" (where our reference position is), we take from the list of non-static entities ONLY the ones that come just after our entity. So if we are checking "object2", and the list (which retains the order of its members) contains [object1, object2, object3], we only take object3.

In the other cells, we take all the non-static objects. The union of these 5 sets is the collection on which we perform our collision detection algorithm.

Why only 5 squares, and not 9 squares ? Well it's complicated to explain this in plain text. You really need to draw these 5 squares on a sheet of paper, and play with dummy entities which are at various places on the map. You will see that checking only these 5 squares will avoid to end up with the same pair of entities for collision detection.

So all together the algorithm would do something like :
for entity in moving_entities:
    Check in the 4 squares adjacent to entity for static object:
        If static object found, react accordingly depending on the object (wall : move out, explosion, die, etc)
    Check in the 5 squares for moving entities situated in the list of moving entities beyond entity position.
        If collision found, react accordingly depending on the object (dwarf, monsters : die; bomb : nothing; power-up : get bonus)

After all these researches, I'm motivated to implement all this. But I don't want to do this without your agreement. So let me know what you think. I realize that it's not that easy to explain all this just by writing. Maybe we could discuss this further during a future chat...

Dan.