AI control for a ship with physics model

Question

I am looking for ideas how to implement following in 2D space. Unfortunately I don't know much about AI/path finding/autonomous control yet.

Let's say this ship can move freely but it has mass and momentum. Also, external forces might affect it (explosions etc). The player can set a target for the ship at any time and it should reach that spot and stop.

Without physics this would be simple, just point to the direction and go. But how to deal with existing momentum and then stopping on the spot? I don't want to modify ship's placement directly.

edit: Just to make clear, the physics related math of the ship itself is not the problem.

Answer 1

Have a look at steering behaviors. Especially seek and arrival might be interesting for your needs. These behaviors will also work when some other influences like an explosion changes the ships position temporarily.

Answer 2

It's not an easy problem to get exactly right. You have two choices, although the specifics of each solution vary:

A mathmatical solution. If your physics system is simple enough you can create the closed form for your motion and calculate when you need to start applying a braking force to stop at a point. If your braking force is a constant and you have no air resistence, this should decompose to a quadratic.

An emperical solution. You can use a hand-tuned PID controller or actually record the braking distances for your ship in your physics system: in a testbed, brake the ship from max speed down to a stop, recording the distance travelled and speed every small timestep. Store the resultant distance/speed graph in a data directory.

At run time, reconstruct the graph and plug in your current speed and target speed to get out a distance. At this distance from your target point you need to be at full brake.

The advantage of this approach is that you can use it to brake exactly to any speed. The disadvantage is that if your brakes have to ramp on or off, you'll never be exactly on the curve.

Answer 3

As said before this situation is perfect for steering behaviours, but I'd just like to extend on it slightly. The Arrive behaviour would be perfect for this scenario. You might also want to take obstacles into account as well. You can make use of the Obstacle Avoidance behaviour here as well.

Unfortunately, http://www.red3d.com/cwr/steer/ doesn't provide source code for the behaviours. However, Programming Game AI by Example does and explains the behaviours in easy to understand chunks. If you can't get the book you can always get the source code here: http://www.wordware.com/files/ai/

Furthermore, if you want to extend your movement to include pathfinding, you can have a pathfinder class that calculates the path (perhaps as a collection of 2D vectors) and use the Path Follow steering behaviour to add that into the mix too.

The source code I've linked to also provides three different methods of combining these steering behaviours together as well.

Hope that helps.

Answer 4

Steering towards a position is not too difficult, but I personally struggled for a while with the problem of steering towards a position and reaching it at a specific speed, or following a path with speed constraints.

I solved the problem using a Hermite curve. Set p0 and m0 to the position and velocities of your ship, p1 and m1 to your target position and speeds. This assumes you want the ship to follow one second after the target. Compute the second derivative of p(0), that will give you the acceleration to apply to your ship.

Here is the code for the second derivative (in F#, I hope you can adapt it to your language of choice; sq() computes the square, single quotes not interpreted as quotes but as characters, they are part of the identifier):

    let h'' t =
        let h00'' t = 12.0 * t - 6.0
        let h10'' t = 6.0 * t - 4.0
        let h01'' t = -12.0 * t + 6.0
        let h11'' t = 6.0 * t - 2.0

        let t = (t - t0) / diff_t

        (sq (1.0 / diff_t)) *
        ((h00'' t * p0) +
         (h10'' t * diff_t * v0) +
         (h01'' t * p1) +
         (h11'' t * diff_t * v1))

Note that if your ship is subject to external forces (e.g. gravity from planets), you will have to account for that when calculating the thrust from the acceleration.

Answer 5

Found this recently - steering behaviors in JavaScript & Processing:

http://shawnldoria.com/works/steering-behaviors.html

Answer 6

I think your ship should have parameters like: position and velocity.

Velocity is in each frame sum of all forces (like gravity, explosions, user input etc) and can also have some kind of damp.

Position is calculated from last position plus velocity * time_step.

However, with this it can be difficult to implement stopping on target.