Games Physics: Basics and Implementation of Predictive Collision Detection

http://codetheory.in/game-physics-basics-and-implementation-of-predictive-collision-detection/

by kushsolitary • 14 years ago

52 23 14 years ago

codetheory.in

grogenaut• 14 years ago

Just use havok

sunwooz• 14 years ago

Isn't havok for industry level 3d games?

neumann_alfred3• 14 years ago

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.

Arelius4• 14 years ago

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.

10098• 14 years ago

Agreed. Even Box2D is overkill most of the time (if we're talking about 2D games).

tlarkworthy• 14 years ago

just use Box2d would be nearer the sensible route

Arelius4• 14 years ago

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.

dave809• 14 years ago

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

Arelius4• 14 years ago

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.

csense• 14 years ago

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.

msie• 14 years ago

Error establishing a database connection

bonobo• 14 years ago

Use the cache, Luke: http://webcache.googleusercontent.com/search?q=cache%3Acodet...

dexter313• 14 years ago

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-...

Radim• 14 years ago

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

ivan_ah• 14 years ago

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

t3hprogrammer• 14 years ago

I've done a lot of amateur research into this field, but I am by no means an expert. Either way, I have a few comments. Let's take this line for example:

  ball.y += ball.vy;
  ball.vy += gravity;

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:

  ball.y = platform.y - ball.radius;

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:

  ball.vy *= -0.4;

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

ismarc• 14 years ago

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.

Games Physics: Basics and Implementation of Predictive Collision Detection

Related Stories