Hi there!

I have solved this similar problem in our game engine when automatic character movement was needed. I use simple linear interpolation to move from a waypoint to the next one as follows:

Vector3D CalcLinearInterpolationStep(const Vector3D& a, const Vector3D& b, float speed, float elapsedTime)
        Vector3D c = b;
        if (speed != 0.0f)
                float distance, time, t;
                distance = Magnitude(b - a);
                time = distance / speed;
                if (time != 0.0f)
                        t = elapsedTime / time;
                        if (t < 1.0f)
                                c = (1.0f - t) * a + t * b;
        return c;

As you can see when I reach the last t value, I simply return the c = b (the next waypoint) so the movement always reaches its destinations. It could make a strange "jump" effect for big speeds, but we always want smooth movement, don't we?

Hope this helps.

-----Mensaje original-----
De: Jason Zisk [mailto:ziskj@optonline.net]
Enviado el: miércoles, 18 de julio de 2001 0:19
Para: Algorithms
Asunto: [Algorithms] Knowing when I'm at the end of a path

We've been having a problem since... well forever... with path following in
our AI.  Say you have a path made up of waypoints in 3D.  You have a
character following this path, maybe a space ship.  The space ship goes in a
straight line from one waypoint to the next to the next, etc.  It only keeps
track of two waypoints, the one it came from and the one it is going to.

My question is, how do you know when you have reached your destination so
you know to update to the next path segment?  Right now we are using a
simple distance check.  If the space ship is within X feet, then switch.
This basically works but causes some problems.

If X is too small the ship may "miss" the radius around the waypoint because
of physics or whatnot, and thus never switch.  Depending on AI this will
cause it to loop back around or just keep on flying forever, either way
unwanted behavior.

If X is too large the ship will decide it needs to switch waypoints too
soon, and end up "cutting corners", which could be a very bad thing if the
waypoints are used to avoid obstacles.  It might cut the corner too much and
try to drive right through something.

Any help with this devious little problem is appreciated.

- Jason Zisk
- nFusion Interactive

GDAlgorithms-list mailing list