getting 2d collisions right – part two

The engine in all its glory

Uses and limitations

My engine is not a real “physics engine”. All it does is detect collisions between AABBs, send collision callbacks and resolve intersections. It doesn’t deal with velocity, friction, or anything similar.

Bodies do not get stuck between tiles in most of the situations.

So, what should you use the engine for?

  • Simple platformers (Megaman, Mario, Cave Story)
  • Simple shooters (Operation Carnage, Hyper Princess Pitch, Crimsonland)
  • Retro games (anything that resembles games from the 8-bit or 16-bit era)
  • Any other kind of game which isn’t physics-based (and is simple enough)

It doesn’t look like my engine is very useful, but it actually is, considering these kind of games are still played a lot nowadays and can be a lot of fun when done correctly.

The engine is not designed for:

  • Bullet hell games (performance issues would arise)
  • Physics-based games (my engine isn’t a true “physics” engine)
  • Games that require precise collision shapes (the engine only currently handles AABBs, but it wouldn’t be that hard to expand its possibilities)

Another limitation is moving environment: it is certainly possible to have moving platforms and lifts, but their implementation should be designed properly to avoid bugs and intersecting with the static world.

The API: example

The engine is intended to be used as a component for my entity-system (which you can find on GitHub). However it’s easy to implement it in any existing game.

Simply “attach” a CBody object to every entity you want to check collisions for.

public Entity Crate(int mX, int mY)
{
    var result = new Entity(_manager);

    var cPosition = new CPosition(mX, mY);
    var cBody = new CBody(cPosition, 1000, 1000);

    cBody.AddGroups(Groups.Crate, Groups.Obstacle);
    cBody.AddGroupsToCheck(Groups.Obstacle);
    cBody.AddGroupsToIgnoreResolve(Groups.Obstacle, Groups.Decoration);

    result.AddComponents(cPosition, cBody);

    cBody.Velocity = new SSVector2I(100, 50);

    return result;
}

The above method returns a new entity (using my entity-system) that is made up of two components:

  • A position component (which stores the position)
  • A body component (which handles collisions and “physics”)

Ideally, in a real life situation, the entity would have a rendering component that required the position component to display sprites in the correct part of the screen.

The position component is constructed by passing the X position and the Y position as its arguments.
The body component is constructed by passing the position component, width, and height as its arguments.

We have three methods that get called in cBody:

  • AddGroups (sets the body’s current groups)
  • AddGroupsToCheck (sets the groups that will be detected by the body)
  • AddGroupsToIgnoreResolve (sets the groups that will be detected, but collision won’t be resolved with them)

This allows complex game interactions between bodies: you could have player-only force fields, you can have bullets that pass through friendly units, and so on.

To start moving the body, we simply change its Velocity. Acceleration and deceleration aren’t built in the body component, but can easily added to another component (or in the entity itself).

The CBody component

We’re finally getting to the interesting part. We’ll see how the component detects and resolves collisions.

The component implements an Update method that gets called every frame.

public override void Update(float mFrameTime)
{
 if (_isStatic) return;

 _previousPosition = Position;
 Position += Velocity*mFrameTime;

 var checkedBodies = new HashSet<CBody> {this};
 var bodiesToCheck = PhysicsWorld.GetBodies(this);
 bodiesToCheck.Sort((a, b) => Velocity.X > 0 ?
 a.Position.X.CompareTo(b.Position.X) : b.Position.X.CompareTo(a.Position.X));

 foreach (var body in bodiesToCheck)
 {
 if (checkedBodies.Contains(body)) continue;
 checkedBodies.Add(body);

 if (!IsOverlapping(body)) continue;

 if (OnCollision != null)
 OnCollision(mFrameTime, body.Entity, body);
 if (body.OnCollision != null)
 body.OnCollision(mFrameTime, Entity, this);

 if (GroupsToIgnoreResolve.Any(x => body.Groups.Contains(x)))
 continue;

 int encrX = 0, encrY = 0;

 if (Bottom < body.Bottom && Bottom >= body.Top)
 encrY = body.Top - Bottom;
 else if (Top > body.Top && Top <= body.Bottom)
 encrY = body.Bottom - Top;
 if (Left < body.Left && Right >= body.Left)
 encrX = body.Left - Right;
 else if (Right > body.Right && Left <= body.Right)
 encrX = body.Right - Left;

 var numPxOverlapX = Left < body.Left ?
 Right - body.Left : body.Right - Left;
 var numPxOverlapY = Top < body.Top ?
 Bottom - body.Top : body.Bottom - Top;

 Position += numPxOverlapX > numPxOverlapY ?
 new SSVector2I(0, encrY) : new SSVector2I(encrX, 0);
 }

 PhysicsWorld.UpdateBody(this);
}

To analyze the code, I’ve made an image which explains everything:

The real strength of the method is in the sorting: it fixes the “getting stuck between tiles” bug, and is very fast thanks to the broad-phase, which gives the sort algorithm a very small amount of bodies so that ordering the list has almost no overhead.

In the beginning of the post, I said that this still has some limitations. I’ll explain with another picture:

This happens because the sorting algorithm sorts the bodies using the X velocity of the updated body – moving in a diagonal direction like in the last situation causes the sort to be executed incorrectly.

I’m sure this can be fixed with some vector math, but I haven’t got around to it yet – maybe someone in the comments will help :)

It’s not a deal-breaking bug though, considering this situation is rare in most of the cases, and if it isn’t then it’s probably worth having a tile-merging algorithm at the beginning of the level, which transforms adjacent tiles in single bodies.

The broad-phase algorithm

My broad phase algorithm is a very simple fixed grid: basically a 2d array of body containers, divided in groups, with a fixed cell size. I’ll explain how it works with another image. Keep in mind that each body has an hashset of cells that can be accessed by the broad-phase algorithm.

It is fast and flexible: without it each body would get tested for collision against every other body, essentially making it a O(n^2) time algorithm. It also is smart enough to contain bodies of any size, even if they’re smaller or bigger than cell size.

Being clever and setting the cell size to a well-thought amount is still useful to speed up querying, so don’t expect to set ridiculously small or big numbers without a performance and memory hit.

Try the library

Remember the prototype I showed in the last post?
http://www.youtube.com/watch?v=KoRIrWukSsY

You can get the entire library and the test game on my GitHub page.

This is the entity-system project: https://github.com/SuperV1234/VeeEntitySystem2012
This is the test game: https://github.com/SuperV1234/TestGenericShooter

The test game contains all the files related to collisions and physics. Here’s a direct link to them if you just want to take a look:

PhysicsWorld: https://github.com/SuperV1234/TestGenericShooter/blob/master/SpatialHash/PhysicsWorld.cs
C
Body component: https://github.com/SuperV1234/TestGenericShooter/blob/master/Components/CBody.cs

What now?

Future plans

Now that I’m done explaining the basics of a solid and flexible collision system, I have a lot, and I mean a lot of things to still show you.

Here’s what I want to cover in future articles (check the videos to see my old projects):

Thanks for reading! Feel free to ask anything in the comments.

Stay tuned for the next article!

About these ads
5 comments
  1. Wow…You’ve got a pretty nice blog here . As a self taught 16 year old programmer myself I can say that I hope to see more of these :D

  2. Raigan said:

    I really enjoyed these two articles, it’s great to see someone discussing the important details which are often overlooked.

    I know of two methods to avoid problems with bumping-into-cracks, however one of them only works for collision vs. static tiles (i.e it would fail in the case of a “floor” made of many adjacent dynamic boxes), and the other only works when the dynamic shape is a circle.

    In the case of a circle, you find all the closest points (if your shapes are all convex, each shape near the circle will report a single closest point on the surface of the shape) and then find the single closest point and push the circle out of it, repeating until the circle no longer overlaps with anything. This seems sort of similar to your approach in that both involve sorting. For a circle it works perfectly, however I’m not sure whether it can be extended to deal with box shapes.

    Anyway, I look forward to future articles :)

  3. Ben said:

    How long did it take you to get this good?

    • I don’t consider myself “good” :)

      I’ve been programming games since 3 years. I’ve improved a lot since I started, but I’m nowhere near as good.

      Practice is the key!

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: