# Path following with Asteroids-like movement. Time to complete path

I'm currently learning about how to do this, but it's best to post the problem beforehand. (posting on Physics and GameDev, as you guys know your math)

It's quite difficult to explain. This specific problem revolves around a problem of creating a guidance system for rocket powered craft.
Think: 'I want the ship from game "Asteroids" to follow a specific path and compute, how much time will the whole trip take beforehand"

A craft has it's own properties like mass, linear and angular acceleration. It is only able to accelerate in its forwards direction. Also, quite a pain in the... it's maximum traverse velocity is limited.

Hopefully the picture clears some things out:

The problem lays in the very first step. The program is initiated while the craft is already moving with random velocity and faces random direction. In order to move fully toward the target point, first the craft has to turn to face "U" vector. But while doing so, it still moves, so the vector "U" will change. From the picture you can see that the direction of turn can change, don't worry, it's not a problem.

So, the problem. I tried using only vector math, but with no success as the variable I'm trying to compute relies on equations involving this variable. I'm too dumb to get only the variable I'm interested in on one side of equation. I think the solution would involve a function of distance from craft to object over time.

[Edit 1]

For your interest. Here is the part where I get stuck.

From the beginning. We have the craft on initial position "A", travelling with velocity "V1" and the target on initial position "B", with velocity "V2" (better include it just in case)

From that we can compute the burn vector "U", that we need to align ourselves to in order to travel towards the target at the speed of "Vmax"

The bigger the angle between craft's heading "Cf" and vector "U", the longer it will take the craft to turn. Which means, the craft will cover more distance while turning (uppermost picture). Which means the angle will change during turning etc. etc.

On second picture, in red box. at the top we compute dot product, at the bottom we multiply magnitudes of vectors. As the Cf vector is of length 1 all the time, we can spare it.

The primary thing I'm looking for is variable "t", currently I'm out of ideas.

• @GameAlchemist I'm interested in your method. Care to spend some time to elaborate? If the in-simulation performance is better & the math is optimal enough, I'd see nothing wrong with approximating yet another thing :) – Gabriel Rej Aug 19 '15 at 15:35
• It seems like really complex math problem. I'd recommend posting it on Mathematics Stack Exchange – nikoliazekter Aug 19 '15 at 18:12
• What game engine? – Vadim Tatarnikov Aug 19 '15 at 20:11
• @VadimTatarnikov Unity – Gabriel Rej Aug 20 '15 at 5:26
• first semplification: as B has costant velocity V2, put the system in a reference that make B as a static point. Then consider V2=(0,0,0) and newV1 = V1-V2. – dnk drone.vs.drones Aug 20 '15 at 6:59

I've done this before. The easiest method is to simulate the projectile, record points along its trajectory and note the closest point to the target. What I then do is get the target's location + (target velocity * time taken to reach closest point*) to get the location it would be by the time the projectile reached it. All you need to do then is Math.atan2 the new coordinate with your ship's coordinate to get the angle you need to be at to hit it (or you could draw a marker on the HUD at the new location if you prefer).

For my purposes, this is efficient enough, and can deal with multiple targets at once without any performance hits. If you want it to be more efficient, simply multiply the projectile's velocity and put less points along its trajectory.

*note that the time taken to reach the closest point is that point's index in the array.

Edit: As requested, below is a rough pseudo-code for what I did, note that the way I simulate my projectile will probably be different to how you have to simulate yours.

Also note that the functions below belong to the ship and 'this' is a reference to the ship instance. Also, this is some kind of modified java :P

list<Point> targetPoints = new list<Point>();
list<Double> targetRotations = new list<Double>();

//the function you call in your update step:
public void doTargetting(list<Asteroid> targets, int targettingRange) {
targetPoints.clear(); //reset the list of targets
targetRotations.clear();

if(targets.size() == 0)
return;
int maxPoints = 50, stepsPerPoint = 3;

list<Point> mypoints = simulateCurve(maxPoints, stepsPerPoint, myProjectile);
for(Asteroid a in targets)
{
if(distance(a, this) < targettingRange) {
list<Point> apoints = simulateCurve(maxPoints, stepsPerPoint, a);
doTargettingFor(a, this, mypoints, apoints);
}
}
}

//physics stuff:
public list<Point> simulateCurve(int maxPoints, int stepsPerPoint, GameObject obj) {
list<Point> points = new list<Point>();
double velx = obj.velx, vely = obj.vely;
double accellx = obj.accellx, accelly = obj.accelly;
double maxSpeed = obj.maxSpeed; //if you want a max speed
double burnout = obj.burnout; //a point at which the projectile runs out of thruster juice
double loss = 1 - obj.friction; //velocity loss in each step, because space dust or something?
double x = 0, y = 0;

int spl = 0; //counter for steps per line
for(int i=0; i<maxPoints*stepsPerPoint; i++) {
if(burnout != 0 && i < burnout) {
velx += accellx;
vely += accelly;
}

velx *= loss;
vely *= loss;

double mag = Math.hypot(velx, vely);
if(maxSpeed != 0 && mag > maxSpeed) {
double mul = maxSpeed/mag;
velx *= mul;
vely *= mul;
}

x += velx;
y += vely;

spl++;
if(spl > stepsPerLine) {
spl = 0;
}
}

return points;
}

//targetting stuff:
public void doTargettingFor(GameObject a, Ship me, list<Point> mypoints, list<Point> apoints) {
int closestIndex = 0;
double closest = MAX_VALUE; //a really really big number
for(int i=0; i<points.size(); i++) {
double distance = Math.hypot((apoints[i].x+a.x) - (mypoints[i].x+me.x), (apoints[i].y+a.y) - (mypoints[i].y+me.y));
if(distance < closest) {
closest = distance;
closestIndex = i;
}
}

if(closest < a.radius) //note that this handy little statement checks if you're on target and will hit ;). I used this to change the colour of the marker on the HUD to help you 'lock on' as it were.
{
}

//this bit looks complicated but it really isn't. I'm taking the simulated points of the asteroid and adding it to the asteroid's current coordinates, then doing the same for the projectile
targetPoints.add({apoints[closestIndex].x + a.x, apoints[closestIndex].y + a.y});
targetRotations.add(Math.atan2((apoints[closestIndex].y + a.y) - (mypoints[closestIndex].y + me.y), (apoints[closestIndex].x + a.x) - (mypoints[closestIndex].x + me.x)));

}

• Would you like to post a snippet of your code here or something that makes it clear exactly how you did it? – Majte Nov 1 '15 at 20:55
• Well, in my case I'd written the physics behind all the game objects, so it was pretty easy for me to simulate them. I guess I can summarize it as pseudo-code. Give me about half an hour to write it and check it over. – Merivo Nov 1 '15 at 21:29
• Ok, I've checked it now and it seems to be in order. – Merivo Nov 1 '15 at 22:34
• Well done. I like this approach and I have a similar implementation, so I didn't want to post it here as it would be redoing what you already posted. Thanks! – Majte Nov 1 '15 at 22:36