🎉 Celebrating 25 Years of GameDev.net! 🎉
Not many can claim 25 years on the Internet! Join us in celebrating this milestone. Learn more about our history, and thank you for being a part of our community!
Best spaceship Chasing algorithm
If you continually adjust your course to head directly toward the target you will cath it. As long as your speed is at least equal to the target and the target occasionally changes it''s course.
quote: Original post by B-Barlow
If you continually adjust your course to head directly toward the target you will cath it. As long as your speed is at least equal to the target and the target occasionally changes it''s course.
That is not always correct. Often, you will end up following the target indefinately. At the very least, it is hardly efficient compared to "leading" the target based on where you know it is going to go.
Dave Mark
Intrinsic Algorithm Development
you will only be stuck following the target if it never changes it's course.
Heading toward a calculated lead point can be even more inefficient if the target often changes its course.
Edited by - B-Barlow on January 7, 2002 3:36:19 PM
Heading toward a calculated lead point can be even more inefficient if the target often changes its course.
Edited by - B-Barlow on January 7, 2002 3:36:19 PM
Or if the course it takes is always directly away from your position... as would tend to be the case in game situations requiring "chasing" AI. Of course, eventually, this would turn into a straight line pursuit. Also, it is far more natural looking (because it is more intelligent looking) for the pursuer to try to lead the target somewhat rather than looking like it is being towed on a swinging rope.
A lot of it depends on what it is we are trying to model. If it is a heat-seeking missile, they are obviously going to point toward the target at all times. If we are trying to model an intercepting plane with an intelligent pilot, then they are going to mentally plot an intercept vector. Also, considering that we are going to be applying the limitations of minimum turn radius, acceleration rates, etc., the pursuer would be better served by leading the target so as not to be lured into too sharp of a turn.
Example, in a 90 degree path situation where the target will pass in front of the pursuer prior to it''s arrival at the intercecting point, the angle to the target will change rapidly as the pursuer nears the trail of the target... likely too fast for it to turn prior to crossing the trail. If, however, the pursuer is plotting towards the vector of the target, it would detect it passing in front sooner and would therefore begin its turn sooner... possibly not even crossing behind the target at all.
If you take a scenario where the target is approaching at a near head on angle (e.g. 135 degrees), the situation is even more grave. The pursuer wouldn''t even ponder turning much at all until the moment the target passes abeam of the pursuer. Depending on the turn rate of the pursuer, the target may be 2-4 times further away by the time the pursuer achieves a reasonable heading again.
Dave Mark
Intrinsic Algorithm Development
A lot of it depends on what it is we are trying to model. If it is a heat-seeking missile, they are obviously going to point toward the target at all times. If we are trying to model an intercepting plane with an intelligent pilot, then they are going to mentally plot an intercept vector. Also, considering that we are going to be applying the limitations of minimum turn radius, acceleration rates, etc., the pursuer would be better served by leading the target so as not to be lured into too sharp of a turn.
Example, in a 90 degree path situation where the target will pass in front of the pursuer prior to it''s arrival at the intercecting point, the angle to the target will change rapidly as the pursuer nears the trail of the target... likely too fast for it to turn prior to crossing the trail. If, however, the pursuer is plotting towards the vector of the target, it would detect it passing in front sooner and would therefore begin its turn sooner... possibly not even crossing behind the target at all.
If you take a scenario where the target is approaching at a near head on angle (e.g. 135 degrees), the situation is even more grave. The pursuer wouldn''t even ponder turning much at all until the moment the target passes abeam of the pursuer. Depending on the turn rate of the pursuer, the target may be 2-4 times further away by the time the pursuer achieves a reasonable heading again.
Dave Mark
Intrinsic Algorithm Development
B-Barlow is right.
As long as the prey is of an equal or slower speed, everytime it changes course it isn''t moving away from the predator as much as it could, while the predator is always moving at its maximum speed toward the prey. If you think about the extreme case of a 90 degree turn, then the prey''s path describes a right-angle, while the predator''s path would be a curve inside of that. I think a smooth curve is shorter, but I am a math dummy so maybe not.
Timkin''s rule-based learning could be used to catch prey faster (but dumber) than the predator, but only to a certain degree. I think that''s the case anyhow.
As long as the prey is of an equal or slower speed, everytime it changes course it isn''t moving away from the predator as much as it could, while the predator is always moving at its maximum speed toward the prey. If you think about the extreme case of a 90 degree turn, then the prey''s path describes a right-angle, while the predator''s path would be a curve inside of that. I think a smooth curve is shorter, but I am a math dummy so maybe not.
Timkin''s rule-based learning could be used to catch prey faster (but dumber) than the predator, but only to a certain degree. I think that''s the case anyhow.
quote: Original post by Argus
If you think about the extreme case of a 90 degree turn, then the prey''s path describes a right-angle, while the predator''s path would be a curve inside of that.
It would not always be inside of that. The dominant factor, as I mentioned, would be the minimum turn radius of the pursuer. Combine this with the "miss distance" - i.e. how close behind the target the pursuer would pass. The closer that is, the less time the pursuer has to turn prior to passing behind the target.
Dave Mark
Intrinsic Algorithm Development
quote: Original post by InnocuousFox
Oh... thank you for clarifying... very helpful. Exactly how, then, does what you posted relate to the original question?
I didn''t see the need to clarify my statements for you since you had already imposed your own preconceptions about the best method over what I was suggesting.
I will make a clarification of my statements about the method I implemented for my predator-prey system.
I should not have said: "The predator selected an action so as to minimise distance and/or angle to the target. "
More correctly, the predator was rewarded for choosing an action that resulted in a decrease in distance and angle to the target. Meaning that it could employ any strategy it wanted to so as to achieve the goal of intercepting the prey. The reward was based on getting closer to the prey is a better strategy than moving away from it , but this is clearly not always the best strategy!
Timkin
quote: Original post by InnocuousFox
Or if the course it takes is always directly away from your position... as would tend to be the case in game situations requiring "chasing" AI. Of course, eventually, this would turn into a straight line pursuit.
This will be the case regardless of what chasing method is used.
quote: Also, it is far more natural looking (because it is more intelligent looking) for the pursuer to try to lead the target somewhat rather than looking like it is being towed on a swinging rope.
Nothing unnatural about it at all. Fighter pilots are trained to use pure persuit(pointing directly at the target) to close the distance, lag persuit( pointing behind the target) to maintain their current distance, and lead persuit(ahead of target) only for shooting. Always pulling lead persuit will eventually put you in front of the target, which is generally a bad place to be.
quote: ...the pursuer would be better served by leading the target so as not to be lured into too sharp of a turn.
It would seem to me that leading a target would be more likely to force the persuer into sharp turns. A small change in the targets heading requires a much greater change for the persuer.
quote: Example, in a 90 degree path situation where the target will pass in front of the pursuer prior to it''s arrival at the intercecting point, the angle to the target will change rapidly as the pursuer nears the trail of the target... likely too fast for it to turn prior to crossing the trail. If, however, the pursuer is plotting towards the vector of the target, it would detect it passing in front sooner and would therefore begin its turn sooner... possibly not even crossing behind the target at all.
And possibly positioning the ''persuer'' directly in front of it.
quote: If you take a scenario where the target is approaching at a near head on angle (e.g. 135 degrees), the situation is even more grave. The pursuer wouldn''t even ponder turning much at all until the moment the target passes abeam of the pursuer. Depending on the turn rate of the pursuer, the target may be 2-4 times further away by the time the pursuer achieves a reasonable heading again.
All of these examples assume that the target is a comatose moron who never does anything but fly in a straight line. I''d recommend using some kind of prediction for long range intercept plotting, but once you get within a certain range to the target you need a lot more flexability than any single chase algorythm can provide.
quote: Original post by B-Barlow
All of these examples assume that the target is a comatose moron who never does anything but fly in a straight line. I''d recommend using some kind of prediction for long range intercept plotting, but once you get within a certain range to the target you need a lot more flexability than any single chase algorythm can provide.
And I think that is the crux of the issue.
1) Are you trying to close distance, impact, follow, etc?
2) Are you too far away, too close or right where you want to be?
3) Is the target manuvering on its own, manuvering in response to you or just plodding along straight?
4) Are we assuming identical agility? Who manuvers quicker, etc.?
We were all taking different answers to the above and applying different methodolgies.
Dave Mark
Intrinsic Algorithm Development
If you want a demo of intercepting etc, try looking at:
http://www.red3d.com/cwr/steer/
it has java applet demos of intercepting a moving or stationary target as well as a load of other stuff. You should look at the Persue and Evade demo.
The explanation of all the demos is at:
http://www.red3d.com/cwr/steer/gdc99/index.html
hope that helps
John B
http://www.red3d.com/cwr/steer/
it has java applet demos of intercepting a moving or stationary target as well as a load of other stuff. You should look at the Persue and Evade demo.
The explanation of all the demos is at:
http://www.red3d.com/cwr/steer/gdc99/index.html
hope that helps
John B
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
