Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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

enter image description here

share|improve this question
1  
No I am trying to calculate the angle the ship needs to move in order to intercept the planet. –  Ausa May 14 at 12:01
4  
This would probably work better in math.stackexchange.com.. –  Jari Komppa May 14 at 12:32
2  
Is your ship able to change speed and direction, or are those constant? Also, this question about avoiding having missiles circle a target might be helpful. –  thegrinner May 14 at 14:53
4  
To clarify, is the situation? given for the planet: orbit centre, orbit radius, angular speed, current location; for the ship: current location, current speed; determine direction of motion for ship in order to intercept planet –  AakashM May 14 at 15:45
3  
As an interesting historical note: planets usually rotate in the same direction as their orbit, which is therefore also anticlockwise as seen from above the northern hemisphere. From this fact we can deduce that sundials were invented in the northern hemisphere. Had sundials been invented in the southern hemisphere then clockwise would be the other way. –  Eric Lippert May 14 at 22:41

6 Answers 6

up vote 3 down vote accepted

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;
}

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.

share|improve this answer
1  
Lots of good answers here, also some interesting alternative options but from what I already had this solutions looks the best for my instance. I have created a little JavaScript demo of my results. Demo –  Ausa May 15 at 12:10

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).

share|improve this answer
1  
You may want to run 2 iterations of this when starting an intercept course, otherwise you may see the ship flicker between two directions momentarily (the second guess can be much better than the first, and result in a very different heading - particularly if the ship is close to or within the planet's orbit) –  DMGregory May 14 at 19:36
1  
@DMGregory Oh! We could just take the current Position of the Planet instead of the Orbit Center as the starting point. When we are close that is much closer, if we are far away it doesn't matter. –  API-Beast May 14 at 21:28
    
It's also worth noting that this works best when the planet moves slowly compared to the ship. If the planet's speed is comparable to or greater than the ship's, you may see oscillations in the ship's path. At pathological speed ratios, the ship can chase the planet forever on a concentric orbit. If your planets are fast and you notice this happening, you may want to plan your entire intercept course up-front rather than iterating mid-flight. –  DMGregory May 14 at 22:16

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.

Line intersecting with circle

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 + μv (where v is a vector, http://en.wikipedia.org/wiki/Euclidean_vector), you insert the line into the circle formula and get

|p0 + μv - c|^2 = r^2

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

(p0 + μv - c)•(p0 + μv - c) = r^2

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

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

Assume that |v| = 1 and we have

μ^2 - 2μ(a•v) + |a|2 - r^2 = 0

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

μ = a • v +- sqrt((a • v)^2 *a^2 – r^2)

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

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

Otherwise, this gives us two μ-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 μ-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 + μv gives us the coordinate, and the μ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.

share|improve this answer
8  
Good analysis, but it doesn't appear to answer the question (clarified in a comment): "No I am trying to calculate the angle the ship needs to move in order to intercept the planet." You are taking the ship's angle as a given and calculating the position of the planet, instead of the other way around. –  Chaosed0 May 14 at 14:53
3  
Not going to downvote this because it's useful analysis, but I agree with @Chaosed0 that it does not answer the question. In your summary you say "Choose a line for your ship..." but choosing that line is exactly the hard part. –  Drake May 14 at 15:40
    
Ah, shoot... I missed that. You are correct. Feel free to edit it in any way. I don't have the time right now. –  Tholle May 14 at 15:46

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*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.

x = x0 + r*cos(w*u + a)

y = y0 + r*sin(w*u + a)

t = u

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:

u * v = sqrt( (x0 + r*cos(w*u + a))^2 + (y0 + r*sin(w*u + a))^2 ) =>

u^2 * v^2 = (x0 + r*cos(w*u + a))^2 + (y0 + r*sin(w*u + a))^2 =>

u^2 * v^2 = x0^2 + y0^2 + r^2 + 2*x0*r*cos(w*u + a) + 2*y0*r*sin(w*u + a)

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

share|improve this answer

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!

share|improve this answer

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.

Unfortunately, without latex, I can't format this answer very well, but we'll attempt to make do. 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
=> s_a = 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.

share|improve this answer
2  
I would love to have TeX enabled for this site. It would make some graphics related stuff (e.g. vector, matrices, quaternions..) easier to represent. –  mvw May 15 at 11:53

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.