Furious Pixels

Building Your Own Game Engine - Graphics

2011-10-23T00:11:00.001+02:00

This is the last one in the series of articles that go through the architecture of a small game engine for a small game, The Jelly Reef. The very last thing that was implemented into the game was the graphics. The art team in the first weeks of development was looking for the right look for the game. In mean time the our designer was looking for the right feel, we decided give this top priority and started writing the gameplay code and all the infrastructure. The graphics would wait up until we know what the game will be and look like.

With four talented drawing artist on the team, we knew that the game will be hand painted for the most part and that we will use sprite sheets for all the animations. You would expect this to lead to a 2D rendering system. After all, the math in all previous articles was 2D and Vector2D's were all over place. But at the same time we wanted to have some depth to our top down perspective and considered using parallax effect to achieve that. Using parallax would have some drawbacks and might be difficult to tweak or draw art for. Instead we opted against it, so the rendering system is actually a 3D one. There is a 3D projective camera and 3D triangles are being send to the GPU so the depth is inherent.

The goal was to have a system that can render static images in layers that would make up the level, some animated sprites for the object in the game and lots of bubbles. All this without killing performance, of course. Almost everything is drawn alpha blended, but some things like the GUI overlay and seaweed would require special treatment. Additionally we also wanted to be able to scale and tint all the sprites.

In the core of our graphics system is the RenderJob which the only thing that our render manager can render. From its fields it's very clear how we implemented the needed functionality.

public enum RenderPass { AlphaTested,
                         AlphaBlended,
                         Overlay }

// All the data need for rendering a object on screen
// A class rather than a struct to enable reference storing
public class RenderJob : IComparable<RenderJob>
{
  // In which pass should the geometry be rendered
  public RenderPass RenderPass;

  // Used for depth sorting in alpha-blended jobs
  public float Height;

  // The vertices in world or model coordinates
  public VertexPositionTexture[] Vertices;

  // Indices of the vertices
  public int[] Indices;

  // If vertices are in model coordinates a suitable transform
  // matrix should be submited, if vertices are in world
  // coordinates the identity matrix should do fine
  public Matrix WorldMatrix;

  // A texture to draw this geometry with
  public Texture2D Texture;

  // Allows the texture to be tinted with a solid color
  public Vector4 Tint;

  // Allows a render job to disable the caustics
  public bool DisableCaustics;

  // Create new render job
  public RenderJob()
  {
    Tint = new Vector4(1, 1, 1, 1);
  }

  // Compares two render jobs
  public int CompareTo(RenderJob other)
  {
     if (Height > other.Height)
       return 1;
     if (Height < other.Height)
       return -1;
     return 0;   // ==
    }
}

The rendering in our game is handled by the rendering manager and all entities that would like to be rendered need to implement the IRenderable inteface.

public interface IRenderable
{
  IEnumerable<RenderJob> GetJobs();
}

The manager simply goes over all the entities and fills up three lists, one for each render pass. The list with Alpha blended jobs gets sorted by height, from the lowest to the highest. Then the lists are rendered in the order they were declared in the enum aboove.

Each level can have up to five layers and they are rendered as any other alpha blended job. The height, and hence the parallaxing amount, can be set for each layer. The size is automatically determinate to fit the level size with some clearing for the parallaxing. The level layers can be drawn as layers in Photoshop. In the game, their alignment at the the middle of the screen would be the same as while drawing. This means that parallaxing does not interfere with gameplay.The game take place underwater. I really wanted for us to get that feeling early on by adding water caustics and started looking for real-time solutions on the subject. In the end none of the options looked convincing enough and many were too computationally expensive. We quickly opted for a precalculated sequence of images that tile in both, space and time. The image is applied in the shader and the strength of the effect can be tweaked per level. The shader also scales the effect with depth, adding another subtle depth cue.

This wraps up the articles series. I hope people will find them useful. If anyone needs more info, you can drop a comment below the article.

A new version of the engine is already in the making. It's based on a somewhat different concept, written in C++ and trying to be as platform independent as possible.

Building Your Own Game Engine - Collisions

2011-09-27T17:27:00.002+02:00

This article discusses collision detection and resolution. It directly follows my previous article on physics. I have decided for two separate articles so that the text doesn't run longer than your (and mine as well) attention span.

Most physics engines combine collision detection system with the rest of the engine, but many also allow the one to used without the other. In the case of The Jelly Reef, both of the systems are simple and completely separated except for the objects they act upon. Basically, first all the forces are applied and paths integrated. Then using the new positions collisions are found and resolved.

To do collision detection we first need to have bodies that collide. Early on, we decided that for all objects in the game the collision shape will be approximated with either a disk or a rectangle. Moreover, every objects stores both and the two are always in sync. The disk is also circumcircle of the rectangle at all time. Having a disk around the rectangle allows for early outs when doing collision checking, as disk to disk is a very cheap test to do.

public class BaseGameEntity : ISceneNode
{
  // Some code...

  [Description("Bounding radius of the entity. Used for collision detection")]
  public float BoundingRadius
  {
    get { return boundingRadius; }
    set
    {
       float s = value / boundingRadius;   // scale
       boundingRadius = value;
       scale *= s;
     }
  }
  protected float boundingRadius;

  [Description("Half dimensions in a single vector.")]
  public Vector2D Dimensions
  {
      get { return scale; }
      set
      {
          scale = value;
          // Set the bounding radius so that a recatangle with the given
          // dimensions will fit in the disk.
          boundingRadius = (float)Math.Sqrt(value.X * value.X + value.Y * value.Y);
       }
  }
  protected Vector2D scale;   

  // some more code...
}

The game also features some static geometry in the form of walls and these were created from linear segments.

The collision system every frame over the objects and tests for collision among them and collisions against the walls. Each collision is stored in a array of Contact structures. The structure holds all the data that is needed to handle this contact.

public struct Contact
{
  // Holds the first bodie in the contact
  public BaseGameEntity FirstBody;
  
  // The second of these can be null, for contacts with the level
  public BaseGameEntity SecondBody;

  // Holds the direction of the contact in world coordinates.
  public Vector2D ContactNormal;

  // Holds the depth of penetration at the contact.
  public float Penetration;

  // A mechanism to detect collisions to raise event but 
  // not reslove in the physics engine
  public bool Resolved;        

  // A hash code uniquely defining the contact of these two entities
  // Makes sure that each pair of entities is checked exactly once
  public override int GetHashCode()
  {
     int hash = firstBody.GetHashCode();
     if (secondBody != null)
        hash ^= secondBody.GetHashCode();
     return hash;
  }
}

For performance reasons we set a predetermined number of contacts that we can have in a single frame, all others will have to wait for the next frame. We also store all the contacts in a preallocated array so that we avoid allocating new objects every frame and strain the garbage collector.

As I mentioned we have two shapes for collision geometry. With the linear segments for the walls this gives us 3 object types that can collide. Walls will not collide with walls, that leaves us with five combinations of shapes we need to handle. For all cases we use the separating axes theorem.
The theorem states that if the two convex objects are not interpenetrating there is an axis for which the projections of the two object will not overlap. This test is very robust and general, straight forward to implement and easy to debug. It also gives much of the needed information we need for resolution. The contact normal is the axis itself and the interpenetration is the amount of overlap along it.

The problem is of course to find this axis. For polygons such axises run through the vertices or are perpendicular the the line segments. For an intersection test among two rectangles that would yield 16 potential separating axises to be tested. We tackled the problem of optimizing the number of axises for each of the cases separately.

As a en example I will explain a very straight forward test from the game on the drawing below, an axis aligned rectangle against a linear segment.

From the drawing we see that one testing axis is aligned with the line segment and the other one is perpendicular to it. The rectangle and its projections are drawn in blue while the line segment and its projections in red. On the drawing we can see that the projection on the axis perpendicular to the line segment there is no overlap, so we have found the separating axis. The drawing also clearly shows that I have a cool whiteboard, but enough of that, lets show the code for this test.

public static bool AARectToWall(
   Vector2D centerR, Vector2D halfDimR,
   Vector2D start,       Vector2D end)
{
  // Create first axis 
  Vector2D axis1 = (end - start);
  // Normalization gives interpretation to the intervals 
  axis1.Normalize();

  // Project the line segment by projection the end points
  float Sp = axis1.Dot(start);
  float Ep = axis1.Dot(end);
  // Make the interval 
  CreateInterval(ref Sp, ref Ep);

  // Project rectangle - All four vertices
  float rectLeft;
  float rectRight;
  // First  calculate the vertices
  Vector2D A = centerR + halfDimR;
  Vector2D C = centerR - halfDimR;
  Vector2D B = new Vector2D(A.X, C.Y);
  Vector2D D = new Vector2D(C.X, A.Y);

  float Ap = axis1.Dot(A);      // Project vertex A
  float Bp = axis1.Dot(B);      // Project vertex B
  float Cp = axis1.Dot(C);      // Project vertex C
  float Dp = axis1.Dot(D);      // Project vertex D

  // Cretate inital interval
  rectLeft = Bp;
  rectRight = Ap;
  CreateInterval(ref rectLeft, ref rectRight);
  // Extend it
  AddInterval(ref rectLeft, ref rectRight, Cp);
  AddInterval(ref rectLeft, ref rectRight, Dp);

  // If there is no overlap, we have found the separating axis
 if (IntervalOverlap(Sp, Ep, rectLeft, rectRight)  <= 0.0f)
    return false;

  // Second axis, perpendicular to the segment
  Vector2D axis2 = axis1.Perp;

  // The line segment projects to a single point
  Sp = axis2.Dot(start);

  // Project the vertices
  Ap = axis2.Dot(A);
  Bp = axis2.Dot(B);
  Cp = axis2.Dot(C);
  Dp = axis2.Dot(D);

  // Create the rect interval
  rectLeft = Bp;
  rectRight = Ap;
  CreateInterval(ref rectLeft, ref rectRight);
  AddInterval(ref rectLeft, ref rectRight, Cp);
  AddInterval(ref rectLeft, ref rectRight, Dp);

  // Check if the second axis e separating  
  if (IntervalOverlap(Sp, Sp, rectLeft, rectRight) <= 0.0f)  
    return false;
  else
     return true;   // No axis found, shapes are intersecting
}

The next step after detection of collisions is to call all the subscribers for each type of collision. This is where gameplay code might be implemented I it was discussed in detail in the article on gameplay. The event can choose to set the resolved flag to true, so the collision manager will not resolve the collision. This can have many uses. When a jelly hits a rapidly rotating propeller for example, the jelly will not bounce back but rather be removed from the scene and replaced with some gooey jelly pieces.
The last step is to resolve the unresolved contacts. This is done by simply moving them along the contact normal. In the case of a collision with the level geometry, the object is simply moved the full penetration depth. In the case of two objects, both are moved by taking their mass into account. The flowing piece of code, adapted from from Game Physics Engine Development, does exactly that.

// Some code ...
BaseGameEntity first = contact.FirstBody;
BaseGameEntity second = contact.SecondBody;
                
// The movement of each object is based on inverse mass, so total that
float totalInverseMass = first.InverseMass + second.InverseMass;
                
// If both have infinite mass, skip this contact
if (totalInverseMass <= 0) return;
                
// Calculate amount of penetration resoluion per total inverse mass
Vector2D movePerInverseMass = contact.ContactNormal *
  (-contact.Penetration / totalInverseMass);
                
// Move 'em
first.Position   += movePerInverseMass * first.InverseMass;
second.Position -= movePerInverseMass * second.InverseMass;
// More code...

Hope this last few articles gave an inside into the bits and pieces of game development that are the not easiest to find information on. The next article is on graphics and will be the last one in the series as well.

Building Your Own Game Engine - Physics

2011-09-01T16:28:00.001+02:00

This is the first one of next two articles that will cover two very close subjects, physics and collision detection. Physics for games for the most part covers moving some bodies in the game world according to the laws of physics. As these bodies occupy some space in the world, we need to detect when collisions among this bodies occur and resolve them. I will assume the reader is familiar with Newton's laws of motion, since you are reading an article about making a game engine and physics in particular.

The Jelly Reef actually uses two somewhat separate physics systems. One used to move objects in the game around and it's completely entangled with the rest of the game. And there is another one, based on particles, used for some specific effects. Our game is not trying to simulate the real word or be realistic, so I decided we take simplistic approach, with plenty of shortcuts. First shortcut was to model the jellies and all other moving objects as point mass and this ignore any actual distribution of mass. Angular movement was not simulated at all, so no torques, no moments of inertia or in fact any physical angular property. This means we treat all objects as particles we can basically reuse the code from the particle. What follows are the properties of the particle class.

public class Particle
{
  // The position of the particle in world space
  public Vector2D Position;

  // Linear velocity of the particle in world space.
  public Vector2D Velocity;

  // Linear acceleration of the particle
  public Vector2D Accleration;

  // Damping is required to remove energy added
  // through numerical instability in the integrator.
  // Or to act as drag
  public float Damping;

  // Holds the inverse of the mass of the particle.
  // It is more useful to have objects with
  // infinite mass (immovable) than zero mass
  // Also one division less
  public float InverseMass;
  //
  public float Mass
  {
    get { return 1.0f / InverseMass; }
    set { InverseMass = 1.0f / value; }
  }
  //
  public bool HasFiniteMass
  {
    get { return InverseMass != 0.0f; }
  }

  // Force accumulator, for dalamber's principle
  public Vector2D ForceAccum;
}

Next we need to move these objects. Newtons laws are expressed as differential equations so the values are calculated using numerical integration. For this purpose we use Euler integration as it's very easy to implement, but it is not very precise.

public void Integrate(float dt)
{
  float duration = dt;

  // Update linear position
  Position += Velocity * duration;

  // Work out the acceleration from the force
  Vector2D resultingAcc = Accleration;
  resultingAcc += ForceAccum * InverseMass;

  // Update linear velocity from the acceleration
  Velocity += resultingAcc * duration;

  // Add drag
  Velocity *= (float)Math.Pow(Damping, duration);

  ForceAccum.Clear();
}

Time is continuous (except maybe in quantum mechanics, which beyond the scope of this article and my brain) and our simulation takes discreet steps into it, so errors get accumulated over time. This imprecision can build up and eventually make the simulation explode and I will return to this later.

Although we are not simulating the angular movement, we still need to know the orientation of the objects for both, gameplay and rendering purposes. The solution was to simply align the object to face their direction of movement. However this looks ugly when the direction of movement changes rapidly over few consecutive frames, so the orientation was in fact interpolated from the current one the desired one limiting the change with maximal angular velocity value. This piece of code was not really elegant of flexible and in future I would consider using spinors for this purpose.

As I mentioned before we also employed a separate particle based physics system. This simple system simulated particles on which some forces can be applied. No contacts or hard constrains were imposed on the particles. The most used part of the system were the spring-damper systems.

The seaweed was implemented with such a system. Each weed modeled as a two particles connected to each other with such a spring, while simultaneously having one of them being attached to the seabed with another spring. A third spring from the base to the tip tries to keep the form of the weed. On the image to the left we see the three springs in red using the debug drawing.
The water motion also imposed forces on all particles in it. The smooth movement of the camera was also implemented using a spring.

Particles were used for the bubbles. Obviously the main aim of this dynamic system was to give feedback to the player while he/she plays by controlling the water.

In an early version of the game the jellies had tentacles, which were modeled with a spring system, exactly like the one on the seaweed. Unlike the seaweed, the jellies move and this adds force to the spring system and tentacles become longer. I tried to remedy this by making the springs stiffer and that is where the Euler integration totally failed. As soon as the spring overextends, a force too large will be applied. In the next iteration the spring will overshoot again and in turn generate and even larger force, until the simulation explodes with the tentacles way outside the screen. This could have been solved by using better integrator like RK4 or Verlet Integration. It turned that the jellies look way better without the tentacles anyhow so I was of the hook.

Building Your Own Game Engine - Why Code Physics

2011-08-28T17:22:00.000+02:00

The next two articles will cover two very close subjects, physics and collision detection. I will do so by going through the relevant pieces of The Jelly Reef's engine. But before I jump into that, I will first put a word or two on why (or why not) to develop your own physics system.

Writing physics for your game is difficult and time consuming task. Collision detection is a subject that alone might consume months of work. There are some superb solutions out there, like Box2D, that work right out of the...well box. Free and open source, this engine drives immensely big chunk of the indie hits in the last few years. Angry Birds is not all that different from the samples that come with the engine.

But sometimes you just need to jump over the hoops yourself, and we did. The decision to code our own physics came was based on few facts we knew at the time:

Water, being the main element of gameplay is not part of any existing engine.
A full physics engine would be an overkill for this game and potentially difficult to control and tweak.
The gameplay would be tightly integrated with the physics and the collisions.
Most of the popular and well documented engines are writen in C++ and our game is in C#.
A lot of time still needs to go into integrating the engine into the game.
There is in fact quite a bit of text on how to do things yourself. I recommend Game Physics Engine Development, Game Physics and Real-Time Collision Detection.
I have had some bad experience with closed source engines and the next paragraph goes over it.

I was working at ZootFly on a vehicle system for quite a bit. The ZEN game engine used in ZootFly employed NVidia Physx, so naturally I built on top of that. I was in awe by how simple it was to get some things running with Physx. In the next few months the more I worked with Physx the more I got to know it, and my respect for its developers grew even further. And then I had to do some stuff that the engine was clearly not made for (obvious when you look at the samples) and suddenly I was in a world of pain. Tweaking parameters didn't get me anywhere fast and as we had binary-only license there was not much else I could do. Eventually the problems were worked around, but the team made a decision to switch to Bullet for their next project. It's open source and Erwin Coumans seems to be doing an awesome job of running it.

So ultimately it's up to developers the make the decision when they know what they are making. For those that decide to go for coding their own physics and haven't done that before the next two articles should provide some insight.

Building Your Own Game Engine - Gameplay

2011-05-05T11:46:00.000+02:00

This article will focus on gameplay, the part of the code that allows making the game fun. In a smaller game, like ours, the gameplay code can take substantial chunk of the whole code-base. The gameplay in The Jelly Reef was not scripted and completely integrated with the rest of the code; and as such written in C#. The separation between what can be considered engine code and gameplay code was mostly logical but still some physical structure was kept.

There are generally four places where gameplay code goes in our engine. Of course, our primary gameplay element is the water itself as the player interacts with it. The implementation of the water waited for the concept of the game to be completely defined, so after we know what our game will be about we started building the water dynamics. Our first try was with simulated fluid dynamics, but after playing with few games and simulators that use fluid dynamics we realized that it might not be the best fit for The Jelly Reef. Fluid dynamics are somewhat difficult to program and even more difficult to make them run efficiently on a larger scale. But the real problem was that they were not a good fit for gameplay and can be notoriously time consuming to tweak. My solution was to fake it and I am talking Shanghai Rolex kind of fake. The water in The Jelly Reef is a grid of 2D vectors representing velocities, what we (not physically correctly) called flow field. The grid is treated as a gray-scale image and every update is filtered using a set of low-pass filters. The resulting image summed with the current image using a tweakable weight factor. The low-pass filtering is done by convolution with a 3 by 3 kernel, which is chosen based on the direction of the water at that cell of the grid. There are 4 kernels in total; horizontal, vertical and two diagonal ones. Basically the value of atan2 is mapped directly into an index in the kernel array. What follows is a piece of code that does exactly that and in some way is the heart of our game.

// FlowField.cs
public class FlowField : ISceneNode
{
  #region Weights

  static float lon = 3;
  static float lat = 0.5f;

  private static float[,] verticalKernel =
    new float[,]{ {lat, lat, lat},
                  {lon, lon, lon},
                  {lat, lat, lat}};
        
  private static float[,] horizontalKernel =
    new float[,]{ {lat, lon, lat},
                  {lat, lon, lat},
                  {lat, lon, lat}};

  private static float[,] diagonalKernel0 =
    new float[,]{ {lat, lat, lon},
                  {lat, lon, lat},
                  {lon, lat, lat}};

  private static float[,] diagonalKernel1 =
    new float[,]{ {lon, lat, lat},
                  {lat, lon, lat},
                  {lat, lat, lon}};

  private static float[][,] kernels = new float[][,]         
  {
    horizontalKernel,
    diagonalKernel1,
    verticalKernel,
    diagonalKernel0,
    //
    horizontalKernel,
    diagonalKernel1,
    verticalKernel,
    diagonalKernel0
  };

  #endregion

  public void Update(float dt)
  {
    // Some update code...

    // Go through all the cells
    for (int i = iFrom; i < iTo; i++)
    {
      for (int j = jFrom; j < jTo; j++)
      {
        // Get vector angle
        float theta = (float)Math.Atan2(vectorField[i, j].Y, vectorField[i, j].X);
        //
        theta += MathHelper.Pi / 8; // Add half a section
        // get index
        int kindex = (int)Math.Floor(theta * (8.0f / MathHelper.TwoPi));
        kindex %= 8;                // Remove extra sections
        //
        float[,] kernel = kernels[kindex];

        // Convolve using this kernel!
      }
    }
  }
}

All the kernels are energy-preserving, so a dampening factor is used to stabilize the velocity field. All hand movements add energy to the system so without dampening the simulation would in fact exploded. This system made interacting with the water intuitive while giving us the ability to easily tweak its behavior. The video below shows a visualization of the velocity field, something that we stared a lot when designing the first levels. The video below shows the debug view of the our flow field.

Most of the levels in our game had regions that were not part of the simulated water field, usually rocks and other such big obstacles. The water should not flow through these obstacles so those regions should be excluded from the flow field. For this purpose, when loading the level we employ a flood fill algorithm, that expands until it hits a wall, that marks all the cells that are part of the flow field. By skipping calculations on those cells we also optimized the flow field significantly. The flow field’s value can be read using nearest neighbor or bilinear sampling, depending on the quality and performance needs. Bubbles for example use nearest neighbor as there are many of them and the physical simulation takes care of the trajectory smoothing. For the jellies on the other side we used bilinear sampling as motion quality and responsiveness was paramount.

Next place where gameplay can be added is the update method of the GameWorld class. The GameWorld has been designed to be extended and new functionality can be added by the inheriting class. The update method is the place where game wide game-play code should be, like checking winning and losing conditions or similar stuff. The inherited class would automatically keep all the functionality of the GameWorld class, like the streaming and real time editing but it needs to do XmlInclude for all the entity types in the class attributes.Much of the gameplay code is in the Update method of the different entities and most entities are in fact built for specifically for that purpose. Enemies, propellers and pipes are all examples of such entities. If the entity is dynamic it can inherit the MovingEntity class and get all the functionality for physically simulated motion.Finally the game implements a mechanism to respond to collision events. The user could subscribe collisions of different pairs of entity types. For example a collision of a jelly with a cannon ball would result in instant death and the event can be used to play a sound, death animation and so on. What follows is are parts of the code doing exactly that.

// JellyWorld.cs

// Include all types that might be used in the game
[XmlInclude(typeof(Jelly))]
// More includes ...
public class JellyWorld : GameWorld
{
   public void SetEvents()
   {
      // Add Jelly vs Propeller
      int hash = EntityTypes.HashCode(EntityType.Jelly, EntityType.Propeller);
      this.collisionManager.SubscribeForCollision(hash, JellyPropellerCollision);

      // Set more events ...
   }

   public void JellyPropellerCollision(ref Contact contact)
   {
      // Play gruesome death, scary sound and remove jelly
   }

   // More JellyWorld code ...
}

From the two entity types hash is created and is used to index the event method to be called. The hash is calculated by using the first 16 bits to store the first type and the second 16 bits for the second type. As long as there are less than 65536 entity types this works. The method gets a reference of the contact information which can be edited too. The above code for example sets the handled flag to true, so that the contact is ignored by the contact resolver in the physics pipeline. Consequently, physics and collision handling is exactly what the next article will be about. I'll end this post with a montage of our game.

The Jelly Reef from Adriaan de Jongh on Vimeo.

Building Your Own Game Engine - Tools II

2011-03-02T13:26:00.001+01:00

This is the second article on tools that we developed and used during the making of The Jelly Reef. It covers our profiler, the level editor and few external tools.

Profiler

Performance is essential for any game and knowing how big of a chunk out of the update time goes to different tasks can be very helpful. For this purpose, we built a profiler early on and always kept a watch over the performance. The profiler has few roles. Firstly, to have a bunch of variables that can be used as counters, like counting the number of collision checks, drawing calls, triangles and such. Secondly, to count framerate. And most importantly, to measure execution time of different sections of the code.The profiler is implemented as a singleton manager, as discussed in the previous post. All the counters are accessible via a public dictionary. The profiler itself only draws the counters as name and value pair. It is up to the user of the counter to take care of the value, like resetting the counter zero or incrementing it.
The game uses a fixed framerate of 60 FPS, but we still use a framerate counter to detect if drop in performance occurs and eliminate the cause.For measuring section execution time we use the Stopwatch, which is a high-resolution timer. At the beginning of update the stopwatch is reset. At the beginning of the section in the update, like collision detection or water simulation, a the BeginSection method is called with the name if the section. When done, the EndSection method is called with the same name of the section. The profiler simply samples the time of the stopwatch so section can be nested or overlap. The profiler draws a bar from the beginning of the section to the end, using the width of the screen as a reference for the 0.0166 seconds (60-th of a second) available CPU time per update. So if we reach the right side of the screen, we know we need to optimize something, and we might as well start with the longest bar. The difference between the end and the beginning of a section gives its duration and this is shown just below the bars with the same color as the corresponding bar. The profiler is only compiled when the PROFILE symbol is defined, so just like the debug draw it is not part of the final build. Unlike the debug drawing, it is also compiled with the release builds of the game to track their performance as the C# compiler can optimize the release version quite a bit.

Editor

What started as a runtime inspector for the entities in the gameworld, quickly turned into a editor that we used to create the levels. This means that we used an in-game editor to author and edit the levels, rather than a separate tool. In fact at any time you can press E button on the keyboard and bring up the editor. This means very short turnaround times for our designer, as changing a value like mass or a position of a wall has an immediate effect in game. On the other hand, the user needs to remember that the game is running at all times. Physics and collision can easily be broken by large changes while the game is running. That is why the editor got a pause button, but somehow it was almost never clicked. And the programers need to remember that the same code runs during designing and playing. The editor is not included in the release build and the Surface unit doesn’t need a keyboard in user mode, so tampering with the game is not a problem.
The editor is very much based on features available in C# the .NET Framework. The editor is basically a window with a tree control a property grid, both of which a regular windows forms. The tree control is depicting the world hierarchy and allows the user to select one or more entities in the world. For the window to be able to create this hierarchy all the object that we would like to display in the editor must implement the ISceneNode interface.

/// 
/// Alows browsing the scene graph in a simple way
/// 

public interface ISceneNode
{
   IEnumerable<ISceneNode> GetChildNodes();
}

// GameWorld.cs
public class GameWorld : ISceneNode
{
   // ...
   public virtual IEnumerable<ISceneNode> GetChildNodes()
   {
            foreach (BaseGameEntity o in Entities) { yield return o; }
            //
            foreach (Wall w in Walls) { yield return w; }            
            //
            foreach (ParallaxLayer l in  Layers) { yield return l; }            
#if DEBUG
            yield return DebugDraw.Instance;
#endif
   }
   // ...
}

Using the interface window can build the tree recursively. This is a simple approach also lets a put things in the tree that are not really part of the world, but we would like to be able to tweak them too, like the options for the debug drawing.
The property grid on the other hand required a bit more attention. The property grid in .NET is uses reflection to give the user an interface to tweak any public property of any object, but some care must be taken. Firstly non-primitive types like our vector implementation would need to implement a conversion to a type that can be displayed properly. This actually took few days to get right, so that is doesn’t delete data when some has typed something wrong. Without some kind of description the user interface would be very difficult to use as it might be hard for the designer to know what linear dampening might mean, there might be too many properties that are public and they are not sorted in any way. So the entities have to have attributes attached to all their public properties, as the code below shows.

class MovingEntity : BaseGameEntity // Which implements ISceneNode
{
   // ...

   #if WINDOWS
   [Category("Physical Parameters")]
   [Description("Max turn rate in deg/s")]
   #endif
   [XmlIgnore]
   public float MaxTurnRate
   {
      get { return maxTurnRate; }
      set { maxTurnRate = value; }
   }
   // Field
   protected float maxTurnRate;

   // ...
}

As it turns out these attributes, especially the description, also help keep code well documented for programmers too. We always knew if a rotation property is in angles or radians. The component model API is only available on Windows, so some preprocessor guards come in handy if you would like to compile the project for other platforms like Xbox and Windows Phone. Our classes already had the XML attributes, so the code for a single property can be a bit long, but maintenance and ease of implementation made all the scrolling totally worth.

A very important part of the editor also were the different design modes. With a press of a button on the keyboard the game would switch to wall editing mode or entity manipulation mode. We added those model in a somewhat ad hoc manner and were more or less hacked into the game. Eliminating turnaround time for the designer was a nice plus and it worked great for this game, but this approach doesn't scale well. In retrospective I think I might have been better to build an editor that still uses the engine with all of its classes and functionality but built a separate editor.

External Tools

Aside from the usual content creation applications like Photoshop and After Effect, we used few plugins for Photoshop some other tools. As we learned Photoshop doesn’t work with explicit alpha when saving in the PNG format, so we needed something that can roll back the time to Photoshop 4.0 when it was the last time it did work. Luckily there was a plugin for that. Another plugin, called Solodify, was used to fade the edges in the color channels so that no white pixels appear when alpha testing is used for rendering. The water caustics were precalculated using Caustics Generator, which available for free. I like to work with FX Composer for developing shaders regardless of the fact that is was a bit of overkill for the few shaders we needed. FX Composer is also available as a free download on nVidia’s developer website. As last line of defense when I need to debug my rendering code, I use PIX. This extremely powerful tool comes with the DirectX SDK and can capture every single call to the GPU, including its internal state and even show the intermediate rendering results.

Building Your Own Game Engine - Tools I

2011-02-20T13:24:00.002+01:00

This article will focus on the tools that were developed and used during the making of the game. It turn out to be a rather large article so it's split in two posts. Basically a tool is everything that helps get the game done, like a level editor or a profiler. We used some external tool aside from the content creation applications like, Photoshop and After Effects. I will cover those after covering our own tools.

Managers

Before jumping to the different tools, I will first give a short overview of the managers the we used in the engine. There are certain services, routines or data that might be needed at any time in the execution of the game. File reading, resource loading and camera properties are good examples of such services. To make them available at all times we use managers, which are just simple singleton objects. At first we used static methods to wrap the actual object calls, making the calls a bit shorter, but we later decided for a more simple implementation. What follows is a short piece of the code from the camera class.

// Camera.cs
public class Camera : ISceneNode
{
   private static Camera instance;

   // Gets the instance of the camera; there can be only one.
   public static Camera Instance
   {
      get { return instance; }
   }

   public Camera(float camSizeX, float camSizeY, GameWorld world)
   {
      // ctor code ...
   }
   
   public void Initialize()
   {   
      instance = this;
   }

   // some camera code...
}

There is only one instance of the singleton object that can be referenced. The parameters in the constructor give the dependencies order among the managers. This strategy was used for many of the tools that will be discussed next.

Debug Drawing

The very first tool that was implemented was the debug drawing. Textures might go missing, shaders might be buggy, triangles might get clipped, scaled, culled and not render at all. Developing a game in the dark can be extremely frustrating and inefficient, so this is where the debug drawing comes in to let us know exactly what is happening in the game. In a game engine usually drawing should only be done within a draw method and might need to set up many shading and rendering parameters. This is the exact opposite of what we need, so we made a debug draw that allows us to call drawing of colored lines from anywhere in the code. This can help visualize local variables like velocities, grids and such. Here is a short piece of code from the debug drawing manager.

// DebugDraw.cs
public class DebugDraw
{          
   protected static DebugDraw instance;

   // Needs a static instance to be able to answer static calls
   public static DebugDraw Instance
   { get { return instance; } }

   // lines
   public VertexPositionColor[] lines;
   public int linesCount;

   public DebugDraw(Game game)
   {
      graphicsDevice = game.GraphicsDevice;
      effect = new BasicEffect(game.GraphicsDevice, null);
      lines = new VertexPositionColor[80000];
      //
      linesCount = 0;
   }

   public void Initialize()
   {
      // Set static instance to this
      DebugDraw.instance = this;
   }

   public void DrawLine(Vector3 start, Vector3 end, Color color)
   {
      if (linesCount + 2 > lines.Length)
         return; // Silent error

      lines[linesCount++] = new VertexPositionColor(start, color);
      lines[linesCount++] = new VertexPositionColor(end, color);
   }

   public void Update(float dt)
   {               
      // Clear all out
      linesCount = 0;
   }

   public void Draw(float dt)
   {
      if (linesCount > 0)
         // call XNA line drawing ...
   }   
}

The approach is very simple; all the vertices are stored in a fixed array and the calls are accumulated into the array. During the render phase, lines are drawn with a single draw call, which is very efficient. Circles and such are simply composed out of multiple line segments. Similarity, methods for drawing points were added too. With this in place we could visualize collision geometry, contact points, forces and similar stuff.
The next posts will discuss the profiler, level editor and some external tools, followed by a post on the water simulation and game play. So if you are curious, you can click the follow button in the top left corner or subscribe to the feed with you favorite reader.

Building Your Own Game Engine - Basic Mechanisms

2011-02-08T13:43:00.003+01:00

There are some game engine mechanisms that are needed in almost any game, and this article will cover exactly that. As I stated in the last article, the work on this common set of features started before we even knew what game we were making. While I have worked on large chunks of a complex system, this was my first time as a lead programmer and building an engine from scratch. So I consulted my favourite books, adapted some ideas from there to fit our needs and was ready to start.

At the very low level we were free from having to develop a memory management system, as we used C# and could let the garbage collection take care of that. Sometimes however the garbage collection can cause hiccups, so special care need to taken. The garbage collection runs fastest when it doesn't run at all, so we had almost no dynamic memory allocation after a level has been loaded. On way we tried to enforce this was to have our low level stuff like math, physics, collisions, render jobs and such as value types. Declaring a structure (struct) instead of a class in C# is not enough, as the garbage collection is a bit more complicated and sophisticated than that, so we made sure that variables are statically scoped whenever possible. Additionally, we passed by reference all bigger structures to avoid copying memory around.

XNA is mostly a 3D rendering framework, so The 2D math that is part of the framework was in my opinion not a good match to what we needed for game. So, we implemented a 2D vector and a matrix class, as well as some helper methods for transformations. These can be lifted from any book in the field. Because we didn't do much rigid body physics or angular interpolation, there was no special class for rotations. In future I would prefer to use spinors (2D equivalent of quaternions) or complex numbers for the purpose.The game structure itself was kept very simple. Everything in the game was derived from GameEntity and all the entities were kept in the GameWorld. The game world had no hierarchy, just a list of level of entities. What follows is a piece of code from the GameWorld class and BaseGameEntity class that I will elaborate on.

// Gameworld.cs
public class GameWorld
{
   // some code ...

   // All the entities in the world
   public List<BaseGameEntity> Entities
   { get; set; }

   // Adds an entity to the world. This can be anything.
   public void AddEntity(BaseGameEntity entity)
   {
      AddQueue.Add(entity);
   }

   // Removes an entity from the world
   public void RemoveEntity(BaseGameEntity entity)
   {
      RemoveQueue.Add(entity);
   }

   public void Update(float dt)
   {
      // Add entities
      foreach (BaseGameEntity bge in AddQueue)
         Entities.Add(bge);
      AddQueue.Clear();
      
      // Update entities
      foreach (BaseGameEntity bge in Entities)
         if(bge != null)
            bge.Update(dt);

      // Remove entities
      foreach (BaseGameEntity bge in RemoveQueue)
      {
         // Call cleanup on the entity
            if (bge is IDisposable)
               (bge as IDisposable).Dispose();
            Entities.Remove(bge);
      }
   }
   // more code ...
}

// BaseGameEntity.cs
[Serializable()]
public class BaseGameEntity
{
   // Refence to the world
   protected GameWorld world;

   // Unique ID of the enitity.
   [XmlAttribute]
   public int ID
   {
      set {
         this.id = value;
         // Make sure their are unique
         if (id >= nextValidID)
            nextValidID = id + 1;
      }
      get { return id; }
   }
   //each entity has a unique ID
   private int id;

   // Every entity has a type associated with it (health, troll, ammo etc)
   public EntityType Type
   { get; set; }
   
   // Called when loaded
   public virtual void Initialize(GameWorld gameworld)
   {
      // init code ...
   }

   // some code ...
}

The flat structure and very simple sequential update are not very flexible, an interactive character on a moving platform might be difficult to implement for example, but was sufficient for our needs. Additionally this approach can be memory coherent, which is very good for cache, which is very important performance. The update method of each entity handles everything from physics and game-play to animation. I opted for simple floating point time in seconds as parameter instead of the XNA's GameTime structure as I it doesn't require every class to calculate time, which can bring inconsistencies, and it allows for easy time manipulation like bullet time or pause. So that there is no inconsistency during the execution of a single world update, entities could only be added and removed at the begging and end of it. Queues of such entities are kept for this reason.

From the piece of code from the BaseGameEntity class we can see few things.

Every entity has a reference to the game world and that is how it communicates with other entities and can be aware of its soundings.
A unique ID is kept to help identify the entities. This ID is persistent and stored in the level.
We have a game entity type for different things in the level, mostly used for game-play and collisions. This is different from the .NET object type, as there can be many different enemies but they are all of the same class.
We are using the .NET framework XML serializing support for writing and reading data, so our executable classes are also our data containers. This can be seen from the many annotations throughout the code.

This last bullet point was not all that straight forward to implement as it may seem. Firstly, the game scene has a general graph structure, while an XML file has a hierarchical structure and cannot represent the scene properly. Secondly, when reading an object from an XML file, the no arguments constructor is always called. These are remedied by calling an initialization method on all entities after streaming, that has a similar role to a constructor. For cross-reference unique entity IDs are stored in the XML and during the initialization references to the actual objects are obtained by querying the world.

When a level grows to contain couple of hundred entities, it's obvious that you would like to change properties in bulk, and that is where a settings file comes in. This is just another XML file which can be referenced by an entity. We decided settings to be strongly typed so settings for a jelly are different from settings for a blow fish even if the contents are the same. Settings are implemented as simple classes so they can be inherited when needed. So if a MovingEntity extends BaseGameEntity, MovinEntitySettings can extend BaseGameSettings, simplifying the maintenance. The settings are applied in the Initialize method and all entities have a GetSettings and SaveSettings methods. The classes extending the entity class must handle all the details of saving the settings, as it's the only class that knows the type of the settings class. This approach puts a bit of extra work for every type that needs to have settings, but it's flexible and can even allow for structured settings, like a blowfish settings having different sprite settings for all the animations.
These settings files might need to be read frequently during the game, as each created rocket or a bullet might need their settings for example. Reading from disk can do some bad hiccups and there is the added slowdown of parsing the file, allocating memory. For this purpose we cache the settings, which a usually very small data structures and more over, are shared among entities with the same settings. We simply use the file name as a key in a dictionary. The same caching is in fact used for all resources to avoid duplicate data in the game. Our resource manager handles this internally, so it's completely transparent for the rest of the code.
There is always room for improvement, so I'll mention few things. For a future project I might opt for a different streaming solution or make macros that do most of the tedious work for me, but the overall performance and flexibility during the development was quite good. We had a inconsistent way of using the entity types, which lead to some funky bugs. A more structured update method that can handle different priorities and different logical steps might also be beneficial.
The next article will be on tools and the world editor.

Building Your Own Game Engine - Introduction

2011-02-06T13:14:00.001+01:00

Fast forward from my last post, the game that I was making with students from the Utrecht School of Arts (HKU) for the Dutch Game Garden is done. At least within the project frame that was given by the school. We decided for "The Jelly Reef" as a name and you can read more at www.thejellyreef.com. The game has been showcased on few occasions and has received some very positive reactions. This is the first in a series of six articles on how the game was developed. The articles will cover some details of the game's engine structure and all the technical choices made along the way. The next articles will focus on Basic Structure, Tools, Game Play, Physics and Collision Detection, and Graphics. The articles should be informative to any small team trying to develop a game, as much of the patterns reappear again and again in very different types of games. First, a screen-shot can give you an idea about The Jelly Reef and there is a montage at the end of the article.

Before there was any game, there was the team and the clients request, so many of the initial decisions came from there. The team was 9 peoples strong; 3 programmers, 4 artist and 2 designers. Two of the programmers on the project, including myself were part time and the third one had a background in interaction design with little experience in programming. All the artist on the project had background in 2d art. For the vast majority of the project, design was handled by the lead designer, as the other designer was perfecting the art of slacking. We knew that we were working with the Microsoft Surface, so technical choice number one was the choice of language, C# and was done for us. Because of performance reasons mentioned in the previous post, we decided to go for XNA instead of Silverlight. With the background of our art guys we knew that we would be making a 2d game and the top down perspective of the device reinforced the decision. While we did have the option to use a game engine like Unity, we didn't think that it would be a good fit the projects needs, so we decided to build our own.
For the first three weeks the team was brainstorming on possible concepts. Time is always in short supply so the tech team was eager to start working on something, to avoid sleepless nights at the end of the project. We discarded some of the concepts and merged features from similar concepts. From the handful of distilled concepts, we took a common denominator and started working on that. This is exactly what the next article will discuss.

Developing for the Microsoft Surface

2010-11-07T19:06:00.011+01:00

My plan for the current semester was definitely to the try out some touch devices, which is why I bought an iPod touch. But little did I know that I would be developing for the Microsoft Surface. I am working with the Utrecht School of Arts (HKU) on a project for the Dutch Game Garden, and so far looks quite promising.
The Microsoft Surface has a huge area that can detect and track an almost infinite amount of fingers. Ok, not infinite, but more than it makes sense to have on it at any given time. Because it uses image processing and not touch, it has some more tricks up the sleeve. For example, tags recognition, markings that you can print or stick to any object and track it on the surface. As well as raw image processing if needed. The SDK is .NET based, so you get to access the .NET Framework and you can use both Silverlight and XNA.
On the other, the machine is hugely underpowered and the GPU is especially ridiculous, considering the $12000 or so price tag. Most of the demos and samples had a reaction lag unacceptable for most game scenarios, which did make me a bit worried. On this particular I get to be the engine architect, so I decided to start from zero and build an engine based on XNA. As it turns out, the lag in the samples actually came fro the way Silverlight processes events, so the XNA games runes smoothly on 60 fps. Leveraging on the power of C# (using reflections, serializing and a some generics abuse) in under two month we have developed and a system that has an in-game world editor, flexible gameplay elements, collision detection with a bit of physics and even our own profiler. In the last phase we will of course inevitable see the ugly side of C# when we'll need to optimize the whole thing to keep running on 60 fps.
The device also brought to attention some interesting design challenges, like which point of view to take so that from no angle the game looks upside down. And that thing should be addressed next week, hopefully just in time for me to report on it. In meantime you can check this video of some of the earlier prototypes.

GDC Europe Retrospective

2010-10-10T22:11:00.006+02:00

It took me some time to write few words for the GDC Europe and not because there wasn't much said on the conference. On the contrary there was so much material, that I needed some time to digest it and put in into the right perspective.
Me being in general on the technical side, I tried to catch as many of the technical lectures as possible and some were very insightful. I'll pick three of them that stuck to my mind and give a short overview.
Eric Chahi from Ubisoft gave a lecture on High-Performance Simulation, by going through the details of their Project Dust. Now named "From Dust", it is a god game where you have the ability to control a dynamic world shaped by the elements. The game achieves interactive simulation of earth, water and wind in the world, by subdividing it into a grid. Each grid cell is simulated separately, using the neighboring cells as inputs. This idea is often used weather prediction models, but what makes the current implementation is the extreme performance optimization done, so that it can run smoothly on consoles. All the data and code per cell are structured so that they fit in 256KB, so all calculations can be done on a Playstation's SPU's or in the case of the Xbox 360 without a single cache miss.
Michael Drobot from Reality Pump Studios gave a lecture on Advanced Material Rendering, which was mainly a collection of dirty tricks on Deferred Shading. Many of them used the long forgotten technique of dithering. Memorable lecture was also given by Mathew Rubin form Black Rock Studio, the focus of which was the “in studio” pipeline, which allows designers to construct and test their levels in shortest time possible. The topic of most of the lectures was quite narrow, but most importantly it gave a glimpse on how deep are developers prepared to dive to create next generation of games and supply their designers and artists with the best possible tools.
The lectures by Crytek and Autodesk were slightly disappointing in comparison and were used more as a showcase for their products than technology lectures. If I would have been a game producer making a choice which technology to license, the lectures would have been more helpful; but I am not.
The real jewel of the conference however is the mix of disciplines that it includes, so I later shifted my focus towards the fields less known to me, like game design, production and even marketing. The ideas presented were extremely helpful often timeless, as good design doesn’t go bad. Which is more than can be said for rendering techniques. Warren Spector’s keynote on the relation of games to other media has been a guideline for most of my recent game design decisions. The lecture by Louis Castle on how to survive the industry was least to say an inspirational one.
In conclusion, I was a great experience to be part of the game-making world. I would love to be there again, and next year with a project to showcase.

Going all Apple

2010-09-20T00:21:00.005+02:00

After quite some years sitting comfortably in the PC camp, last month I decided to go Apple all the way. And by PC user I mean Microsoft Certified Trainer, DirectX and .NET developer and an avid gamer. Now what makes a man turn Mac and fork money for computer that is being sold in the lobby of a fashion store here in Utrecht?

It’s the only way to develop for the iPhone/iPod touch.
It’s shinny.
And finally it’s the only way to develop for the iPhone/iPod touch.

Obviously strong reasons…so I bought an iMac and got an iPod touch for (almost) free. After few weeks of using it all I can say is, I love it! Snow Leopard runs extremely smooth and so does Window 7. The bright LED screen blows my 22” Samsung LCD out of the water. It runs whisper quiet even when under heavy load. The sound signal doesn’t have interference noise from the hard drive or any other hardware component, unlike my previous not-so-cheap HP. The ergonomics are great (except for the silly location for the stereo jack!) and the drivers for my Wacom Ituos4 tablet seem to be more stable, allowing me to use hardware rendering in Photoshop. Time Machine is the best backup solution I have used, easy to set up while still giving you all needed options. Compatibility is no issue as it runs Microsoft Office (in fact did from the 80’s) and easily shares any media with my Xbox 360.

However few things are less then perfect. Graphics performance is below my expectations. Both Maya and Portal ran slower then under Windows and on top of that Portal shows screen tearing and flickering. Using vertical sync didn’t alleviate the problem either. I am not sure if it is the GPU drivers, the OpenGL implementation or the game itself, but needed my Windows 7 installation anyhow. How else I am going to run Visual Studio, my all time favorite Microsoft product (after the Xbox steering wheel :) )

[Non-geeks can skip this paragraph]

And this takes me to developing on the Mac, which why I have it in the first place. Xcode in my opinion is not as slick as Visual Studio. It is not always easy to find the window that you need without using Exposé. Alt-Tab is less then useful as all windows of the same application are bundled together, so after getting to your application you need Cmd + ~ to cycle through the windows. On the other hand the excellent code editor stays out of your way and the simple code completion is better than IntelliSense for C/C++, which is not too hard to beat. The language of choice (or lack of one) for developing applications for the Mac and iOS (iPhone/ iPod/iPad) and hence Xcode, is Objective-C. Objective-C has syntax that can make C++ look elegant and C# a wet dream. The language does have some great features like categories, allowing for extending the functionality of an existing class without creating a new one but the memory model is somewhat scary for game developers. It has all the performance nausea of a garbage collection with none of its benefits.

Is it all worth to have your game on the small screen and potentially thousands of people enjoying it? Hell yeah! So be on the lookout for some handcrafted pixels hitting the App store.

Gamescom 2010

2010-08-26T21:51:00.026+02:00

Thanks to the fine people of Task Force Innovatie Utrecht I got to see this year’s gamescom and GDC Europe. And what I got was more information on games than one can handle, so I’ll try to put what stuck to my mind most into few paragraphs, combined with some photos.

I’ll start with the organization of the gamescom fair, which was excellent. The daily ticket also included a train ticket for the same day, combined with the city’s train system, made getting to the fair a breeze. Quarter of million people flooded the Cologne exhibition center, yet I never felt that it was too crowded. However, I did have to wait in line for quite a bit in front the booths of most games, except the teen rated ones.

The first thing I noticed; German players seem to be big on the MMO games and games featuring dragons and monsters in general, so naturally plethora of those were being showcased. My personal favorite was Torchlight II. It has the same unique visual style of the first game, while removing many of the annoyances of its predecessor. Moving on to the next hall...

Two trends that were predominant on the fair and can give a glimpse of what is in store for the next year or so, were motion controllers and 3D. Nintendo has been ruling the sales with the Wii, largely due to its motion controller, the Wiimote. This holiday season, both Kinect for the Xbox 360 and Move for the PlayStation are coming out. The two new devices and completely different and both have their pros and cons.

The PlayStation Move is a more traditional controller and somewhat similar to the Wii remote. The main controller has the usual PlayStation buttons including a trigger. It tracks motion and rotation over all axes independently and it feels quite accurate but in some games there is an annoying lag between the input move and the reaction on screen. Most of the games shown that were using the new controller were casual games made especially to take advantage of motion input. My personal favorite was on on-rail shooter that actually had similar gameplay to Duck Hunt for the Nintendo Entertainment System (NES) from 1984. On the other hand, the serious games using the PlayStation Move, like Killzone 3 and SOCOM 4, worked perfectly fine without it.

The Xbox 360’s Kinect takes a whole different approach by removing the controller all the way. The Kinect allows the Xbox 360 to do a full motion capture of two players in real-time, using a whole array of sensors including an infrared projector. We have all seen that after some time with the Wiimote everyone learns how to fake a move and do it with least amout of effort . Kinect on the other hand tracks the movement of the whole body in space, so you really have to jump around to make things happen in the game. I had lots of fun playing Kinect Adventures!, Kinect Sports and even Dance Central; and if you have seen me dance you would know I not exacltythe dancing type. All of the Kinect demos were done in a protected bubble, so my main concern is the ability if the sensor to handle distractions and noise. There could be people moving in the background, dog running if front of you legs or simply having a table in the living room.

3D was a big topic on the GDC and lots of games were shown in 3D later at the gamescom; even Halo Reach was playable in 3D. Crysis looked great in 3D and the effect had been carefully balanced to add to gameplay rather than just serving as an eye-candy. Sony bring full support for 3D TV screens to the PlayStation over the HDMI 1.4 standard. But even with Nvidia’s crystal clear 3D Vision my eyes get tired and headache might follow. So I'll just say that I can’t wait to see Wipeout HD in 3D. I bet this time around they can bring up seizures even to people without epilepsy.

Regardless of the upcoming technical novelties coming in the next year, I am personally most exited about upcoming games that focus on fun gameplay, like Portal 2, Little Big Planet 2 and hopefully and plethora of good Indie games like Limbo and Burn Zombie Burn!

Going HD and Twitter-y

2010-05-09T13:39:00.014+02:00

I'll try not make it sound like a commercial for Utrecht University, but the projects in the last period were just pure awesome. So awesome, only to be fully captured in HD. The notebook had to be suspended in midair to get some fresh air respiration as it embarked on a three day pixel crunching journey to create the following 30 seconds of animation. Enjoy a bit of programmer's artwork.

On top of this, I have decided to go all Twitter happy to spread some pixel furiosity a bit faster. Follow me on http://twitter.com/furiouspixels

Fiat Turbina - The Making of

2010-03-18T10:26:00.027+01:00

It seems that I have one more post on ray-tracing, but now for something a bit different, a 1954 Fiat Turbina. I have chosen this model because of few reasons. It is sufficiently complex and there can be many approaches on how to model it. Equally important, it was the most aerodynamic shape of a car for 30 years, powered by a gas turbine yet technologically and commercially a complete failure, making it somewhat romantic.

What follows is not really a tutorial, but more a "making of". I'm not a 3D artist nor an expert on Maya, but I will try to answer any questions. I will start with the making of the wheels that will be used later. For this purpose I had set up an image projection for the side view and added tubes showing the rough dimensions of the tire and rim.

Then I drew a profile curve, revolved it into a tire and set up a cylindrical UV texture coordinate, needed for bump mapping.

Next I used revolve to create the rim, the axel of the rim and then a cylinder for the rim spike.

I cloned 32 spikes using Duplicate Special to create the complete rim.

I added "Gametechnology" text as a tire brand and bended it.

With the wheel done, I moved to the handle for opening the bonnet. As the handle is small and does not need to be modeled in much detail, I used polygon operations on a box to get the basic shape and then applied smooth to it. I started with a box and then pulled the vertices the get the silhouette

I then extruded the top faces and re-sized them.

And finally, I extruded the actual handle part of it.

With the small details done, it's time to move on to the body of the car. There are royalty free schematics on the internet for most cars, even exotic ones like the 1954 Fiat Turbine. I used three projections, one for each view.

In hope to work with NURBS, I drew the cross sections of the car.

After few tries with NURBS, I decided to leave that to the industrial designers around the world and other skilled professionals and move on to SubD surfaces. I used Loft to join the cross sections and get a polygonal mesh, which provided a better starting point then a simple box.

The next few steps show the process of refining the mesh into the car shape using just few operations like extrude, remove, append, split and merge vertex.

I also cut off the faces where the windscreen and windows will be. The original faces were curved along both axes which is usually not the case for glass, especially not in the 50's. This is very important for realistic reflections and refractions, so I decided to model them later instead of using the faces already there.

Conversion of the model into SubD showed that the topology of the model needs to be changed in order to get a smooth surface fitting the car. All the faces with more than four vertices needed to be modified and while keeping as regular structure as possible. Triangles and vertices shared by more than 4 edges were not my friend as they can break the surface too.

Next I created the windows from the refined mesh.

Early in the making of the model I decided to use bump map for some of the small details in the body instead of the modeling them. Having the low polygon mesh, I thought it would be the best time to create the UV coordinates. I used manual selection of faces and planar projection on them the get the basic layout and then manually stitch them in the UV editor.

Conversion to SubD proved to be quite destructive for the UVs as lines are mapped onto curved lattices and the tessellation is adaptive.

I used a Subdiv proxy instead, which was easier to control because of the regular tessellation. Next few screen shots show creasing on some of the edges and vertices.

With the final structure of the fully defined I moved to creating the frames for the windscreens using extrusion and later the windscreens themselves. We can also see some of the early renders.

Next I added some chrome details using lofted curves on the mesh and then extruding the polygons on them. I also added some interior, which simply serves to prevent the car from looking as an empty shell.

The geometry is finally finished, as we can see from the render below.

Next I added bump mapping and did refinements on the color texture mapping. To do this, I had to unwrap the UVs, as bump mapping in Maya uses world coordinates in combination with UVs and therefore did display properly on the mirrored side of the body. The screenshots shown the final UV setup for the bump map and color map

I will not go into more details about the texturing process, since is not part of the assignment. I'll just state that it took a surprisingly big amount of the time (more than 30% of the total.

With the model done it was time to render it. The materials in use are just basic blin for body, anisotropic for the chrome parts and transparent glass with index of refraction around 1.4. As all materials are highly reflective, I added some objects to the scene to be reflected into the car. First, a background was added, similar to a backdrop used in photo studios that doesn't have any visible sharp edges. In addition I added two stripes to further pronounce the shape of the body. For lighting, I used a simple three light setup with area lights and multisample shadows. All of this can be seen on the screenshot.

The final addition was a slight tint if green in the glass material, as this draft renders shows.

Done using an Intous 4 Wacom Tablet and Maya 2009.

Tracing Boxes

2010-03-10T01:10:00.015+01:00

This is my last post on ray tracing, and it’s on tracing boxes. Spheres alone are not all that fun and the infinite planes have the drawback of being...well infinite. Therefore, I decided to put boxes to my ray tracer. It is of course possible to use 12 triangles. This is a general solution but it is not exactly cost effective and moreover, it does not scale well to collision detection, where boxes are often used (I am working on some physics code too). I started my journey by searching the web and of course, Real-Time Collision Detection by Christer Ericson, which is probably the best book in its field. What I got was plenty of fast algorithms that only tell if the there is an intersection or not, some of which give the intersection position too. Also few algorithms that give the normal vector as well, but most of them did checking against all 6 planes and went through lots of boundary conditions. As a normal vector is needed in ray tracing for light calculation, I decided to make the best of the both worlds.
The idea is very simple. Use the fast algorithm to get the intersection position and then use that information to get the normal. Say we have an axis aligned unit cube centered at the origin, a point on it and a vector to that point. The surface normal at that point is in the direction in which the vector extends the most. In case it’s not immediately obvious, let’s take one side of the cube, say the one laying on the x=1 plane. The side can be defined as an intersection of the x=1 plane and the cone made of half-spaces defined by x>|y| and x>|z|, which is exactly the same as the original statement. So now we have three steps of the algorithm.

First, calculate the position of the center of the box and calculate the vector from it to the point on the surface.
Next, scale the vector into a unit cube, to cancel the scaling of the box along the axes.
Finally, zero out the coordinates with smaller absolute value, and then normalize the resulting vector.

The first part of the algorithm, used to calculate the position of intersection, is taken straight from a text book on graphics. The relevant code from the Box class is below.


public class Box extends Traceable {

protected Vec3;
protected Vec3 max;

// Component-wise min
public static Vec3 min(Vec3 a, Vec3 b) {
return new Vec3( min(a.x, b.x),
               min(a.y, b.y),
               min(a.z, b.z));
}

// Component-wise max
public static Vec3 max(Vec3 a, Vec3 b) {
return new Vec3( max(a.x, b.x),
               max(a.y, b.y),
               max(a.z, b.z));
}

@Override
public IntersectionInfo intersect(Ray r) {
// Interval based test
Vec3 direction = new Vec3(r.direction);
direction.normalize();
//
Vec3 oneoverdir = new Vec3(1.0f / direction.x, 1.0f / direction.y, 1.0f / direction.z);
Vec3 tmin = min.minus(r.origin).times(oneoverdir);
Vec3 tmax = max.minus(r.origin).times(oneoverdir);
//
Vec3 realmin = min(tmax, tmin);
Vec3 realmax = max(tmax, tmin);
//
float minmax = min(min( realmax.x, realmax.y), realmax.z);
float maxmin = max(max( realmin.x, realmin.y), realmin.z);

if(minmax >= maxmin && maxmin > 0.0f) { // Have intersection
 // Get position
 float t = maxmin;
 Vec3 position = r.origin.add(direction.times(t));

 // Get normal
 // 1. Get vector to relative position
 Vec3 center = max.add( min ).times(0.5f);
Vec3 normal = position.minus(center);

 // 2. Scale to matching unit box
 normal.x /= max.x - min.x;
 normal.y /= max.y - min.y;
 normal.z /= max.z - min.z;

 // 3. Keep the largest axis
 if(Math.abs(normal.x) > Math.abs(normal.y)) {
    normal.y = 0.0f;
    if(Math.abs(normal.x) > Math.abs(normal.z))
       normal.z = 0;
    else
       normal.x = 0;
 } else {
    normal.x = 0;
    if(Math.abs(normal.y) > Math.abs(normal.z))
       normal.z = 0;
    else
       normal.y = 0;
 }
 // 4. Normalize to unit
 normal.normalize();
 return new IntersectionInfo(position, normal, t, this);
}
//
return new IntersectionInfo(false);
}
} // end class

This might not be the fastest algorithm, but it beats most that I have come across on the internet. Here is one very ugly image showing ray tracing of a box in room and some normal mapping. Also the scene from the post on ambient occlusion was modeled with some boxes and a sphere.

The algorithm assumes that the box is axis aligned. This is not really an issue, as you can always do the intersection in the local space of the box. Transform the ray to the local space of the box with the inverse of rotation matrix of the box, find the intersection and normal and transform them back to world space with the rotation matrix of the box. Just have in mind that if you have scaling and translation applied to the box, the direction of the ray and the normal of the surface need special care.

Ambient Occlusion

2010-01-04T15:17:00.017+01:00

Ambient Occlusion is a cheap and simple way to add global illumination effect to an rendered image, especially for a ray tracer. This adds depth and realism to the image. The sample below shows the difference.

An image rendered with ambient occlusion.

An image rendered without ambient occlusion.

The technique is as fake as it is straight forward, but if it's good enough for Pixar should be good enough for most purposes. Ambient occlusion for certain surface point is calculated by measuring how much light is blocked by it's surroundings. In a ray tracer this is done by casting rays from the surface point in all directions and counting how many hit the scene. In the following implementation we can also limit the radius if needed and the amount of shadowing due to occlusion.

int smp = Tracer.ambientOcclusionSamples;
int c = smp;
for(int i = 0; i < smp; i++) {    
   Vec3 dir = Vec3.randomOnHemisphere(nearestHit.normal);
   dir = dir.times(Tracer.occlusionRadius);
   Vec3 org = nearestHit.location;
   Ray feeler = new Ray(org, dir);
   if( feeler.hit( nearestHit.object ) )
      c--;
}
color = color.times(1.0f - Tracer.occlusionAmount) .add( color.times((c * Tracer.occlusionAmount) / (float)smp) );

Most of the code should be staright forward and easy to understand only the Vec3.randomOnHemisphere(nearestHit.normal); function requires some explanation. As the name states, this function returns a vector, uniformly distributed on the unit hemisphere above the given vector. This is achieved by trail and error; we create random vectors in a unit cube and discard the corers to get uniform distribution on a unit sphere and than discard all the vectors not facing the same way as the given vector using a dot product test.

public static Vec3 randomOnHemisphere(Vec3 direction) {
   // Cut off the corners of the cube
   Vec3 v;
   do {
   v = new Vec3(
      2 * (float)Math.random() - 1,
      2 * (float)Math.random() - 1,
      2 * (float)Math.random() - 1);
   } while(v.length() > 1.0f && v.dot(direction)
   v.normalize();
   return v;
}

On average, no more than two thirds of the vectors are discarded. This might not be the most efficient method, but it does not require any vector transformations and matrix multiplication. Another way to achieve the same effect is to use a precalculated set of vectors distributed on the vertices of a regular polyhedron and transform it to face in the given direction. In a addition a random rotation around the main axis will remove the artifacts of using the same set of vectors.
UPDATE: It seams that this article is getting a lot more attention during the semester, so what better date to make a small correction than beginning of September.
The above method treats all rays shoot from the a certain point equally, while actually they don't contribute to the illumination of that point equally. Instead their contribution needs to be weighted by the dot product of the ray direction with the normal at that point, according to the cosine law.
I have the original sources for the tracer, but have lost the scene files. If I find them and find some time I might post an updated version of the code and a better looking image.

Reflection and Refraction

2009-11-10T13:15:00.014+01:00

After some tinkering with the stats, I got some interesting finds. Many people coming across this blog were searching for "cream pasta", but more importantly, the rest 75% were actually searching for ray tracing topics, especially reflection and refraction. While the image from the last post beautiful as it is, it does not give too much info. Some Java code snipets should help a bit more.
Now reflection is fairly simple. The angle between the reflected ray and the normal is the same as the angle between the incoming ray and the normal.


public static Vec3 reflect(Vec3 normal, Vec3 incident) {
float cosTheta = normal.dot(incident);
return incident.minus( normal.times(2 * cosTheta) );
}

Calculating the direction of the ray after refraction is a bit more involved. We start with Snell's Law, stating that ratio of the sines of the angles of incidence and refraction is equivalent to the opposite ratio of the indices of refraction, to get the direction of the refracted ray. The outgoing angle is obviously not always defined with this formula, which bring us to the next phenomena. When the light is traveling from a medium with higher optical density to a medium with a lower one and the incident angle is larger than the critical angle total internal reflection occurs and no light leaves the medium. In fact some light is almost always reflected and the amount is governed by the Fresnel equations. In my implementation I just approximate the amount with the dot product (with complete disregard for all the complexities, not to mention frequency and polarization), but the visual result is good.
With some lengthy transformations we can get a formula for the direction of the refracted ray that contains the same condition, defining total internal reflection, as Snell's law. Thus, when the flowing method can't calculate the direction total internal reflection has occurred.


public static Vec3 refract(Vec3 normal, Vec3 incident, float n1, float n2) {
 float dn = incident.dot(normal);
  
 float c = 1 - ((n1*n1)*(1-dn*dn) ) / (n2*n2);
 if(c < 0)
  return null;
  
 Vec3 t = incident.minus( normal.times( dn ) ).times( n1/n2 )
  .minus(
  normal.times( (float)Math.sqrt(c)) );
 
 return t; 
}

I hope that was more insightful. Feel free to drop a comment.

Tracing Rays

2009-10-03T23:40:00.005+02:00

I have never considered simple rays more precious than I do now and not just because I am building a ray tracer, but because I have recently moved Utrecht, Netherlands and sunlight is a scarce commodity here. I missed the thrill of long lectures and midterm exams, so am student yet again! Game and Media Technology postgraduate at Utrecht University and so far it's great. This brings me back to my ray tracer and no ray tracer is complete without a Cornell Box and some balls, exhibit below:

It sports a vast number of very basic features (hugely popular in ray tracers from the early 90's) like:

Phong materials
Anti-aliasing
Light reflection
Light refraction (with Fresnel reflection)
Area light and soft shadows
Soft reflections
and more to come!

The policy of the university on source sharing is "No." so no code pasting this time, but I am open for questions and discussion. I don't think too many people will find the code useful anyhow and plus you can always download POV ray, which is a world class open source ray tracer.

Last.fm and Spinach Pasta

2009-04-01T00:39:00.003+02:00

The latest news from Last.fm says that users who are in countries other than USA, UK and Germany will have to subscribe for €3.00 per month for listening to Last.fm Radio. I am not too happy about this, generally because I have discovered a whole bunch of new bands and musicians with Last.fm, even with the very limited selection of songs the service has. In fact lets make an experiment. Go to http://www.last.fm/listen and waste one of your 30 trail plays by typing "Hot Action Cop". I bet "Fever The Flava" will start in few seconds. It is a cool song, but gets a bit old after ten times in the same day. Now €3.00 is not really that much in some countries but the again in some it might be, and the selectiveness is just plain not cool. Being bought up in half country, half zoo one might think that I should have grown immune to any discrimination coming my way, but somehow this bothers me.
Now so far this post has been somewhat informative, but not really helpful. But instead of geeky advices on how to get streaming music now when last.fm has gone all sour, I will tell you what else you can do with €3.00. How about a nice spinach and cream pasta.*

Preheat the oven to 200ºC (473 K). Boil some pasta, preferably whole wheat pasta for this one, in a big bowl. Throw about 150 gr of spinach into a sauce pan and drizzle it with olive oil. Add just a bit of garlic and salt. When the spinach is soft, but still bright green add some white cheese or alternatively some feta cheese. After a minute of stirring, add some cream. As soon as the cream gets homogeneous, reduce the heat to very low and let it simmer. The pasta should be done by now, so drain it and mix it with the creamy sauce. Add some freshly grounded pepper and grated parmesan. Put it in the oven for 20 minutes. Bon appétit!

*Note that the quantities and costs are per serving. The total cost of the meal may vary with to electricity prices and hence country.

Vehicle

2009-03-21T20:39:00.016+01:00

As I wrote the previous post, this week I'll be writing about AI agents. It is a cool subject and I am eager to see what the final results will be. Now, AI might be a strong word for the dumb behavior that this vehicle displays but all the underlying math is there and should provide a basis for development of a more sophisticated system. To make thing more interesting I have decided to implement everything in Silverlight so that can be available in a browser and to test drive the technology while I am at it. Lets see the final result, and than go through the process.

I have used the Vehicles as a title, generally because it's the title of a vary inspirational book by Valentino Braitenberg, that touches the subject of autonomus agents as a early as 1984 and I can recomend it to anyone even remotely interested in the subject. It's just 17$ on Amazon. While this book gives more than enough philosophical background, most of the engeenering is based on the Steering Behaviors by Craig W. Reynolds. Steering behaviors are just simple rules that give steering directions to the vehicles. By smart use and combination of these rules we can build complex behaviors that mimic the behavior a bird or sheep in a flock. Some pepole like Craig W. Reynolds have been working on steering behaviors since the 80's, making them more experinced on the subject than I am in waking, so I will not give a watered down explanation, rather just refer to their pages. What I will give is a some C# code. Now why C# and Silverlight? I have been a long time Flash user for small demos like this one. But having a real programing language like C# is just too good not to try and I am not a huge fan of scripting languages, like Action Script. Plus the tools are completely free. For this post I will implement only the most basic behavoirs seek and flee. Bacause I would like to use it in a Silverlight aplication I will create a Silverlight Library project in Visual Studio. This will be our AI library and should not be aware of any drawing code, so that it can be used in a difirent project, say an XNA game. Now, the first thing that stroke me was that the System.Windows.Vector was just not available on my computer and of course I have the latest SDK. Now instead of wasting couple of days I decided to write my own implementation of a 2D Vector. I think I have done one in every language I have come across. And then a Matrix class implementation to do some transformations over the vectors (I assume knowledge basic linear algebra). With all that in place we can make a simple vehicle class which simply takes the output from the steering behavior and apply is as a force. The update method of the vehicle class looks something like this:


virtual Update(float dt)
{
   Vector2 steeringForce = steering.Calculate();
   //Acceleration = Force/Mass
   Vector2 acceleration = steeringForce / mass;
   velocity += acceleration * dt;
   velocity.Truncate(maxSpeed);
   position += velocity * dt;
   if (velocity.LengthSq > 0.00000001)
   {
      heading = Vector2.Normalize(velocity);
      //
      side = heading.Perp;
   }
   position.WrapAround(400, 400);
}

The Seek and Flee methods are extremely simple as you can see:


Vector2 Seek(Vector2 targetPos)
{
   if ((targetPos - vehicle.Position).LengthSq > threshold)
   {
      Vector2 desiredVelocity = Vector2.Normalize(targetPos - vehicle.Position) * vehicle.MaxSpeed;
      return desiredVelocity - vehicle.Velocity;
   }
   return new Vector2(0.0f);
}

private Vector2 Flee(Vector2 targetPos)
{
   if ((vehicle.Position - targetPos).LengthSq < panicDistanceSq && (vehicle.Position - targetPos).LengthSq > 0.1f)
   {
       Vector2 desiredVelocity = Vector2.Normalize(vehicle.Position - targetPos) * vehicle.MaxSpeed;
      return desiredVelocity - vehicle.Velocity;
   }
   return newVector2(0.0f);
}

In the Calculate method we just average the force from both, like so:


Vector2 Calculate()
{
return (Seek(target1) + Flee(target2)) * 0.8f;
}

Now I want to use that in the Silverlight application, and one of the coolest features in Silverlight, the MatrixTransform class enabling us to apply some affine transformations fast. Anyone who has done some graphics programming will appreciate this. All we need to do is take the heading vector from the vehicle, its perpendicular vector and the position of the vehicle and we have our transformation matrix:


transformMatrix.M11 = vehicle.Heading.x;
transformMatrix.M12 = vehicle.Heading.y;
transformMatrix.M21 = vehicle.Heading.Perp.x;
transformMatrix.M22 = vehicle.Heading.Perp.y;
transformMatrix.OffsetX = vehicle.Position.x;
transformMatrix.OffsetY = vehicle.Position.y;
transform.Matrix = transformMatrix;                // Makes sense ha?
shape.RenderTransform = transform;

Just be careful with the origin of the transformation. Expression Blend uses the center by default, while the API will use top left. You can download the code here.

Next week pizza! Just kidding, I’ll be adding obstacles.

Cave Day

2009-03-15T10:46:00.008+01:00

Lets start in a completely reverse order, with a nice photo of the Postojna Cave.
It has been confirmed by a comity of four friends that this place is actually more humid than my apartment in Ljubljana. Which brings me to another topic, I currently live in Ljubljana, Slovenia, where I work for ZootFly, a medium size game studio. The studio is very busy developing a game based on popular TV series by Fox that has lot to do with someone escaping from place where you put convicts in. This somewhat explains the hiatus on this blog. Now to add some twist, next post will be on simple AI agents.

The Cake is a Lie!

2008-01-17T12:05:00.002+01:00

Portal is by far the best game I've played in years. For those who haven't tried Portal yet, this is one of the most innovative games in quite some time, with a nice dose of cynical humor. It's a 3d puzzle game from Valve, where you pass through the level by manipulating portals. Gamespot has a detailed review of the game, so I will not go into details.

What I find cool about the game is that its gameplay mechanics come from Narbacular Drop, an independent game developed by students of the DigiPen Institute of Technology. The guys were employed by Valve to work on the project.
So enough fooling around, I'd better graduate soon, so I can apply somewhere and create an awesome game.

Microsoft Vizija 2007

2007-09-19T23:45:00.000+02:00

I will be talking about XNA next month at the Microsoft Vizija conference. I hope to familiarize people here in Skopje with the platform, create some interest and maybe even find someone enthusiastic enough to work with. If I have the time to fix some bugs in the Tunnel Vision game before the conference it would be great. Here is the timetable.

Home Again

2007-08-17T11:00:00.003+02:00

Well, vacation is over. I had some really nice time.
Did some traveling

Went high

Went deep

Ate (and cooked) some fantastic food

And now its time to go back to everyday life.

Tunnel Vision

2007-07-08T18:49:00.000+02:00

After weeks of hard work it is finally done. Tunnel Vision has reached a playable version that you can grab here. Here are some screenshots too.

The game features nice graphics, fast gameplay and a great soundtrack. The aim is to simply pass the track in the shortest time possible.
The vehicle control is inspired by the Xbox 360 controller, and therefore is best played with it. The game can also be played with mouse or/and keyboard.
The game is incredibly easily expandable. Tracks and vessels are stored as XML, and can be added within minutes, so if anyone that feels like joining in drop an email.

System requirements:

Windows XP SP2
.NET 2.0
DirectX 9.0c
XNA Runtime
Approx 50MB Hard disk space
Video card supporting Shader Model 2.0
Standard audio card

About This Blog

2007-07-04T09:23:00.000+02:00

I made Furious Pixels as a blog for posting about my projects, some technology info and general geek stuff. Most of my projects will probably be in computer graphics.

My current project is a game called Tunnel Vision. An update on its progress will soon follow.