Target prediction system / Target leading

kickkick · 2011-06-12T14:00:20

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.

Artificial Intelligence Programming

Started by kickkick June 30, 2006 12:26 PM

14 comments, last by Max Power 13 years, 5 months ago

kickkick

Author

100

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.

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

alvaro

21,607

July 01, 2006 10: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.

alvaro

21,607

July 01, 2006 11: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]

Max Power

393

June 11, 2011 09:57 AM

I have to bring this topic back from the dead, because I'm using the equotion from this post and I have a question about it. I was getting constant crashes in my simulation recently and I could narrow the source down to my getInterceptDir-function. Apparently, some of my projectiles are too slow to actually intercept their target. I need to do a check first, I guess. So my question is: how can I tell wether interception is possible or not?

alvaro

21,607

June 11, 2011 03:23 PM

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.

Max Power

393

June 12, 2011 02:00 PM

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!

Target prediction system / Target leading

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Target prediction system / Target leading

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines