Chapter 7

Very straightforward, isn't it? You can easily implement new interactions by adding another if clause. Want to intercept enemy missiles? No problem; add a case for

Category::AlliedProjectile and Category::EnemyProjectile. Allow friendly fire, and see enemy planes taking each other down? Just write a collision for two entities of category Category::EnemyAircraft.

An outlook on optimizations

Since we test all possible scene node combinations, the number of collision checks increases quadratically (by a power of two) with the number of scene nodes. This can become a performance bottleneck if we have very many entities. There are several ways to cope with this issue.

First, needless comparisons can be reduced. Recursion can be replaced with iteration; one possible solution is to write an iterator class that traverses scene graphs. This would avoid checking each combination twice, and checking a scene node for collision with itself.

for (SceneNode::iterator left = mSceneGraph.begin(); left != mSceneGraph.end(); ++left)

{

for (SceneNode::iterator right = std::next(left); right != mSceneGraph.end(); ++right)

{

... // Collision detection

}

}

By storing pointers to entities that are interesting for collisions (instead of all scene nodes) in a separate container, we would reduce unnecessary checks too. We could even go further and directly store the entities with their full type. For example, we might have std::vector<Aircraft*> for the enemies and

std::vector<Projectile*> for the allied bullets, so there would be no need for category dispatching.

Those approaches are a good start, but the time complexity is still quadratic. In a big world, it is clearly meaningless to check every possible pair of entities for collisions, since most of them are too far away. An optimization would base on locality. We only check entities that are close to each other. In order to achieve this, the world could be divided into a grid of equally sized cells. Each entity is assigned to a cell. For collision detection, only entities inside the same cell and the neighbor cells are checked, which drastically reduces the amount of required comparisons. Going this way further would lead to data structures such as quadtrees.

[ 179 ]

www.it-ebooks.info