Intercepting a moving target easily - Vectors
Blitz3D Forums/Blitz3D Programming/Intercepting a moving target easily - Vectors
| ||
| Hi. It's one of those common problems in games with AI turrets and AI shooting: shooting 'ahead' of a moving target so when the projectile gets there the target is also there and gets hit. I was looking for solutions to this problem. Most deal with quadratic equations, and that can be a bit daunting if your math is rusty - they do, at least, provide the fastest way to compute the solution. In a Stackoverflow thread on this subject a guy suggested a different approach, using vectors. Here's his post: http://stackoverflow.com/a/2248934 After digesting it for a while it made a whole lot of sense to me, so I thought I'd take the time to explain how it works, as it can benefit other people. It avoids quadratic equations, discriminants etc., dealing instead with vectors and coordinate contexts. It works for 2D and 3D with minimal differences. It can be used for other things as well, not just interception-prediction. • The problem:  We're at the top, looking down at a 3D scene. We have a moving target (A) with known speed and direction, and we want to shoot 'ahead' of it so our shot certainly hits it. We don't know which direction to shoot at, however. We only know the place we're shooting from (B) and the speed of its projectiles. • Changing the point-of-view:  We 'spin' this scene so the segment that goes from object A to object B (in other words, the distance between them) gets aligned to one of the axes of this new space. In this case, it's the Z axis (their distance is aligned to the new space's Z axis). • Decomposing the target's vector:  We can then decompose the target object's movement vector into its components WITHIN this new coordinate space. In this specific coordinate space, the X (sideways) and Y (pointing up) axes don't do much, but movements in the Z axis can bring the objects together or distance them. • Copying X and Y components:  We then create a vector and make its X and Y components be the same as the X and Y components of the target object's movement vector. This keeps the projectile and target object aligned while they move. The Z component of this new vector is derived from the predefined projectile's speed\length\magnitude: Z = Sqr(speed^2 - x^2 - y^2). • The interception:  This new vector is going to be our "projectile vector". Having its X and Y components the same as the target's keeps it aligned to it, but the Z axis will draw it closer to the target until it hits. We can use a simple space equation (X = Xo + V * t) to calculate the time taken for the projectile to hit the target in the future. • Restoring the old view:  We then transform the "projectile vector" we computed back to the original coordinate space of the scene. We now have the projectile vector, the time it'll take for the projectile to hit the target and we can also find out the interception point. But is this method fast? you tell me. For the following demo... - Move the Mouse to aim, and shoot with the Left Mouse Button. - Hold Space while shooting so you use the "auto-aim". - Press Enter so you change the movement speed for the target object. PS: Since the target object has volume, some shots will still hit even if they're aimed a bit off. |
| ||
| Ok .... So to avoid quadratic equations, you have : - A positionEntity (which involve a 4*4 multiplication matrix) - A pointEntity (I don't even know how Blitz handle such a function ... probably some matrix multiplied and such things) - At least 2 TFormXXXX (that involve 2 matrix multiplication) sorry but, it 's ... much much much complicated and slow than the "quadratic" solution where all you need is that : ; Normalize the Target Direction + multiply the Target_Velocity Local In# = Target_Velocity/Sqr(TargetDir_x*TargetDir_x+TargetDir_y*TargetDir_y+TargetDir_z*TargetDir_z) Local Ix# = TargetDir_x*In, Iy# = TargetDir_y*In, Iz# = TargetDir_z*In ; square target velocity substract square bullet velocity Local a# = Ix*Ix+Iy*Iy+Iz*Iz - Bullet_Velocity*Bullet_Velocity ; distance Bullet-> target Local Dx# = Targetx-Bulletx Local Dy# = Targety-Bullety Local Dz# = Targetz-Bulletz ; a not really complicated equation : no big deal (2.0* dot product of Distance and Target Velocity) Local b# = + Float(2.0)*( Dx*Ix + Dy*Iy + Dz*Iz ) ; the Square distance Local c# = (Dx*Dx+Dy*Dy+Dz*Dz) ; then the famous Discriminant, which is really simple Local Det# = b*b-4.0*a*c Local time#=0.0 ; And deal with 2 solutions If Det<0 Then Return -1 ; no solution If Det>0 Det=Sqr(Det) time = -0.5*(b-Det)/a If time<0 Then time=-0.5*(b+Det)/a Else time = -0.5*b/a EndIf ; And Here we are. ResultX = Dx + time * Ix ResultY = Dy + time * Iy ResultZ = Dz + time * Iz ; Eventually, normalize the result Local n# = 1.0/Sqr(Resultx*Resultx+Resulty*Resulty+Resultz*Resultz) Resultx = Resultx * n Resulty = Resulty * n Resultz = Resultz * n So, there is only small maths involved, and really less operations |
| ||
| I disagree that it is "much much complicated"; vector manipulation is more intuitive to me, I feel like a kid playing with sticks. I agree that it can be slower, I said that in that post already. Do you know how slower it is in comparison, however? please benchmark both methods, because you'd be surprised of the fact that making use of internal Blitz3D functions is many times faster than doing the same but with Blitz3D code. For example, make a simple 3D euclidean distance function with Sqr(x*x + y*y + z*z). It's slower than using EntityDistance(). |
| ||
| For sure the internal function runs pretty fast, but not "that" fast. This can explain easily My code only use some simple multiplications and 2 squareroots happy internal function are not faster, else it would not mean "internal stuff is really fast" but "blitz code is reaaally slow" :) A Tform call is made internally with 2 matrix multiplications you have a point x,y,z, you transform it in the local matrix (Source) let's say sxx,sxy,sxz, syx,syy,syz, szx,szy,szz the source matrix newx = x * Sxx + y * Syx + z * Szx + SourceX (absolute coords of source) newy = x * Sxy + y * Syy + z * Szy + SourceY newz = x * Sxz + y * syz + z * Szz + SourceZ then you have to get the coords in the Destination matrix x = newx - DestX : y = newy - DesyY : z = newz - DestZ resx = x*dxx + y*dxy + z*dxz resy = x*dyx + y*dyy + z*dyz resz = x*dzx + y*dzy + z*dzz And here we don't even care of the "If / Else" if you set Source or Dest (or both) to "0" Then, I think the slowest function in your code is the pointentity it's a process that require to inverse the matrix to estimate it to the destination matrix the transform matrix is a 4*4 matrix (not just a rotation) And as it also performs a "Roll" effect (the last optional parameters) I suppose it involves some kind of Lerp interpolation At last but not least : The "PositionEntity" function It requires a multiplication of the Root matrix * entity matrix, then update the entity (if you ever tracked the memory offsets of an entity, you would see something not really elegant but it's still here : the entity matrix is stored in many locations, and each time to modify with a PositionEntity/Move/Translate etc ... you manipulate all the matrix to update the entity) It's probably where my code is much ( much much much :) ) faster is : I don't update anything. You can also make it with a c++ dll, it will be probably 2 or 3 time faster. Actually, on the bench I processed, my function runs 3 times faster than yours. - 30 ms for 100000 tests vs 100ms or above for your function - 100-120 ms in debug vs >500ms for your function. Then I suppose " vector manipulation is more intuitive to me" is just a matter of point of view. I'm easy with maths and vectors, so I can manipulate them in a more "low level", then making the stuff of the function here is not really difficult, and whatever you think about it, it's still some vectors stuff, it's just that it is more theorical than the PositionEntity/TFormVector etc ...) And for someone who better not deal with "low level" codes, of course, using the blitz stuff is surely easier in some way [edit] BTW, I just found a small memory leak in your code : You never use "Delete" on the TVector objects when you release the bullets If EntityCollided(b\mesh, SHIP_COL_TYPE) Then Cls Flip Delay 10 Flip FreeEntity b\mesh Delete b\vector ; insert here Delete b Else If EntityZ(b\mesh) > 75 Then FreeEntity b\mesh Delete b\vector ; insert here Delete b EndIf EndIf |
| ||
| Hi. Thanks for the explanations. I like your tabbed indentation, it makes working on an entity's settings (color, position etc.) much more organized. I was skeptic at first, but then realized you are right on PointEntity: it's abusive. I replaced it with AlignToVector() (among other optimizations, taking away redundancy) and now the benchmarks are much less apart. Take a look: |
| ||
| This is one of those rare occasions when a bit of rivalry actually benefits everyone :) I was wondering though do both algorithms assume both source and target objects are travelling at the same speed or can they be independent of one another? Thanks to both of you for your submissions. |
| ||
| Yep, the AlignTovector thing is really a fast method to PointAt Position :) (actually, it divide by 2 the times to perform the check, still not as fast as pure maths but, already quite performant enough) @MCP : Actually the bench code works with target and emitter with different velocities, and both Kryzon's code and mine work, so I think you've got your answer :) ps : I always indent this way, I'm a bit ... obsessive with order IRL :) ps2 : i've made a "pure maths" method involving the Kryzon's code (converting the Position/PointEntity/TForm stuff with matrix) it runs at almost the same speed than mine (a bit slower, but I'm sure it can be optimized) So the theory involved is not that bad actually, it's even well thought... I wouldn't expect it be that robust |
| ||
| For fun, I tested with the bullet library (I mean : the physics libraryr, not the "tBullet type") So here is a c++ code to compile to dll (if you have the bullet library)
/*
@result = a bullet vector to store the final direction vector (normalized)
@em = emitter
@tg = target
@td = target direction (velocity include)
@v = emitter velocity
returns : the time to intercept the target at their respectives velocities (as float)
small note :
take care to check if time is >=0 before using the result
as for performance, the function use the result as a temporary vector to store some vector operations.
so if the function returns '-1' the @result will contain some fake datas.
BTW, I probably would better set it to {0,0,0} before returning '-1' ...
*/
extern "C" _declspec(dllexport) const float _stdcall Extrapolate(btVector3& result,btVector3& em,btVector3& tg,btVector3& td, float v)
{
result = tg-em;
float a = td.length2() - v*v;
float b = 2.0f*result.dot(td);
float d = b*b-4.0f*a*result.length2();
float t = 0.0f;
if (d<0.0f)return -1.0f;
if (d>0.0f){d=sqrtf(d);t=-0.5f*(b-d)/a;if(t<0.0f){t=-0.5f*(b+d)/a;};}
else{t=-0.5f*b/a;};
result+=td*t;result*=(v/result.length());return t;
};
you'll need some tweaking to set/create the vectors, but not a big deal if you know how to wrap some c++ class it's a bit faster than my blitz3d function for 100 000 test : - 20-30 ms with the dll - 30-35 ms with blitz native maths |
| ||
| Thanks for the code Bobysait I'll look at that when I get some free time :) |
| ||
| I was wondering though do both algorithms assume both source and target objects are travelling at the same speed or can they be independent of one another? The only elements necessary to use these methods in 2D or 3D contexts are: - Start position of the shot; - Speed of the shot; - Current position of the target; - Movement\translation vector of the target used in the current frame; So you get in return the ideal movement\translation vector for the shot. This method of target-prediction (or "extrapolation", as it was better put) is ideal for space games. I have Microsoft's Freelancer in mind: when battling in space, you would "lock" in an enemy and the interface would show a little red cross that represented the extrapolated interception point. You'd then aim at this cross so your shots would hit the enemy. It's quite easy to dodge shots like these. The object being targetted has to simply change orientation\direction. These methods assume the targetted object will remain under its current orientation while the projectile gets there. For fun, I tested with the bullet library (I mean : the physics libraryr, not the "tBullet type") So here is a c++ code to compile to dll (if you have the bullet library) Thanks for sharing. |
| ||
| I just discovered this. (I work on weekends). Excellent discussion that I can't but think I might have inspired with my question on this topic! As to the debate about intuitiveness vs efficiency, I think it depends on how much time you have to devote. For this and many other issues, learning the maths way provides a consistent approach to deal with many issues, but requires much more time to learn. It's not really about whether the maths way is faster, it's about whether one can do what Bobysait did, or feel confident applying something they don't understand. That's the advantage of Kryzon's approach, which I have also generally followed. I mean, clearly we want to create our game at a reasonable pace of development, not spend several days trying to wrap our heads around concepts like the discriminant. However, I have to admit that in the long run, those few days of study would accelerate not only the pace of development of all our games, but the games themselves as well, in terms of more efficient code. Part of the problem is that it's hard to find a tutorial on these concepts that doesn't presume significant prior knowledge (accidentally or intentionally) in the given area of math. Here's an example. These tend to be written by experts, not surprisingly, and they tend not to think about which terms their audience already know and don't know. On the other hand, I just found a site on Essential Math for Games Programmers: http://www.essentialmath.com/tutorial.htm Everything is in powerpoint for some reason. But the point is that there are probably some good "entry-level" tutorials on these topics if we really look. Anyway, great discussion! |
| ||
| I would also add that nobody has compared either of these methods to less accurate methods, like Stevie G.'s method in the other thread. What I'm doing in the meantime is just: A. Calculating the time for a bullet to reach the target where it is now B. Moving the target forward it's speed x that time. C. Aim & fire D. Move the target back where it was. No one is the wiser! Of course there is still a pointentity and two moveentity's, but it has the advantage of simplicity. And, where it's implemented correctly at the moment, it works reasonably well. Still, if you want truly accurate results, the Kryzon's and Bobysait's methods are da bomb. |
| ||
| When you come to 3D stuff, It's always a matter of maths anyway, even when you do a "simple" MoveEntity, you have to understand some standard at some maths level, like "what is a vector" (even if you don't know the "words" you have to understand how it works) Else you can't deal with 3D without the logic of what you're doing. By the way, the Kryzon's method is a maths approach (he used the blitz-commands to get it working, but it still remains some maths) And that's the part that makes me a bit laugh, its method is probably more complicate (and mostly more mathematical on the logic) than mine on the basis, because it relies on vector projections to simplfy the problem in a 2D coords space -> which is not a natural human behavior. (when I only used a physic approach, and it is by the way, the same approach than the one involved in the actual physic engines to compute collision detection, for ex: they use the same kind of stuff in the bullet physic engine) But the real difference I think is important in our methods, is not how we deal with it in blitz, (maths algorythm or bblitz-stuff) but the way we come to a solution before using a single operator. To simplify every thing, let's come back in -2500 AD, where physicians did already exist and build house, but maths hadn't been writen yet, so they had to compensate their lack of knowledge and they did. The only matter was to understand the global thing to do what they needed. Nowadays, In programmation, the matter remains the same. We just have more tools to come to solutions. And maybe where the hard part relie, is to have enough logical mind to even start thinking of a way to do things, and that, no matter the tools we have to do them, because, efficient or not, the maths remains a hammer, and only the brain can draw is the planes of the house. Then it 's not a maths question anymore to be an "expert". It only requires to be curious on the way to do things, else, we just have to use what has already been done. (and that's here where <it's about whether one can do what Bobysait did, or feel confident applying something they don't understand> is the most relevant in my opinion) It's just like being a geak or not. You're obsessed to solve solutions like you're obsessed to learn everything about something. Or you're not, and you just want something to be done, no matter how it is done. So I'm probably a geak in some way, where most "blitzers" are not (it's probably the main reason "blitzers" are "blitzers" by the way ... they prefer not having to deal with the manner, they just want things to be done "easily" or "basically") (and Kryzon is probably a geak too ... in evidence, he made is own stuff, wether or not he used some "already made functions", it still made is own method) ps : the "discriminant" is not a complicate thing, actually, we learn at it school (don't know away, but in France it is) at 12-14 years old. (Generally children does not really understand when we could apply it in real life, but the maths thing is pretty simple. Maybe teachers could or should learn maths in a different manner... like involving more concrete exemples than some triangles on a sheet of paper ...) |
| ||
| Good points all around. It makes me wonder, did Michelangelo make his own paints? How thoroughly did he need to understand the properties of the various ingredients in order to optimize a formula for the particular requirements of the Sistine Chapel ceiling? I could see that going both ways; some artists might prefer to spend their time mostly on the form and detail of their technique and artistic vision, or they might prefer a more thorough grounding in all the chemistry first. I bet most artists could benefit hugely from a better understanding of the chemistry, in the same way that most Blitzers would benefit from better understanding of the maths. Anyway, you've motivated me to do more training in maths, so thanks! |
| ||
| A. Calculating the time for a bullet to reach the target where it is now B. Moving the target forward it's speed x that time. C. Aim & fire D. Move the target back where it was. No one is the wiser! About this that you're using. You can change step B to a TFormPoint so you don't need step D. You see, with TFormPoint you can see a 3D point from an entity's point of view - for instance, having the target as origin [0,0,0] - and you can make this point offset relatively to the target by [vectorX*time, vectorY*time, vectorZ*time]. Then this function takes this same point that is relative to the target and sees it from the world's origin point of view: instead of being relative to the target, it'll be relative to the world origin, giving you the "actual" position you need to aim at. ;A) Get the time. timeTaken# = EntityDistance(playerShip\mesh, enemyShip\mesh) / bulletSpeed ;B) Find the target point in world space (the vector you're using here has to be a local vector, the values you'd be using in a MoveEntity). TFormPoint enemyShip\vectorX*timeTaken, enemyShip\vectorY*timeTaken, enemyShip\vectorZ*timeTaken, enemyShip\mesh, 0 ;C) Aim the player\cannon\etc. AlignToVector playerShip\mesh, TFormedX()-EntityX(playerShip\mesh,True), TFormedY()-EntityY(playerShip\mesh,True), TFormedZ()-EntityZ(playerShip\mesh,True), 3As you said, the method isn't exactly precise but should give that vibe of correctness. PS: If one needs to pick one of these, then go straight to the quadratic solution presented by Bobysait. It's faster and works seamlessly with 2D by simply removing the Z axis from all vectors\normals being used. And it's conveniently interfaced in that benchmark code, you just have to copy-paste. |
| ||
| Kryzon, Thanks for this. Yes, clearly Bobysait's code is much more accurate, and probably faster than either my method or your version above (although maybe not, because it's doing more; it's taking into account the actual time to reach the target where it will be, not just where is now. And that takes more time.) But I do enjoy knowing why a function works, which is the advantage of the other solutions (for me). If someone asks "How does that work" I can explain it. Of course, everything is based on lower level code that might be impenetrable to me, but if the code I see in my program is understandable to me, it gives me a feeling of authority over it. (Including the fact that I can fix it if there's a bug). That said, my Catmull-Rom interpolation function is ported from the web and is pretty much indecipherable to anyone but a mathematician. But in that case there really was no other option. Your method above does pass the test, so I'll probably go with either that or Bobysait's anyway eventually. Depends how much speed I need! |
   |