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 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.
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 ?
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:
- Download the zip at https://github.com/Niriel/Infiniworld/zipball/v0.0.5
- or clone/pull/checkout the last tag with
git clone firstname.lastname@example.org:Niriel/Infiniworld.git git pull git checkout v0.0.5
- 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.
- 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.
- 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/.
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:
- 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.
- We must transfer energy between the collider and the collidee, including some loss to simulate friction in deformable bodies. This changes velocities.
The simple case.
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.
- An entity (circle) is at position Black.
- We integrate its motion.
- The motion integrator says that after the time step, the entity should be in the Red position.
- Our collision detector notices that the Red circle intersects the edge of an obstacle (the gray thing). We must respond to this collision.
- We measure how much the entity penetrated the obstacle: we get a penetration vector.
- 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.
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.
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 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.
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.
Picture 4 shows a frontal collision, but our collisions won’t always be frontal. See figure 5 for an illustration.
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 :).
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.
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 :
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.
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.
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.
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 !
I spent quite some time in my previous article writing about the problem of integrating the equations of motions. I looked at three models: Euler, Verlet and RK4. I did not spend much time explaining them because I provided the reader with links to detailed articles about them. After reading this literature, I decided to give RK4 a try.
Copy-pasting the RK4 integrator.
This was much easier and faster than I anticipated. The RK4 integrator itself did not need any work as it is a well known problem and has well known solutions. I just had to copy paste twenty lines of code from the article Fourth order Runge-Kutta numerical integration, by Doswa (not sure it’s the name of the author, could also be the name of the site). That took me a couple of minutes, hop, done!
After that, I needed to feed the integrator with data to integrate. I created a new class named Particle. You can see it in the new module physics.py. A Particle represents a point in space with a mass. It has a position and a velocity in that space. Finally, it contains a set of the forces that are acting on it. A particle does not have a shape or a volume/area; I will introduce these elements later in another class when they will be needed for detecting and responding to collisions.
From the set of forces, and from its mass, the Particle is able to compute its own acceleration at a given moment in time. That’s the famous .
The forces can be anything really. I created two types of forces: a ConstantForce and a KineticFrictionForce. Forces in this framework are actually functions of several parameters. The KineticFrictionForce which simulates friction and slows down Particle has the expression : the faster you go, the stronger the friction. If you give a negative value to the friction coefficient , your particle will slow down. The ConstantForce is simpler, it does not use any of the parameters and always return the same thing when you compute it. That is used for making your entity walk for example.
All that takes 130 lines of code including comments and documentation. Physics engine are easy!
Running the physics.
From the EntityModel I removed the position information and put a Particle instead. The EntityModel declares two forces: the walk force and the friction force. When the player presses or releases the movement keys, the walk force is modified. For now, the friction force is never touched, although it will later when the Entity walks on ice.
The last step is to actually run these physics computations. This is done at the AreaModel level. The AreaModel is a self-contained space with all its landscapes and entities, so it has all the information it needs to calculate trajectories and resolve collisions. Then, I just ask the main game loop to post a RunPhysicsEvent every so often.
That’s it. Very straightforward, it works immediately. You’ve got to like this Model-View-Controller pattern, it really makes our lives easier.
Our implementation is not perfect though. There are no collision detections at all, that’s obvious. But there are other things that can be improved:
- We should introduce a speed threshold: if the speed of a particle is under that threshold then it is considered null. We are not doing that yet, and as a result, many EntityMovedEvent’s are posted even if the entity is moving at the speed of a picometer per century. The kinetic friction force slows particles down but never stops them completely.
- It is time to have a better time loop to: we do not need, and therefore we do not want, to update the physics 60 times per second. We chose RK4 because this algorithm is good with bigger time steps. We should have the physics running at something like 20 Hz. It is commonly said among game developers that in order for the player to feel that its order are instantaneously taken into account, the response to its action should come within one hundred milliseconds. At 20 Hz, we are twice faster than that so we are on the safe side. Running the physics more often is a waste of CPU.
Edited on Monday 15 aug 2011:
Oops, there was a LOL bug in v0.0.4 so I released a patched version: v0.0.4.a. I updated the link at the top of this post. The bug was that units were moving together, all of them following your keypresses. I forgot to tell them to only listen to the orders containing their identification number :p. Fixed now!
Would you like some science with your game?
Not too much science now, since we are focusing today on physics only. And within physics, on mechanics only. Of the classical kind only. With a focus on dynamics only. And within this, of rigid bodies only. And all that in 2D only. This is a very tiny bit of science so we should have it implemented and tested by Monday, right? Right… -_-
Classical dynamics describes and predicts the motion of bodies under the influence of forces. If we model the legs of your in-game character by a ‘walk force’, then you can change the amplitude and direction of this force by pressing the WASD keys and see your character respond to it. If you’ve had a look at the code pushed on GitHub you might have noticed that the MoveCommand event has a force parameter. It is properly generated by the PygameController, but it is stupidly used because there is no physics engine:
class EntityModel(......): ... def moveTo(self, pos) """Set the position of the entity.""" self._pos.icopy(pos) self.post(events.EntityMovedEvent(self.entity_id, self._pos)) def onMoveEntityRequest(self, event): if event.entity_id == self.entity_id: self.moveTo(self._pos + event.force)
So what we are doing here is , which is as far from the Newton equations of motion as you can get while still kinda move in the right direction.
Introducing the time step.
If we try to copy-paste the equations of motion into our code we hit a wall: physics is continuous, but our simulation is limited to using a time step. The time step is the in the equation above. In real life, that time step is tiny, so tiny we can say it is infinitely tiny and we can use calculus to solve the equations of motion exactly, at least in simple cases.
But a game is not simple: there are many bodies moving around at the same time, many forces applied on them at the same time, plus all the collisions that can occur. Solving the equations exactly is out of the question so we have to satisfy ourselves with an approximation that we can compute with numerical analysis.
The smaller our time step, the better the approximation. There are at least two limits to that statement:
- The precision of the floating point calculations is not infinite. A tiny time step can lead to differences in position or velocity that can hardly be represented (if at all) by a 64-bits float. Then your simulation explodes.
- The smaller the time step, the more computations we need to make. If you divide the time step by 10, you have to run your physics engine 10 times more to get to the same time. There is a limit to the number of computations that our computers can do in one second and if we use small time steps then our simulation is going to run late. If it takes you 0.02 seconds to compute the equations with a time step of 0.01 you’ll never catch up and the game will look super slow.
What do the equations of motion look like when we discretize them with a time step ? Well, there are a bunch of possibilities. They are all equivalent with an infinitesimal time step but they won’t be equivalent for us:
# Possible implementation: position += velocity * dt velocity += acceleration * dt # Another implementation: velocity += acceleration * dt position += velocity * dt # Yet another one: position += velocity * dt + 0.5 * acceleration * dt * dt velocity += acceleration * dt
These are all variations of what many people call “Euler integration”. I don’t know why it’s called after Mr Euler since anyone who starts writing his/her first physics engine comes up with one of these. They just feel very straightforward and natural.
Euler integration works decently in some cases. However, it depends a lot on the choice of the time step. Indeed, with that integrator, the acceleration and the velocity are considered constant during the whole time step. That does not make sense: if the acceleration is constant (and not null), then the velocity CANNOT be constant during the time step. That’s the very definition of accelerating. Different time steps will give very different results and you are forced to use a small time step in order to have the best predictions you can. Which is bad, because small time steps force you to compute more.
Verlet and Runge-Kutta integrators.
Fortunately there are other integrations methods around. They are more complex, less straightforward, but not more complicated. For example, Minecraft uses a Verlet integrator. Another popular integrator is Runge-Kutta. There is a bit of a holly war on teh tubes about which one is better and it’s a bit hard to choose. So let’s apply science, shall we?
- Google scholar for “verlet integration” yields 16300 articles.
- Google scholar for “runge kutta integration” yields 78200 articles.
Therefore Runge-Kutta is better than Verlet :D.
Both Verlet and RK come in several flavors. However, from what I’ve seen around the tubes, what people often mean by “Verlet” is Position-Verlet, and “Runge-Kutta” is most of the time referring to Runge-Kutta-4.
You can have a look at the following articles:
- Verlet Explained: A Simple Time-Corrected Verlet Integration Method, by Jonathan “lonesock” Dummer.
- Runge-Kutta (RK4) integration for game physics, by Kai.
The idea behind position-Verlet is to not use a velocity vector at all. Instead, the velocity is implicit: that’s the distance between the last two positions divided by the last time step. This has the enormous advantage of keeping velocity and position in sync. The algorithm is also very light, it’s almost as light as Euler from a computational point of view. Verlet also lets you rewind a trajectory; that time-reversal symmetry is a nifty thing that has its uses in particle physics but I can’t think of a use-case in a game. Also Verlet is good at conserving the energy of the system, which is cool for serious simulations but we don’t care about it in games where external forces (those damn players keep wanting to move their characters) apply all the time.
The idea behind RK4 is to sample the velocities and accelerations at different times within the time step and make use of Newton series for doing its magic. It’s way less easy to grasp, and there are many more computations involved.
Yeah, Verlet is cool. However, I find it a bit weird. Indeed, how do you start it? You need at least two positions to begin with. Of course you can always say that they are equal, that’s easy, but then all your objects are created at rest which may not be what you want. Perhaps it’s enough: the arrow is at rest in the bow and the force of the string is applied only once when the arrow is fired. You’ll have to tweak the force using your time step to ensure that the arrow achieves the same speed regardless of the time step. Another possibility is to use Euler to define the second point. The example of the bow and arrow also illustrates the lack of impulses. An impulse is an instantaneous change of the velocity. Bouncing on a wall creates an impulse: your velocity is mirrored on the wall. With Verlet, just changing the position is not enough to simulate the impulse because your body won’t bounce in the right direction ; instead you have to create a one-time pseudo force that takes the time step into account. Messy.
On the other hand, RK4 lets me do my physics the way I am used to: I have both my position and my velocity. RK4 is very resistant to a change in time step. So even though RK4 is heavier from a computation point of view, I can call it less often. I choose RK4. It’s not even that hard to implement : Integration basics, by Glenn Fiedler on gafferongames.com.
Once I have implemented the integrator, I will have to start the serious business: collisions.
Edit: One hour later…
Wow, that went pretty well. I spent more time writing the post than actually implementing the thing. The version v0.0.4 is pushed on Github, you can pull or and download it already. See my previous post to know how.
Now, I’ll write something about how I implemented it. So little code has changed ! Have a look: