Archive

Tag Archives: game

Official page: http://www.facebook.com/OpenHexagon
Download: http://78.47.100.242/VeeSoftware/OpenHexagonV1.1.zip
Mirror: http://www.mediafire.com/?1vtbeterz951ejo

Fixed: input being registered when the game was not in focus.
Added: config overrides. (JSON files that override certain config parameters)
Added: .bat files for WINDOWED and FULLSCREEN modes.
Changed: JSON name members for windowed/fullscreen config parameters.
Fixed: sudden side number changing bug. (now it waits until all the obstacles are removed)
Fixed: impossible pattern bug.
Added: another tutorial level.
Added: new style. (zen2)

Advertisements

Open Hexagon is my first completed game.
It’s a fast paced fun clone of Super Hexagon (by Terry Canavagh).

The goal of the game is to survive as long as possible, by avoiding the walls closing in towards the center.
You are the little triangle, and can rotate by using the left/right arrow keys.

The soundtrack is made by BOSSFIGHT.

The game is completely customizable: you can create and share levels/patterns/styles/music.
Everything can be modified and created with your favorite text editor, thanks to the simple JSON language.

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!

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:
https://veegamedev.wordpress.com/2012/08/14/getting-2d-collisions-right-part-two/