17 users logged in
Proud partner of GDC 2025
Before posting, review our community guidelines.
Support GameDev.net with a monthly GDNet+ subscription!
Target prediction system / Target leading
June 30, 2006 12:26 PM
An excellent AI system should have everything coded in it, including the so called "target leading" (I like to call it the target prediction system). We should come up with an algorithm that has the purpose of calculating the direction in which to shoot a non-infinite-velocity bullet, in order to hit a moving target. As you know, calculating the direction is easy if the bullet has infinite speed: just look directly at the target! However, if bullets have a certain speed, the target has a good chance of moving away after the bullet has been fired. For that, the shooter should shoot AHEAD of his target. I've heard that this topic's been posted more than once in some math or physics forums, but I have't found anything with google searches, just basic ideas on it. Also, a search on GameDev reveals nothing. So I hope that we will finally post a fully working target prediction system. Technically, this means it's more like a math problem than a programming problem, though the algorith optimization is a programming part. If math were so easy, everyone could just solve it by himself. Coming up with a 3D target prediction system is too hard, 1D is just nonsense, so the 2D will do. That is, consider a 2D plane which is viewed from a top camera, and nothing special like air resistance and gravity. First I'm going to ask some of you about your opinion on how to approach this problem, maybe for someone just to post the final result :). We can work together on the algorithm. In the end, if nothing comes out of it, I'm going to post my own system.
June 30, 2006 01:22 PM
That is a simple process once the TPS has been solved.
If the bullet's speed does not depend on the shooter's speed, then it is the same as if he were not moving.
If the bullet's speed does depend on the shooter's speed, then we just substract the shooter's vector (X-speed, Y-speed) from the target, as if the coordinate system were moving with the shooter.
If the bullet's speed does not depend on the shooter's speed, then it is the same as if he were not moving.
If the bullet's speed does depend on the shooter's speed, then we just substract the shooter's vector (X-speed, Y-speed) from the target, as if the coordinate system were moving with the shooter.
June 30, 2006 01:25 PM
It also depends on the Physics system you are using, i.e. many games use a 'fudged' physics system which makes things much harder to reliably predict.
Tristam MacDonald. Ex-BigTech Software Engineer. Future farmer. [https://trist.am]
June 30, 2006 01:35 PM
Hmm.. what do you mean by fudged?
explain it...
Btw, it's not about the system I'll use, we're just making any system that shoots ahead. Preferably it's something as fluid as possible. You should make assumptions youself, such as the current location of the target is always known (otherwise it won't be much of a game engine).
In my system, the shooter, the bullet and the target are all point-like objects for maximum accuracy. You just pass the current data into the main function, and it returns the current targeting location.
explain it...
Btw, it's not about the system I'll use, we're just making any system that shoots ahead. Preferably it's something as fluid as possible. You should make assumptions youself, such as the current location of the target is always known (otherwise it won't be much of a game engine).
In my system, the shooter, the bullet and the target are all point-like objects for maximum accuracy. You just pass the current data into the main function, and it returns the current targeting location.
21,610
June 30, 2006 01:53 PM
The math is not hard at all, and it's exactly as easy in 3D as it is in 2D. This is the code to do it in 2D (although you can just change the definitions of Vector and Point to be 3D if you want, and it should all work the same):
#include <iostream>
#include <cmath>
struct Vector {
double x,y;
Vector(double x, double y):x(x),y(y){
}
double dot(Vector const &v) const{
return x*v.x+y*v.y;
}
};
Vector operator*(double s, Vector const &v){
return Vector(s*v.x,s*v.y);
}
struct Point {
double x,y;
Point(double x, double y):x(x),y(y){
}
Vector operator-(Point const &p) const{
return Vector(x-p.x,y-p.y);
}
Point operator+(Vector const &v) const{
return Point(x+v.x,y+v.y);
}
};
double largest_root_of_quadratic_equation(double A, double B, double C){
return (B+std::sqrt(B*B-4*A*C))/(2*A);
}
Point intercept(Point const &shooter, double bullet_speed, Point const &target, Vector const &target_velocity){
double a = bullet_speed*bullet_speed - target_velocity.dot(target_velocity);
double b = -2*target_velocity.dot(target-shooter);
double c = -(target-shooter).dot(target-shooter);
return target+largest_root_of_quadratic_equation(a,b,c)*target_velocity;
}
Vector shoot_at(Point const &shooter, Point const &interception, double bullet_speed){
Vector v = interception-shooter;
return bullet_speed/std::sqrt(v.dot(v))*v;
}
int main(){
Point shooter(0,0);
Point target(0,10);
Vector target_velocity(3,0);
double bullet_speed = 5.0;
Point P = intercept(shooter,bullet_speed,target,target_velocity);
Vector V = shoot_at(shooter,P,bullet_speed);
std::cout << "Shoot in direction (" << V.x << ',' << V.y << ") and you'll hit the target at (" << P.x << ',' << P.y << ").\n";
}
June 30, 2006 05:03 PM
Thanks alvaro, the code works fine and is better than my code. My math calculations start like this:
x1 + cosA = x2 + cosB
y1 + sinA = y2 + sinB
This goes into a second degree equation, also aCos() can be + or -. So I need to check 4 values for validity! That's very unoptimal!
Too bad don't have the math knowledge to understand this code :). Specifically, I've got to look up info about dot products. I would appreciate a math explanation or some equation showing what's going on here. A link is enough.
Could you also post the code for 3D?
x1 + cosA = x2 + cosB
y1 + sinA = y2 + sinB
This goes into a second degree equation, also aCos() can be + or -. So I need to check 4 values for validity! That's very unoptimal!
Too bad don't have the math knowledge to understand this code :). Specifically, I've got to look up info about dot products. I would appreciate a math explanation or some equation showing what's going on here. A link is enough.
Could you also post the code for 3D?
21,610
July 01, 2006 07:29 AM
My code works as follows (I am afraid you have to understand the dot product to follow it):
Say the target is initially at position A with a velocity vector v and the shooter is at position B and not moving. At time t the target will be at (A+t*v). We'll try to find the time t at which we can hit the target with a projectile. That value of t satisfies that the distance between (A+t*v) and B is t times the projectile's speed, s.
distance(A+t*v,B) = t*s
The distance between two points is the length of the vector between them (A+t*v-B), and the length of a vector is the square root of the dot product of the vector with itself.
sqrt((A+t*v-B).(A+t*v-B)) = t*s
We can square both sides of the equation to make it easier to deal with (although this type of manipulation often introduces new solutions, so be careful...).
(A+t*v-B).(A+t*v-B) = t^2*s^2
(A-B+t*v).(A-B+t*v) = t^2*s^2
The dot product is bilinear, so we can do:
(A-B).(A-B)+t^2*(v.v)+2*t*((A-B).v) = t^2*s^2
(s^2-(v.v))*t^2 - (2*((A-B).v))*t - (A-B).(A-B) = 0
This is now a quadratic equation in t, which has too solutions.The larger solution is the one we are interested in. I think you can look at the smaller solution as the time at which the target could have shot at you if you were to be hit now. [EDIT: Any positive solution will work. If you simply take the larger solution of the two, you are guaranteed it will be positive as long as the bullet is faster than the target.]
Once we know the value of t, it's easy to compute A+t*v to find out where the target is going to be hit, and we just have to shoot towards that point.
Notice that the procedure I just described doesn't depend on the dimension of the space in which we are moving, so it can be applied to 3D as easily as to 2D. The modifications to my code in order to do that are fairly obvious, and I think you should try to make them yourself. Just change the definitions of Vector and Point (and the basic methods and functions to deal with them) so there is an extra component z, which is treated just like the others. The functions largest_root_of_quadratic_equation, intercept and shoot_at remain exactly as they are.
If you are serious about game development, you should try to get familiar with linear algebra, including low-dimensional vector spaces, matrices as linear mappings, dot product, orthogonal projection and probably quadratic forms, while you are at it.
Say the target is initially at position A with a velocity vector v and the shooter is at position B and not moving. At time t the target will be at (A+t*v). We'll try to find the time t at which we can hit the target with a projectile. That value of t satisfies that the distance between (A+t*v) and B is t times the projectile's speed, s.
distance(A+t*v,B) = t*s
The distance between two points is the length of the vector between them (A+t*v-B), and the length of a vector is the square root of the dot product of the vector with itself.
sqrt((A+t*v-B).(A+t*v-B)) = t*s
We can square both sides of the equation to make it easier to deal with (although this type of manipulation often introduces new solutions, so be careful...).
(A+t*v-B).(A+t*v-B) = t^2*s^2
(A-B+t*v).(A-B+t*v) = t^2*s^2
The dot product is bilinear, so we can do:
(A-B).(A-B)+t^2*(v.v)+2*t*((A-B).v) = t^2*s^2
(s^2-(v.v))*t^2 - (2*((A-B).v))*t - (A-B).(A-B) = 0
This is now a quadratic equation in t, which has too solutions.
Once we know the value of t, it's easy to compute A+t*v to find out where the target is going to be hit, and we just have to shoot towards that point.
Notice that the procedure I just described doesn't depend on the dimension of the space in which we are moving, so it can be applied to 3D as easily as to 2D. The modifications to my code in order to do that are fairly obvious, and I think you should try to make them yourself. Just change the definitions of Vector and Point (and the basic methods and functions to deal with them) so there is an extra component z, which is treated just like the others. The functions largest_root_of_quadratic_equation, intercept and shoot_at remain exactly as they are.
If you are serious about game development, you should try to get familiar with linear algebra, including low-dimensional vector spaces, matrices as linear mappings, dot product, orthogonal projection and probably quadratic forms, while you are at it.
755
July 01, 2006 01:42 PM
Quote:
Original post by Anonymous Poster
alvaro,
what is your reason to have both, point and vector, instead of a single class?
I also have both types. The reason being: type safety in mathematical expressions.
In my experience, I was almost(*) always able to distinguish logically wheater a variable is a position or an offset. Logically, you would make all the math computations on vectors (meaning: offsets in space, n-dim distances). Position is meant as a placement unit (**).
You would never:
- add two positions
- normalize position (as opposed to direction vector)
- take dot/cross product of position/position or position/vector
- scale position (unless for graphic purposes, but that should be done by affine matrices anyway)
---------------
(*) the only exception was when I was tweaking projection-matrix, and un-projecting screen-positions - affine w wasn't equal to 0 or 1.
(**) It's similar to what iterators mean in std containers. There's an iterator and a distance unit.
iterator1 - iterator2 = distance.
iterator * 2 // error
iterator1 + (iterator2 - iterator3) * 2 // ok
July 01, 2006 03:53 PM
I've analyzed the code and the math. One thing I don't understand is why are we interested in the largest quadratic root. The rest I understood. The way I think about vectors has changed (well, I haven't learnt much about them before). I've modified the code to work with 3D enviroment, but I'm not 100% sure it's correct.
The Vector and the Point is now combined, also operator% is used as the dot product. I've made optimizations where I could. The results are quite satisfactory: on my PC one million of these calculations take only one second. Thanks alvaro, your help is greatly appreciated!
There's something I concluded from this. Geometry sucks! :)
#include <iostream>#include <iomanip>#include <cmath>#include <ctime>using namespace std;class Vector { double x, y, z;public: Vector(); Vector(double x, double y, double z); friend ostream &operator<<(ostream &stream, const Vector &v); friend Vector operator+(const Vector &v1, const Vector &v2); friend Vector operator-(const Vector &v1, const Vector &v2); friend Vector operator*(const double &m, const Vector &v); friend Vector operator*(const Vector &v, const double &m); friend double operator%(const Vector &v1, const Vector &v2);};Vector::Vector(){}Vector::Vector(double x, double y, double z): x(x), y(y), z(z){}ostream &operator<<(ostream &stream, const Vector &v){ stream << '(' << v.x << ',' << v.y << ',' << v.z << ')'; return stream;}Vector operator+(const Vector &v1, const Vector &v2){ return Vector(v1.x + v2.x, v1.y + v2.y, v1.z + v2.z);}Vector operator-(const Vector &v1, const Vector &v2){ return Vector(v1.x - v2.x, v1.y - v2.y, v1.z - v2.z);}Vector operator*(const double &m, const Vector &v){ return Vector(m * v.x, m * v.y, m * v.z);}Vector operator*(const Vector &v, const double &m){ return Vector(m * v.x, m * v.y, m * v.z);}double operator%(const Vector &v1, const Vector &v2){ return (v1.x * v2.x) + (v1.y * v2.y) + (v1.z * v2.z);}Vector intercept(const Vector &p_shooter, double bullet_speed, const Vector &p_target, const Vector &v_target){ Vector BA = p_target - p_shooter; double vxv = v_target % v_target; double b = BA % v_target; double a = bullet_speed * bullet_speed - vxv; return p_target + (b + sqrt(b*b + a * (BA%BA))) / a * v_target;}Vector shoot_at(const Vector &p_shooter, const Vector &p_interception, double bullet_speed){ Vector v = p_interception-p_shooter; return bullet_speed/sqrt(v%v) * v;}int main(){ unsigned int c, n; unsigned int EVENT_COUNT; bool q; // ask the user cout << "Enter number of shots to calculate: " << endl; cin >> EVENT_COUNT; // allocate the memory cout << "allocating memory" << endl; Vector *p_shooter = new(nothrow) Vector[EVENT_COUNT]; Vector *p_target = new(nothrow) Vector[EVENT_COUNT]; double *bullet_speed = new(nothrow) double[EVENT_COUNT]; Vector *v_target = new(nothrow) Vector[EVENT_COUNT]; Vector *p_hit = new(nothrow) Vector[EVENT_COUNT]; Vector *v_shoot = new(nothrow) Vector[EVENT_COUNT]; if(!p_shooter || !p_target || !bullet_speed || !v_target || !p_hit || !v_shoot) { cout << "failed!" << endl; return 1; } else cout << "completed" << endl; // randomize timer cout << "randomize_timer: 1 second" << endl; c = clock() + 1000; while(clock() < c) rand(); cout << "randomize_timer completed\n" << endl; // simulate EVENT_COUNT shots cout << "calculating " << EVENT_COUNT << " events" << endl; c = clock(); for(n = 0; n < EVENT_COUNT; n++) { *p_shooter = Vector((rand() % 101) - 50, (rand() % 101) - 50, (rand() % 101) - 50); *p_target = Vector((rand() % 101) - 50, (rand() % 101) - 50, (rand() % 101) - 50); *bullet_speed = (rand() % 5) + 10; *v_target = Vector((rand() % 7) - 3, (rand() % 7) - 3, (rand() % 7) - 3); *p_hit = intercept(*p_shooter, *bullet_speed, *p_target, *v_target); *v_shoot = shoot_at(*p_shooter, *p_hit, *bullet_speed); p_shooter++; p_target++; bullet_speed++; v_target++; p_hit++; v_shoot++; } cout << "calculation finished in " << clock() - c << " milliseconds" << endl; // ask the user cout << "do u want to see the results? (1/0)" << endl; cin >> q; if(!q) return 0; // display 4xEVENT_COUNT lines of bulk data cout << "displaying calculations:" << endl; p_shooter -= EVENT_COUNT; p_target -= EVENT_COUNT; bullet_speed -= EVENT_COUNT; v_target -= EVENT_COUNT; p_hit -= EVENT_COUNT; v_shoot -= EVENT_COUNT; for(n = 0; n < EVENT_COUNT; n++) { cout << clock(); cout << "shooter loc: " << *p_shooter << ", target loc: " << *p_target << '\n'; cout << "bullet's speed: " << *bullet_speed << ", target dir " << *v_target << '\n'; cout << "shoot dir: " << *v_shoot << ", intercept loc: " << *p_hit << '\n' << endl; p_shooter++; p_target++; bullet_speed++; v_target++; p_hit++; v_shoot++; } return 0;}The Vector and the Point is now combined, also operator% is used as the dot product. I've made optimizations where I could. The results are quite satisfactory: on my PC one million of these calculations take only one second. Thanks alvaro, your help is greatly appreciated!
There's something I concluded from this. Geometry sucks! :)
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
Recommended Tutorials
Advertisement