I am developing a 2D game where x is increasing rightwards and y downwards. Thus, the top-left corner is 0,0.

I have an enemy that moves towards a set of waypoints. When one is reached, it will start moving towards the next waypoint in the list.

I use the following code to move towards a point:

	Vector2 norP = normalize(this.x, this.y, target.x, target.y);
			
	float accelx = thrust * -norP.x - drag * vx;
	float accely = thrust * -norP.y - drag * vy;
		 
	vx = vx + delta * accelx;
	vy = vy + delta * accely;
			
	this.x += delta * vx;
	this.y += delta * vy;

That piece works fine. The problem is detecting when a point has been reached.

Right now, I use the following:

if(distance(this.x, this.y, target.x, target.y) < 25)
{
     ...

The value 25 is a fixed value and works sometimes. As you alter thrust and drag properties, the value 25 stops being effective.

So I need a formula that calculates this value that works good no matter what thrust and drag is(taking them into consideration).

It appears that you allow thrust and drag to vary each update (assuming "delta" is the delta-time between updates). As a result, the enemy may pass through the waypoint during an update (as you've found).

When a new waypoint is selected, calculate the distance from the enemy position to the next waypoint, and set another variable distance_traveled to 0. Each update, add the distance traveled in delta time by the enemy to distance_traveled. When distance_traveled >= distance, the enemy will reach or pass the waypoint during that delta time.

I.e., each update:

distance_traveled += delta * sqrt( vx² + vy² );

if( distance_traveled >= distance ) arrived_or_passed();

N.B., this assumes that the enemy travels in a straight-line path from start to finish. That is, norP (which I assume is the normalized direction from start to waypoint) is constant for that waypoint - which, from your code, it appears to be. FYI, if that is true, then you need to calculate the normalized direction just once - not each update.

Collision detection like that can be tricky for fast moving objects.

Rather than check if they've reached the waypoint, check if they've passed the waypoint.

The difference on one or more axes would have swapped from positive to negative (or the other way around). That may be the easiest way, but will yield problems if your enemy is traveling vertically or horizontally, so you have to ignore the opposing axis to that it's traveling on (or very nearly traveling on): e.g. if you're traveling very horizontally, ignore changes in Y and just focus on the difference in X switching from positive to negative or vice versa.

You can also check the distance from the waypoint to the closest point on the line between the previous position and the current position, and see if it's closer than the current position. That's more math, though. Let me know if you want to know how to do that.

What about this approach:

When you select a new way point store a vector that points from the enemy's position to the way point. Then on each update, find a new vector from the enemy's current position to the way point and take the dot product with the original direction. If the result is positive then the waypoint is "ahead" and the enemy should continue forward, but if the result is negative then the waypoint is "behind" and the enemy should pick a new way point.

This approach doesn't need special case logic to handle horizontal and vertical movement and it should also handle curved paths (from off-axis acceleration) just fine.

What about this approach:

When you select a new way point store a vector that points from the enemy's position to the way point. Then on each update, find a new vector from the enemy's current position to the way point and take the dot product with the original direction. If the result is positive then the waypoint is "ahead" and the enemy should continue forward, but if the result is negative then the waypoint is "behind" and the enemy should pick a new way point.

This approach doesn't need special case logic to handle horizontal and vertical movement and it should also handle curved paths (from off-axis acceleration) just fine.

I was thinking the same thing, but there are still pathological cases. If drag is zero and the initial velocity points in a perpendicular direction with the right magnitude, you can have an enemy orbiting the waypoint at a fixed distance. Your method would declare success after going 90 degrees around the circle, which seems kind of odd.

It is possible that a better controller is needed to make sure the enemy actually passes near the waypoint.

If drag is zero and the initial velocity points in a perpendicular direction with the right magnitude, you can have an enemy orbiting the waypoint at a fixed distance. Your method would declare success after going 90 degrees around the circle, which seems kind of odd.

It is possible that a better controller is needed to make sure the enemy actually passes near the waypoint.

Hmm... That is a pathological case since an orbiting path would *never* get any closer to the way-point. It's a flaw but I don't think it's a fatal one. At least the enemy would declare success at *some* point and move on to the next way-point instead of circling endlessly around the same point. If you chose your way-points carefully (and avoided right-angles) then it should be possible to design paths that don't have this problem.

That said, I'd really like to have code that works in all cases. I was going to say you could fix it by applying an acceleration towards the way-point, but then I remembered that's pretty much the definition of a circular orbit. What we need is a way for the enemy to recognize when it's going the wrong way and steer towards the way-point. We also need to tell it to speed up if it happens to be not moving (or moving too slowly), and maybe slow down if it's moving too fast.

I think the solution is to decompose the enemy's velocity into orthogonal components, with one component in the direction toward the way-point (call it u) and the other (call it v) at right-angles to it. If u is less than a target speed (or negative) then we need to apply an acceleration towards the way-point. Optionally, if u is too high then we can apply an acceleration *away* from the way-point to act as a brake. If v is other than zero then there is a lateral velocity and we should apply an acceleration *perpendicular* to the direction we want to travel, in the opposite direction of v. That will serve to cancel out the lateral velocity (and break us out of any orbits). At each frame we should do a distance check to see if we've reached the way-point and a dot-product with the direction of travel to see if we've over-shot it.

I *think* the above changes should give us the behavior we want. If enemies are stopped then they'll automatically start moving toward the way-point. And if they're heading the wrong way then they should slow down and reverse course. Fast-moving enemies might still over-shoot their target way-point but I think that's better than forcing them to back-track to bulls-eye a missed way-point.

Let me know if you see any more pathological cases. This is a fun exercise to think about.

At each frame we should do a distance check to see if we've reached the way-point and a dot-product with the direction of travel to see if we've over-shot it.

Do you mean direction to the waypoint? Travel implies current velocity.

Also, why bother doing a distance check? You'll probably overshoot the next frame anyway (unless the distance tolerance is huge or the speed pretty low). Unless the one frame delay is so important to include an extra test in the function...

I like your use of polar coordinates to dampen orbit, which seems useful for any solution, but otherwise this looks to suffer from the same issue as my first solution, where fast enemies might pass the waypoint without coming close enough, and still be regarded as a hit.

A proper solution really needs to draw a line between present and prior coordinates and test distance to the closest point on the line from the waypoint. Which only fails if it's orbiting really fast. But I don't think anybody wants to get into testing a curve.

I was being lazy by not explaining the trig before (hopefully you can follow my explanation):

You have three points:

Old position, New Position, and Waypoint

You need three distances:

OldNew

OldWay

NewWay

These give you a triangle.

Bisect it into two triangles with a right angle perpendicular to OldNew

This gives you two right triangles

One has side lengths of:

D (the unknown distance you want to check)

OldNew1 (part of Old-New)

OldWay

The other has side lengths of:

And D (again, the distance you want to check.

OldNew2 (the other part)

NewWay

Using basic trig for right triangles:

A^2 + B^2 = C^2

We know:

D^2 + OldNew2^2 = NewWay^2

D^2 + OldNew1^2 = OldWay^2

And thus:

D^2 = NewWay^2 - OldNew2^2

D^2 = OldWay^2 - OldNew1^2

And:

NewWay^2 - OldNew2^2 = OldWay^2 - OldNew1^2

NewWay^2 - OldWay^2 = OldNew2^2 - OldNew1^2

Remember: OldNew2 = OldNew - OldNew1

NewWay^2 - OldWay^2 = (OldNew - OldNew1)^2 - OldNew1^2

NewWay^2 - OldWay^2 = OldNew^2 -2OldNewOldNew1 + OldNew1^2 - OldNew1^2

(NewWay^2 - OldWay^2 - OldNew^2) / -2OldNew = OldNew1

Therefore (solving for D):

D = ?(OldWay^2 - ((NewWay^2 - OldWay^2 - OldNew^2) / -2OldNew)^2)

Sorry that's so messy

You can also do it with input based on the X and Y coordinates rather than distances. That's arguably even messier to write, but you can find it here:

http://en.wikipedia.org/wiki/Distance_from_a_point_to_a_line#Line_defined_by_two_points

And there's the vector form, on the same page:

http://en.wikipedia.org/wiki/Distance_from_a_point_to_a_line#Vector_formulation

Alternatively, you may want to look into cheating and just interpolating from point to point. Obviously, may not work for your situation, but I figured it should be brought up as an option.

StarMire: I see you're calculating the distance from the way-point to the (infinite) line defined by the enemy's original position and its current position. But what's the actual test to decide whether you've reached the way-point or not?

You can also check the distance from the waypoint to the closest point on the line between the previous position and the current position, and see if it's closer than the current position.

The distance from the way-point to the line (D in your formulas above) is one side of a right triangle, and the distance from the current position to the way-point (NewWay in your formulas) is the hypotenuse of the same right-triangle. But the hypotenuse is always the longest side so you're always going to find that D < NewWay. Am I misunderstanding your approach?