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/.

Collision response.

Urgh, the night was too short but I had to wake up early otherwise I’ll be a zombie tomorrow Monday.

Since my last post, we are experts in detecting collisions in our super simplistic universe.  It is time to react to it.

I can see two things to do:

  1. We must correct the position of the entity to put it in a legit place, that is a place where it does not collide anything.
  2. We must transfer energy between the collider and the collidee, including some loss to simulate friction in deformable bodies.  This changes velocities.

Position correction.

The simple case.

Figure 1: Correction of the position of a circle colliding with an edge.

Since we’re doing science here, I started giving numbers to my figures.  See Figure 1.  On this figure, the arrows do not represent speeds, they represent translation (movement, displacement) vectors.

  1. An entity (circle) is at position Black.
  2. We integrate its motion.
  3. The motion integrator says that after the time step, the entity should be in the Red position.
  4. Our collision detector notices that the Red circle intersects the edge of an obstacle (the gray thing).  We must respond to this collision.
  5. We measure how much the entity penetrated the obstacle: we get a penetration vector.
  6. We add the penetration vector to the Red position to get the Green position.  That’s where out entity ends up.

Doing it that way has an advantage: when you hit a wall you don’t get stuck on it but you start sliding.  We see that behavior in many games, now you know how it is done.

The correction algorithm is identical for collisions with circles and corners, only the detection changes.  Actually, a corner is a circle with a radius of 0, I can use the same code.

Chained collisions.

Now, what if Green is also a bad position?  See figure 2.  Well, Green becomes the new Red, and we start again at the step number 4.  We keep doing that until we stop being in wrong places.  Just to make sure we don’t get stuck in an endless loop, I will authorize a maximum of, let’s say, 5 such attempts.  After that, I cancel the whole movement and the entity is sent back to the Black position.  5 is an arbitrary number, maybe there is a better one ; I will log something in the console when this number is exceeded so that I can see the situations where things are going wrong.  Maybe I will come up with a better algorithm to solve these situations.

Figure 2: chain of position corrections.

Simultaneous collisions.

Let’s look at figure 2 again.  The first red circle intersects two edges simultaneously.  We reacted by correcting for the closest collision first.  Indeed, we hit the right wall before the bottom wall so it makes sense to react to these collisions that way.  We ordered collisions by distances.

But maybe we could also correct all these collisions at the same time instead of going back to step 4 (detecting the new closest collision).  Since each collision comes with a penetration vector, we just add them all and we get our Green position immediately.  Only after correcting for all these collisions we go back to step 4.  Indeed, maybe something else that we didn’t notice with our first Red position is in the way now.  Look at Figure 3.

Figure 3: Same as Figure 2, but a small entity intersects Green.

Figure 3 shows a small entity with which we did not collide after our integration.  We corrected for the two walls and we got the Green position, but now we have to test Green for collisions again otherwise we miss the small entity.  GOTO 4.

Velocity correction.

Elastic collision.

We are going to implement elastic collisions.  You have an elastic collision when, after the collision, the energy and the momentum of the system are the same than before.

Figure 4: Elastic collisions.

Picture 4 shows a frontal collision, but our collisions won’t always be frontal.  See figure 5 for an illustration.

Figure 5: geometry of a collision. Only the normal component of the velocities is modified by the elastic collision.

When two bodies collide, there are two preferred axis for describing the collision: the normal and the tangent axis.  If the velocities of the two bodies were collinear to the normal axis, then the collision would be frontal.  In any case, only the normal component of the velocities is modified during an elastic collision.  So the first thing we must do is decompose the velocities, which reduces our problem from vector to scalar.  Then we can use the formulas from the wikipedia page to exchange the energy.  Finally we rebuild the vectors.

Energy dissipation, efficiencies.

Unless you are made of rubber or super hard metal, there is very little chance that you bounce back when you hit a wall.  We can introduce here two efficiencies: one for the normal component and one for the tangential component.  These efficiencies should be between 0 and 1.  After applying the formulas for the elastic collision, we multiply our four scalars (two per velocity times two velocities) by these efficiencies.  A very high normal efficiency such as 0.95 could simulate the very low loss of energy or a bouncing rubber ball.  A lower efficiency such as 0.50 could simulate what happens to you when you run into a wall.

The efficiencies are functions of the material.  The two bodies have a priori different materials and their efficiencies are multiplied.  If a rubber ball (0.95) bounces pretty well on a stone wall (0.99) with a combined efficiency of 0.95 * 0.99 = 0.94, the same rubber ball does not bounce well at all on you (0.50) since the combined efficiency is 0.99 * 0.50 = 0.49.

It is easy to understand the normal efficiency: it tells you how bouncy the material is.  The tangential efficiency is weirder, maybe it can simulate some kind of friction.

The order of the collisions.

When we are computing the collision response for the velocities, we cannot do what we did for the positions.  For the position correction, we applied all the corrections for all the detected collisions at once.  With velocities, the order of the collisions matters.  We run the dissipative elastic collision code on all the detected collisions, one by one, starting with the closest one.

Actually, if we were trying to be super precise, we could imagine that after our collision on the right wall of Figure 2 we lost so much speed that we won’t collide with the other wall.  There is no way we implement that: doing so would require to find the exact time of the first collision then restart our integration from there with the corrected velocity.  We are not going for something that precise; instead, we will consider that somehow we did collide with all that, and at the very end we’ll see if we have some speed left.  Remember, it all happens within a twentieth of a second (the period of our physics engine).

We have another problem: what if we collide two things at the same time?  The two collisions are at the same distance, so we should compute an elastic collision of three bodies.  It could even be worse, with four or five bodies…  That’s many variables and only two equations (conservation of energy and conservation of mass).  I could group bodies together and replace them by their center of mass but I declare that “too complicated for now”.  I will just apply the collisions one after another, essentially randomly.  We are dealing with distances that are way smaller than a pixel here, and we are represented by circles but we are not circles, so let’s not over-design a simplification.

Let’s start coding then!

That should work, right?  Something tells me this won’t be done by Monday :).