**2**

# Target prediction system / Target leading

###
#1
Members - Reputation: **100**

Posted 30 June 2006 - 06:26 AM

###
#3
Members - Reputation: **100**

Posted 30 June 2006 - 07:22 AM

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.

###
#5
Members - Reputation: **100**

Posted 30 June 2006 - 07:35 AM

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.

###
#6
Crossbones+ - Reputation: **15259**

Posted 30 June 2006 - 07:53 AM

#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"; }

###
#7
Members - Reputation: **100**

Posted 30 June 2006 - 11:03 AM

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?

###
#8
Crossbones+ - Reputation: **15259**

Posted 01 July 2006 - 01:29 AM

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.

###
#9
Anonymous Poster_Anonymous Poster_*
Guests - Reputation:

Posted 01 July 2006 - 06:56 AM

what is your reason to have both, point and vector, instead of a single class?

###
#10
Members - Reputation: **754**

Posted 01 July 2006 - 07:42 AM

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

###
#11
Members - Reputation: **100**

Posted 01 July 2006 - 09:53 AM

#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! :)

###
#12
Crossbones+ - Reputation: **15259**

Posted 01 July 2006 - 04:40 PM

Quote:

Original post by Anonymous Poster

alvaro,

what is your reason to have both, point and vector, instead of a single class?

Deffer's explanation is correct, but I'll add a little bit to it.

A correct mathematical framework for dealing with this type of problems is Affine Geometry. Vectors are things that we can add, substract and scale (multiply by scalars), with these operations satisfying some basic axioms. Affine space is defined as a set of points, together with a vector space and an "action" of the vectors on the points. That "action" is the operation of adding a vector to a point, with the result being another point. Again there are some axioms that have to be satisfied, basically saying that from any point we can get to any other point by adding an appropriate vector, and that from a given point we will get to different points if we add different vectors.

In any case, although you end up representing both vectors and points as triplets of numbers (in the case of dimension 3), they are definitely not the same thing. Where you place the origin in your space is not important, and it shouldn't change the result of any computations. In the case of vectors, though, the vector (0,0,0) is very special in the sense that you can add it to any point and you get back the same point. There is a natural opposite of a vector, but not for a point: the opposite of "going North 10 feet" is "going South 10 feet", but what is the opposite of the spot where my dog is? The list goes on and on. Keeping separate classes for vectors and points prevents you from accidentally performing many of those meaningless computations.

###
#13
Crossbones+ - Reputation: **15259**

Posted 01 July 2006 - 05:05 PM

Quote:

Original post by deffer(*) the only exception was when I was tweaking projection-matrix, and un-projecting screen-positions - affine w wasn't equal to 0 or 1.

Actually, thinking of vectors as points with a last homogeneous coordinate of 0 and thinking of points as points with a last homogenous coordinate of 1 is not exactly correct. When you use homogenous coordinates, two sets of coordinates that are proportional to each other refer to the same point. These are the coordinates used in Projective Geometry, which is very convenient to use if you are going to be dealing with projections. You can look at affine space as a subset of projective space, for instance looking at the points [x,y,z,w] with w=1 (which is to say w!=0, since you can scale the coordinates however you want). In that case, the points [x,y,z,0], which are not affine points, are not exactly vectors either; they are points at infinity, which can be thought of as something like the points where sets of parallel lines meet. For instance, [1,0,0,0] and [2,0,0,0] are the exact same point (they indicate the direction of the x axis), but (1,0,0) and (2,0,0) are not the same vector.

The points with w different from 0 and 1 are just regular points in projective space. If you want to look at them in their more familiar affine version, you need to divide every coordinate by the w coordinate so you get back your common [x,y,z,1] type of points (or [x,y,1] if you are on 2 dimensions at this point, since you said you were projecting).

Ok, that didn't come out very clear. I guess it's too much information to put in so little space or to explain in so little time. I took an entire year of Projective Geometry in college, and at the beginning it wasn't very intuitive, but with time you realize that there is some deep truth behind this way of thinking.

[Edited by - alvaro on July 4, 2006 9:05:07 AM]

###
#14
Members - Reputation: **287**

Posted 11 June 2011 - 03:57 AM

###
#15
Crossbones+ - Reputation: **15259**

Posted 11 June 2011 - 09:23 AM

###
#16
Members - Reputation: **287**

Posted 12 June 2011 - 08:00 AM

At some point you are solving a quadratic equation and using sqrt(). If you would be taking the square root of a negative number, no interception is possible. If the solutions of the quadratic equation are both negative, there is no interception.

So if the expression inside the sqrt() is negative, theres no interception? That's simple enough. Thank you as always. After having finished my diploma thesis a few weeks ago, I also finally got around to implementing your intercept-equations and polynomial-root-finder (the ones you wrote for me about half a year ago or so...). Now interception with accelerating and steering interceptors works as well - and very fast, too. Thanks again!