Get it here:
https://github.com/SuperV1234/VeeSharpTemplate/downloads

Outdated video:
http://www.youtube.com/watch?v=Uz868MuVvTY


This is especially useful when dealing with numeric types.
It can be easily used to generate vector classes for every numeric type, and also utility classes that can allow you to add/subtract the generated.
The possibilities are endless – the generated code is easy to update and recompile, and since it’s like you’ve written it, there is no performance loss.

After being fed up with some limitations of generics (why isn’t there an IArithmetic interface?), I decided to make a code generator that creates C# code by simply reading templates made in C#.

It’s hard to explain with words, but I have made a video with voice commentary that will explain how it works and show a simple result.

With this code…

var types = new []{"int", "float", "double", "long"};

foreach(var type in types)
{
    $$("public class Vector2_" + type)
    $${         
        $$("public Vector2_" + type + "(" + type + " mX, " + type + " mY)")
        $${
            $$ X = mX;
            $$ Y = mY;
        $$}

        $$("public " + type + " X { get; set; }")
        $$("public " + type + " Y { get; set; }")

        $$("public " + type + " ComponentSum()")
        $${
            $$ return X + Y;
        $$}
    $$}
}        

…my program automatically generates and automatically adds to a .csproj four new classes: Vector2_int, Vector2_float, Vector2_double and Vector2_long.

Watch the video for a better explanation! Thank you :)

2d level procedural generation

Thoughts

I’ve always been a fan on procedural generation, not only for environments, but also for entities (enemies, items, weapons, etc.).

However I don’t think at all the procedural generation is “better” than user-made content.
Procedural generation works best when the entire game is designed around it, when level design doesn’t require a lot of creativity or when the elements are simple enough that any level will be fun to play.

User-made content is still superior in most of the results, but it is obviously more consuming in terms of development times.

Also, even though I never experimented with it a lot, I’ve always liked the idea of mixing user-made content with procedural generation. An example could be levels made up of user-made rooms attached together randomly.

Something similar is modular item creation, like in Borderlands, where developers create a lot of pieces and then the system attaches them together randomly, creating interesting results.

I think that procedural generation is a very powerful tool, it can help you save precious development time on content creation and also dramatically increase any game’s re-playability.
I think it is suitable for any game genre, in one way or the other – it shouldn’t be limited to roguelikes.

My first tests

This probably was my first test, made in 2009. It is very simple, it generates empty rooms in a wall-filled 2d array, then carves a path from every center of the room to the other centers. It generated predictable and boring levels. It is an example of what not-to-do.

This is the updated version. It still gives the same results, but stores rooms and paths in objects, so that you can collect and manipulate them more easily. It also creates walls around walkable tiles to make the levels look a little nicer.

Then I experimented with field of view algorithms and other typical roguelike mechanics, and this prototype is what came out of it: http://www.youtube.com/watch?v=FyHrHb76lnY

Moving on

I stopped experimenting with procedural generation after a while, and worked on other stuff. That’s when I started getting into a puzzle game, called DROD (Deadly Rooms of Death), which caught my attention for a lot of time, so I decided to make a clone of it.

When suddenly it struck me – I’ll make a roguelike clone.
I started working on a level generation library, this is the first video of it: http://www.youtube.com/watch?v=tbMcle88t3U

The generation was still largely similar to the one of the previous video. I was however storing room outlines and rooms separately, so that I could easily add doors or pathways that didn’t start from the center.

This next video shows how useful storing rooms in separate objects was – I added special tiles that prevented diagonal movement in random rooms: http://www.youtube.com/watch?v=9EEh0OJjKO4

The last video shows why storing paths is also a good idea – I randomly added doors along paths to spice up levels: http://www.youtube.com/watch?v=QFMM4qtUbx4

You can download the latest version of the game here, which should be perfectly playable:
https://dl.dropbox.com/u/3724424/Programming/DRODRoguelike.rar

The source is also available on GitHub, along with the resources needed to compile it. (Keep in mind that this is an old project, and code quality is not good.)

Improving the generation

In 2011, I started experimenting with pathfinding. I had the idea of randomly generating levels by placing rooms around in a big open space, then pathfinding from the first one to the next one, until they were all connected.

This was my first attempt: http://www.youtube.com/watch?v=Ve0s8109Erg

As you can see, it was slow. It also added doors on random room outline tiles.

I improved it a bit later, rendering tiles with SFML.NET. Also added a simple player entity and basic collisions: http://www.youtube.com/watch?v=NDeM5oQyve8

This is much more interesting than the DROD Roguelike one, because it doesn’t create overlapping rooms and paths, which can lead to unintended solutions or simply bad-looking levels.

The generated levels could also be retrieved as a connection of nodes (a graph). This was incredibly useful, because you could actually write some clever code that automatically added keys and doors that were accessible only in a specific order and make levels less linear.

his is still my favorite approach – it could also be sped up by using Jump Point Search instead of A*.

VeeGen

I decided to create a library for easy 2d terrain generation. Code quality is not the best, considering it’s from late 2011, but its features are working and it’s easy to use in any project.

It’s called VeeGen, and it is available on my GitHub page, along with a demo.

Here’s how the API looks:

int width = 100;
int height = 100;
int initialValue = 0;

var world = new VGWorld(width, height, initialValue);
// creates a world that contains a 2d array of tiles

var area = new VGArea(world, 0, 0, 50, 50);
// defines an area that goes from 0;0 to 50;50

var dungeonGenerator = new VGGBSPDungeon(mSplits: 9, mCarveOffset: 1);
dungeonGenerator.Generate(area);

There are three different generators in the library:

  • BSPDungeon: generates a dungeon via binary space partitioning
  • Cave: generates a cave using cellar automata
  • Walker: uses “walkers”, entities that walk around the area, carving it and spawning rooms randomly

In retrospect, the API could be highly improved, but the functionality is still there. I have a video explaining most of the features right here, check it out: http://www.youtube.com/watch?v=d0ByM6mkce4

The cool thing about VeeGen is that you can mix’n’match different generators. Areas allow you to use a generator in a certain part of the world, and another generator in another part.
With some interesting code you could create dungeons with rooms filled of caves, for example. Or a large open world with dungeons and caves placed randomly

But even more interesting is the fact that you can use more generators in the same area. You can see in the video (and try it for yourself in the demo) that it is possible to generate a dungeon on top of a cave, then, hypothetically, have some walkers carve some additional paths and rooms in the dungeon.

The possibilities are endless, and creating custom generators shouldn’t be hard at all.

What now?

My next post will be about bullet-hell games. In particular, it will follow the birth and the death of my Touhou clone. I will cover some interesting topics:

  • Performance (bullets everywhere!)
  • Collisions (point vs circle, line segment, polygon)
  • Flexibility (scripting capabilities, C# lambdas)

Stay tune – thanks for reading! 

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/