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.
10 replies on “Physics, Collision Detection, and Porting Code”
“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.”
Why?
If you’re making Pong, don’t think about Space Invaders.
What if I want to take Pong and change small aspects? Add gravity, add or remove friction, add walls that speed up or slow down the ball? If I generalize it, it is a lot easier to change.
True, but you should only generalize when needed and as far as needed.
OOP is all about making abstractions easy to write, but in practice you often don’t need it (or don’t need it now). I’ve fallen in this trap too many times myself.
I don’t mean to sound all preachy here; I just wanted to give you something to think about.
No, I think you make a valid point. Even if you have a finished game as your goal, and you know all of the stories about projects that don’t get past being a tech demo, if you keep getting stuck with decisions to make generalizations as opposed to doing something that works right now, you’ll never finish and the result would be the same.
When working with components, generalizations are the rule. If something collides with something else, you might have different behaviors depending on what collided with what and from what direction. Maybe a collision means nothing, so entities will pass through each other, such as Ghosts in Pac-man, or bullets will only affect entities not on your team.
Of course, if you’re trying to write an engine that will be Pong, Space Invaders, Warcraft, and Super Mario Bros, it will need to be very general, almost to the point of uselessness. At least, developing such an engine would be a massive undertaking, and it would probably be worth it to write separate engines for certain types of games.
I wouldn’t say you’d never finish, but you’ll certainly spend a lot of time on it (as I have ;)). But you’re right, you need to make sacrifices somewhere, and you’re probably not going to make the right ones the first few times. Even still, it’s probably the best practise to just do it, and fix it later, that way you have something to show.
Generally speaking what I’ve done, instead of making a general purpose collision system, is at the level of physics, I classify game entities as either dynamic or static. Static’s obviously don’t move, and dynamics move through the physics, but that is their restriction. Any sort of motion must be done via physics, though you can achieve stiff/rigid motion if you wanted it (moving platforms for example). Creating a combination partially static object is achieved via a dynamic object with anchor’s that weigh parts of it’s geometry to positions. And custom behaviors are done through the overloading of a “Work” method of the dynamic object, which allows you to do all that weird stuff, like cancel out gravity or clamp your position if you were trying to build a pong paddle, or to monitor the status of parts and sensors to learn and act on the world. Well, at least it’s taken me 4 commercial 2D platformer games, 2 canceled titles/pitches that never made it, and 1 heavy restructure of my engine (that I’m in the middle of) to seemingly get it “right”. But after all, it’s only right until I determine the next big flaw. 😉
Hey GB, sorry man but I’m coming down on the “generalize as you need” side, mostly for sanities sake but its also the method that’s given me the most success. It’s basically the XP approach, if you don’t need something yet, don’t code it. Granted, this can make for some terrible refactorings later, but that’s why you have those test cases for right?
In terms of my code, I focused on a single game (Boxen3) and coded things specifically for it. After we finished, I started working on new projects and looking for ways to reuse the Boxen3 code. A lot of times I was pulling methods upward in the heirarchy to generalize them and it worked out really well. Similarly for collisions I managed to get a general solution but only after coding a few specific ones and looking at them to see what they had in common. It might have taken more rewriting this way, but at the rewrite point I *KNEW* how different games coded collisions, so I had a great idea on how to generalize them.
You’re trying to do things in reverse I’d say, you’re trying to predict the future of your code, guess at how things will be used. For just yourself that’s a feasible task (unless you don’t know yourself that well), but if others are going to use your code, its a lot harder to tell what they’ll want.
***You’re trying to do things in reverse I’d say, you’re trying to predict the future of your code, guess at how things will be used. For just yourself that’s a feasible task (unless you don’t know yourself that well), but if others are going to use your code, its a lot harder to tell what they’ll want.***
Actually, since I made this post, I came to the realization that even though I want to generalize it, it would probably be more impressive to focus on one particular game. You know, to finish it. B-)
The second game might have slightly different needs, and at that point, I’ll know more about those needs to have a better idea of what generalizing for it actually means.
Otherwise, I’m simply trudging along in my code, which works really well for what it does, but it doesn’t do much.
I’ve actually fallen into the trap you’re in, and constantly fall in it every time I type in code. How do you make a general purpose engine? How do you keep your code from becoming obfuscated? How do you include the things you might need later?
I think what needs to be done is sort of what most people are saying here, don’t try to be too general. What I’m doing currently I think will serve me well but generally I start on a specific application of code. In other words I go, okay for this game what do I need here, well I need an entity that moves on it’s own (well when it’s told too but generally to be a free moving object in the world). Okay great I got that working, then what’s next, well I want to make asteroids style control, so I apply physics (a little)… we have thrust, and we have something working against that when the thrust button isn’t down, okay so I need to add friction. Okay so this sounds too much like you’re programming specifically, and you are, but then you go. Hmm how could I make this general for my future games. Well I know that all game entities need to move independently based on physics. I know that I will have to be able to tell about collision between two entities. So then I write specifically but with an eye towards generalization.
Now I know when game #2 comes out, i’ll have a quicker time dev’ing it, and it wasn’t so hard to create what I did because I made it specifically for the game I was working on.
So really the short answer is, just code what you need, and then figure out how you can apply it to future projects and then build a class out of it.
Sir,
can u provide more information about various condition under which an arbiter has to perform
Preeti, you can find more information at the link to Erin Catto’s blog post. There is a PowerPoint slideshow, and while it isn’t as good as being at the tutorial, it might help to clarify things. Otherwise, all I know about arbiters is that they are used to decide what happens to two bodies during a collision.