path finding - How can I maneuver an AI pirate ship for a sea battle?

I'm trying to picture in my head what would be required to make an AI controlled enemy do the following in a top down pirate sailing game:

1. Approach the player ship



2. Bring player in line with port / starboard guns


3. Keep guns trained on player


4. Be able to manoeuvre around obstacles


5. Not cheat acceleration to achieve the above

When I first started thinking about the idea it was quite simple, but the more I think about it, the more complex the requirements become; with the major problem being the AI calculating perfectly the curve required to come up along side the player, or to better yet, make a pass along their bow / stern before coming along side without needing to let them quickly speed up / slow down to achieve this.

Answer

I think we can actually plan a complete curve that meets your needs, using some techniques similar to my earlier answer about spaceship waypoints.

I'm going to assume that we can model your ships' movements using Newtonian physics (ie. masses moving inertially and accelerating quadratically under constant force). Depending on how much simulation of real wind/waves/water resistance/buoyancy you're doing, this might not be fully accurate, but it should be close enough to capture the broad-scale behaviour we need to plan, with error terms that will diminish as we close in on our target.

First we need a time horizon over which to plan: "how long will it take us to reach our desired passing / parallel position?" We can estimate this iteratively, starting with a naive guess (like the total distance to the target divided by our current speed) and improving it based on the results of our last planning attempt.

As we get closer to our target position, this time horizon gets smaller and smaller, helping to diminish errors we get from using a simplified model.

Next, we need to predict where the target ship will be at that time. For instance, we could track its current velocity and acceleration and assume it will continue that behaviour. Then we can use \$\vec p(T) = \vec p_0 + \vec v_0 T + \frac 1 2 \vec a_0 T^2\$ and \$\vec v(T) = \vec v_0 + \vec a_0 T\$ to plot its expected position & velocity at the end of that time interval. You can also use more sophisticated predictors if you like.

Now we can construct our own desired position & velocity relative to this predicted target ship. Like choosing a spot nearby along our approach line so our forward guns can stay trained on it as we close. Or planning to cross a set distance ahead / behind along its velocity vector for a bow or stern pass. Or choosing a spot parallel at a given distance left or right, with matching velocity for a broadside or boarding attempt.

Now we have a target endpoint with a given velocity, and of course our ship's own starting point with a given velocity. We can join these with a cubic Bezier curve like so:

(Disclaimer: it's first thing in the morning and I won't have time to thoroughly check the math here until after work. I think that square on the T in acceleration is right, but not certain)

Our current position \$p_0\$ and target position \$p_T\$ form the anchor points of the curve.

We get our first control point \$p_A\$ by advancing from our current position by our current velocity times one third of our time horizon.

We get our second control point \$p_B\$ by backtracking from our target position by our target velocity times one third of our time horizon.

The acceleration needed to follow this curve is greatest at the very beginning \$a_0\$ and the very end \$a_T\$.

You can offset these two vectors by a constant representing how much wind/current your ship is fighting against to get the input acceleration it would need to provide to overcome the resistance and achieve this net accelerated path.

If that acceleration value is outside your ship's limits (here's where we enforce no cheats), then the time horizon we chose is too short. We're trying to close too quickly or turn too sharply. So, we increase our time horizon for the next attempt. You can do multiple attempts in a loop, or refine it iteratively frame by frame, falling back on the last good/naive approach path for one frame when planning fails.

If the needed acceleration has less magnitude than our ship's limits, then we can tighten our time horizon to approach more aggressively in our next planning update.

Bouncing between too-tight and too-loose time bounds, we can iteratively zero-in close to the edge of feasible trajectories.

Next, for collision checking, once you have a path with permissible acceleration: the entire path is contained in the convex hull of the anchor & control points, so we can use those bounds to do a crude check for any obstacles. You can then iteratively subdivide the Bezier curve into rectangular segments (similar to how we draw might Bezier curves with straight lines) to check it more precisely when that broad check hits something.

To plan around an obstacle, we use an offset from the obstacle's position (or the narrow gap between two obstacles) as our target, and repeat the same planning procedure to that intermediate point.

I haven't explicitly covered top speeds above, so the planned path might at times predict your ship moving faster than it's allowed to go in your game's actual physics simulation. As long as you still move your ship with permitted accelerations, any speed deficit should just feed back as input into the next planning iteration ("oh, we're not as far along as I thought we'd be. Oh well, I'll just plan from here instead"). Assuming you're fast enough to overtake the player ship, this should mainly happen in reasonably straight-line chase segments of the path, rather than introducing errors into the fine maneuvering once you've matched speed with it.