I'm doing a top down game where the enemies will be able to patrol. That is, at design time I'm able to say "travel through these points A, B, C, D", and the enemy will go from A->B->C->D->A, and so on. My problem is that the enemies are vehicles, and have a turning radius, so if A,B,C,D forms a square, the ship will not hit those points exactly due to its wide turning radius if it travels in straight lines. The result is that the ship travels at a tilt to reach the points. This is alright from a functional standpoint, but it looks sloppy. What I'd like is to have the ship even out its course so that it travels in horizontal and vertical lines as much as possible, correcting for its turning radius at each point. Does anyone have any ideas on how I can do this?

How about this: when you approach a waypoint, look ahead to the next sector, and start turning a distance proportional to the angle change before you actually get there.

Improve your pathfinding/navigation system so that you can not only give position constraint, but also orientation/velocity at arrival.

How about a spline?

This is a well considered problem in robotics and controls engineering. The problem you have is sometimes called kinodynamic planning (although that term has also been 'stolen' by the random tree pathfinding community) but also called constrained motion planning. To give you an overview...

There are three basic solution methodologies to the problem:

1) Pass through the waypoint at the end of the current track segment and then execute a turn to the next track segment. Because the vehicle has inertial velocity it will overshoot the next track. A simple inner-loop controller designed to minimise across track distance (with an outer loop controller maximising along track velocity) can provide a good turning behaviour. This method works well when the distance between waypoints is reasonably greater than the turn radius of the vehicle.

2) Determine the minimum radius circle that the vehicle can achieve and then connect this circle to the two track segments at the specified waypoint. There are a variety of ways to do this, but a common one is to ensure that the waypoint falls on the circles edge, so that the vehicle will be turning through the waypoint. It's then a matter of having the vehicle transition onto and off this circular track when it arrives near the waypoint.

3) Using lookahead, determine the appropriate distance from the waypoint to turn out toward the back extension of the next track segment (that is, if the next segment were extended back toward the current segment). Then, when sufficiently close to this back-segment, use a minimum radius turn to turn onto the back segment. Optimally, this turn would cease at the waypoint, so that the minimum deviation off-track occured.

Now, most of the papers you'll read assume that there is little or no background flow (drift) in the dynamic model. If you're dealing with aircraft or vessels in a fluid current, then you'll need to account for this in the turning dynamics and hence in the solution methodology. If you need to deal with this situation, I can forward you a paper specifically on solving this sort of problem. Otherwise, you'll find heaps of literature on making turns in the robotics literature. Look for keywords such as 'waypoint manoeuveres', 'waypoint tracking', 'kinodynamic motion planning', or simply grab a good book on robot motion planning and it will almost surely cover this topic.

Cheers,

Timkin