Black Golem

Two months ago I wrote an article about collision detection optimization for Nordenfelt. At that time the basic problem emerged from the fact that the engine used rectangles for collision detection. In this article I want to explain why I dropped the rectangle approach.

Simple Collision Shapes

There are two simple solutions for collision detection: Using rectangles or circles. Testing rectangles for intersection is as simple as the following code shows:

bool Intersect(Rectangle& a, Rectangle& b)
{
    return a.Left < b.Right && a.Top < b.Bottom &&
           b.Left < a.Right && b.Top < a.Bottom;
}

Collision detection between circles is a no-brainer to:

bool Intersect(Circle& a, Circle& b)
{
    Vector2D distance = a.Center - b.Center;
    return distance.Length < a.Radius + b.Radius;
}

The calculation of the distance length is rather expensive due to the need for a square root (length = Squareroot(x*x + y*y)). Therefore we use a common trick and compare the squared values (length*length = x*x + y*y):

bool Intersect(Circle& a, Circle& b)
{
    Vector2D distance = a.Center - b.Center;
    float radiusSum = a.Radius + b.Radius;
    float squaredDistanceLength = distance.x * distance.x +
                                  distance.y * distance.y;

    return squaredDistanceLength < radiusSum * radiusSum;
}

Detecting points inside a rectangle or circle are special cases where the point is a rectangle/circle with an area equal zero:

bool Intersect(Rectangle& r, Vector2D& v)
{
    return r.Left < v.x && r.Top < v.y && v.x < r.Right && v.y < r.Bottom;
}

bool Intersect(Circle& c, Vector2D& v)
{
    Vector2D distance = c.Center - v;
    float squaredDistanceLength = distance.x * distance.x +
                                  distance.y * distance.y;

    return squaredDistanceLength < c.Radius * c.Radius;
}

I don't know how good triangles would fit into collision detection. I did not investigate this shape. The simplicity of rectangle and circle was enough for me.

A Wrong Choice

Back in the days when I planned to use pixel art for Nordenfelt I chose rectangles as physical representation atoms. Airplanes, turrets, ships and other war machines have angular shapes. So rectangles were the first choice. The only drawback were rotations. Only axis-aligned rectangles provide simple collision detection routines. But pixel art is not rotatable anyway (without ugly distortions) so that was no problem.

After some graphical experiments I dropped the pleasing idea of pixel art - sob :( - and switched over to rendered 3D models and higher screen resolutions. Now rotations became possible and were included right away. This created the demand for rectangle rotation which was solved by including polygons for physical representation. Complex algorithms and some trickery were needed to make them usable for the engine.

Circles have a huge advantage over rectangles and polygons: Rotation is faster (rotation of one center compared to rotating every polygon corner) and does not change the shape, related to axis alignment. I thought about using circles instead of polygons. Laziness stopped me pondering.

Profound Refactoring

Integration of the new power-ups (coming in Nordenfelt 0.2) created a refactoring demand for state machines, animations and sprite management. Why not kill two birds with one stone and replace the awkward polygon shapes with circles? So I dived deep into the "physics" code again.

After four days of refactoring the results manifested as hierarchical circle structures. These structures can easily be scaled, translated and rotated. The hierarchic struture speeds up collision tests. When the envelope circle does not intersect neither do the inner circles:

Bonus

Another advantage of circles over polygons and rectangles appeared while coding: Line intersection is a breeze and can easily be extended with line thickness:

float GetSquaredLength(Vector2D& v)
{
    return v.x * v.x + v.y * v.y;
}

float GetDotProduct(Vector2D& v1, Vector2D& v2)
{
    return v1.x * v2.x + v1.y * v2.y;
}

bool Intersect(Circle& c, Vector2D& p1, Vector2D& p2, float lineThickness)
{
    float virtualRadius = c.Radius + (lineThickness / 2);
    float squaredVirtualRadius = virtualRadius * virtualRadius;
    Vector2D f = c.Center - p1;

    if(GetSquaredLength(f) < squaredVirtualRadius)
        return true;
 
    if(GetSquaredLength(p2 - c.Center) < squaredVirtualRadius)
        return true;

    Vector2D distance = p2 - p1;
    float t = GetDotProduct(f, distance) / GetSquaredLength(distance);
 
    if(0 <= t && t <= 1)
        return GetSquaredLength(f + (t * distance)) < squaredVirtualRadius;
    else
        return false;
}

This intersection would be much more complex, slower and uglier for rectangles and polygons.

Line intersection is needed e.g. for shots which need to check their trace. Otherwise they may fly through an object without detecting the collision:

Conclusion

I don't know if there are better collision detection solutions out there. I bet there are. Finally hierarchical circle structures are a beautiful, fast and easy to understand method for body representations. It also applies to 3D very well. Simply add axis Z in the vectors and it works in three dimensions. Try this with polygons :)

Cheers,
Thomas

Call For Your Opinion

Nordenfelt is approaching version 0.2. An important point on the TODO list is fixing the player ship graphics. Therefore I did some draft sketches and posted them on the Nordenfelt blog. It would be great if you could give me some feedback which designs you like the most. Please drop me your comments here.

Shortening Release Interval

The release of Nordenfelt 0.1 was four weeks ago. Version 0.2 will be out next week. In my opinion a release interval of roughly five weeks is far too long. It's like driving a car with both eyes closed and taking a look only once a minute. Continuously watching the street would be the best case here but that's impossible, at least for me. An attentive look every few seconds is enough. So I'm going to shorten this interval length. One week would be nice which is possible in most cases. Let's see how this will work. There may be releases without any visible changes but that's the nature of such short dev circles.

Cheers,
Thomas

Currently I'm refactoring the input system of Nordenfelt. The reason for this is to enable mapping input from mouse, keyboard and joystick to any actions in the game. E.g. it should be possible to control the ship by WASD for movement and SHIFT for fire as well as by cursor keys for movement and any mouse button for fire. Mouse button functionality should be swappable for left-handers, etc. Briefly: players will be allowed to set their input scheme as they please.

After two days of refactoring one design guideline proved itself as well suited for refactoring: the pimpl idiom.

The pimpl idiom stands for "private implementation idiom". Modern object-oriented languages like Java or C# favour public implementation: the implementation details are intermixed with the interface declaration. There are design patterns for hiding details like interfaces, proxies or factories. Nevertheless, modern languages expose their class internals like private methods or properties in their interface. Firstly it clutters the interface with needless "information" and secondly creates unnecessary dependencies. More dependencies result in longer recompile times. Recompilation is not really an issue for modern languages. Unfortunately C++ has complex features like templates or argument dependent lookup which make compiling cpp files a time consuming task.

An easy way to avoid dependencies is writing pure interfaces which stay the same, regardless of their internals. Lets say we have the following class declaration in C++ header Character.hpp:

#include <rectangle.hpp>
#include <vector>

class Animation;
class Gun;

class Character
{
public:

  Character();
 
  ~Character();
 
  void Update();
 
  void Render() const;
 
  inline unsigned int GetHitpoints() const { return hitpoints; }
 
private:

  void FireAllGuns();

  bool PointCollides(float x, float y) const;

  std::vector<Gun*> guns;

  Animation* shoot;
  Animation* run;
  Animation* idle;

  Animation* currentAnimation;
 
  Rectangle shootBody;
  Rectangle runBody;
  Rectangle idleBody;
 
  unsigned int hitpoints;
};

There are two hidden methods and many properties in this declaration. They are not available to foreign operations. So why should we expose them here at all? The above mentioned dependencies are a further reason for hiding the guts. What if we replace the animation/body pairs and combine them in a new class Action? The declaration of Character will change and every cpp file including Character.hpp has to be recompiled. Characters are a common unit in games so many classes would be affected.

Let's use the pimpl idiom to hide the internals:

class Character
{
public:

  Character();
 
  ~Character();
 
  void Update();
 
  void Render() const;
 
  unsigned int GetHitpoints() const;
 
private:

  struct Pimpl;
  Pimpl* pimpl;
};

Oh yeah, that's much better! No private detail is visible in the declaration (well, nearly) and all includes are gone. Only the class Pimpl is there. Pimpl will contain all the private stuff we kicked out. The forward declaration of Pimpl does not reveal anything about its structure, neither private nor public. As long as we keep construction, changes and deletion of pimpl in the cpp file we have no need for its interface anyway. Let's take a look on the implementation in Character.cpp:

#include <animation.hpp>
#include <gun.hpp>
#include <rectangle.hpp>
#include <vector>

struct Character::Pimpl
{
  ~Pimpl()
  {
    delete shoot;
    delete run;
    delete idle;

    for(std::size_t i = 0; i < guns.size(); ++i)
      delete guns[i];
  }

  inline void FireAllGuns()
  {
    for(std::size_t i = 0; i < guns.size(); ++i)
      guns[i]->Fire();
  }

  inline bool PointCollides(float x, float y) const
  {
    if(currentAnimation == shoot)
      return shootBody.PointCollides(x, y);
    if(currentAnimation == run)
      return runBody.PointCollides(x, y);
    if(currentAnimation == idle)
      return idleBody.PointCollides(x, y);
    return false;
  }

  std::vector<Gun*> guns;

  Animation* shoot;
  Animation* run;
  Animation* idle;

  Animation* currentAnimation;
 
  Rectangle shootBody;
  Rectangle runBody;
  Rectangle idleBody;
 
  unsigned int hitpoints;
};

Character::Character()
  :pimpl(new Pimpl)
{
  ...init pimpl here...
}
 
Character::~Character()
{
  delete pimpl;
}
 
void Character::Update()
{
  ...pimpl->FireAllGuns() and pimpl->PointCollides() may be used here...
}
 
void Character::Render()
{
  pimpl->currentAnimation->Render();
}

unsigned int Character::GetHitpoints() const
{
  return pimpl->hitpoints;
}

As you can see: a pure interface is clean, has less dependencies and therefore is more refactoring-friendly. The pimpl idiom does not have additional overhead compared to writing common class declarations and it will boost your development cycle in the long run.

Code well,
Thomas

I just switched www.nordenfelt-thegame.com over to its blog interface. Everything concerning Nordenfelt will be published over there from now on. Feel free to subscribe to the email newsletter or the blog's RSS feed to keep in touch with the development process. See you there!

Cheers,
Thomas