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 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 bookhttp://www.amazon.com/Dynamic-Simulations-Multibody-Systems-Coutinho/dp/0387...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

...

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

Am Freitag, 6. März 2009 14:34 schrieb Daniel Bünzli:

...

without using recursive signal functions,

If this is because there's this limitation in the frp system you use

It is.

then better fix the system.

The system is Grapefruit, by the way. And I’m its developer, by the way. :-) I have to say that it’s hard, if not impossible, to combine recursive signal definitions with other features, I want to have. The point of recursive definitions is that you want to turn recursive equations from your problem domain directly into Haskell definitions. This is nice from a user’s point of view but hard from a programmers point of view. Standard Haskell already shows that. While it is possible to define an infinite list of ones by ones = 1 : ones, it is not possible to do the same for sequences of type Seq. The above definition of ones relies very much on the structure of lists. Analogously, the ability to define signals recursively restricts the set of possible signal implementations seriously. Haskell’s recursive definitions are very general. They have to find fixpoints of arbitrary functions over arbitrary type. Therefore, their semantics are rather weak. They give you the least defined fixpoint. The consequence is that you get bottom if you use something like x = 0 * x although x = 0 might be what you prefered. What I want to say is that coming up with a signal implementation that allows Haskell recursion and has other advantages at the same time is a big challenge. There are three features, you might want from a signal implementation: 1. support for recursive signal definitions using Haskell equations 2. memoization (for avoiding time leaks, for example) 3. signals which may depend on external sources I tried hard to support 2 and 3 well in Grapefruit. Fran has 1 but has problems with 2 and 3. I don’t know whether Reactive has a solution for 2 in the context of recursive definitions, i.e., whether the space and time leak problems of Fran were solved. I think, it has at least problems with 3. For me, 2 and 3 are more important than 1. One reason is that 1 has other problems than being in conflict with 2 and 3. The result of a recursively defined signal depends on when sampling occurs. Since a recursive definition tends to result in accumulation of values, errors introduced by sampling may accumulate too. So you have to use clever approximation algorithms in addition. My new idea is to view the problem in a different way. Let’s take the problem where the position of a ball is the integral of the difference between the mouse position and the ball position. As far as I can see, the transformation of the mouse position signal into the ball position signal forms a linear system. So the ball position signal is the mouse position signal convoluted with another signal. If we would have a function that performes convolution, we could probably implement many problems using this function. Using convolution would let us get rid of the problems with accumulating errors. I suppose that most of the recursive definitions you would use in FRP are differential or integral equations. Let’s look at the equation for the ball-following-the-mouse example: ballPos = integral (mousePos - ballPos) ballPos can be represented in terms of mousePos as follows: ballPos = (exp . negate) * mousePos where * means convolution. We could provide a library which supports common stuff like distance-dependent acceleration, friction etc. Of course, you could say that now the programmer isn’t able anymore to enter his equations directly which isn’t nice. However, this situation is not different to other areas. For example, you cannot write x = 5 - x / 2 and expect x to be 10 / 3. Instead, you have to transform the equation first.

Soon or later it you'll want it elsewhere. A recursive reactive signal just means that some of what your reactive program computed will be usefull/necessary for the next step.

You can do this with convolution, I think. By the way, continuous signals don’t have steps. These are just introduced by sampling.

You'll see that happen very quickly (e.g. any simple reactive state machine).

“State machine” sounds like a discrete problem. You can use accumulation over event sequences here (as, for example, provided by the scan function in FRP.Grapefruit.Signal.Discrete). By the way, the adress of the Grapefruit mailing list is grapefruit@projects.haskell.org, not grapefruit@haskell.org. Best wishes, Wolfgang

Le 6 mars 09 à 17:57, Wolfgang Jeltsch a écrit :

However, my e-mail also reached the Grapefruit mailing list (but Daniel Bünzli’s didn’t) and the version there has the correct address in its To: headers.

Btw. the one for haskell-cafe didn't either, I guess you must be subscribed to post there.

What I want to say is that coming up with a signal implementation that allows Haskell recursion and has other advantages at the same time is a big challenge.

I understand this is a tough problem. I cannot help here, my own frp implementation is impure -- which brings in other problems -- and despite this I also did put some limitations in recursive definitions.

I suppose that most of the recursive definitions you would use in FRP are differential or integral equations.

Not necessarly, for example for UIs it is common to feedback the result of the ui interaction to the ui itself until a particular condition is met.

By the way, continuous signals don’t have steps. These are just introduced by sampling.

Ok so replace "step" by "dt", where "dt" is an infinitesimal delay.

“State machine” sounds like a discrete problem. You can use accumulation over event sequences here (as, for example, provided by the scan function in FRP.Grapefruit.Signal.Discrete).

Maybe the wording "state machine" was too restrictive, the problem is when you want the argument "DSignal era val" of scan to be the result of scan "DSignal era accu" itself, higher order state machines. Maybe you can work around the recursive behaviour issue by providing special combinators, I don't want to argue that. It's just that I see recursion occuring naturally in systems and recursion is the natural way of expressing things in FP. This is why I'd prefer a system that allows me to write directly such definitions. (actually the gist of my message was more about the physics than about the recursion issue) Best, Daniel

Le 11 mars 09 à 12:48, Wolfgang Jeltsch a écrit :

I don’t quite follow you here. Could you give an example?

A text field, the string resulting from the interaction (edition) is fed back into the text field for futher editions. Ui transitions where the result of the current ui interaction dictates the next ui to show. For example in my breakout game the whole ui and its transitions are a signal, and the result of that signal switches the ui signal itself (by switch I mean the usual switch combinator). More precisely the switching event depends on the ui signal itself but delayed by an infinitesimal delay. The result of the game ui is the score which leads via switching to a game over screen that prints that score which can lead to either start the game over or quit etc. Best, Daniel

Am Freitag, 6. März 2009 17:57 schrieb Wolfgang Jeltsch:

Am Freitag, 6. März 2009 17:51 schrieb Wolfgang Jeltsch:

...

By the way, the adress of the Grapefruit mailing list is grapefruit@projects.haskell.org, not grapefruit@haskell.org.

Oh, this is really strange: I addressed my e-mail to grapefruit@projects.haskell.org but the version arriving at the Reactive mailing list has grapefruit@haskell.org in its To: header. However, my e-mail also reached the Grapefruit mailing list (but Daniel Bünzli’s didn’t) and the version there has the correct address in its To: headers.

Does anyone know who is responsible for the Haskell mail server?

Best wishes, Wolfgang

It was a misconfiguration of the mailserver which is believed to be fixed now. Best wishes, Wolfgang