Sorry, my message was inadvertently sent - hit the wrong key - a gmail feature<br><br>Peter,<br><br>Backtracking: yes it is the computation of the exact collision time.<br><br>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<br>
<br>x(T) = integrate(speed(x(t), t), T0, T) or on a diff form : dx/dt = f( x(t), t)<br><br>where speed depends, without any lost of generality, on t and x(t).<br><br>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).<br>
<br>x(Tc) = Collision_position<br>where <br>x(Tc) = integrate(speed'(x(t), t), T0, Tc) where speed' is the speed as if there were no obstacle.<br><br>So I would say that the main algorithm to solve such a problem is:<br>
<br>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.<br>
<br>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.<br><br>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.<br>
<br>4 Continue with first step.<br><br>Rem: If an 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
use S(tn+1) to check whether a collision took place. <br>
<br>If no collision: continue and compute S(tn+2) etc.<br>If collision: Assume that the system is linear between tn and tn+1 and then solve the linear equation:<br><br> x(tc) = x(tn) + (x(tn+1) - x(tn))/(tn+1 - tn) * tc = Collision_position<br>
<br>Once tc is known, replace your system as explained above with S'(t) , t>= tc<br><br>The condition here is that [tn, tn+1] must be choosen small enough in order that the assumption if linearity holds.<br><br>Regards <br>
<br>Jean-Christophe Mincke<br><br><br><div class="gmail_quote">On Fri, Mar 6, 2009 at 2:26 PM, jean-christophe mincke <span dir="ltr"><<a href="mailto:jeanchristophe.mincke@gmail.com">jeanchristophe.mincke@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">Peter,<br><br>Backtracking: yes it is the computation of the exact collision time.<br><br>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<br>
<br>x(T) = integrate(speed(x(t), t), T0, T) or on a diff form : dx/dt = f( x(t), t)<br><br>where speed depends, without any lost of generality, on t and x(t).<br><br>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).<br>
<br>x(Tc) = Collision_position<br>where <br>x(Tc) = integrate(speed'(x(t), t), T0, Tc) where speed' is the speed as if there were no obstacle.<br><br>So I would say that the main algorithm to solve such a problem is<br>
<br>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.<br>
<br>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.<br><br>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.<br>
<br>Continue with first step.<br><br>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. <br>
<br>If no collision: continue and compute S(tn+2) etc.<br>If collision: Assume that the system is linear between tn and tn+1 and then solve the linear equation:<div><div></div><div class="h5"><br> <br><br><br><br><br><br>
<br><br><br><br><div class="gmail_quote">
On Fri, Mar 6, 2009 at 1:01 PM, Peter Verswyvelen <span dir="ltr"><<a href="mailto:bugfact@gmail.com" target="_blank">bugfact@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<span style="font-size: small;">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 <a href="http://www.amazon.com/Dynamic-Simulations-Multibody-Systems-Coutinho/dp/038795192X" target="_blank">physics book</a> that implements it that way (at least that why I got from reading it diagonally, the books contains a lot of advanced math...)</span><div>
<span style="font-size: small;"></span><div><div><div><div><span style="font-size: small;"><br></span></div><div><span style="font-size: small;">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.</span></div>
<div><br></div><div><span style="font-size: small;">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.<br>
</span></div><div><div></div><div><div><br></div><div><br></div><div><div><div><div><div><div><div><div class="gmail_quote"><span style="font-size: small;">On Fri, Mar 6, 2009 at 11:59 AM, jean-christophe mincke </span><span dir="ltr"><span style="font-size: small;"><<a href="mailto:jeanchristophe.mincke@gmail.com" target="_blank">jeanchristophe.mincke@gmail.com</a>></span></span><span style="font-size: small;"> wrote:<br>
</span><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"><div><span style="font-size: small;">Hello Peter,<br><br>The backtraking in time to solve the collision problem you mentionned is not, in my opinion, efficient.<br>
<br>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.<br><br>In any case, you have to use a 'serious' variable time step integration algorithm (I.E Runge-Kutta).<br><br>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.<br>If the mass/velocity are high, that leads to a stiff system and the time steps may become very small.<br>However, this solution does not require any modification of the equations of motion.<br>
<br>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. <br>The difficult here (especially in the context of aFRP) is to derive the new equations.<br><br>Hope it helps<br><br>Regards<br><br>Jean-Christophe Mincke <br>
<br><br></span>
</div><div class="gmail_quote"><div><span style="font-size: small;">2009/3/6 Peter Verswyvelen </span><span dir="ltr"><span style="font-size: small;"><</span><a href="mailto:bugfact@gmail.com" target="_blank"><span style="font-size: small;">bugfact@gmail.com</span></a><span style="font-size: small;">></span></span><span style="font-size: small;"><br>
</span></div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<span><span style="font-size: small;">Regarding </span></span><span style="border-collapse: collapse; white-space: pre;"><span><span style="font-size: small;">hpysics, d</span></span></span><span><span style="font-size: small;">id anybody did some experiments with this? The blog seems to be inactive since december 2008; has development ceased? </span></span><div>
<div></div><div><div>
<span><span style="font-size: small;"><br></span></span></div><div><span><span style="font-size: small;">Do alternatives exist? Maybe good wrappers (hopefully pure...) around existing engines?</span></span></div>
<div><span><span style="font-size: small;"><br></span></span></div><div><div><div><div><div><span><span style="font-size: small;">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. </span></span></div>
<div><span><span style="font-size: small;"><br></span></span></div><div><span><span style="font-size: small;">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.</span></span></div>
<div><span><span style="font-size: small;"><br></span></span></div><div><span><span style="font-size: small;">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 :-)<br>
</span>
</span></div><div><span><span style="font-size: small;"><br></span></span></div><div><span><span style="font-size: small;">Cheers,</span></span></div><div>
<span><span style="font-size: small;">Peter Verswyvelen</span></span></div>
<div><span><span style="font-size: small;"><br></span></span></div><div><span><span style="font-size: small;"><br></span></span></div><div><span><span style="font-size: small;"><br>
</span>
</span></div><div><span><span style="font-size: small;"><br></span></span></div><div><span style="font-size: small;"><br></span></div></div></div></div></div>
<span style="font-size: small;"><br></span></div></div><div><span style="font-size: small;">______________________________</span><span style="font-size: small;">_________________<br>
Reactive mailing list<br></span>
<a href="mailto:Reactive@haskell.org" target="_blank"><span style="font-size: small;">Reactive@haskell.org</span></a><span style="font-size: small;"><br></span>
<a href="http://www.haskell.org/mailman/listinfo/reactive" target="_blank"><span style="font-size: small;">http://www.haskell.org/</span><span style="font-size: small;">mailman/listinfo/reactive</span></a><span style="font-size: small;"><br>
<br></span>
</div></blockquote></div><span style="font-size: small;"><br></span>
</blockquote></div><br></div></div></div></div></div></div></div></div></div></div></div></div></div>
</blockquote></div><br>
</div></div></blockquote></div><br>