getting 2d collisions right – part one

Welcome to my blog

Allow me to introduce myself: I’m a 17 years old italian self-taught developer. I use C# and SFML.NET to transform my ideas into playable games.

I’ve been reading a lot of game development blogs lately, and I’ve found all of them very helpful. Crafting a lot of game prototypes gives you an insane number of problems to solve – I’ve finally decided to create a place where I can share the best solutions I found to some of the problems that every game developer must face.

I’ll begin with a long and detailed story on how I managed to create a flexible 2d collision library that gets the job done in most simple 2d games.

This first article will narrate the story of a young game developer who decided to write his own physics engine. I won’t cover many technical details in this post, but expect a lot of source code and a downloadable library on the next one! :)

Back in time

The (nonexistent) joys of physics engines

Let’s go back to the previous year. I was trying to develop a puzzle platformer, with non tile-based environments. Game design is not my biggest strength, so all I had was a Abe’s Oddysee companion system ripoff and some basic elements such as crates, spikes, buttons, doors, etc.

This is a mockup I made for the game. Simple programmer-art… I can’t draw.
After a while, I had a playable prototype using Box2D. Levels were made up of entities which could be placed anywhere (non tile-based), but were actually positioned to resemble a tile-based environment.

This is where everything started going to hell.

The first thing I noticed is that, even when I changed friction and acceleration on the player entity, controls didn’t feel as tight as a non physics-engine-based platformer.
Then, the worst happened: the player kept getting stuck between “tiles”.

I browsed the Box2D community forums for a while to find out this was a common problem. I realized the only decent fix would’ve been merging adjacent tiles before starting the level, but I didn’t find that elegant enough, and decided to take a big step: develop my own collision engine.

Reinventing the wheel

My first approach was quite simple. I had a World object, which held all the bodies of a certain level. Bodies were divided in static and dynamic. Dynamic bodies were updated each frame.

Bodies were simple axis-aligned bounding boxes (AABB). I was using a fixed grid spatial hash to make broad-phase collision detection much faster.

My first update loop was quite simple and ineffective - a Frankenstein monster of many techniques read online which resulted in:

  • Loop through each body
  • If it intersects the player, find the intersection vector
  • Get the smallest axis of the vector
  • Move the player only in the previously found smallest axis

You can see the result of this primitive physics engine here: http://www.youtube.com/watch?v=3tIoD6zu5iA

It doesn’t look so bad, does it?
Well, looks can be deceiving.

After a while, I found a bug where crates in certain positions of the level would shake uncontrollably and give all sorts of collision problems. I had no idea what to think. You can see the bug for yourself in this video: http://www.youtube.com/watch?v=bRynch1EtnE

It was one of those weird bugs that came out of nowhere with no explanation.
Why were the crates shaking?
Why did it affect them only in determinate places?

Debugging didn’t help much. Then I remembered that floating-point values (which I was happily using throughout my whole physics engine) could be imprecise and result in strange behaviors.

I’ve experimented multiplying or dividing every value and my fears were proven right: floating point values were causing this bug.

I asked for help on stackoverflow here: http://stackoverflow.com/questions/6422293/floating-point-precision-and-physics-calculations

I was told to use an epsilon value in my comparisons. I tried doing that but it was harder than I expected. Then I decided to cut the Gordian knot: I simply ditched floating-point values for integers.

Ta-dah! The bug was fixed. At the cost of not being able of having increments smaller than a pixel. Or so I thought at first.

I decided to multiply every value (position, velocity, size) by an arbitrarily large value, and render everything dividing by that value. This way I could have increments or decrements as precise or imprecise as I wanted.

It did the trick. This video shows how stable it was: http://www.youtube.com/watch?v=07I3TZvk1tU

It still had a big problem: flexibility.

  • What if I wanted to have a player-only force field?
  • What if bullets had to be ignored from friendly units?

I decided to implement a grouping system where every physical body would contain different lists:

  • Groups: the groups the body belongs to.
  • Detection groups: the groups the body should test detection against (and return a collision callback)
  • Resolution groups: the groups the body should test detection against, then find the penetration vector and resolve its position.
  • Ignored bodies: an hashset of specific bodies that had to be ignored (both in the detection and resolution steps).

Thankfully, the powerful LINQ syntax made querying those lists easy, and I was able to filter detection and resolution easily. To celebrate, I made a Super Crate Box clone, shown in this video: http://www.youtube.com/watch?v=V7RDNXeiulU

The celebration and the joy quickly turned to despair when I found a deal-breaking bug. Entities were getting stuck between tiles.

“How did you miss that for all this time?” - you may ask.

Well, the bug happened only in vertical pseudo tile-based walls (entities placed adjacently), when the player was both jumping and moving against the wall.

This happened because the smallest penetration axis would sometimes be the vertical one on the edge of the tiles. And to make everything more confusing, it only happened when tiles were placed from top to bottom in the world, and not viceversa.

This image illustrates the problem: http://i.stack.imgur.com/NLg4j.png

I decided to go for a quick-fix, and simply resolve the X axis before the Y axis. Always. Needlessly to say I wasn’t happy at all with this, because it made my physics engine much less flexible (think about non-platformer games, with no gravity: there isn’t a priority between axes!)

I was making progress, though, so I decided to make something resembling my first mockup.

Take a look at this video: http://www.youtube.com/watch?v=iOr_BTZ5U28
I was even developing an in-game level editor :)

I decided to add more objects. I added non-deadly spikes and crushers that moved around the level and could be programmed directly in the in-game level editor. I also decided talking over my dev videos (I’m sorry for the terrible pronounce): http://www.youtube.com/watch?v=wKwq_Ga5d-k

I implemented even more stuff… you can see the results here:

http://www.youtube.com/watch?v=psFfbDrRR9Q
http://www.youtube.com/watch?v=cou_tVcgT38

I was happy with the development, but kept wanting more out of my engine. I added springs which would boost entities in different directions. Then an idea struck me: what would happen if I had to stack multiple entities on top of a spring?

All hell broke loose.

My physics engine wasn’t really a “physics” engine. There was no velocity transfer between bodies, things kept behaving in the wrong way, et cetera.

This is the first bug that really broke the game: since I was resolving the X axis first, the player would get pushed away from vertically rising entities.

I posted an in-depth discussion on stackoverflow (gamedev section) about the bug, and people were really helpful: http://gamedev.stackexchange.com/questions/14486/2d-platformer-aabb-collision-problems

Remember when I said that the “getting stuck between tiles” bug happened only when tiles were placed in a certain order? I decided to fix it by simply sorting the tiles the player had to detect collision with in the direction the player was moving. If the player was falling, sort them from top to bottom. If he was jumping, do the opposite.

It fixed the bug and made the engine a little more flexible, since by sorting in both axes I could have implemented a non-platformer game easily.

Then, I tried working on the infamous spring bug:

I posted an even more detailed discussion on the same website, and people were even more helpful, trying to give me the best solutions: http://gamedev.stackexchange.com/questions/15621/momentum-and-order-of-update-problems-in-my-physics-engine

However, the best solutions weren’t easy at all to implement, at least not without writing the whole engine again, at the cost of performance and precision. Basically, I had to write my own version of Box2D. And why? To fix the player getting stuck between tiles, the bug I had in my first prototype (which actually used Box2D).

I was really unmotivated to do that and completely scrapped the project. I will upload the latest playable build on this website soon.

End of part one

What exactly went wrong?

I wanted to make a physics platformer. And I didn’t want to use a physics engine.
I tried to reinvent the wheel, with promising results at first, but failed.

I didn’t have any design document – I didn’t know what I was doing, what I wanted from my game, what I was going to implement next and what consequences it would’ve had.

In retrospect, the game could’ve worked perfectly if, for example, I never had decided to implement springs. Or if I just decided to use Box2D and work around its problems.

All of my work, gone?

Nope. My physics engine wasn’t really a “physics” engine but it was a damn solid collision detection and resolution engine, that was actually pretty fast, flexible (groups!), and when it was used with the knowledge of its limitations could give amazing results.

I cleaned up the code and turned it into a component for my current project: a component-based entity system.

The engine is now perfectly adequate for any kind of simple 2d game, that doesn’t involve crates or springs (and especially crates and springs stacked on top of each other).

I’ve been making a simple shooter prototype to demonstrate that my engine works, you can see the latest video I released here: http://www.youtube.com/watch?v=KoRIrWukSsY

Now what?

This article was pretty much a story of a failure in game development. A failure that gave birth to a useful library and gave me a lot of experience, though.

The next article will cover in detail how the collision engine works:

  • Spatial hashing broad-phase for high performance
  • Sorting entities to avoid “getting-stuck” bug
  • Collision callbacks
  • Detection and resolution groups
  • How the resolution actually works
  • Uses and limitations of the engine

Thank you for reading! Keep in mind that this was my first serious article so I may have missed something and made some spelling mistakes. Feel free to ask anything in the comments.

Stay tuned for part two!

 

Part two is now finished – check it out here:
http://veegamedev.wordpress.com/2012/08/14/getting-2d-collisions-right-part-two/

2 comments
  1. Hey Vee! I think I may have posted something earlier here but, I recently made a “text based adventure game” with the console in C++. I thought it was pretty cool. So this was a few days ago, and it was after 3 months of learning C++. I had to make myself get out of the comfort of C++ and learn new syntax, that of C Sharp. Must say, I’ve been messing around with it for a few hours, and I’m already liking it! Haha, I’m 16 years old, and, I tried SDL with C++ and it seems to old, and I tried looking at SFML with C++ and it hurts. But, lol I’m gonna be just like you! I’m trying C Sharp for awhile, then I will apply SFML 1.6 or SFML.NET for a graphics library. I’m into programming, especially games. ~just thought I’d let you know!

    • Hey, thanks for commenting. Honestly C++ is a great language, but it can be harder to pick up than C# or Java. I think both C++ and C# are good candidates to start programming, but C# is much more streamlined and generally makes “more sense” than C++. Also, if you use C# with Visual Studio and ReSharper, you practically have productivity and refactoring heaven: think about auto-completion, automatic refactoring, and so on – you can only dream about this stuff in a C++ IDE.

      The only downside is that C++ is much faster and more powerful than C#. But you will hardly be hindered by C# performance overhead or lack of specific features.

      Good luck with your goals! :)

Leave a Reply

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

WordPress.com Logo

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

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 28 other followers

%d bloggers like this: