Blog Archives

Physics engine – collisions, wrap up.

New version, with ∞ % more physics.

It took a few days but it’s here: the new physics engine that handles collision detection and collision response.

A screen shot.

I should try to make videos, they would show the physics better.

Figure 1: The tile map shows regions of tiles of the same material. This allows us to explore their physical properties more easily than with the previous maps.

Figure 1 shows a screen shot from the last version. The tiles with a ‘3D’ border are raised: they are obstacles on which you collide and bounce more or less according on their material. The flat tiles have a friction coefficient that also depends on their material, which slows you down as you walk. Materials pictured here are sand, rock, shallow water, deep water and rubber (rubber is stupid but I wanted to try 100% bounce).

You may have noticed that the entities looked circular now: I represent their bounding box. I chose to give them a diameter of exactly one meter, which corresponds to the width of a tile. That allowed me to make sure that entities could squeeze in exactly in the tightest conditions.

Small misadventure.

Everything worked pretty much immediately which really makes me appreciate having spent some time doing the analysis in my previous posts.

One thing went wrong though: I implemented the position correction before implementing anything about velocity correction. Which is okay. I wanted to have a perfectly working position correction before moving on. I unfortunately included in the code a couple of lines that made perfect sense for a game with position correction only, but which bugged weirdly later with the velocity correction added: entities would stick to walls, but only sometimes, and they couldn’t fit in a one-meter-wide corridor, but sometimes they teleported to the end of that corridor. Creepy! It took me about one hour to find what was wrong :(. Once I removed the few lines, it all worked smoothly. I shall try to pay more attention to these kind of things: I should not polish a my code before it’s finished.

One step away from the design.

The implementation followed the design very closely. There is one difference though, and it has to do with a suggestion I made in my previous post in the section about Simultaneous collisions. I suggested that I could apply all the position corrections at the same time by adding their penetration vectors.

It wouldn’t have worked: I should not add everything. I should pick the biggest correction in X and the biggest in Y. It would force me to start projecting on some axis, and projections are expensive. Actually, they are more expensive than my collision detections (I’m lucky to have such a simple geometry). Also, I don’t even know what to do in case of corrections that cancel each other, because how do I define the biggest then ?

Wine helps too.

Do not worry if the previous paragraph confuses you. I hardly understand it myself: it’s messy, complicated, it treats position and velocity differently, and wouldn’t even make the code faster. So I ditched that. The code is so simple now!

Download the demo.

Have it your way:

Thoughts.

  1. I dislike the tangential efficiency applied in collisions. You can feel it when you move in diagonal against a wall: a kind of friction is there, slowing you down. It’s particularly strong on waterfalls (raised water tiles) but you can feel it on piles of sand or other tiles too. Although it makes sense to be slowed down when you run against a wall, it’s just annoying to play. I think I will just set this tangential efficiency to 1.0 unless I really need it different.
  2. I do not make any difference between entities that walk and entities that fly or entities that are pushed (like a boulder). The friction to apply is very different in these cases. The engine does not handle it at all.
  3. The friction of the floor slows you down, but there is nothing that makes you have difficulties starting. Imagine sanding on ice: the low friction makes it hard to stop –which my engine can reproduce– but the same low friction reduces the grip of your soles and steals some of your walking force –which my engine does not handle at all–.

I will implement the point 1 because it’s just a matter of changing a few constants. However I shall not on the points 2 and 3 in the near future. I think that we have enough physics to make things interesting: we can move around and push things. Now that we can explore, we need something to explore. It is time to spend some time on procedural content generation \o/.

Advertisements

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 !