I'm making a small tower defense games, just to practice.

I have a set path, with checkpoints. So when the enemies get there, they walk towards the next checkpoint.
The problem is that...
I calculate a vector towards that point and add the speed to that vector, so they move in that direction.
The problem comes now, since the new position might end up with floats, and the checkpoint is an int, the guys miss the checkpoint... So they go like:
check point at 10,10. the guy is at 9.5, 10, I add 1 which is the speed, and it ends up being at 10.5, 10.
so just asking "if (enemy.position == checkpoint.position) won't work.

Now, I'm not saying I can't fix this, I just wanted to consult the problem with you guys. I have several ideas.

1. check if distance between checkpoint and the enemy is less than a set amount. Then move the enemy to the point and tell it to go to the next checkpoint.

2. Check if the guy has passed the point, so if he comes from 9.5 (smaller than the point) and ends up in 10.5 (bigger than the point) then he reached it. This would have to take into consideration where the enemy was coming from, and it doesn't look like the ideal solution.

3. I could figure out the distance to the point at the start, and find out how many "steps" it would take it to reach it, and then after that number of steps, assume he reached it.


OR, I could ask you guys what the ideal, obvious, and most used method is.

I like the first idea. Define the checkpoint to be a circle, not a point. Whenever a unit touches the circle, we consider that it has arrived at the checkpoint and can start heading towards the next one.

I like the first idea. Define the checkpoint to be a circle, not a point. Whenever a unit touches the circle, we consider that it has arrived at the checkpoint and can start heading towards the next one.

yes, it's also the one I like most because it's simple. But if the enemies went too fast, they might still miss it. Or I'd have to make that circle bigger.
It probably won't matter with my game, but I think it's a bit inaccurate.

Is this the default way to solve this problem?

If the checkpoints are basically segments to be crossed (like a finish line at a race), you can check if the segment joining the unit's previous position and its current position intersects the checkpoint's segment. That would work for any speed.

Only you know the specifics of your game, but if the simple solution works, I would go for it.

Giving your checkpoints a radius is only half of the solution - if your entities are travelling too fast, you can still miss detecting them.
One solution would be to adjust the waypoint radius dynamically according to the current velocity of the entity, however this will lead to overlapping of the waypoints, and potential problems regarding multiple positives.
The most obvious solution (to me) that works regardless of the velocities involved is based on direction (as you suggested).

At each frame, get the DotProduct of the current movement direction vector with the vector direction from the entity to the waypoint, and then just check the sign of the result.
If its positive, then we're not there yet... and if its negative, we went too far

Note that we don't even need to make sure these vectors are of Normal length, since we don't care about the VALUE of the result, just its SIGN

Another thing we can do is determine the distance from the waypoint at each frame (you probably already do that), and check whether the distance is getting smaller or bigger.

Finally, we can examine the distance represented by the delta-position we calculated for the current frame, and check whether it is in fact larger than the remaining distance to the waypoint - this would allow us to detect the 'overshooting' before it occurs.

At each frame, get the DotProduct of the current movement direction vector with the vector direction from the entity to the waypoint, and then just check the sign of the result.
If its positive, then we're not there yet... and if its negative, we went too far

I like this solution. I will try that and see if I can make it work.

Thanks to both of you though!

[quote name='__Homer__' timestamp='1306124173' post='4814448']
At each frame, get the DotProduct of the current movement direction vector with the vector direction from the entity to the waypoint, and then just check the sign of the result.
If its positive, then we're not there yet... and if its negative, we went too far

I like this solution. I will try that and see if I can make it work.

Thanks to both of you though!
[/quote]


I'd actually suggest a modification to this myself. When you start on the path towards the target, store the plane equation from start to end point. I.e. assuming x/y ground movement plane the normal of the plane would be start-end normalized, assume z=1, plug in normal and destination*z axis to calculate ax + by + bz = d. So, now if you have framerate hickups or other problems calculating d should always be >0 until such time as you pass the waypoint at which point it goes <=0 and you know without a doubt you have arrived at or passed the waypoint in relation to your starting point. This is similiar to using the line equation mentioned but it gives you several benefits:

1. If you need to perform obstacle avoidance on the path, say navigate around a slowed/stopped unit, the line based solution has issues if the avoidance happens when you are close to the destination.
2. Given the plane, current destination and the "next" destination you can easilly perform path smoothing. Basically compute the plane for the "next" waypoint , dot the current and next plane normals and when unit turn radius >= distance to current target - (1+dot)*move rate you start your turn towards the next goal. (Takes some tweaking and experimentation but it can look very good. NOTE: may have the math a little wrong, been a while.)
3. Basically impervious to missed targets since you do not recalculate the plane equation unless it becomes completely invalid.

Figured I'd post another option for you.

[quote name='stromchin' timestamp='1306130539' post='4814472']
[quote name='__Homer__' timestamp='1306124173' post='4814448']
At each frame, get the DotProduct of the current movement direction vector with the vector direction from the entity to the waypoint, and then just check the sign of the result.
If its positive, then we're not there yet... and if its negative, we went too far

I like this solution. I will try that and see if I can make it work.

Thanks to both of you though!
[/quote]


I'd actually suggest a modification to this myself. When you start on the path towards the target, store the plane equation from start to end point. I.e. assuming x/y ground movement plane the normal of the plane would be start-end normalized, assume z=1, plug in normal and destination*z axis to calculate ax + by + bz = d. So, now if you have framerate hickups or other problems calculating d should always be >0 until such time as you pass the waypoint at which point it goes <=0 and you know without a doubt you have arrived at or passed the waypoint in relation to your starting point. This is similiar to using the line equation mentioned but it gives you several benefits:

1. If you need to perform obstacle avoidance on the path, say navigate around a slowed/stopped unit, the line based solution has issues if the avoidance happens when you are close to the destination.
2. Given the plane, current destination and the "next" destination you can easilly perform path smoothing. Basically compute the plane for the "next" waypoint , dot the current and next plane normals and when unit turn radius >= distance to current target - (1+dot)*move rate you start your turn towards the next goal. (Takes some tweaking and experimentation but it can look very good. NOTE: may have the math a little wrong, been a while.)
3. Basically impervious to missed targets since you do not recalculate the plane equation unless it becomes completely invalid.

Figured I'd post another option for you.
[/quote]

thanks