c# - Finding the correct speed for AI to turn to reach goal

I have a ship that travels at max speed maxSpeed and can turn rotationSpeed degrees per second. The ship always moves in the direction it is facing which means that the faster the ship is travelling the larger its turning radius is.

I know my position, and rotation and the target's position.

What I would like to figure out is whether a target is inside my turning radius at this speed, or better, what is the maximum speed I can travel at is in order to make the turn to the target without continually circling around it.

Is there an efficient(ish) way to do this?

Here is what I am thinking so far: because I know how far I am travelling per step and how much I am rotating per step, I can figure out where I will be in the next two frames. My current position is p1, my next position is p2 then p3. I can take the perpendicular bisectors of (p1, p2) and (p2, p3). Their intersection point will give me the center of a circle. I can then test if the target is in that circle.

I'm unsure if this will work in 3D (I'm unsure how to calculate a sphere with my inputs). This solution also doesn't help too much with finding the right speed at which to travel, I would have to try a few times with different speeds to find a reasonable one.

Can anyone shed some light on a better solution?

Answer

There are two ways an AI controlled unit with a bound rotation speed and an adjustable movement speed could reach a goal.

First, lets consider the challenge we are presented with so we could understand it better:

If the player is moving and rotating in constant speeds while trying to reach a goal that is on its right or left side, it will move in circles forever, never facing it's goal. The two areas that the player will circle are marked in red above.

The circular area marked in red can be computed like this:

radius = movementSpeed / rotationSpeedInRadians;
circlesCenterX = unitX + cos(unitAngle + / - PI) * radius;
circlesCenterY = unitY + sin(unitAngle + / - PI) * radius;

This results in the red circles' position and radius. We can use this to determine if a certain goal is outside the reach of the AI controlled unit if it continues to turn towards the goal's direction.

To find out if a certain item is within one of the circles, we simply calculate the distance from the circles's center:

if ((circleX - goalX)^2 + (circleY - goalY)^2 < radius^2) //goal is within red circle

There are two possible solutions for this:

1.

Build up some distance until the goal is outside the circular red area and then turn around in a u-turn like fashion. This is simple, let the unit keep moving until the check returns that the goal is not within this circle. Then you can turn around.

The other option require a bit more work to compute:

We draw an imaginary line between the AI unit and the goal. Using the angle between them:

angle = Math.atan2(goalY - unitY, goalX - unitX);

Now you need to do the following in order to compute the correct speed:

correctSpeed = rotationSpeedInRadians * (distance / 2) / cos(angle);

In order to get it working in the 3d case:

Find the plane on which the following three points reside:

1. The goal point.


2. The position of the AI unit in the previous frame.


3. The current position of the AI unit.

You could use that plane to compute the speed in the 2d way. You just need to convert the dots from their 3d values to the 2d values embedded on their common plane.

You might want to use this:

How to convert a 3D point on a plane to UV coordinates?