Unrelated to Torque - C++ Chasing Algorithms
by Benjamin Dobell · in Technical Issues · 04/11/2005 (12:33 am) · 14 replies
Hey,
I was just hoping if someone has time that they could take a look at this bit of C++ code for a 2D space game I'm making as there is something wrong with it.
I have a bot and a drone (player) and the bot (it's actually a class because there is multiple bots) is meant to meant to face the player (or more specifically where the player is going to be).
This is probably a lot to ask but any help would be appreciated. Also the game is OpenGL so it uses floating point number for practically everything.
Here is a link where you can download the game and the bit of code i need help with. I would have included it but it is a bit messy and makes things hard to read.
Also don't expect much, it's a cut down version bsaically a triangle:
http://boredom.illuminise.org/2D Game.zip (it's only 50 kbs)
Thanks a heap if anyone has time to look at this.
NOTE: Please don't pay any attention to the actual website, it's a bit out of date and very very bad!
I was just hoping if someone has time that they could take a look at this bit of C++ code for a 2D space game I'm making as there is something wrong with it.
I have a bot and a drone (player) and the bot (it's actually a class because there is multiple bots) is meant to meant to face the player (or more specifically where the player is going to be).
This is probably a lot to ask but any help would be appreciated. Also the game is OpenGL so it uses floating point number for practically everything.
Here is a link where you can download the game and the bit of code i need help with. I would have included it but it is a bit messy and makes things hard to read.
Also don't expect much, it's a cut down version bsaically a triangle:
http://boredom.illuminise.org/2D Game.zip (it's only 50 kbs)
Thanks a heap if anyone has time to look at this.
NOTE: Please don't pay any attention to the actual website, it's a bit out of date and very very bad!
#2
it's pretty simple:
1. find the vector V1 from H to T.
2. calculate the line L1 which is the perpendicular bisector of V1.
3. calculate the intersection of L1 and the target's path (TP).
4. if that intersection is in the future, you're stoked, that's the place to aim for.
otherwise the target has escaped.
for different speeds, let's see..
- yow, much more difficult!
but you could use this as a first guess to Mark's iterative method.
05/11/2005 (11:26 am)
If the target (T) and the hunter(H) both have the same speed,it's pretty simple:
1. find the vector V1 from H to T.
2. calculate the line L1 which is the perpendicular bisector of V1.
3. calculate the intersection of L1 and the target's path (TP).
4. if that intersection is in the future, you're stoked, that's the place to aim for.
otherwise the target has escaped.
for different speeds, let's see..
- yow, much more difficult!
but you could use this as a first guess to Mark's iterative method.
#3
05/12/2005 (2:10 am)
Thanks for the help I havn't had a chance to test any ideas out yet but i will try tomorrow. Also I've had a look on the net for vector addition so I hope I can work it out.
#4
05/12/2005 (10:48 am)
@Benjamin - Just to clarify for myself what you are trying to do: bot is moving with a given velocity ( speed and direction), as is drone. You want the bot to change its direction but not its speed to intercept the drone, assuming the drone maintains its velocity. Is this correct?
#6
05/13/2005 (3:02 am)
@Xander - I want the bot to keep it's current velocity add it's acceleration rate and work out the point of interception using the drones current velocity. It would be much better if the bot accounted for the fact that it will constantly be accelerating when it works out the interception point.
#7
05/16/2005 (12:33 am)
Thanks for the help everyone but I managed to solve my problem by looking at source code for a visual basic program found at: http://www.rookscape.com/vbgaming/tutAO.php
#8
www.gamedev.net/community/forums/topic.asp?topic_id=122528&forum_id=9
In particular, pay attention to posts by Waverider. While I haven't tested his code, it would appear that the guy knows his stuff.
05/24/2005 (5:06 pm)
There's some GOLD in this thread over at GameDev.net:www.gamedev.net/community/forums/topic.asp?topic_id=122528&forum_id=9
In particular, pay attention to posts by Waverider. While I haven't tested his code, it would appear that the guy knows his stuff.
#9
I've put together a white paper deriving the nuts and bolts of general motion mechanics for 2D, and am in the process of writing specific examples of how you apply the general solution to common problems in game systems. I'll try to generate usable code with each example as well (possibly a small library if people are interested). Hopefully I'll be able to post it by next week as a resource, provided work doesn't drag me away. If people find this useful then I'll expand it to 3D mechanics as well.
@Benjamin - looks like you are all squared away, but if you still need an implementation for your problem, I've got a very tight piece of code that does not require iterative targeting (it has a very short 5 step iteration to solve a polynomial function, but this only needs to be executed once). The end result is if you know your target's location and velocity, your own location and velocity, and the maximum acceleration you can apply to yourself, the function returns the direction that will provide an intercept with the target in the minimum amount of time if the acceleration is applied constantly in that direction.
05/29/2005 (4:01 pm)
I've seen several threads asking about algorithms to solve different types of motion mechanics problems across the forums, ranging from Benjamin's question of finding the direction of acceleration that should be used for a specified magnitude of the acceleration to the ballistics question of finding the velocity or velocity direction for a projectile to intercept a moving target. All of these types of questions fall under a single broad description in motion mechanics: Given two objects, each with their own acceleration, velocity and position, how do you calculate the changes to some of the parameters on one object to get it to intercept the other.I've put together a white paper deriving the nuts and bolts of general motion mechanics for 2D, and am in the process of writing specific examples of how you apply the general solution to common problems in game systems. I'll try to generate usable code with each example as well (possibly a small library if people are interested). Hopefully I'll be able to post it by next week as a resource, provided work doesn't drag me away. If people find this useful then I'll expand it to 3D mechanics as well.
@Benjamin - looks like you are all squared away, but if you still need an implementation for your problem, I've got a very tight piece of code that does not require iterative targeting (it has a very short 5 step iteration to solve a polynomial function, but this only needs to be executed once). The end result is if you know your target's location and velocity, your own location and velocity, and the maximum acceleration you can apply to yourself, the function returns the direction that will provide an intercept with the target in the minimum amount of time if the acceleration is applied constantly in that direction.
#10
Keep on chugging, you bring an outstanding experience set to the community, and it's awesome to see you are willing to discuss your knowlege!
05/29/2005 (4:27 pm)
@Xander: That would be an outstanding resource, and I for one think the community would benefit greatly from hearing about your expertise in the 3D space as well!Keep on chugging, you bring an outstanding experience set to the community, and it's awesome to see you are willing to discuss your knowlege!
#11
However I'm definitely interested in that resource and I presume everyone else will be also.
05/30/2005 (12:53 am)
Thanks for the help I'll be sure to let you know if i need help. I think I've got most of it worked out now, including AI object avoidance. However I'm definitely interested in that resource and I presume everyone else will be also.
#12
However I'm definitely interested in that resource and I presume everyone else will be also.
05/30/2005 (1:08 am)
Thanks for the help I'll be sure to let you know if i need help. I think I've got most of it worked out now, including AI object avoidance. However I'm definitely interested in that resource and I presume everyone else will be also.
#13
Which is kinda strange when there's a non-iterative, get-it-right-the-first-time approach available.
Military Intelligence
Jumbo Shrimp
Honest Politician
*sigh*
05/31/2005 (8:19 am)
Incedentally, while performing the search for more info that lead me to the GameDev forums, I found a Naval paper on a missile interception algorithm that recommended an interative algorithm similar to the one I originally definied...Which is kinda strange when there's a non-iterative, get-it-right-the-first-time approach available.
Military Intelligence
Jumbo Shrimp
Honest Politician
*sigh*
#14
1) Put the target at a fixed location on your windscreen (meaning on a line representing an specific angle between flight paths)
2) If the target moves forward of your point, turn away very slightly, and if the target moves behind your point, turn towards very slightly.
3) Maintain on that point until you are within your contact envelope.
This gives a perfectly useful (if not 100% optimized) intercept solution, which has the additional benefit of being independent of changing velocity vectors of the target (assuming your correction delta can compenstate for their flight path delta).
05/31/2005 (10:16 am)
I've actually discussed this in a thread a long time ago, but the basic intercept/closure algorithm that pilots use to do a visual rejoin/intercept is extremely simple:1) Put the target at a fixed location on your windscreen (meaning on a line representing an specific angle between flight paths)
2) If the target moves forward of your point, turn away very slightly, and if the target moves behind your point, turn towards very slightly.
3) Maintain on that point until you are within your contact envelope.
This gives a perfectly useful (if not 100% optimized) intercept solution, which has the additional benefit of being independent of changing velocity vectors of the target (assuming your correction delta can compenstate for their flight path delta).
Torque Owner Mark Storer
Current point = target's location for(some number of loops, 2 or 3 is decent and reasonably fast, more is better) { Compute how long it'll take to get to the "current point". Aim for/travel to where the target will be after that amount of time. current point = where the target'll be }The first pass is always way off, unless the distance-to-target doesn't change from one end of their movement vector to the other during a given slice of time (the target is traveling perpendicular to aimer, which is actually kinda common in FPS-type games where circle-strafing is possible). The second pass is decent, and the third is usually in the right ballpark. The more passes you do, the more accurate you get, at the expense of more processing time.
I don't remember my "sigma" math, so I'm sure there's a way to calculate this non-iteratively, I just don't remember how anymore. So much for my minor in mathematics(not that I actually graduated, but I did complete all the classes for my minor, barely).
If anyone who's actually taken those classes in the last decade would care to chime in, I'm sure we'd all love to hear about it.
(and if there's A Better Way, that'd be good too... this is just what I whipped up for a game programming class a year or two ago)
This strikes me as something that would be handy to have in the engine. A "computeIntercept" script command would be nifty. Give it the targetER, the targetEE, and the velocity the intercepter will have (could be the targetER's movement speed, could be some sort of projectile), it could cough up an intercept location. You could then "aimAt" or "moveTo" that location depending on what your were doing.