## RE: [Algorithms] Knowing when I'm at the end of a path

 RE: [Algorithms] Knowing when I'm at the end of a path From: Tom Forsyth - 2001-07-18 17:07:00 ```The subdividng plane idea is a good one too, and robust even if the current position is quite a way off and heading in the wrong direction. If a path goes from A->B->C, then the plane that divides AB from BC has normal Norm(Norm(AC)+Norm(BC)), and goes through point B. So decide which side of it you're on, and there you go - you know if you're past the waypoint or not. Yes, you need all three Norm() calls to cover the case where AB is short but BC is very long. Though you can change a lot of the divides into multiplies for a bit of extra speed if it's important. Tom Forsyth - Muckyfoot bloke. What's he up to now (and can I have a go)? http://www.eidosinteractive.com/downloads/search.html?gmid=86 > -----Original Message----- > From: Jason Zisk [mailto:ziskj@...] > Sent: 18 July 2001 17:31 > To: gdalgorithms-list@... > Subject: Re: [Algorithms] Knowing when I'm at the end of a path > > > Thanks for all the great responses to this question. I > didn't expect the > deluge of suggestions. :) > > I like the idea of checking the delta distance each frame, > and if its larger > you have passed the waypoint. This works really well with our current > system since we are getting the distance anyway, and would be > easy to debug. > > I was hoping for a more "perfect" solution, though. If the > character starts > off facing the wrong direction and has to loop around it > looks like every > suggestion here would need special code to detect this and > start checking > only after the character is facing the right direction. I > guess this is why > we went with a simple distance in the first place, its the > only method we > could think of that didn't need coding for that case. But of > course its > better to be less zen and more robust, especially with critical > pathfollowing like we are doing. > > Thanks again, > > - Jason Zisk > - nFusion Interactive > > > > > _______________________________________________ > GDAlgorithms-list mailing list > GDAlgorithms-list@... > http://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > ```

 RE: [Algorithms] Knowing when I'm at the end of a path From: Jason Dorie - 2001-07-17 22:32:16 ``` I haven't given this much thought, but wouldn't a plane at waypoint #2, whose normal points at waypoint #1 act as a good test? When the ship passes through the infinite plane, you've passed the point and can update your desired point. It seems like it should work... Jason Dorie BlackBoxGames -----Original Message----- From: gdalgorithms-list-admin@... [mailto:gdalgorithms-list-admin@...]On Behalf Of Jason Zisk Sent: Tuesday, July 17, 2001 3:19 PM To: Algorithms Subject: [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 GDAlgorithms-list@... http://lists.sourceforge.net/lists/listinfo/gdalgorithms-list ```
 RE: [Algorithms] Knowing when I'm at the end of a path From: Kelvin McDowell - 2001-07-17 22:41:41 ```Instead of finding the distance from the current ship position and the waypoint position find the distance from a line segment whose endpoints are your current and previous ship positions and the waypoint. Kelvin McDowell -----Original Message----- From: Jason Zisk [mailto:ziskj@...] Sent: Tuesday, July 17, 2001 3:19 PM To: Algorithms Subject: [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 GDAlgorithms-list@... http://lists.sourceforge.net/lists/listinfo/gdalgorithms-list ```
 Re: [Algorithms] Knowing when I'm at the end of a path From: - 2001-07-17 22:46:57 ```Jason Zisk wrote: >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. An alternative approach to checking the distance to your destination waypoint is to see if you've passed over into the negative halfspace of the plane specified by the destination waypoint B and the normal A-B (where A is the previous waypoint). I.e. if C is your current position, you do: if (Dot(A-B, C-B) > 0) ...still aiming for B... else ...passed waypoint... In some cases you might want to determine you've 'reached' a waypoint before you've actually physically reached it. In this case you could instead use B' in the expression above, where B' is a biased version of B, moved towards A by some given factor. Christer Ericson Sony Computer Entertainment, Santa Monica ```
 RE: [Algorithms] Knowing when I'm at the end of a path From: Bruce Woodard - 2001-07-17 22:53:50 ```That's basically what I use... project your ship onto the path: (start - end) dot (end - shipPos) < 0 You can also take into consideration the plane of the next path seg... -----Original Message----- From: Jason Dorie [mailto:jason.dorie@...] Sent: Tuesday, July 17, 2001 4:32 PM To: gdalgorithms-list@... Subject: RE: [Algorithms] Knowing when I'm at the end of a path I haven't given this much thought, but wouldn't a plane at waypoint #2, whose normal points at waypoint #1 act as a good test? When the ship passes through the infinite plane, you've passed the point and can update your desired point. It seems like it should work... Jason Dorie BlackBoxGames -----Original Message----- From: gdalgorithms-list-admin@... [mailto:gdalgorithms-list-admin@...]On Behalf Of Jason Zisk Sent: Tuesday, July 17, 2001 3:19 PM To: Algorithms Subject: [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 GDAlgorithms-list@... http://lists.sourceforge.net/lists/listinfo/gdalgorithms-list _______________________________________________ GDAlgorithms-list mailing list GDAlgorithms-list@... http://lists.sourceforge.net/lists/listinfo/gdalgorithms-list ```
 RE: [Algorithms] Knowing when I'm at the end of a path From: - 2001-07-18 08:08:42 Attachments: Message as HTML ```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 =3D b; =09 if (speed !=3D 0.0f) { float distance, time, t; distance =3D Magnitude(b - a); time =3D distance / speed; if (time !=3D 0.0f) { t =3D elapsedTime / time; if (t < 1.0f) { c =3D (1.0f - t) * a + t * b; } } } return c; } As you can see when I reach the last t value, I simply return the c =3D = 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@...] Enviado el: mi=E9rcoles, 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 GDAlgorithms-list@... http://lists.sourceforge.net/lists/listinfo/gdalgorithms-list ```
 Re: [Algorithms] Knowing when I'm at the end of a path From: Favnir - 2001-07-18 08:57:14 ```In your case, it might help setting the waypoint a distance X beyond the end of actual segment. This may cause your ship to slightly fly off tangents, but this should be OK for most cases, if you're using a good pathfinding algorithm, as you will expect obstacles to appear mostly on inner sides of turns. Are, F ----- Original Message ----- From: To: Sent: Wednesday, July 18, 2001 11:11 AM Subject: RE: [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 ```
 Re: [Algorithms] Knowing when I'm at the end of a path From: Jason Zisk - 2001-07-18 16:30:30 ```Thanks for all the great responses to this question. I didn't expect the deluge of suggestions. :) I like the idea of checking the delta distance each frame, and if its larger you have passed the waypoint. This works really well with our current system since we are getting the distance anyway, and would be easy to debug. I was hoping for a more "perfect" solution, though. If the character starts off facing the wrong direction and has to loop around it looks like every suggestion here would need special code to detect this and start checking only after the character is facing the right direction. I guess this is why we went with a simple distance in the first place, its the only method we could think of that didn't need coding for that case. But of course its better to be less zen and more robust, especially with critical pathfollowing like we are doing. Thanks again, - Jason Zisk - nFusion Interactive ```
 RE: [Algorithms] Knowing when I'm at the end of a path From: Peter Lipson - 2001-07-18 18:08:10 ``` It sounds like your definition of 'at the waypoint' isn't as simple as might be. Especially if your waypoint path has acute angles in it, the problem can be subtle. For example, you may not really -care- if you pass the middle waypoint completely before you bend toward the final waypoint. Otherwise, the half-space suggestions, using a plane normal that connects the two points, should do the job. If you're allowing very free movement, your plane normal could be the one connecting the next waypoint with the one following THAT. If instead you want to guarantee that you (roughly) trace out the path, the rabbit will do the best job of pulling you along. Its velocity along the waypoint path should be a function of your heading and your own velocity. Peter -----Original Message----- <..snip..> I was hoping for a more "perfect" solution, though. If the character starts off facing the wrong direction and has to loop around it looks like every suggestion here would need special code to detect this and start checking only after the character is facing the right direction. I guess this is why we went with a simple distance in the first place, its the only method we could think of that didn't need coding for that case. ```
 RE: [Algorithms] Knowing when I'm at the end of a path From: Tom Forsyth - 2001-07-18 17:07:00 ```The subdividng plane idea is a good one too, and robust even if the current position is quite a way off and heading in the wrong direction. If a path goes from A->B->C, then the plane that divides AB from BC has normal Norm(Norm(AC)+Norm(BC)), and goes through point B. So decide which side of it you're on, and there you go - you know if you're past the waypoint or not. Yes, you need all three Norm() calls to cover the case where AB is short but BC is very long. Though you can change a lot of the divides into multiplies for a bit of extra speed if it's important. Tom Forsyth - Muckyfoot bloke. What's he up to now (and can I have a go)? http://www.eidosinteractive.com/downloads/search.html?gmid=86 > -----Original Message----- > From: Jason Zisk [mailto:ziskj@...] > Sent: 18 July 2001 17:31 > To: gdalgorithms-list@... > Subject: Re: [Algorithms] Knowing when I'm at the end of a path > > > Thanks for all the great responses to this question. I > didn't expect the > deluge of suggestions. :) > > I like the idea of checking the delta distance each frame, > and if its larger > you have passed the waypoint. This works really well with our current > system since we are getting the distance anyway, and would be > easy to debug. > > I was hoping for a more "perfect" solution, though. If the > character starts > off facing the wrong direction and has to loop around it > looks like every > suggestion here would need special code to detect this and > start checking > only after the character is facing the right direction. I > guess this is why > we went with a simple distance in the first place, its the > only method we > could think of that didn't need coding for that case. But of > course its > better to be less zen and more robust, especially with critical > pathfollowing like we are doing. > > Thanks again, > > - Jason Zisk > - nFusion Interactive > > > > > _______________________________________________ > GDAlgorithms-list mailing list > GDAlgorithms-list@... > http://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > ```

JavaScript is required for this form.

No, thanks