Drone targeting

Imagine a "drone" and a target point on a 2d plane. There are eight parameters:

P = my position
Q = target position
V = my velocity
I = my moment of inertia
w = my angular velocity
s = my angular position
T = max thrust
U = max torque

(we'll just say the target is stationary)

The drone's job is to get to the target as fast as possible, obeying max torque and max thrust. There are only two ways to apply the torque, since this is only in a 2d plane. Thrust is restricted to only go in one direction relative to the orientation of the craft, and cannot be aimed without rotating the drone. Neglect any resistance, you can just pretend it is floating around in 2d outer space. Let's say the drone checks an equation at time interval t (maybe something like every .01 seconds), plugs in the parameters, and adjusts its torque and thrust accordingly. What should the equations for thrust and torque be?

• If thrust can only go in one direction, you're never going to change directions. – MichaelHouse Apr 23 '13 at 16:10
• I should have specified more clearly — you cannot gimbal the thrust, i.e. the thrust can only go in one direction relative to the orientation of the craft. You can still rotate the craft and change the direction of thrust. – Gus Apr 23 '13 at 16:16
• Is this question related to nodewar? – Seth Battin Apr 25 '13 at 18:23
• Then I think I can post a good solution for you (a little later tonight). :) – Seth Battin Apr 25 '13 at 21:49
• This question needs a more descriptive title, but I can't think of a good one. Halp? – Anko Apr 26 '13 at 13:40

In light of your question's context, http://nodewar.com/, there are a couple specific considerations for your solution:

1. You have a (low) maximum angular velocity, and enough maximum torque to reach it in very short time.
2. Your drone and target each have velocity and external acceleration unrelated to thrust (gravitation abounds).
3. Your desired target changes so frequently that trying to aim perfectly would be a waste. You should try to get close, and correct it every frame.

These methods are what I determined to work for reaching a desired acceleration.

Acceleration, not velocity

Because you have a given velocity already, and your target is moving, you don't need thrust toward a point. You need thrust to change your velocity to what it should be. This means that your ship needs to point not toward where it is going, but in the direction in which it should accelerate.

// My target velocity is for maintaining a circular orbit.  Yours may differ.
// Earlier, I calculated total gravity and the perpendicular direction.
// You may wish to subtract gravity from your total, rather than match it.
var targetVel = o.lib.vec.times(lateralDir, targetVelMag);

var targetAccel = lv.sum(
o.lib.vec.diff(targetVel, o.me.vel),
o.lib.vec.times(gravity, 1 / o.me.mass)
);

Steering toward the right heading

You have an acceleration vector, now you want to apply it. Determine how far you need to rotate. I probably used more steps than required here, but rotational coordinates confound me, and I think the uncapped ship rotation value is a bug in the API anyway.

// convert acceleration to an angle
var polar = o.lib.vec.toPolar(targetAccel);
var traj = polar;

// constrain the angle to +/-2PI, because the ship's rotation is not limited
// by default
var fixed_rot = o.lib.ang.rescale(o.me.rot);

// limit the correction to be +/-1PI
var traj_correction = traj - fixed_rot;
if (traj_correction > (Math.PI)){
traj_correction = (2 * Math.PI) - traj_correction;
} else if (traj_correction < (-1 * Math.PI)){
traj_correction = (2 * Math.PI) + traj_correction;
}

A simple formula. There is no harm in turning all the time, so don't bother applying partial torque values. If you need a small correction in angular velocity, you get to make this determination many times per second, anyway.

if (traj_correction > 0){
torque = 1;
} else if (traj_correction < 0){
torque = -1;
}

A less simple formula. There will come a point where you don't want to continue turning, because you eventually want to stop. Fortunately, that angular velocity cap means that you can rapidly slow down from max angular speed to zero. You only need to calculate when to do so.

var max_a_accel = c.MAX_TORQUE / o.me.m_i;
var a_deccel_time = Math.abs(o.me.a_vel) / max_a_accel;
// the same math as linear acceleration, now in angles.
var stopping_angle = 0.5 * max_a_accel * a_deccel_time * a_deccel_time;

if (stopping_angle >= Math.abs(traj_correction)){
// slowdown required.  Reverse torque
torque *= -1;
}

After tweaking the code above to suit your needs, your ship should rapidly and precisely rotate to whatever angle you gave it to target.

Ramming speed

So, when to thrust? Again, the rapid change of the target and other factors create great difficulty in resolving an exact solution. Don't try to.

// if the heading is close to the final value, thrust.
if (Math.abs(traj_correction ) < 0.02) {  // about 1 degree
if (true
// some logical test, in case you don't want to accelerate past
// a maximum speed, or some such.  Not required for your stated purpose.
){
thrust = 1;
}
}

For those cases where you need partial thrust, you can again rely on the fact that you can choose between 0 and 1 thrust many times per second. This gives you an effective partial thrust without varying the actual value.

Good luck!

• Great, thanks, this helps a lot. I will have to modify it a little I think. What's your species' name? – Gus Apr 26 '13 at 4:13
• I haven't pushed them to the ladder. They have no method to attack. :) – Seth Battin Apr 26 '13 at 4:23

A similar question, with some good answers, including the apparent name of this whole subject, "motion planning":
https://stackoverflow.com/questions/2560817/2d-trajectory-planning-of-a-spaceship-with-physics

As a programmer, I like the practicality of user470365's suggestion. However, I'll take a stab at a more rigorous approach. My suggestion here computes a full plan at the start, but I suppose you could re-evaluate as often as desired if the parameters are changing.

The Plan

1. Turn to a certain direction, d, and hold that direction.
2. Wait until a certain time, t, then do one, sustained thrust until the target is reached.

Details

I suggest iterative methods to find d and t:

1. Assuming no thrust, traverse along the drone's future trajectory using a loop and a small timestep:

• For the drone's position and velocity at this future time, find the direction, d, such that a sustained thrust will bring the drone to the target. Do this by sampling lots of directions between 0 and 360 degrees and finding the one that will bring the drone close to the target in the shortest time.
• Check to see if we have enough time between now and this future time to turn to d. (Turning is non-trivial. See discussion at end.)
• If we have enough time, then our search is complete, so break out of this loop.
2. We've now found d and t.

3. Turn to d as quickly as possible (again, see discussion below).
4. Wait until t, then start the sustained thrust.
5. The drone should eventually hit the target.

Turning

When I say "turn to d", I really mean, "do a sequence of torques such that we rotate to d as quickly as possible while also bringing angular velocity to zero". There's probably an equation for this involving current direction, current angular velocity, and max angular acceleration, but it's complicated by the wrapping behavior of angles.

• Interesting approach. So what governs our selection of that future time? It seems like any technique to determine it has its issues, so iteration there might be necessary as well. – Gus Apr 25 '13 at 21:17