Spaceship acceleration for following waypoints

Question

I'm creating a turn based space ship strategy game with simultaneous turn resolution similar to Steam Birds. After all the orders are given, the ships run through a real time simulation where they rotate, accelerate and shoot each other.

The physics work similar to the old asteroids game. At the beginning of each turn the ships can be given a constant acceleration, they will then rotate into position so that their engines will be pushing them in the acceleration direction, and they will maintain the acceleration for the rest of the turn. Each ship has a maximum acceleration value based on their engine strength and mass.

I'm having trouble calculating the proper accelerations for the AI ships to get them to go where they need to go.

I had a diagram here, but this video makes it much more clear what I'm trying to do. This is a player controlled ship moving through some asteroids in the same way I need an AI ship to move.

I've got a ship moving through some obstacles, there are waypoints defined that will guide the ship through the obstacles. There are a couple of things I'm trying to calculate:

• I need to calculate how much the ship has to slow down to make a fairly tight turn so that it doesn't run into obstacles
• I need to calculate the acceleration to get the ship to change directions at the waypoint, again making sure that the turn is fairly tight
• Between the waypoints I would like the ship to accelerate to as high a speed as it can and still have time to slow down to make the turn

Any help here would be greatly appreciated. Thanks.

Answer 1

I'm going to assume that the rotation of the engine is purely visual, and the acceleration during any thrust is in a constant direction. (If we're accelerating in a rotating direction, the math for planning the trajectory gets a LOT more complicated very quickly, so I'd recommend turning off the thruster when turning, and just accounting for that as a linear segment in the path)

Quadratic Bézier curves are isomorphic to a point moving with constant acceleration, so you can think of this problem as a matter of planning a quadratic Bézier spline under certain constraints.

At the beginning of each turn, two of your control points are fixed, and you're making a choice for the third point (unless the ship is allowed to coast without acceleration for a span, that is - then add another two variables for pre-thrust and post-thrust drift)

Point A is where the ship begins this turn.

Point B is where the ship would be halfway through the turn if it were not thrusting. If one turn is T simulation-seconds long, then this is A + (T/2)*v1, where v1 is the velocity of the ship at the start of the turn.

Point D (not part of the curve) is where the ship would end the turn with zero acceleration. It acts as an anchor for our choice of point C...

Now we get to choose point C, where the ship will be at the end of the turn. We can select any point in a radius of (T*T/2)*max_acceleration of D. This ensures our max acceleration constraint is respected. Our velocity coming out of this turn will be parallel to C-B (specifically, it will be (C-B)*2/T).

From this, a few things follow:

1. If we want to come out of the turn with a velocity in a particular direction (say, we've passed one waypoint and want to steer toward the next one), we can draw a line with that direction through point B. The part of that line that overlaps the circle around D includes all our options that put us on the desired trajectory, with the one furthest from B being the fastest option.

2. The turn is fully-contained within the triangle ABC, so we can check that triangle for collisions and re-plan as necessary.

3. If the radius of the circle is r = max_acceleration * (T*T/2), then the maximum angular change we can effect in one turn is:

   180° if (T/2)*v1.magnitude <= r

   asin(r/((T/2)*v1.magnitude)) = asin(T * max_acceleration/v_1) otherwise

So, if you need to pivot through an angle of theta in one turn, slow down to (2 * r)/(T * sin(theta)).

If you're still n turns away from this rotation, then you can safely travel up to nmax_accelerationT faster than this limit and still slow down in time. If you're going faster than that, start braking.

Note that you can apply this recursively to get the AI thinking one or more steps ahead - any choice for point C this turn dictates A, B, and D next turn. So you can choose C this turn in such a way that the circle around next turn's D includes next turn's goal, and reject choices of C that take you too far off course even with a full turn to correct it.

There are still a lot of judgement calls for you to make in designing your AI, but I hope this provides a useful framework for making those decisions in a way that's appropriate for your game.