Collision detection.

In the previous post I explained how I implemented the equations of motion using a RK4 integrator, a Particle class and a couple of Force classes.  That was the easy part of the physics engine, for the fun begins now \o/.

Collision detection in games is a big topic.  Such a big topic that people have written books about it (I didn’t read them though :p).  Fortunately, we do not need to apply these complex models.  First, we are in 2D and that simplifies a lot of things.  Then, our entities are atomic, not made of fingers and eyeballs that can be sent flying all over the room independently.  I won’t be doing this or that.  Even what you saw in the Pacman video I posted earlier is beyond my scope since I am not even sure I want to care about rotations.

Boundary boxes.

Everything that moves in the world of Infiniworld is called an Entity.  Since they are the only things moving, they are the only things that can collide with anything else.  An entity can collide

  • with another entity,
  • with a tile (some tiles represent walls),
  • or with a placeable object.

Placeable objects have not been implemented yet.  They can be a chest on the floor, a chair, a boulder, a pillar, a sign…

I am facing a potentially big variety of shapes and I don’t like that at all.  If I don’t limit myself, I will still be working on that next year.  So this is what I came up with :

In translucent red, the boundaries boxes for calculating collisions: for tiles (clear grass on top of a cliff, bottom left), for entities (Minecraft dude and spider) and for a placeable object (the chest).

I searched the tubes for quite some time in order to find a nice game image but I couldn’t so I made one myself :D. You can see the grid in black, it shows the border of the tiles. It’s grass on the floor, and in the bottom-left corner it’s grass too but it’s on top of a steep cliff so it’s brighter (closer to the sun you know) and you can’t go there. There is a chest for some reason. The chest is not a tile, it’s on a tile. And there are two friends hanging out.

The boundary boxed that I chose are:

  • squares for the tiles,
  • circles for the entities,
  • rectangles or circles for the placeable objects, depending on how they look.

Please note that I do not circle the entire entity sprite! If you see a circle, imagine that in fact it’s a cylinder extending upward; the guy is completely in the cylinder.  I should have drawn the circle for the spider a bit lower, and the circle for the guy should be smaller.  But you get the idea.  Likewise, the sprite of the chest is not entirely within the boundary box, you could approach it from behind, and it would mask your legs.  It’s almost 3D!

Some entities will be huge, wider than one tile.  That’s cool because it means you can hide from them by running in narrow passages.

The placeable objects cannot be placed freely.  They place themselves on a tile according to their design.  For example, the chest is centered on the tile.  A long table, several tiles long, will have to be made from several placeable objects.

The reason I am limiting the placeable objects that way is because it helps me making sure the game is winnable.  If you cannot cross the room because it’s cluttered with stuff, you have a poor game experience.  At the moment of checking the winability of the game, I will consider that a tile with a solid placeable object is totally unwalkable even though you could actually squeeze yourself through stuff: better safe than sorry.

So we have to check circles against circles, and circles against square/rectangles.

Circle versus circle.

Circles colliding or not. The distance between the centers of the circles A and B is equal to the sum of their radii: they are touching. The distance between the centers of A and C is smaller than the sum of their radii: they are colliding. The distance between the centers of A and D is greater than the sum of their radii, they are neither touching nor colliding.

Testing the collisions of two circles is the easiest of all.  All you have to do is to compare the distance between their centers with the sum of their radii.  If the distance is greater than the radii, nothing to worry about.  If it’s equal we have contact.  If it’s smaller we have a collision and that must be solved.  I do not really know what to do with contacts yet…  For now I’ll consider that a contact is an absence of collision and that’s it.

Circle versus rectangle.

The distance between the center of A and the edge is greater than the radius of A: no collision. Likewise, the distance of the center of B to the corner is greater than the radius of B: no collision either. But for C and D, the distance to the edge or the corner is smaller than the radius: they are colliding.

We have many more tests to do now.  A rectangle is made of four edges and four corners.  You can collide on any of these.  Since you are an entity, your boundary is a circle.  When I speak about your distance to something, I measure that distance from the center of the circle.  So if your distance to a corner or an edge is smaller than your radius, you are colliding something.

Testing eight features per tile is going to be way too expensive from a computation point of view (remember that the maps have about 16000 tiles and that we run the physics 20 times per second).  The first thing to do is to prune the tiles: only test against the neighboring tiles.  That’s a quick pre-selection to reduce the tiles to test to a maximum of 9 (maybe more if the entity is bigger than a tile).  After that, we can make things easier still.

Ever heard of Voronoi diagrams ?  They’re perfect for us here.  After all, we can only collide against the closest feature.  On the figure above, the gray lines delimit the Voronoi cells outside of the rectangle.  All the points of the cell where the circle A lies are closer to the left edge than to any other edge or corner.  Likewise, the all the points of cell where B lies are closer to the top-left corner than to any other corner or edge.  So, instead of testing 8 features per rectangle, we only test 1.  That’s a good thing.  Finding the Voronoi cell you are in is a trivial matter, just compare your x and y with the two x and two y of the rectangle.

Another simplification arises: if two solid (wall/cliff) tiles are touching by an edge, then there is no need to test the two corners they have in common.  Just grab a pen and some paper if you don’t believe me.  If you have to test a corner more than once, you don’t have to test it at all.  Sweet.

A priori and a posteriori collision detection.

There is a very well explained paragraph on Wikipedia on the subject of a priori and a posteriori detection.  We’ll settle for the easy one: a posteriori.  This is enough for games anyway.  It is way, way, way, waaaay easier to implement.  It has some disadvantages but they’re worth it.  First, we lose some precision, but that’s not a problem because we’re a game, not a scientific application, and we just need a result that’s good enough to be believable.  Don’t forget I approximated you with a circle.  The second disadvantage of the a posteriori detection is that if you are fast enough, you can go through objects.  Let’s do the math:

Let’s say that the radius of the circle of our entity is 0.5 m.  And let’s say that our entity is close to the edge of a tile but does not touch it yet.  If during the time step to come it moves by 55 cm toward the edge, then the center of the circle will be inside the rectangle, missing the edge completely.

The physics engine runs at 20 Hz.  That means that the time step is 1/20=0.05 s.  Moving 0.5 m in 0.05 s corresponds to a speed of 10 m/s.  If an entity with a radius of 50 cm moves faster than 10 m/s, some collisions can go undetected.  The smaller the entity, the smaller the critical speed.

You may wonder why I cannot detect that the center of the entity is inside a forbidden tile.  Well, I can detect that, but what do I do then ?  Shall I push the entity outside the closest edge ?  What if behind that edge is another forbidden tile ?  What if that edge is on the wrong side of the wall and you just quantum-tunnelled yourself through ?  Messy.  It is wise to keep speeds reasonable.

However, 10 m/s is still not very fast.  The game screen you have seen on screenshots is 13 meters wide.  Crossing the whole screen in one second is fast, but not ridiculous.  I can imagine some nasty fireballs traveling at that speed.  How can we have good collision detections with fast objects ?

It’s easy: we just have to rerun the RK4 integrator with a smaller time step.  If at the first run the entity moved by more than its radius, then the movement is canceled and instead we run the integration with a time step divided by 2, or 3, or 4, depending of the number of radii you moved.  We run it 2, 3 or 4 times to compensate.  We test for collision after each and we stop at the first collision we find.  It’s very fortunate that we have chosen to integrate with RK4 because this integrator gives the same results for a wide range of time steps.

Tomorrow…

I’ll write about my plans for the collision response: what to do when entities are bumping into stuff.

It’s almost 2am, my eyelids are violently colliding.  I go crash in bed.  Bye !

Advertisements

About Niriel

Cynical utopist who likes red wines from Languedoc and playing Minecraft instead of working on his own game.

Posted on 14/08/2011, in Infiniworld and tagged , , , , , . Bookmark the permalink. 2 Comments.

  1. I understood you point of detecting the collisions between two very fast moving objects.

  1. Pingback: Collision response. « Electric stars

What do you think about it?

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: