Category: Game Development

As I develop Oracle’s Eye Prime using component-based methods, I have found myself thinking about how to implement features in a general way. For example, if I am trying to make Pong, I shouldn’t hardcode the Ball and Paddle and Walls. Instead, I should have a more general way to detect collisions. After all, even if I have a Ball entity bouncing off of a wall entity in Pong, I might want to do Space Invaders next and have bullet entities that destroy alien entities.

There are two aspects to collision detection with which I am grappling. The first problem is determining how to detect collisions between different, arbitrarily defined objects, which generally are represented by sprites on the screen, while still knowing where it collided. In Pong, I would like to know if the Ball hit the front or the sides of the Paddle since it would bounce differently. The second problem is figuring out what to do when a collision happens. If the Ball hits a Paddle, it should bounce off depending on the side it hit. If the Ball hits the goal, or goes out on one side, it should result in the score increasing for one of the players.

Metanet Software’s N Tutorials section helped me to figure out the solution to the first problem. While the code examples use ActionScript, the interactive example animations demonstrate the concepts and make them easy to grasp.

However, in the forums, there was a mention of Erin Catto’s GDC presentation on sequential impulses. Sequential impulses for “fast and easy” physics? It technically takes care of both problems? Count me in!

My first task: port the code.

It was originally written in Visual C++, but I am using an entirely different operating system and compiler. I obviously had to remove the #include for “windows.h”. The application used GLUT so I didn’t need to worry about WinMain or anything specific to VC++. On Windows, filenames are case-insensitive, so including <GL/glut.h> is the same as including <gl/glut.h> is the same as including <gL/Glut.H>. On Gnu/Linux, filenames are case-sensitive, so I had to determine which name was needed.

The next problem I encountered was a bit trickier. The code makes use of the class Arbiter, which basically regulates the collisions between different bodies. The World class has makes use of std::set to hold and sort through the Arbiters. The problem?


for (ArbIter arb = arbiters.begin(); arb != arbiters.end(); ++arb)
{
(*arb).PreStep(inv_dt);
}


g++ won’t compile the above code. It complains that it is modifying a const Arbiter, even though ArbIter is not a const iterator. VC++ will compile it just fine, obviously. Which one is correct?

It turns out that both are correct. At least, the standard library implementations are both correct. See, std::set’s keys must be ordered, and if a key can be modified, the ordering can’t be guaranteed. A set could be implemented so that std::set<T>::iterator is equivalent to const_iterator, which is how it is implemented for g++. If the key is only accessible through const methods, then there is no concern that the key can be changed in a way that would change the order. Other implementations can allow modification of a set’s keys so long as the parts relevant to ordering don’t change.

The problem is that the code as written wasn’t portable, and I didn’t like the idea of using const_cast or mutable to work around it.

Scott Meyers, author of “Effective C++” and “Effective STL”, provided the safe and portable solution.


ArbIter arb = arbiters.begin();
while (arb != arbiters.end())
{
// Erase key from set, modify it, then add it again.
Arbiter newArb((*arb).body1, (*arb).body2);
newArb.PreStep(inv_dt);
arbiters.erase(arb++);
arbiters.insert(newArb);
}


As the comment above states, you modify a copy of the key, erase the original, and then insert the copy. The above code should compile on any implementation, which means that it works with g++ on Gnu/Linux or VC++ on Windows.

Moments later, I was able to get the physics demos to run on Gnu/Linux.

The next step: integration with Oracle’s Eye Prime.