[devel] Bumping into walls

If you are developing games, you have probably already been faced with this issue: How to make characters nicely slide against the walls?

For a long time I did the usual trick: Detect a collision, compute (somehow) an extraction vector, remove from the motion vector the part parallel to the extraction vector (dot product ...). However, this never seemed to work quite well and I always ended up with troublesome cases. (Well, arguably this was due to poor coding ;) )

In one of my latest projects (a never-to-be-released zombie game I will maybe blog about someday), not only had I to face this problem, but on top of it I had tens of zombies bumping into each other, through network latency to add to the mix. What a nightmare.

After much wasted time, I figured out a simple and (I believe) elegant solution. The link may not be obvious, but it was in fact inspired by the Lloyd algorithm.

Assuming a 2D scene layout, seen from above, let's consider a disk centered around a character. A trivial but important consideration is that the center of mass of the disk is right below the character.



Now, let's consider a wall nearby the character:



The disk is cropped by the wall. The center of mass of the remaining part is now displaced. The trick is simply to correct the position of the character so that it always goes to the center of mass of the cropped disk. In summary at every frame: Compute motion vector, displace, compute center of mass, correct position.



Of course the figure is exaggerated. In practice a disk with smaller radius is used.

For collisions between characters, I subtract from the disk the half plane which is mid-way between the characters:



Now, you might be wondering how in hell you will be able to compute the center of mass. There are two different approaches. Both rely on a square instead of a disk.

In the first approach I used convex shapes as colliders ('brushes') and sliced the collision square by the shape of the colliders, keeping only the parts outside. (For code doing this, look back at Quake's code for slicing polygons by convex brushes). A simple center of mass computation then gives you the corrected position.

The second approach relies on rasterization. Setup a viewport matching the square around the character, render a quad outputting pixel positions in the map, render the colliders in black. Then read back and average the values of non black pixels to obtain the center of mass. This is the new position.

This works nicely, gives a feeling of 'soft' collisions (depending on how large the collision shape is) and supports easily even the trickiest cases (many characters in a tight space of complex shape).

Enjoy!