Collisions: Part 2

With a full weekend of coding, I was finally able to make good progress on my collision detection and resolution.

Last week, I began to implement the AABB Sweep Test. This is a continuous collision detection algorithm that solves the ‘bullet through paper’ problem, in which a fast moving object will pass through another object undetected. This issue arises if your collision detection algorithm fails to check a sufficient set of positions between in start and end position for each time step. The AABB Sweep Test uses the Separating Axis Theorem which states that there exists an axis on which the projection of the objects do not overlap. Therefore, all we have to do is track the earliest times of collision and disjointing for each axis. If all axes collide before any axis becomes disjoint, then a collision occurs. Not only that, but we know exactly when and on which axis the collision occurred. The following video demonstrates the Sweep Test at work, causing blocks to flash red if they detect a new collision caused by the player (overlaps are not colored red for demonstration purposes):

With collision detection completed, I was able to move onto collision resolution. My current solution is not perfect, but I certainly feel that I am on the right track. In short, I am following this structure:

Adjust entities according to input and velocities
For all entities i
  For all entities j from i + 1
    If i is colliding with j, add to contacts
For all contacts c
  For all c's entities a
    If c's time is == a's earliest time
      Add force to a's forces
      Add impulse to a's impulses
For all entities i
  Add force aggregate to i's position
  Add impulse aggregate to i's velocity

The basic idea here is that the collision resolution will calculate two things: force and impulse. Force is the vector required to remove the object from its collision, and impulse is the resulting velocity after the collision. I have to be careful about how and when I apply these values. If I were to apply the force as soon as it was calculated, than the proceeding force calculations for this time step would be incorrect. Similarly, if I were to apply the impulse before all collisions were resolved, I could easily cause undetected collisions. The end result is demonstrated in this short video:

There is still some collision work to be done and bugs to be fixed, but with any luck I should be able to add some more realistic physics and controls. Look for that and more next week.

Collisions: Part 1

Now things start to get tricky. My first goal this week was to devise a plan for collision detection/resolution.

Because my game will be axis-aligned, I’m able to stay in the realm of AABB (axis-aligned bounding box) collision detection algorithms. In particular, the one that caught my eye was the AABB Sweep Test. This algorithm uses the Separating Axis Theorem, or SAT, to detect if during the next timestep two AABBs will overlap across all axes before they become disjoint along any axis. If the first time of overlap occurs before the last time of overlap, a collision occurred. Now we can simply return the time at which these two AABBs collided and extrapolate a good approximate of the position of collision.

Next up is the collision resolution. We now have the position of the collision, so we can move the two AABBs to their respective positions at the time of collision. I see a couple options at this point. I could compute the new velocities for each AABB and resume movement and collision detection for the remainder of the timestep. Another method, inspired by this post, involves stopping the current timestep at the time of collision and applying an impulse to the next timestep.

I’ve began implementation on collision detection and I’m still researching the best approach on collision resolution for now, stay tuned for part 2.



Screen Manager and Level Editor

Happy Tuesday!

The last couple weeks I have completed a lot of the initial footwork to get the game up and running. In the end I was able to complete three major game components: the Screen Manager, Level Editor, and XML serialization/deserialization.

Before we get into those, it’s worth discussing my game organization. The game is split into three projects: Game, Content, and DataTypes. The Game project contains the main code to be executed during run time, including the main game and level editor. The Content project contains all of my textures, tilemaps, audio, and fonts that will be loaded from my Game project during run time. The DataTypes project is used to define any types used during the XML serialization process (The reason this is separated is due to cyclic referencing when the XML tries to build using a type that is defined within the same project, see build time vs run time).

The first component that I was able to complete was the Screen Manager. This component controls was modeled after the Game State Manager tutorial and these Screen Manager posts. The Screen Manager component keeps a list of all of the game’s possible screens, currently containing the StartScreen, ActionScreen, EditScreen, and LoadingScreen. The StartScreen contains the main menu with entry points to the ActionScreen and EditScreen, which contain the active gameplay and the level editor respectively. The Screen Manager is responsible for keeping track of which screen is the active screen and invokes its update and draw methods.

Simple StartScreen with menu options

I decided to create a simple level editor because creating ASCII level files or manually editing XML was quickly becoming unmaintainable. So I created a simple level editor in which I could interactively add and delete tiles from the screen. In addition, I could select different color tiles to draw onto the screen. This quick implementation is nothing fancy, but it allows me to quickly develop levels to load into the main game.

A simple level editor creation

Simple level editor creation

Once I draw a level onto the screen, I needed a way to save that and load it into my main game. I did some research and discovered an interesting solution: XNB Serialization. By creating a TileData class in my DataTypes project, I was able to fill an array of TileData objects and serialize that into an XML file containing my TileData definitions. Then referencing some XNA Storage tutorials, I was able to save that XML file to disk. Finally, once the XML is added to my Content project and recompiled, the XML files compile into XNB files which can be deserialized back into the TileData array on the main game side at runtime. Because this deserialization plus loading all of the textures takes some time, I added a LoadingScreen to disable to active screen until the loading process is complete. This process is requested by the active screen and managed by the Screen Manager, who hides/shows the LoadingScreen upon request/completion.


ActionScreen loading level form level editor

Now with all of that out of the way, I will start working on some simple 2D physics as well as collisions. Look for updated relating to that next week!

New Project: 2D Puzzle Platformer

My first project will be a 2D puzzle platformer. The basic concept that will make this game unique comes from the 8-puzzle, a game consisting of a 3×3 board in which you can make a sequence of slide operations on numbered tiles into adjacent empty spaces in order to sort the tiles numerically. This game’s environment will be using a similar tile structure in which each tile is a traversable set of blocks. As the player traversing through these tiles, he will be able to shift or rotate the tile in which he is currently located in order to alter the environment. By manipulating the world, the player will be able to navigate within and between the tiles in order to reach the goal.

Take this simple mockup for example:

Original state of level

Solution path

Solution path of level

In this example, the player (blue tile) begins in the bottom left tile and is trying to reach the goal (green tile) in the top right tile. The player cannot reach the upper two rows, so he approaches the help box (yellow tile) in the bottom right tile, which informs him about sliding tiles. Following the help’s advice, the player shifts the bottom right tile into the middle right position. From there, the player can navigate to the middle left tile and shift up to the top left. Finally, the player can progress to the goal in the top right.

In addition to shifting tiles, this game will also feature rotating blocks CW or CCW as well as flipping blocks horizontally and vertically. As the player progresses the environment will also become more complex with larger level dimensions, new tile dimensions (such as 1×2), and new obstacles. Of course, the game will also feature simple 2D physics and collisions. I will go into more detail into the game’s specific features as they present themselves during development.

This game will be developed using the Microsoft XNA Game Studio 4.0 in C#. This project is intended to be fairly small in scope and I’m viewing it as a learning experience. It is something that I can have fun working on and share with others as I go along. I’m very much looking forward to working on this project and seeing it through to completion, and I hope you enjoy following along as well.

Hello world!

Good evening all,

Programming has always been a great passion of mine, however I have never been very active in sharing my work and experiences with others except for my immediate classmates and coworkers. Today that is going change. I’ve created this blog as a place where I can record and share my progress and discoveries as I mature as a developer.

My first project that I will be sharing is a small 2D platformer that I have recently began developing. I have had some exposure to game development in college, but this will be my first self-driven game project. To keep myself on a steady schedule, I will be updating this blog every Tuesday with the latest developments. I hope this experience will pave the road to more involved and higher quality projects in the future.

Stay tuned for updates!