Games Physics: Basics and Implementation of Predictive Collision Detection(codetheory.in)
codetheory.in
Games Physics: Basics and Implementation of Predictive Collision Detection
http://codetheory.in/game-physics-basics-and-implementation-of-predictive-collision-detection/
7 comments
I made a flash game at one point with gravity as the core feature, tuned the acceleration, etc, then added collision detection. The simplest way I found was to give everything a destination x, y first, then collision detection checked current to destination vector and updated destination with the results (drag, bounce, etc.). Destination then became current. The downside was the multi wall reflection caused n + 1 collision checks (n being number of collisions). This wasn't an issue for my game, but one with lots of collisions could have slowed it down.
The proper term for this type of collision detection is 'Continuous Collision Detection.' The math breaks down when you introduce rotation and you end up having to binary search to find when the collision will occur
For games, there are two different parts of the physics simulation: Integrator and collision detection/response.
The integrator uses a lot of math. It gives the positions of everything at time t and time t+D, where D is the timestep. The integrator functions under the assumption that no collisions occur.
The collision detection/response system takes as input the integrator's output, namely the positions of everything at time t, and at time t+D. It finds the earliest collision, say at time t+d where d < D, and does something about it -- usually changing position and velocity of the objects involved -- and then re-runs the integrator from time t+d to t+D, again stopping to process the earliest collision.
The important point is that your results are "good enough" if the collision detection just assumes objects travel in a straight line at constant velocity between their positions at t and t+D. The exact path is something that's confined to the integrator, and only linear paths exist in the simulation outside of it.
Of course there are various optimizations and corner cases you have to take care of -- like making sure colliding objects don't immediately register a second collision when the integrator is restarted, and bounding the number of collisions an object is allowed to experience per frame (to handle for example a ball resting in a V-shaped cup from alternating collisions between the two pieces of the cup thousands of times per frame).
And you can optimize since you don't actually have to re-run the integrator for objects that didn't change their physics state (position/velocity) due to the collision.
The integrator uses a lot of math. It gives the positions of everything at time t and time t+D, where D is the timestep. The integrator functions under the assumption that no collisions occur.
The collision detection/response system takes as input the integrator's output, namely the positions of everything at time t, and at time t+D. It finds the earliest collision, say at time t+d where d < D, and does something about it -- usually changing position and velocity of the objects involved -- and then re-runs the integrator from time t+d to t+D, again stopping to process the earliest collision.
The important point is that your results are "good enough" if the collision detection just assumes objects travel in a straight line at constant velocity between their positions at t and t+D. The exact path is something that's confined to the integrator, and only linear paths exist in the simulation outside of it.
Of course there are various optimizations and corner cases you have to take care of -- like making sure colliding objects don't immediately register a second collision when the integrator is restarted, and bounding the number of collisions an object is allowed to experience per frame (to handle for example a ball resting in a V-shaped cup from alternating collisions between the two pieces of the cup thousands of times per frame).
And you can optimize since you don't actually have to re-run the integrator for objects that didn't change their physics state (position/velocity) due to the collision.
That is indeed the case. I've however seen ray checks used effectively to prevent "tunneling" of objects cheaply since often exact solutions aren't as valuable as something more pragmatic, which solves the most noticeable portion of the problem -- Objects passing straight through walls.
I've generally heard this referred to as "continuous collision detection" predictive implies we care about collisions in the future, where in fact, we just care about all collisions in the frame.
Aye, decoupling the rendering (visual "frames") from the simulation speed and physics in general can be tricky!
I remember I wrote a fun little OpenGL game [1] some time ago, with flocking agents aka boids. I had a lot of fun making the creatures' "thinking speed" independent of the rendering speed and the simulation speed of the virtual world itself.
[1] https://github.com/piskvorky/PredatorPrey
I remember I wrote a fun little OpenGL game [1] some time ago, with flocking agents aka boids. I had a lot of fun making the creatures' "thinking speed" independent of the rendering speed and the simulation speed of the virtual world itself.
[1] https://github.com/piskvorky/PredatorPrey
Further reading on the subject of physics simulation.
[review paper discussing lots of techniques] http://depts.washington.edu/amath/courses/533-winter-2011/St...
[A PhD thesis with good background material] www.visionday.dk/VD05/graphical/slides/kenny.pdf
[review paper discussing lots of techniques] http://depts.washington.edu/amath/courses/533-winter-2011/St...
[A PhD thesis with good background material] www.visionday.dk/VD05/graphical/slides/kenny.pdf
Error establishing a database connection
Use the cache, Luke: http://webcache.googleusercontent.com/search?q=cache%3Acodet...
How did you find that? My google search for the link [0] showed no cached link/button.
[0]: http://codetheory.in/game-physics-basics-and-implementation-...
[0]: http://codetheory.in/game-physics-basics-and-implementation-...
Just type cache:http://example.com/ into Google.
Secondary tip: to access via the UI instead of search, at some point Google decided it'd be cool to make you click the ">>" button for a "live preview" before showing the "cached" link.
Just use havok
That is overkill for a lot of things. For others, it's useless... it's very hard to make good arcade-style "physics" with a full-blown physics simulator, and totally unrealistic stuff may not be possible with it at all... but those things still may need collision detection.
While I generally agree that "just use havok" is a bad approach, havoc, along with most physics engines, are able to be used for just collision detection, and not response. In many cases, it may prove useful to use an existing engine even for very unrealistic things.
That's a great point. I probably wouldn't do it with a HTML5 shooter with hundreds of projectiles though... what I mean is, those engines still have to check "what shape is it, oh, it's a circle, so now check what I am colliding with..", while you e.g. know the projectiles are circles and the walls are orthogonal planes. This may not always apply, of course, and I agree that as soon as you enter more complex territory you can save yourself a lot of pain by using a "proper physics engine".
> what shape is it, oh, it's a circle, so now check what I am colliding with
While this is true, consider that the huge library of built-up optimizations in a well used collision library like Havok very likely makes up for these checks.
Alternatively, they generally offer a lower level API such that you could just always call: `Havok::CheckCircleAAPlane` and then not have to worry about Havok doing it's dispatch. But then again if you don't use Havok's spatial culling you're likely missing out on a whole lot of optimizations, and advantages to using Havok.
While this is true, consider that the huge library of built-up optimizations in a well used collision library like Havok very likely makes up for these checks.
Alternatively, they generally offer a lower level API such that you could just always call: `Havok::CheckCircleAAPlane` and then not have to worry about Havok doing it's dispatch. But then again if you don't use Havok's spatial culling you're likely missing out on a whole lot of optimizations, and advantages to using Havok.
Agreed. Even Box2D is overkill most of the time (if we're talking about 2D games).
With my limited experience with Box2D, I can hardly think of a case where it would be both useful and overkill. It's really a quite straight-forward tool and provides rich features. Once I started using it, I immediately found that many of its features made a lot of interesting options suddenly trivial to implement. The only 2D projects where I would discourage it are ones without any semblance of physics; tile-based games, or example.
Right now I am looking at hundreds of projectiles bouncing around (cheaply, that is they are points) a tile based maze without any slowdown at all (Javascript). I'm sure Box2D does a lot of smart things, but in this case it just cannot beat simply doing one lookup into an array to see if the tile is solid or not. And that's all the world collision I need, since I intend enemy/player movement to be slower and less physic-y, they don't need to bounce off corners correctly or anything, sliding along them is just fine :P
I used Box2D it with C before and loved it, but with Javascript every bit of CPU I save I need for doing the game logic in my amateurish ways :) I'm a sucker for particles etc, and since I don't need accurate physics, it would just be throwing away resources I could use for stuff I do need (or rather want).
I used Box2D it with C before and loved it, but with Javascript every bit of CPU I save I need for doing the game logic in my amateurish ways :) I'm a sucker for particles etc, and since I don't need accurate physics, it would just be throwing away resources I could use for stuff I do need (or rather want).
Isn't havok for industry level 3d games?
just use Box2d would be nearer the sensible route
It looks okay and seems to match the constant acceleration kinematics formulas, but what we're really doing is Euler integration, a first-order numerical integration method. It's pretty bad even for numerical integration, so we should use fourth-order Runge-Kutta (RK4) instead [1].
Taking a look at the collision detection, look at this line of code:
It works in the given situation, of course, but wait a minute - if the ball is moving at 5 cm/frame and, at that particular frame, happens to be 1 cm above the platform, then the ball will move only 1 cm/frame! This means that the velocity has apparently dropped to some nonsensical value! But we can't move it anywhere else, because we haven't checked for collisions yet, and this example also assumes that there is only one other platform the ball could collide with - if it was an acute corner of two platforms, then we're in a bit of a rough situation.
Lastly, in this particular line of code:
The value, 0.4, is called the coefficient of restitution. In his particular case, where the platform is immovable, it's fairly reasonable (if we had immovable objects in reality!) but obviously a more sophisticated collision will need to consider energy factors.
Conclusion? Collisions are hard [2]!
[1] http://gafferongames.com/game-physics/integration-basics/
[2] ftp://www.myphysicslab.com/beta/Collision-methods.html