We have a number of vehicles that have legs and right now we treat these walkers as tanks with invisible treads/wheels and animate the legs through a mess of code and a pair of "walk forward" and "walk backward" animations. We want to improve this so the legs can be made to move move fluidly and accurately regardless of what direction the vehicle is moving.

Is there any information or info out there on the math/physics/animation stuff for walkers/mecha/vehicles with legs and how to make the legs animate realistically? We have 4-legged walkers (that move somewhat similarly to the AT-AT in Star Wars) and 2-legged walkers (that move somewhat similarly to the AT-ST in Star Wars) plus smaller walkers that move like spiders.

I'm working on a walking ragdoll for several years now, and this is what i have so far:



A true simultaion is too much work if your motivation is just 'it does not look well'.
But you can use some related math to improve the legs animation, while internally sticking at the tank model.


So, what i suggest is:

Build an Inverted Pedulum model from your tank.

Calculate the 'ICP' (Instaneous capure point).
This is the point wehre an inverted pendulum stops falling, if it can put it's 'COP' (center of pressure) to this location.
Moving the COP works by:
If inverted pendulum has a cart as its base, move the cart (often used model in research)
If base is a single ore more legs at rest, move the COP inside the support polygon (convex hull of feet projected to ground) by ankle torque.
If the legs have knees, you can simply move a leg to the target COP position. This alone is the interesting case for you.

Now, assuming you know ICP (simple to calculate. E.g. http://www.elysium-labs.com/robotics-corner/learn-robotics/biped-basics/zero-moment-point-zmp/ ),
This can help to get some realistic looking feet targets from this observation:
A walker will place its swing foot somewhere between ICP and ground projected COM (center of mass).
Moving this 'somewhere' closer to the COM means accelerating, moving closer to the ICP means deaccelerating and stop.

Then you need some simple IK solver to calculate knee angle, aligning foot to terrain etc. and that's it.


I've had some discussion with Newton physics engine developer which contains some links to useful papers on the subject:
http://newtondynamics.com/forum/viewtopic.php?f=9&t=8860

Yeah we dont want a full physics simulation for these legs, we just want math to make them move realistically.

looks a bit off, like that Honda robot you've probably seen on TV

Agree to that, but then look at the quadrupes from Boston Dynamics.
They move like living animals (remember their reflexes while slippering on ice).
It works for them so it will work for us.

I'm pretty sure i'll have natural walking and running.
Those are behaviours defined olmost entirely by physics laws and shape of the human body,
so it's possible to reproduce with analytical methods and it will look right.

I'm worried about other things - motion that is result of intelligence.
Operating tools, complex tasks etc... don't know how to handle that.


Back on topic, simulation is surely overkill here.
So there remains the options to use and modify existing animation, or use procedural animation only.
Both require a IK solver that orients and positions the foot, so i'd start with that.

Any examples out there of how to do an IK solver for leg movement? Procedural animation is exactly what we want (i.e. something that generates correct rotation/translation positions for a foot bone, knee bone etc based on the forwrads/backwards movement of the vheicle)

Its technically a modification of an existing engine but its not an engine thats in any kind of use (I am the lead developer on a huge code modification/rewrite for the game Command & Conquer Renegade which used a custom engine called W3D and physics/engine code that only ever got used for that game) so for all intents and purposes its totally new code.

Oh and no the source code was never released, this code modification is done via a boatload of reverse engineering and C++ work and stuff (so we patch into the engine so it calls our new code where we need it to and we call back into the engine where we need to)

Any examples out there of how to do an IK solver for leg movement?

IK solvers have two problems: Either there are infinite solutions or none.
But because our body is made for walking / running we get away with a very simple 'solver' for this purpose.
Below is the simplified solution i use (a bit hard to read, but it shows necessary complexity).
Most probably you do not need to define and care for joint limits as long as your units do only basic movement,
and it should not be necessary to read papers on IK solvers, because they focus on harder problems.

How it works:
Take a line from hip to target and stretch leg along that line.
If target distance is shorter than leg length, bend knee accordingly.
Set foot orientation to target.

So you see it's very easy.
Complexity arises because bones and joints each have their own spaces we need to tackle and so forth.
You may wanna start with a 2D case to feel safe.

After the IK solver is working, you only need to care for target foot positions.
For now i keep the swivel angle to a constant value keeping the knees pointing forwards.
For turning and walking smaller circles it would look better to modify it a bit.

void Ragdoll::IKSolveLegChainEffSimplyfied (Chain &chain, BodyInfo *bodyInfos, 
	float swivelAngle, // Sit on a chair and keep your foot on the ground. You can rotate your knee arond the line from hip joint to ankle joint without moving foot or pelvis - that's why we need to provide swivelAngle to avoid infinite solutions
	sVec3 tPos, // target ankle joint position
	sQuat *tOrn) // target foot orientation
{
	float limitShrink = 0.0; // tolerance to keep from max joint limits

	Target &tUpper = chain.target[Chain::UPPER];	// bone upper leg
	Target &tLower = chain.target[Chain::LOWER];	// bone lower leg
	Target &tEff = chain.target[Chain::EFF];		// bone foot

	RagdollJoint &jUpper = *tUpper.joint;			// joint pelvis - upper leg (hip)
	RagdollJoint &jLower = *tLower.joint;			// joint upper leg - lower leg (knee)
	RagdollJoint &jEff = *tEff.joint;				// joint lower leg - foot (ankle)

	sQuat qBase, qUpper, qLower, qEff;

	qBase =	bodyInfos[jUpper.index[1]].orn;			// pelvis orientation in world space
	qUpper = bodyInfos[jUpper.index[0]].orn;		// upper leg orientation in world space
	qLower = bodyInfos[jLower.index[0]].orn;		// lower leg orientation in world space
	qEff = bodyInfos[jEff.index[0]].orn;			// foot orientation in world space
	
	float lUpper = tUpper.boneLength;
	float lLower = tLower.boneLength;
	float lSum = lUpper + lLower;

	float curTwist, curSwing;
	sVec3 axis; float angle;
	sQuat rot;

	sQuat oB, oU, oL; // new bone orientations
	sVec3 pB, pU, pL; // new bone positions
	
	oB = qBase;
	pU = tUpper.cPos;
	
	// measure hip - target dist
	
	sVec3 dUT = tPos - pU;
	float lenUT = dUT.Length();
	if (lenUT < FP_EPSILON) return;
	dUT /= lenUT;
	
	sQuat oBunmod;
	sQuat oUunmod;

	sVec3 dL, dU;
	
	{
		// upper...

		float angU = 0;		
		if (lenUT < lSum) // bend knee if target dist is sharter than leg length
		{
			angU = acos (min(1.0, max(-1.0, (lenUT*lenUT + lUpper*lUpper - lLower*lLower) / (2.0 * lenUT * lUpper))));
		}

		oU = oB * jUpper.localRot1  * jUpper.localRot0.Inversed();
		rot.FromVecToVecR (dUT, oU.XAxis()); // X axis = axis of rigid body capsules per bone
		oU = rot * oU;

		oU *= sQuat::rotationX (-swivelAngle);
		oU *= sQuat::rotationZ (angU);

		sQuat oUn;
		jUpper.CalcTwistSwingLimitTarget (oUn, curTwist, curSwing, oU, oB, limitShrink); // makes oUn the relative rotation from oU to oB. Ensure this does not violate joint limits (never happens when walking or running)

		oU = oUn;
		oU.Normalize(); // oU finished
		dU = oU.XAxis();


		oUunmod = oU;
		oU *= chain.upperOffset;
		jUpper.CalcTwistSwingLimitTarget (oU, curTwist, curSwing, oU, oB, limitShrink);
		oU.Normalize();
		dU = oU.XAxis();

		
		// lower...

		pL = pU + dU * tUpper.boneLength;
		sVec3 lTar = oU.Inversed().Rotate (sVec3(tPos - pL));

		sVec3 lTarQ (lTar[0], lTar[1], 0);
		float len = lTarQ.SqL();
		if (len > FP_EPSILON)
		{
			len = sqrt(len);
			lTarQ /= len;
			angle = atan2 (lTarQ[1], lTarQ[0]); // knee angle
		}
		else angle = 0;
		if (angle > jLower.twistLimitAngleP - limitShrink) angle = jLower.twistLimitAngleP - limitShrink; // knee joint limits
		if (angle < jLower.twistLimitAngleN + limitShrink) angle = jLower.twistLimitAngleN + limitShrink;

		oL = oU * sQuat::rotationZ (angle);
		oL.Normalize(); // lB finished

	}



	// apply upper & lower leg (set joint targets for simulation)
	{
		sQuat oU1 = oB * jUpper.localRot1;
		sQuat oU0 = oU * jUpper.localRot0;
		sQuat rotUpper = oU1.Inversed() * oU0;
		rotUpper.SafeNormalize();
		jUpper.targetOrn = rotUpper;
		
		sQuat oL1 = oU * jLower.localRot1;
		sQuat oL0 = oL * jLower.localRot0;
		sQuat rotLower = oL1.Inversed() * oL0;
		rotLower.SafeNormalize();		
		jLower.targetOrn = rotLower;
	}


	// foot (just set to target and ensure joint limits)...
	if (tOrn)
	{
		//float effSpeed = 1;

		sQuat eB = *tOrn;
		float limitTwist = jEff.CalcTwistSwingLimitTarget (eB, curTwist, curSwing, eB, oL, limitShrink); // joint limits

		sQuat oE1 = oL * jEff.localRot1;
		sQuat oE0 = eB * jEff.localRot0;
		sQuat rotEff = oE1.Inversed() * oE0;
		rotEff.SafeNormalize();
		jEff.targetOrn = rotEff;
	}

}

struct Target // just some joint data
{
	sVec3 cPos; // position of the joint (not the bone)
	float boneLength;
	RagdollJoint* joint;
}