Peter,

Backtracking: yes it is the computation of the exact collision time.

I gave 2 solutions that can be used in multi-body dynamics, in general (that is, with 2nd order derivatives). I am not a game writing  specialist but, if I understand you, I would say that, in a game,  we have 1st order diff equations of the form

x(T) = integrate(speed(x(t), t), T0, T) or on a diff form : dx/dt = f( x(t), t)

where speed depends, without any lost of generality, on t and x(t).

In case of a collision, that is when  x(t) = Collision_position (i.e a ball boucing against a fixed wall), the speed may change discontinuously (i.e. speed = - speed).  It will happen at an unknown time Tc. It is possible to find Tc, accurately, by solving the equation (i.e Newton Raphson or another root finding method).

x(Tc) = Collision_position
where
x(Tc) = integrate(speed'(x(t), t), T0, Tc) where speed' is the speed as if there were no obstacle.

So I would say that the main algorithm to solve such a problem is

1.Suppose  that S(t) is the description (equations) of your system with t >= some initial  t0. This system will behave continuously (that is, all its state variables will be continuous) between t0 and t1. In your example t1 is the exact moment of the collision.

2. With a combination of a integration/root finding algorithm, find t1 - you get all the state variables for free because to find t1, we need to integrate the system.

3 Change S(t) to S'(t) where t >= t1. S'(t) is a description of the system that takes into account the effect of the collision.

Continue with first step.

Rem: If a accurate root finding algorithm is too costly, another solution is, knowing S(t) at some tn, compute S(t) at tn+1 without paying attention to any collision. Than using S(tn) to check whether a collision took place.

If no collision: continue and compute S(tn+2) etc.
If collision: Assume that the system is linear between tn and tn+1 and then solve the linear equation:
 









On Fri, Mar 6, 2009 at 1:01 PM, Peter Verswyvelen <bugfact@gmail.com> wrote:
Thanks for the info. With backtracking I actually meant the computation of the exact collision time, and let (part of the simulation) only go that far, so it's not really "back tracking" in the physics engine; does that correspond to your 2nd proposal. I just got this from a physics book that implements it that way (at least that why I got from reading it diagonally, the books contains a lot of advanced math...)

But do you mean that with your proposed methods the simulation will advance a full "time step" anyway, so the time interval does not need to broken up into smaller ones, where each sub-interval ends with a collision event? I wander how this could work since most of the time in a game when a collision happens, the game logic decides what forces to apply next, so the simulation can't really advance a full time step anyway (although that could be hacked I guess). Converting the game logic into differential equations with constraints seems very hard.

However, I must admit I haven't used any modern physics engines the last 5 years or so... But it's interesting to hear from people that did.


On Fri, Mar 6, 2009 at 11:59 AM, jean-christophe mincke <jeanchristophe.mincke@gmail.com> wrote:
Hello Peter,

The backtraking in time to solve the collision problem you mentionned is not, in my opinion, efficient.

From a previous life as an aerospace engineer, I remember that two other solutions exist to handle contact or collision constraints, at least if 2nd order diff. equations are used to describe the motion of a solid with mass.

In any case, you have to use a 'serious' variable time step integration algorithm (I.E Runge-Kutta).

1. The naive one: introduce a (virtual) spring between every 2 objets that may collide.  When these objets get closer, the spring is compressed and tries to push them back.
If the mass/velocity are high, that leads to a stiff system and the time steps may become very small.
However, this solution does not require any modification of the equations of motion.

2. The serious one: modify or augment the equations of motion so that the collision constraints are implicitly taken into account. If I remember well, the magical trick is to use langrangian multipliers.
The difficult here (especially in the context of aFRP) is to derive the new equations.

Hope it helps

Regards

Jean-Christophe Mincke


2009/3/6 Peter Verswyvelen <bugfact@gmail.com>
Regarding hpysics, did anybody did some experiments with this? The blog seems to be inactive since december 2008; has development ceased? 

Do alternatives exist? Maybe good wrappers (hopefully pure...)  around existing engines?

Integrating hpysics with Grapefruit might be a good topic for the Hackaton, trying to make a simple game (e.g. Pong or Breakout) without using recursive signal functions, but with correct collision response and better-than-Euler integration, all handled by the physics engine. Other FRP engines could be tried, but Grapefruit hacking is already a topic on the Hackaton, so it would combine efforts. 

It feels as if none of the current FRP engines can handle physics correctly, since a typical physics implementations requires "time backtracking", in the sense that when you want to advance the current simulation time by a timestep, collision events can happen during that time interval, and hence the FRP engine can only advance time until the earliest collision event. So to do physics *with* an FRP engine, the implementation and maybe even semantics of the FRP system might need to be changed. *Using* a physics engine as a blackbox inside an FRP system might make more sense.

Thanks to Wolfgang Jeltsch and Christopher Lane Hinson for having a discussion with me that lead to this.  Interestingly a similar discussion was help by other people in the Reactive mailing list at the same time :-)

Cheers,
Peter Verswyvelen



_______________________________________________
Reactive mailing list
 Reactive@haskell.org
 http://www.haskell.org/mailman/listinfo/reactive