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

Question

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 1

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.

Answer 2

Approach the player ship

With the major problem being for the AI to calculate 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.

You'll need to solve these problems iteratively, as there's no "perfect curve" because ships are in constant motion, with their motion affected by player twitches, sea and wind conditions. So the best your AI can do is to try to approach, updating the course every few frames (10x a second, for instance). Also, it doesn't need a full battle plan at each moment, it just needs to worry about what it needs to do to get to the next stage of the plan - "let's cross that bridge when we get to it."

I would suggest approaching on a line that is tangent to a circle of some radius representing the distance we want to be from the enemy ship. So say your maximum firing range is 500 yards, but you want to be quite accurate, so you decide on getting quite close, 250 yards. Then you aim for the nearest edge of a circle of 250 yards radius, that surrounds the target ship. Or maybe not the nearest, but rather the one that will bring you parallel to their current heading.

Keep guns trained on player

This will come second to just getting close to (or getting away from) the target. Once that has been achieved, you can begin to think about gradually changing the tactic to "line up a broadside".

Remember also that historically, the guns didn't move a whole lot inside their gunports, so you should expect maybe 10 degrees of movement to be a lot, and that's you taking artistic license! If I remember my naval history correctly, carronades were something of an exception and could be wheeled around freely above decks, but had a shorter range than main cannon.

Bring player in line

There is some variability on defining this. If you want to deliver a full broadside, you need to check that your current motion vector matches the enemy ship's, and that the centres of each ship line up on a perpendicular between those two parallel motion vectors. Otherwise you can be as parallel as you like, but you'll still miss!

Also, how parallel the two facing vectors are, is up to your own code; use the dot product here to check similarity, and some epsilon value to check equality within some margin of error. In history, there were times where they took shots even when not parallel, for example targeting the quarterdeck from astern. May even be that it depends on how desperate the AI is feeling, or how much it thinks it can gain by firing at the stern or bow of an enemy. P.S. I would imagine there is a much higher chance of deflection when firing directly at the bow, due to its shape.

Be able to manoeuvre around obstacles

This is the least of your worries, and in any case, as in many historical naval battles, collisions will happen and ships will sink if only because of the fickle nature of the ocean and winds, in spite of the crew's best efforts. Of course, any time you get too close to another ship, especially when facing vectors are different (i.e. one is going to plunge right into another), emergency manouevres will need to engage. Same applies for land or rocks.

Get the rest right first - movement, alignment, firing - then worry about this at the end.

Considering all the above...

You need to order your implementation according to importance, start simple and see what evolves:

• Proximity to enemy (approach or escape)
• Alignment (once fairly close in, but not too close, as we need space/time to do get aligned)
• Side-to-side (matching position / speed once aligned)
• Firing or boarding (once close up)
• Obstacle avoidance

In terms of the first two points, I would set up debug circles and projected curves and watch them change size / shape as AI thinking adapts to the current situation. This should really help you to visualise the situation and work with it more easily than trying to sum everything up in your head.

About realistic winds... I would not worry about that early on, if at all. For now just assume that ships are under their own power. Then if you want to, you can gradually introduce the effects of (and indeed, need for) wind-powered sailing, later.

To sum up, AI will constantly change tack (arr! maritime jokes!), and the rest relies on vector maths.