03-29-08 - 2

03-29-08

While I'm at it I'll write up the PD I'm using for the record. This is not an exact solution of the PD - it's an implicit Euler step. You can actually totally solve the PD exactly, but using an implicit Euler step actually is more stable than the exact solution, it adds a sort of fake drag which is a nice thing in practice. It's also a lot nicer numerically for doing tiny steps than using the exact solution with exponential functions.

K & D are unitless config parameters of the PD
  K = 1 and D = 1 are reasonable ; D = 1 is critical damping
time_scale = desired time to converge
dt = current time step
x0,v0 = start position & velocity
x1,v1 = target position & velocity

ks = 36 * (K / time_scale)^2
kd = 9 * K * D / time_scale

scale = ( 1  + kd * dt + ks * dt^2 )

a = ( ks * (x1-x0) + ( kd + ks * dt ) * (v1-v0) ) / scale

vt = v0 + a * dt
xt = x0 + vt * dt

If you had no min velocity that would be it. Note the funny scale numbers in ks & kd ; those are just there so that the time to converge roughly matches "time_scale", and so that K = D = 1 is a good choice. Note that K,D, and time_scale are really not three independent parameters, there are only two free parameters, but it's easier to tweak if they're seperated because you can leave K and D alone and just change "time_scale" to match your desired duration to converge.

To handle min velocity you add some logic after the above PD step :

mv = min velocity

if ( |xt - x0| <= (mv * dt) )
{
	if ( |x1 - x0| <= (mv * dt) && |v1 - v0| <= 2*mv )
	{
		xt = x1;
		vt = v1;
	}
	else
	{
		vt = (x1 > x0) ? mv : -mv;
		xt = x0 + vt * dt
	}
}

This is ugly in various ways. The first part was a pure PD that works in N-d. Now we've gone to 1d. Also the first part worked with arbitrary end velocities. This min velocity part only really works for a still target. I think it's not too hard to fix for a moving target by using a min velocity relative to the target but I haven't bothered.

Now of course PD's don't always take the same amount of time to converge, unlike the cubic. Converge time depends on initial seperation and initial velocities. With the constants in the equations above, and if you set up your tweaks right, then you can have a PD that converges in roughly "time_scale" for typical starting situations. Here's how the time varies :

PD convergence graph

the X axis is the "time_scale" parameter, and the Y axis is actualy time to converge. If it converged in the time you wanted, all the points would be on the red line (Y=X). There are four series of points for different starting distances so you can see how converge time varies for starting distances. The distances are {160,320,480,640}. In the graph the start & end points are all at zero velocity.