Archive for March, 2012


Who can see what is pretty important in a game. For the rendering, it indicates what is going to be drawn on the screen. For the AI, it influences the action to be taken.

I don’t have AI yet, but visibility is on the critical path to getting it working. It can be used for the rendering too, so I can kill two birds with one stone.

The key is the good old navigation zones that I built for pathfinding. The zones are connected by portals, so to calculate visibility I just have to trace through zones recursively until I can’t see any more portals. This provides a tree structure that can be used to determine visibility of anything from the root position: e.g. a map square or an object.

The map looks a lot nicer with fog-of-war turned on.

Game Objects

I hit the need for a game object system when I wanted to have enemies that you can shoot. The physics system could do a ray cast, but the result of that needs to be linked somehow to the game logic. I decided to do this by storing a handle on the physics object. Given a generic handle, I could pass it a message telling it that the object was damaged.

This is the Actor Model of programming, originally designed for concurrency, but I’m using it just because it decouples objects much more than standard OO. There’s no need to expose an interface because any message can be sent to any object. If the object that gets shot is not damageable, it doesn’t have to process the message.

It’s useful to put the actors together from components:

Using this system, actors can even be composed at runtime.

There are some downsides. It’s more work to declare a message than a function. There’s some overhead, too. And the code isn’t as strongly checked at compile time, which could lead to more bugs. I think overall it’s a win, though, given that the alternative was nightmare inheritance hierarchies and virtual functions everywhere.



The Physics Update

I mentioned in the last post that checking for pairs of colliding objects was O(N^2), and a stress test on the system shows that up very plainly with only a few hundred objects. What I really want is O(N active objects), where an active object is one that is potentially doing something during the frame. And it’s possible to code it that way.
There are a few options:

  • Sweep and prune.
  • Hierarchical structures (quad tree etc).
  • A regular grid.

Sweep and prune is, I think, the best for minimising the number of collision tests performed. It is also pretty good at using frame-to-frame coherence, i.e. if the objects don’t move, they don’t cost anything. On the other hand, it’s a pain to implement and not so good for fast moving objects. A hierarchy might be good for a static world with a wide range of object sizes; in my opinion, it’s good for visibility culling but just wrong for collision detection, which rarely has those properties. A regular grid though, is going to be pretty good all round, only needing a bit of tweaking to get the grid spacing right. So, in pseudocode, here it is.

for each active object
  update object position, velocity

Clearly, O(N active objects). So far so good. The objects start out active, by the way.

for each active object
  for each cell covered
    add to the cell
    wake up the cell

I don’t keep a list of active objects in each cell from frame to frame. This is because they can move, so the test has to be performed anyway. I do keep a list of sleeping objects (in a hash table with the cell ID as the key). If an active object enters the cell, they all wake up (the list can then be deleted). This step is also O(N active objects), although N is now larger because some objects woke up. Adding an object to a cell is a constant time operation. Note that objects can be in more than one cell. To avoid duplicate collisions, I store the cell IDs on the object and only allow collisions to be registered from the lowest cell ID present for both objects.

for each active cell
  check for object collisions

for each active object
  check collisions with the world

The number of objects in each cell is roughly constant, but the number of active cells is proportional to the number of active objects. So both these loops are O(N active objects).

for each active cell
  if cell should sleep
    put cell to sleep

If nothing is moving in a cell, it can go to sleep. The objects are all added to the sleeping list for that cell.

resolve collisions

Finally, resolve all the collisions we found previously. I won’t go into the details of this stage here.

Now I can even run the stress test in debug mode. Excellent.


Ordinarily I wouldn’t recommend writing your own physics engine. There are plenty of good, free ones and it would take years to achieve the same quality and feature set.

However, I don’t like having a dependency on a big, complex piece of code if you don’t need it. My requirements for physics are limited; I can probably fulfil them in no more time than it would take to learn and integrate a new library. And as a bonus I will understand and be able to tweak the code at any level.

First stop is collision detection. And here I have a head start: the navigation zones built for the pathfinding are ideal. Intersection tests and ray casting fall out in no time. Perhaps this shouldn’t be surprising. A pathfinding data structure must necessarily be able to determine whether a path is valid or not.

Beyond that my main requirement is to constrain moving objects against each other and the world. The algorithm goes something like this:

1. Update object positions.
2. Find pairs of intersecting objects and objects intersecting with the world.
3. Put all the intersections in a matrix.
4. Solve the matrix equation.
5. Move the objects to the constrained positions.

Note that one object can push another which in turn pushes a third and so on. This is why the constraints must be solved together.

Now, there are a few implementation details. Finding intersecting pairs is O(N^2) using brute force; it needs a spatial data structure for acceleration. You don’t want all intersections in the same matrix, only the ones that affect each other. So the world needs to be split up into islands. Matrix maths can get pretty complex but in this case a simple iterative method works. I might also want to constrain velocities. It’s much the same process.

A lot of typing and a few division-by-zero bugs later it’s all working. Was all that worth it? Well, it was fun and I learned some new things. So yes then.