Monthly Archives: August 2011

Apocalypse Bunny, lessons learned.

Working on Apocalypse Bunny was quite fun.  The ambition was low, which makes the goal reachable and the progress quick.  Also I got to touch many pieces of the software so there was no time to be bored.  I even had to do some pixel art \o/.

Sure there’s no sound, and yes the world map doesn’t make sense, and of course the gameplay is limited.  Don’t care.

It’s time to go back to Infiniworld, the big project.  I learned some valuable lessons thanks to Apocalypse Bunny.

Let’s split our code in packages and modules as early as we can.

I know the zen of Python: “Flat is better than nested”, and I agree.  Python is not java, and theses periods don’t come for free.  The thing is that we do not need to have a flat code to have a flat interface.  To the user, it does not matter that the constant infiniworld.NATURE_GRASS is actually a shortcut for infiniworld.models.tiles.NATURE_GRASS.

The more files we have, the less code they contain.  The less code they contain, the less reasons we have to modify them.  The less we modify, the less we break.  It also helps us keeping our list of import statements short, which helps keeping track of dependencies.

I started by keeping all my modules in the root package but they grew very big.  I got entangled in that mess and had to reorganize all the code in smaller pieces.  That’s not a problem at all for Python, and not a problem for the user either if we make our __init__.py files properly, but that’s a problem for git or every version control system: I lost all my history.  Git accepts that we move or rename a file, but it cannot handle the fact that one file became five or ten.  There’s a big discontinuity in the tree now :(.

So if you know in advance that you will have to split your module, don’t write a module but write a package instead.

We need to make room for the special effects.

Until Apocalypse Bunny, all the EntityViews used to corresponding to an EntityModel.  Apocalypse Bunny changed that with what I called “special effects”.  The expanding circle drawn when we blast a psy-wave does NOT exist in the model, this is a purely visual artifact created only by the view.  Same goes for the blood left on the floor when a creature dies, it’s only visual special effects.

A special effect has a position, a rendering method, a sprite, and listens to events like any other EntityView, but it does not have any corresponding entity in the model.  It is so similar to an EntityView that I actually inherited the special effect classes from EntityView.  I will reconsider the names here because that’s going to be confusing.

Because of the similarities, we want to process special effects like we process the views corresponding to real entities.  So we want to put them in the same list/dictionary/set/group than the ‘real’ ones.  But because of the difference, we need a special identifier that no real entity is using.  I decided that since the entity models were having positive integers as identifiers, I would use negative integers for the special effects.  And thanks to this tiny trick, I got all the special effect code working for free with absolutely no effort at all.

Disappearing entities break everything.

When a fox dies, or when a carrot is picked up, their entity disappears.  That crashes the entire game.  Imagine: the carrots are picked up when we collide with them.  It means that the physics engine is in the middle of its iteration doing collision response when we pick up the carrot and it disappears: RuntimeError: dictionary changed size during iteration.

So you think: “okay, let’s not destroy the carrot entity now, instead let’s schedule it from destruction by posting a DestroyEntityRequest which will be processed when the physics has finished running”.  Think again, because you end up with the following possibility: you touch the carrot, and your friend touch the carrot, so you both pick it up and then it’s scheduled for destruction twice.  It may not crash (although I did ask the event manager to crash when something is unregistered twice) but it’s buggy: only one of you should get the carrot.

So we need:  to remove the dead entity immediately, but also to keep it around, alive.  At the same time.  Schrödinger would have loved this.

Imagine if the wave function had collapsed the other way :(.

Solution: add a boolean variable on our entity saying “I (don’t) exist”. Since the entity stays in memory the dictionaries don’t splode. And since we can tell that the entity doesn’t exist, we can skip it in the physics step. We must really get rid of the entity at some point though, so after setting this variable to False, we post a DestroyEntityRequest.  Neat!

Now, the same is true for appearing entities, except that I do not see any reason to create new entities during a physics iteration. Yet. I’ll think about it tonight.

Not all entities are tangible.

Carrots are supposed to represent small things on the floor.  They should not be obstacles, they should not be pushable.  Sure they won’t block the bunny since the bunny picks them up when she touches them, but they should not be an obstacle for the foxes either.  So we want an entity that detects collisions (so that they detect that a bunny touched them) but does not trigger any collision response code from the physics.

Easy: just add a “I’m (not) solid” boolean variable on the entity body and use it well.  Neat, again!

I tried for fun to make the bunny non solid: she crosses the walls and everything, awesome!  Now we can have ghosts \o/.

We need to pause the physics.

The physics engine should not run all the time: we may be on the title screen, or paused, or maybe there is not even a world yet.  It was not easy to add a pause function to my game loop because of the way I wrote it, so a lot of code has changed in there.  Surprisingly, the code got cleaner ô_O.

Partition space for entities.

My collision code for entity vs entity was brute force: test every entity against every other.  This O(n2) algorithm is of course very poor, but I didn’t know how poor, so I chose not to optimize it early.  Well, after having seen how the performance was crashing once I was reaching 50 entities (I’m talking about 5 FPS here), I HAD to optimize.  I did not use any quadtree or cool stuff like that yet, I just cut my map in chunks of 8×8 tiles and query entities by chunks.  8 is a quite random number, I could probably reduce it to 4, 2 or maybe 1, but that creates more chunks containing nothing and therefore more overhead when updating or searching the chunk map.  I need to test to find a good value.  In any case, as soon as we don’t look at the entire map, we’re fine.

That’s all…

At least all I can think of right now.

The engine source files changed quite a lot ; there is no point in merging the two branches.  I will branch out of Apocalypse Bunny and remove the code related to this specific game (it’s all in the bunny package!) to have my new codebase for infiniworld.  I’ll be doing some refactoring in the next days.  Then, new fun stuff!

Prelude of the Chambered, a game by Notch.

It took Notch 48 hours to make this fully playable game from scratch. I can’t play it right now because I’m at work, but I’ll beat it tonight!

It’s amazing because yesterday night I re-installed my old Might and Magic 3 to have a feel of old-school 3D. Prelude of the Chambered is more on the Wolfenstein side, but that’s a perfect timing.

Here, have a glimpse of how a real coder (not me) works:

It should be quite possible to render Infiniworld with such a 3D engine.  It’s actually one of my goals for Infiniworld 2 or 3 :].

Edit, later that evening:

I died, I was so close! I got lost on my way back from the temple, the ghost boss running after me while I had only 4 health points left. Now I’m scared.

No save/reload buttons, like in real life :(.

Full game: Apocalypse Bunny.

You’ve waited for one week; now is your patience rewarded. Behold my first game, Apocalypse Bunny.

You play as a bunny in a post apocalyptic world. The only place where carrots still grow are in cemeteries because of their fertile soil. However, zombies grow in cemeteries too, especially zombie foxes. They are a bit slow and a bit dumb, but they are legion. You hop and run between your foes and try to gather all the carrots before too many zombie foxes hit you. Fortunately, the radioactive carrots give you strange abilities. With each carrot you eat, your super bunny mind can create a telekinetic shock wave that will repel and maybe even kill the zombie foxes.

Let’s see how you long you can survive ! Don’t become a zombie bunny.

Nyuszi the bunny wakes up in a sinister cemetery, very hungry and very lost. What happened to the world?

Oh, after a long walk near the beach, Nyuszi spots a delicious carrot floating on the murky water. It must be eaten!

Oh no, Nyuszi is not alone, horrible rotten creatures want to nibble her cute ears!

Enough ear nibbling ! Nyuszi gathers the radioactive power of her carrots to blast zombie foxes into oblivion. Good riddance.

Too bad Nyuszi sucked at managing her stock of carrots, she did not last long :(.

Here is a direct link to the zip archive: Apocalypse Bunny v1.0.1.

The Git users will find a new branch on the infiniworld repository called “apocalypse_bunny”, ready to be pulled.

As usual your machine will need Python 2.7 or 2.6 and pygame 1.9.

How to play.

Deflate the zip archive or pull the git branch.

Run the solo.py script that’s in the src directory.

Controls.

• [W][A][S][D] keys to move.
• [Space] key to blast a psy-wave.
• [M] key to take a screen shot (it’s close enough to the space key so that you don’t have to look for it too much).
• [Esc] key to quit.

If you’re using a French keyboard, then it’s ZQSD to move and [,] to take a screen shot.  So it’s the position of the keys that matter, not what’s written on them.

Hey Taurus my friend, I have not merged your code for configuring the keys as you’ll notice that the code changed a LOT.  On the good side, the new code makes configuring the keys easier.  Little work is needed to adapt your code to the new codebase.  I’ll take care of it :).

Goal.

Survive as long as you can.  Like with real life you cannot win, you can only delay the inevitable horrible end of your cute fluffy bunny.  Who wouldn’t want to help her?

To survive, avoid the foxes (they bite you) and kill them with the psychic powers that the uranium-enriched carrots give you.  Foxes appear every 3 seconds somewhere on the map (there’s a zombie counter on the screen).  Carrots appear every 10 seconds.

We’ll see who survives the longest :D.  Remember: pics or it didn’t happen.

Feedback.

If the game crashes, refuses to start, is horribly slow or jerky, maxes at 20 FPS or whatever, please tell me.  I did spend time optimizing performances, and I tried to make sure the code was cross platform (Windows and Linux have totally different ways of measuring time even with python as a common language) but I don’t have that many computers to try the game.

No need to tell me the sound doesn’t work: I have not put sounds yet.

And if it works, tell me that too !  Along with a words telling what kind of operating system and CPU you use.

In the next post…

In the next post I’ll tell you what I learned when writing Apocalypse Bunny.  Trying to make a complete working game out of the minimalistic game engine of Infiniworld took quite some effort, and I have a much better insight into what features the engine needs to support.  Not much of the engine changed, which is relieving because it means I didn’t get too many things wrong.  But many things should be added in.  There shall be refactoring soon!

Until next time, folks, until next time.

Edit, 30/08/11.

Python 2.6 didn’t like the version 1.0.0 of the game: it complained about a syntax error.  I corrected it and made it the version 1.0.1.  The download link above is already updated.  Thanks for the bug report, MilanFIN!

Apocalypse Bunny, first sreenshot.

Super quickly before going out with friends, this screen shot!

There are 50 zombie foxes on the map.  I want to be able to handle 100 or 200 but I didn’t optimize anything so we run at 40-50 FPS.  It’s not too dramatic.

They run toward you when you get too close. You’re faster, but you can get stuck.

I think the Bunny's pretty much dead :(.

Next steps: timer for the score, life meter of course, and these carrots !

Let’s make a quick and dirty game.

Hello hello!

With my previous post regarding the game loop, I wrapped up the basics of what could become a game. It has physics, interactivity, display. However, technical demos are not very interesting to download and run. I thought I should craft a very simple game using the primitive engine I have built. That game will have very little to do with Infiniworld, but it will serve as a proof of concept: this engine can support a game. So let’s do that.

You play as a bunny in a post apocalyptic world. The only place where carrots still grow are in cemeteries because of their fertile soil. However, zombies grow in cemeteries too, especially zombie foxes. They are a bit slow and a bit dumb, but they are legions. You hop and run between your foes and try to gather all the carrots before too many zombie foxes hit you. Fortunately, the radioactive carrots give you strange abilities. With each carrot you eat, your super bunny mind can create a telekinetic shock wave that will repel and maybe even kill the zombie foxes (that’s for using the physics engine :p).

Let’s see how you long you can survive ! Don’t become a zombie bunny.

ZOMBIE BUNNY by ~RM73 on deviantART.

And let’s code that :D.

A wild game loop appears!

Figure 1: Game loop, I choose you!

I told you in my previous posts that the physics would update at 20 Hz while we would render frames at 60 Hz.  It is now implemented and available in the v0.0.6.b of Infiniworld.

There were two things to do:

• make the game loop smarter,
• make the view able to interpolate.

Frame interpolation.

If we update the frames three times faster than we update the physics, then we end up rendering three times the same scene with all the entities in the same positions, making our game look like it is rendered at 20 FPS instead of 60.  Nobody wants that.  To avoid this, we can modify the AreaView so that it can perform some interpolation between two physics states.

It felt immediately obvious to me that I should interpolate between the last known physics step and the next one.  Of course the next one hasn’t occurred yet, so I should predict it.  I can predict it for example by using a simple Euler integration: this is computationally cheap and noone is likely to notice any error on a time span of a twentieth of a second.  Then I realize it cannot work because it does not predict the collisions at all.  I need to run the full physics engine in order to have my predicted future. But that does not work either: I cannot predict what the user will do.  I can predict what the Entities will do by running their AI, but the player is a mystery.  And then, what ?  At the next time step I have to recompute the same physics step again, this time with the right player input.  This means that I run the physics twice for every step, and half of these computations give a wrong result because the player cannot be easily predicted.  It sounds like a bad idea doesn’t it?

When we try to guess the future we are not really interpolating, we are extrapolating.  And this, for the reasons given in the previous paragraph, will not work well.  What we should do is interpolating between two known physics steps in the past.  This has the strange consequence that the scene we render on the screen does not show the present state, but a state from a very close past.  This made me feel strange at the beginning, until I realized that we are talking about a delay of a sixtieth of a second, which nobody will notice.

I chose to apply a linear interpolation: we can compute it very fast and it looks good enough.  In short, it means that our entities are smoothly moving in straight lines between the positions given by the physics engine.  I could do some splines or fancy things, using more physics steps, but that would not look nicer.

Figure 2: We render frames using positions interpolated from the last two known physics steps.

The EntityView objects need to store three positions now: the position at the last physics state, the position before that, and an interpolated position.  The latter comes from this very simple line of code:

# Snippet from pygame_.EntityView.interpolatePosition
self.int_pos = (self.old_pos * (1 - ratio) + self.new_pos * ratio)


Each RenderFrameEvent now comes with a ratio.  We use this ratio to interpolate the position of all the EntityView sprites.  Then we draw the scene using these interpolated positions.

Note that only the view does this: the model does not know anything about this interpolation.  Not a single line of code is changed in the model and its physics engine.  We respect our Model-View-Controller pattern.

A smarter game loop.

In order to feed the AreaView with a ratio for its interpolation, the game loop has to compute this ratio. But that’s not the only thing the game loop should do. It should:

• read the inputs from the keyboard/mouse/joypad/touchscreen but also from the network if we play online ;
• run the physics ;
• render the frames with the proper interpolation ratio.

But that’s not it, it also should

• run the physics at a rate that does not depend on the speed of the machine, which means catching up if the rendering takes so much time we are getting late ;
• have the highest FPS we can achieve, while still limiting it to what makes sense with the refresh rates of out monitors, independently from the physics ;
• save some battery and keep the CPU cool by sleeping as much as we can.

I am giving you here links to two very famous and well written articles about game loops:

They present various game loops and their behaviors on fast and slow hardwares.  That’s a good read for people who develop on PC and have to worry about guys like me who change their computer once every five years (and buy each time a cheapos one).  The loop I came up with looks pretty much like what they present at the ends of their articles: everything is independent from everything else, the physics is able to catch up when it’s getting late but even in that case it renders frames once in a while (better have horribly slow game than no game at all).  What I added is the possibility for the CPU to take a rest, and some protection against time jumps that the Network Time Protocol can cause on some machines.

There is a weird thing on the tubes…  I was wondering whether my game loop should sleep or not and many people seemed to find perfectly normal to have the game loop eat ALL the CPU (that’s just one source, I read that in several places).  Even Fiedler and Witters do that.  Why ?  I’ve seen screenshots of Minecraft with absurd frame rates (see Figure 3). Do these people know that their monitor is limited at something like 60 Hz ?

Figure 3: Some dude running Minecraft at 556 FPS. Testosterone much?

At the old times of CRT monitors, 100 Hz was not a luxury, it was a need-to-have if you didn’t want to be staring at a stroboscope all day.  Believe me, I can see a refresh rate smaller than 100 Hz on a CRT.  But we have LCD/TFT/Plasma/dunnowhat monitors now where 60 Hz is perfectly healthy.  Why would you render 10 frames to only display one ?  Maybe it makes sense when you use accelerated graphics cards, but that’s still dumb.  It’s going to make your fans turn at full speed which is never pleasant to the ears and prevent you from playing in summer.  And if you are one of these weirdos who like playing with a laptop on battery in the train (or worse, a Pandora!) you are pretty much doomed.

Now, sleeping is not super reliable, we can wake up if a signal is sent to our process, or we may sleep a bit longer than we hoped.  But I designed a game loop robust enough to handle change in speed, so let’s just do it!  I’ll put the CPU to sleep.

Here you can read the code of my game loop: https://github.com/Niriel/Infiniworld/blob/v0.0.6.b/src/loop.py.

Conclusion.

Figure 1 shows the new game loop in action: This picture is totally representative of what Infiniworld will look like in the end{.} Dear font nerd Pokémon fan: I know I didn’t use the right character font, that’s because I pixel-arted the text in the picture myself ; now, go glitch yourself a Mew. Dear rest of the Universe, let this video blow your mind:

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.

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!

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 :).

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 !

Physics engine – integration, wrap up.

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!

Defining particles.

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 $F=ma$.

Calculating forces.

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 $F=\mu \times v$: the faster you go, the stronger the friction. If you give a negative value to the friction coefficient $\mu$, 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.

Future improvements.

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.

Next step, collisions!

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!