How can I Intercept object with a circular motion

Question

I am creating a 2d space game and need to make the spaceship intercept a planet. I have working code for straight line intercepts but cannot figure out how to calculate the planets location in a circular orbit.

The game is not scientifically accurate so I am not worried about inertia, gravity, elliptical orbits, etc.

I know the spaceships location and speed and also the planets orbit (Radius) and speed

Answer 1

An analytic solution to this is difficult, but we can use binary search to find a solution to within the required accuracy.

The ship can reach the closest point on the orbit in time t_min:

shipOrbitRadius = (ship.position - planet.orbitCenter).length;
shortestDistance = abs(shipOrbitRadius - planet.orbitRadius);
t_min = shortestDistance/ship.maxSpeed;

The ship can reach ANY point on the orbit in time less than or equal to t_max:

(Here, for simplicity, I assume the ship can drive through the sun. If you want to avoid this then you will need to switch to non-straight-line paths for at least some cases. "Kissing circles" may look nice and orbital mechanics-y, without changing the algorithm by more than a constant factor)

if(shipOrbitRadius > planet.orbitRadius)
{
   t_max = planet.orbitRadius * 2/ship.maxSpeed + t_min;
}
else
{
   t_max = planet.orbitRadius * 2/ship.maxSpeed - t_min;
}

If our orbital period is short, we might be able to improve on this upper bound by choosing the t_max to be the first time after t_min that the planet makes its closest approach to the ship's start position. Take whichever of these two values of t_max is smaller. See this later answer for a derivation of why this works.

Now we can use binary search between these extremes, t_min and t_max. We'll search for a t-value that gets the error close to zero:

error = (planet.positionAtTime(t) - ship.position).squareMagnitude/(ship.maxSpeed*ship.maxSpeed) - t*t;

(Using this construction, error @ t_min >= 0 and error @ t_max <= 0, so there must be at least one intercept with error = 0 for a t-value in-between)

where, for completeness, the position function is something like...

Vector2 Planet.positionAtTime(float t)
{
  angle = atan2(startPosition - orbitCenter) + t * orbitalSpeedInRadians;
  return new Vector2(cos(angle), sin(angle)) * orbitRadius + orbitCenter;
}

Note that if the planet's orbital period is very short compared to the ship's speed, this error function may change signs several times over the span from t_min to t_max. Just keep track of the earliest +ve & -ve pair you encounter, and continue searching between them until the error is close enough to zero ("close enough" being sensitive to your units and gameplay context. The square of half the frame duration may work well - that ensures the interception is accurate to within a frame)

Once you have a nice error-minimizing t, you can just point the ship at planet.positionAtTime(t) and go full throttle, confident that the planet will reach that point at the same time you do.

You can always find a solution within Log_2((2 * orbitRadius/ship.maxSpeed)/errorThreshold) iterations. So for example, if my ship can traverse the orbit in 60 frames, and I want an intercept accurate to within one frame, I'll need about 6 iterations.

Answer 2

Let's not over-complicate this. This is not a "perfect" solution but should work for most games and any imperfection should be invisible to the player.

if(!OldTargetPoint)
  TargetPoint = PlanetPosition;
else
  TargetPoint = OldTargetPoint;
Distance = CurPosition - TargetPoint;
TimeNeeded = Distance / Speed;
TargetPoint = PlanetPositionInFuture(TimeNeeded);
SteerTowards(TargetPoint);
[...repeat this every AI update, for example every second...]

1. Calculate the time needed to reach the target point.
2. Calculate at what position the planet will be at the calculated time.
3. Move towards the calculated point.
4. Repeat

This works because the nearer the spacecraft gets towards the lower the error becomes. So the calculation becomes more stable over time.

The error is the difference between the calculated needed time to reach the planet (TimeNeeded) and the actual time needed to reach the planet (after taking into account the new TargetPoint).

Answer 3

Let's start off by taking a look at the math behind the problem.

Step 1:

Finding the intersection between a line and a shape is just a matter of inserting the equation of the line in the equation of the shape, which is a circle in this case.

Take a circle with center c and radius r. A point p is on the circle if

$$ |p - c|^2 = r^2 $$

With a line expressed as \$p = p0 + \mu v\$ (where v is a vector, http://en.wikipedia.org/wiki/Euclidean_vector), you insert the line into the circle formula and get

$$|p0 + \mu v - c|^2 = r^2$$

The squared distance can be rewritten as a dot product (http://en.wikipedia.org/wiki/Dot_product).

$$(p0 + \mu v - c)•(p0 + \mu v - c) = r^2$$

Define \$a = c - p0\$ and rewrite to \$(\mu v - a)•(\mu v - a) = r^2\$

Perform the dot product and we get \$\mu ^2(v•v) - 2\mu (a•v) + a•a = r^2\$

Assume that \$|v| = 1\$ and we have

$$\mu ^2 - 2\mu (a•v) + |a|2 - r^2 = 0$$

which is a simple quadratic equation, and we arrive at the solution

$$\mu = a • v +- sqrt((a • v)^2 *a^2 – r^2)$$

If \$\mu < 0\$, the line of the ship in your case does not intersect with the planets orbit.

If \$\mu = 0\$, the line of the ship will simply touch the circle in one point.

Otherwise, this gives us two \$\mu \$-values that corresponds to two points on the orbit!

Step 2:

So we can define a line for the ship, and out of that we get either 0, 1 or 2 \$\mu \$-values. If we get 1 value, use that one. If we get 2, simply choose one of them.

What can we do with this? Well, we now know the distance the ship has to travel and what point it will end up in!

\$p = p0 + \mu v\$ gives us the coordinate, and the \$\mu v\$-component gives us how far is will have to travel. Simply divide this last component with the speed of your ship to get how much time it will take for it to get there!

Now, all that is left to do is to calculate where the planet should be when the ship begins coming towards it's orbit. This is easily calculated with so called Polar coodinates (http://mathworld.wolfram.com/PolarCoordinates.html)

$$x = c + r*cos(θ)$$

$$y = c + r*sin(θ)$$

And since you had the speed of you ship, and we have the time it will take for the ship to reach the orbit, and where it will collide, we simply move the planet back \$t*angularVelocity\$ degrees in it's orbit, and we are done!

Summary

Choose a line for your ship, and run the math to see if it collides with the planets orbit. If it does, calculate the time it will take to get to that point. Use this time to go back in orbit from this point with the planet to calculate where the planet should be when the ship starts moving.

Answer 4

Here are two slightly "out of the box" solutions.

The question is: given that the ship moves in a straight line at a given velocity, and the planet moves in a circle of given radius at a given angular velocity, and the starting positions of the planet and ship, determine what direction vector the ship's straight line should be in to plot an intercept course.

Solution one: Deny the premise of the question. The quantity that is "slippable" in the question is the angle. Instead, fix that. Point the ship straight at the center of the orbit.

• Calculate the position at which the ship will encounter the planet; that's easy.
• Calculate the distance from the ship to the intercept position ; also easy.
• Calculate the time it will take until the planet next reaches the intercept position. Easy.
• Divide the distance from the ship to the intercept by the time until the planet gets to the intercept.
• If that is smaller than or equal to the maximum speed of the ship, you're done. Set the ship moving at that speed straight towards the sun.
• Otherwise, add the orbital period of the planet to the time and try again. Keep doing that until you get a speed that is within reason for the ship.

Solution two: Don't do it on autopilot at all. Make a mini-game where the player has to use thrusters to approach the planet, and if they hit it at too high a relative speed, they blow up, but they have limited fuel as well. Make the player learn how to solve the intercept problem!

Answer 5

If you dont' want to use polar coordinates, consider that the all the possible positions of the ship form a cone in \$(x, y, t)\$ space. The equation for this is

$$ t \cdot v = \sqrt{x^2 + y^2} $$

where \$v\$ is the the ship velocity. It is assumed the ship starts at zero.

The position of the planet in space and time can be parametrized by e.g.

$$ \begin{align} x &= x_0 + r \cdot cos(w \cdot u + a) \\ y &= y_0 + r \cdot sin(w \cdot u + a) \\ t &= u \end{align} $$

where \$u\$ goes from \$0\$ upwards. \$w\$ is the angular speed and \$a\$ is the starting angle of the planet at time zero. Then solve where the ship and planet could meet in time and space. You get an equation for \$u\$ to solve:

$$ \begin{align} u \cdot v &= \sqrt{ (x0 + r \cdot cos(w \cdot u + a))^2 + (y_0 + r \cdot sin(w \cdot u + a))^2 } \implies\\ u^2 \cdot v^2 &= (x_0 + r \cdot cos(w \cdot u + a))^2 + (y_0 + r \cdot sin(w \cdot u + a))^2 \implies\\ u^2 \cdot v^2 &= {x_0}^2 + {y_0}^2 + r^2 + 2 \cdot x_0 \cdot r \cdot cos(w \cdot u + a) + 2 \cdot y_0 \cdot r \cdot sin(w \cdot u + a) \end{align} $$

This equation needs to be solved numerically. It may have many solutions. By eyeballing it, it seems it always has a solution

Answer 6

Here's part of a solution. I didn't get to finish it in time. I'll try again later.

If I understand correctly, you have a planet's position & velocity, as well as a ship's position and speed. You want to get the ship's movement direction. I'm assuming the ship's and planet's speeds are constant. I also assume, without loss of generality, that the ship is at \$(0,0)\$; to do this, subtract the ship's position from the planet's, and add the ship's position back onto the result of the operation described below.

Let:

• \$s_s\$ = the ship's speed (\$s_s.x, s_s.y\$, likewise)
• \$s_a\$ = the ship's bearing (angle of movement, what we want to calculate)
• \$p_p\$ = the planet's initial position, global coords
• \$p_r\$ = the planet's distance (radius) from the center of orbit, derivable from \$p_p\$
• \$p_a\$ = the planet's initial angle in radians, relative to the center of orbit
• \$p_s\$ = the planet's angular velocity (rad/sec)
• \$t\$ = the time to collision (this turns out to be something we must calculate as well)

Here's the equations for the position of the two bodies, broken down into components: $$ ship.x = s_s.x * t * cos(s_a) $$ $$ ship.y = s_s.y * t * sin(s_a) $$ $$ planet.x = p_r * cos(p_a + p_s * t) + p_p.x $$ $$ planet.y = p_r * sin(p_a + p_s * t) + p_p.y $$

Since we want \$ship.x = planet.x\$ and \$ship.y = planet.y\$ at some instant \$t\$, we obtain this equation (the \$y\$ case is nearly symmetrical):

$$ s_s.x * t * cos(s_a) = p_r * cos(p_a + p_s * t) + p_p.x $$ $$ s_s.y * t * sin(s_a) = p_r * sin(p_a + p_s * t) + p_p.y $$

Solving the top equation for \$s_a\$:

$$ s_s.x * t * cos(s_a) = p_r * cos(p_a + p_s * t) + p_p.x \\ \implies s_a = \frac{arccos((p_r * cos(p_a + p_s * t) + p_p.x)}{(s_s.x * t))}$$

Substituting this into the second equation results in a fairly terrifying equation that Wolfram alpha won't solve for me. There may be a better way to do this not involving polar coordinates. If anyone wants to give this method a shot, you're welcome to it; I've made this a wiki. Otherwise, you may want to take this to the Math StackExchange.

Answer 7

I would fix the location at which to intercept (graze the circle, at the "outgoing" side of the orbit.)

Now you just have to adjust the spaceship's speed so that planet and ship reach that point at the same time.

Note that the rendez-vous could be after N more orbits, depending how far away the ship is, and how fast the planet is orbiting the star.

Pick the N that in time, comes nearest to the ship's journey duration at current speed.

Then speed up or slow down ship to match the timestamp for those N orbits exactly.

In all this, the actual course is already known! Just not the speed.