19
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ I expect to be encountering a similar issue to this soon; I look forward to seeing answers to this. \$\endgroup\$
    – Bill
    Feb 3, 2011 at 15:59

6 Answers 6

15
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ +1. For a 2D space game I would recommend using steering behaviours as your framework, and using one of my answers as a component within that framework. \$\endgroup\$
    – tenpn
    Feb 3, 2011 at 15:11
  • \$\begingroup\$ Was going to suggest the same think when I read the question. I've used steering behavior alot, it's easy and allows for some pretty nice AI/motion. \$\endgroup\$
    – dotminic
    Feb 4, 2011 at 16:08
5
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ The red3d.com link doesn't provide sources directly, but there's a link right on that page to OpenSteer (opensteer.sourceforge.net) which is an open source implementation of steering behaviours. \$\endgroup\$
    – bummzack
    Feb 6, 2011 at 12:40
  • \$\begingroup\$ Ahh didn't know that, thanks. Although, I looked at the source for OpenSteer and found it easier to look at the more obvious in your face code found in Buckland's book. Especially when starting out. \$\endgroup\$
    – Ray Dey
    Feb 6, 2011 at 16:23
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

Found this recently - steering behaviors in JavaScript & Processing:

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

\$\endgroup\$
-3
\$\begingroup\$

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.

\$\endgroup\$
1
  • 3
    \$\begingroup\$ -1 It sounds like Petteri Hietavirta knows how use use a basic physics system. So your answer to this question is that stopping on a target is too difficult? \$\endgroup\$ Feb 4, 2011 at 16:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .