I am using this code in a game I am creating (asteroids clone). The computer opponent uses it to target an enemy, usually the player. The intent of the code is to predict where the player will be. It should also compensate for the computer oppoenent's speed to make sure it hits the target every time.

For some reason, however, the computer occasionally enters some sort of "berserk" mode in which it rapidly targets one way and then flips 180 degrees the other way. This results in a rather funny spectacle, but at the same time the computer opponent is basically an easy target. Can anyone suggest ways to improve the algorithm and/or fix the flipping-back-and-forth problem?

Also note, in the code I placed a command to draw small rectangle at the point the computer is aiming for. When the computer enters this "berserk mode," the point is always right near the computer opponent. It then rapidily flickers from one side of the computer to the other, resulting in the 180 degree change.

I know the code is slow because it uses floating point math. I don't particularily care about speed at the time being however, all I want is a function that works.

To sumarize, the problem is basically:
- Determine a point on the screen, where, if fired at, the shot would hit the opponenet.

- The speed of the shot is always 6.5 pixels/frame. Of course, the shot's speed in the x and y planes will vary, but the total speed is 6.5/frame.

- The shot's speed is affected by the player shooting it, thus if the player shooting it is moving at 10 pixels/frame to the left, the shots fired by that player would have their speed adjusted accordingly. I suspect this means that the player firing the shot's speed must be taken into account as well as the target's speed.

- You know the opponent's position and speed in the x and y planes.

- You know your (the player firing's) speed in the x and y planes.

Basically, all information that could possibly be relavent can be obtained about where to aim.

I am really stuck on this problem, and have asked several questions in the past regarding it, none of which recieved a good, solid, algorithm (scrapdog's was a great help though). So, for this problem, I am offering 200 points. If anyone can provide any insight on how to do this, please contribute. I really would like to get this thing figured out once and for all. Thank you!

// None of these three algorithms works very well.
// The last two result in the "berserck" mode problem,
// and the first one is not very accurate.
// I am confident the problem lies in these lines...
//targetx = players[m_Target].GetSpeedX () * numframes + players[m_Target].GetX ();
//targety = players[m_Target].GetSpeedY () * numframes + players[m_Target].GetY ();
targetx = (players[m_Target].GetSpeedX () - m_SpeedX) * numframes + players[m_Target].GetX ();
targety = (players[m_Target].GetSpeedY () - m_SpeedY) * numframes + players[m_Target].GetY ();
//targetx = (playerx + players[m_Target].GetSpeedX () * numframes)/* - (m_SpeedX * numframes)*/;
//targety = (playery + players[m_Target].GetSpeedY () * numframes)/* - (m_SpeedY * numframes)*/;

//BoundCoords (targetx, targety);

// This was added in the hope that I could figure out where the problem lied. It failed.
// CString temp;
// dc->SetTextColor (RGB (255, 0, 0));
// temp.Format ("Distance X: %.1f, Distance Y: %.1f", xdist, ydist);
// dc->TextOut (50, 50, temp);
// temp.Format ("Number of Frames: %.1f", numframes);
// dc->TextOut (50, 75, temp);
//
// temp.Format ("SpeedX of comp: %.1f, SpeedY of comp: %.1f", m_SpeedX, m_SpeedY);
// dc->TextOut (50, 100, temp);
// temp.Format ("SpeedX of player: %.1f, SpeedY of player: %.1f", players[m_Target].GetSpeedX (), players[m_Target].GetSpeedY ());
// dc->TextOut (50, 125, temp);

OK, OK, I'll try and give you a hand. A little more info from you though please...
What happens at the edge of the screen? Does player wrap-around? Does the shooter or its shots? Hopefully no! (just kidding).
Also, at first glance I'm a little stuck on the idea that the shot's speed is constant, yet the shooter's speed is factored in. Say the ship is coasting heading 0 degrees and shoots at 90 degrees. I'm picturing this as slowing down the shot's horizontal motion to add some to it's vertical to achieve the "screen speed" of 6.5/frame. Let me know if that is what you want, or if you have other ideas in mind. Thanks!

0

a121496Author Commented:

At the edge of the screen, the players wrap around to the other side. The same thing happens with the shots.

What I mean about the shot's speed is basically just that the total distance a shot travels per frame is 6.5 pixels. The actual speed that the shot is going will vary. Just think about what makes sense in this scenario, that if the player is moving, the shot's actual speed will be adjusted accordingly. Does that make sense?

Here is an algorithm that takes into account the speed of the computer.
Unfortunately, I wasn't in a position to test it first, so buyer beware.

Let's solve this mathematically first.

Let's do the analysis from the frame of reference of the computer. That is, we will consider the computer to be stationary.

Define some terms:
B = Speed of bullet
Pv = Vector speed of player (target)
Cv = Vector speed of computer
P = Vector position of player (target)
C = Vector position of computer
T = target vector to fire along.

t= time to impact
a = angle to fire the bullet at
b = angle of the player's motion relative to the computer at the moment of firing

B, Pv, Cv, P, C are given. We need to calculate b, and then a.

A position vector from the player to the computer is:

C - P (using vector addition)

A velocity vector from the player relative to the computer is:

Pv - Cv (using vector addition)

b is the angle between the two vectors.
Now we can use the vector dot product:
(C - P) * (Pv - Cv) = |C- P| |Pv - Cv| cos(b)

Another definition of the vector dot product is simply to sum the product of the components:
M*N = (Mx * Nx) + (My * Ny)

So we can solve for cos(b) in terms of the given information.

Now draw a triangle with the player, computer, and point of impact.
The computer is stationary.
The player is moving with speed |(Pv - Cv)|.
This side of the triangle will be (rate*time) | Pv - Cv | * t.

The bullet is moving with speed B.
This side of the triangle will be B * t.

We know the angle b.
We need to know the angle a.

Now we can use the law of sines to compute a.

a / (|Pv - Cv| * t) = b / (B * t)

simplifying,

a = b * |Pv - Cv| / B

And now we know the angle to shoot at.
Let's translate this angle into a vector. Take the postion vector and rotate it through a.
The equations for that are:
x'= x*cos(a) + y*sin(a)
y'= -x*sin(a) + y*cos(a)

Next, translate this into code.

// We want to solve for the angle b, we need the two vectors
// the position vector and the velocity vector

// position vector from player to computer
posX= playerx - m_PosX;
posY= playery - m_PosY;

// Find the magnitute of the vectors
posMagnitute= hypot(posX, posY);
veloctiyMagnitude= hypot(velocityX, VelocityY);

// compute the dot product using components
DotProduct= (posX * velocityX) + (posY * velocityY);
// Use the other definition of dot product, solve for cos(b)
CosineOfB= DotProduct / (posMagnitute * VelocityMagnitute);
// b is in the range of 0 to pi, because that is what acos returns
// but b could also be 0 to -pi
b= acos(CosineOfB);

// Now we can solve for 'a' using the law of sines.
a= (b * velocityMagnitude) / B;

// Let's take a vector from the computer to the player, and rotate it through an angle a:

Why did you delete the other thread? I have no access to my algorithm now...looks like it's going to have to be done from scratch now.

0

a121496Author Commented:

scrapdog, I didn't know that you needed it. I would have thought you were working it out on paper or something similar and then copied it to the computer. I am very, very sorry. I had left a message there several days ago, the 9th I think, but you never responded. I assumed you didn't want to bother with it any more. At least your getting plenty of practice with you math skills =)

zyqwert, here is the code I have implemented:
double posX, posY;
double velocityX, velocityY;
double posMagnitude, velocityMagnitude;
double DotProduct, CosineOfB;
double b, a;
double targetx, targety;
// We want to solve for the angle b, we need the two vectors
// the position vector and the velocity vector

// position vector from player to computer
posX = players[m_Target].GetX () - m_PosX;
posY = players[m_Target].GetY () - m_PosY;

// Find the magnitude of the vectors
posMagnitude = hypot (posX, posY);
velocityMagnitude = hypot (velocityX, velocityY);

// compute the dot product using components
DotProduct = (posX * velocityX) + (posY * velocityY);

// Use the other definition of dot product, solve for cos (b)
CosineOfB = DotProduct / (posMagnitude * velocityMagnitude);
// b is in the range of 0 to pi, because that is what acos returns
// but b could also be 0 to -pi
b = acos (CosineOfB);

// Now we can solve for 'a' using the law of sines.
a = (b * velocityMagnitude) / 6.5;

// Let's take a vector from the computer to the player, and rotate it through an angle a:
posX = -m_PosX;
posY = -m_PosY;
targetx = posX * cos (a) + posY * sin (a);
targety = -posX * sin (a) + posY * cos (a);

// The target vector is relative to the computer, so let's offset it by the computer position:
targetx += m_PosX;
targety += m_PosY;

BoundCoords (targetx, targety); // Makes the coordinate
// be on the screen. It
// wraps points around which are not.

Is it all correct? It doesn't seem to work quite right..... Note that all of this is being calculated in the player class, thus m_PosX/m_PosY represents the computer whose firing's point. players[m_Target].whatever represents the ship the computer is firing at.

OK, here's my "shot" <grin> at this problem. I started from scratch instead of using your code (not that I have a problem with it, but my trig is rusty!)

I might get booted from EE altogether though cause this is FAR from an elegant solution, but maybe you'll give it a whirl.

Assumptions: 1.The shot will travel faster than the target in all but special cases
2.The hit detection area is at least 10x10 pixels.
3.The coordinates I used represent the center of the sprites.
4.The target's path can be predicted with constant velocity
(no or negligible "friction")
5.Screen coordinates are all positive starting with (0,0)
in upper-left corner of screen.

What SHOULD happen <g> is that the shot will try and directly intercept the ships predicted path. By this I mean that it won't anticipate a screen wrap-around, but it will be accurate through even when following the ships through wrap-arounds.

Performance: worst case is 42 fabs and 22 sqrts, best case is 4 fabs and 3 sqrts.

I didn't test it, but if you don't mind, please give it a run and let me know how it works. Don't feel bad if you end up wanting to reject this answer and look for other solutions. This is an awesome thread.

//this should be plenty of iterations to hit.
for(int i=0;i<20;i++)
{
//will be squared, sign doesn't matter
xDistToTarget=targetTempXpos-shooterxpos;
yDistToTarget=targetTempYpos-shooterYpos;

//How much time has elapsed on this path
//to our target? Where would he be by then?
frames=distToTarget/6.5;//frames is an int on
//purpose,but you could try a float
targetNewXpos=targetXpos+targetXv*frames;
targetNewYpos+=targetYpos+targetYv*frames;
if(fabs(targetNewXpos-targetTempXpos)<10.0 &&
fabs(targetNewYpos-targetTempYpos)<10)
{
//We have a reasonable hit!
i=20;
}
else
{
//aim for his new position and try again.
//Since we are faster, we'll narrow the gap
targetTempXpos=targetNewXpos;
targetTempYPos=targetNewYpos;
}
}//end for

//back to Pythagoras.A squared + B squared = C squared
//Reduce shotXv and shotYv to where their total is 1
int divisor=fabs(shotXv)+fabs(shotYv);
shotXv/=divisor;
shotYv/=divisor;
float Csquared=6.5*6.5;
shotXv=sqrt(shotXv*Csquared);
shotYv=sqrt(shotYv*Csquared);
shotXpos=shooterXPos;
shotYpos=shooterYPos;

Good luck! Let me know if this helps, or if you'd like more.
David

0

a121496Author Commented:

For now, I am going to reject your answer.

For everyone who is helping, I can switch between the algorithms quickly, so if you wish to change something in your solution, please feel free. The points go to the first person who can give me a solution that works perfectly.

Now, dvest, thank you for your answer. Unfortunatly, like most of the others, it doesn't take into account the speed of the player who is firing. This causes the ship who is firing to have a much lower accuracy if it is moving quickly past its target.

It seems the main problem has become how do I take into account the speed of the player who is firing? All the algorithms so far, except mine, do not take it into account. But mine has that berserck mode problem which causes the firer to miss 50% of the time anyway.

I suspect I have to take into account the speed of the player who is shooting on these lines, but I don't know.

dvest, to elaborate a bit more, what happens is if the target (me) is sitting still, and the opponent (the one using this algorithm) is moving quickly past the target and fires, its shots do not hit the target. Does this make sense? Hope so =)

If anyone needs further clarification about what is happening please ask. Points ---> 300.

0

a121496Author Commented:

By the way, dvest, I am using angles rather than vectors. Accordingly, I commented out your algorithm's last lines and replaced them with

targetx = targetNewXpos;
targety = targetNewYpos;

Then, below all that code, it calculates the angle around the ship that it should fire at. I don't think this should affect the results any though.

0

a121496Author Commented:

Just for anyone else who wants to help, here are some variables that I would rather you use so it is easier for me to integrate it with the program:

target player object = players[m_Target]
target player x speed = players[m_Target].GetSpeedX ()
target player y speed = players[m_Target].GetSpeedY ()
shooter x speed = m_SpeedX
shooter y speed = m_SpeedY
speed of bullet = 6.5

It doesn't really matter because I can use the find and replace option, but it would be nice =)

Thanks for evaluating my algorithm. By the way, did you already run it? Was it at least close? <grin>. Gotta admit I'm kinda curious.
I was thinking this would work regardless of the shooter's velocity. The idea being the shot goes directly to the calculated intercept point at an on-screen speed of 6.5. Did you add code that adds shooter velocity to my calculated shot speeds? Also, were the assumed conditions in my posting correct?
Back to the drawing board for now. We'll keep plugging along. If you can provide more feedback, that will be a help.

We'll whip this yet!
David

0

a121496Author Commented:

Yes, I did run it =) Guess I wasn't that clear on that account. Here is the exact code that I implemented:

//this should be plenty of iterations to hit.
for (i = 0; i < 20; i++)
{ //will be squared, sign doesn't matter
xDistToTarget = targetTempXPos - m_PosX;
yDistToTarget = targetTempYPos - m_PosY;

// How much time has elapsed on this path
// to our target? Where would he be by then?
frames = distToTarget / 6.5;//frames is an int on purpose, but you could try a float
targetNewXpos = players[m_Target].GetX () + players[m_Target].GetSpeedX () * frames;
targetNewYpos = players[m_Target].GetY () + players[m_Target].GetSpeedY () * frames;
if (fabs (targetNewXpos - targetTempXPos) < 15.0 &&
fabs (targetNewYpos - targetTempYPos) < 15.0)
{ //We have a reasonable hit!
break;
}
else
{ //aim for his new position and try again.
//Since we are faster, we'll narrow the gap
targetTempXPos = targetNewXpos;
targetTempYPos = targetNewYpos;
}
}

targetx = targetNewXpos;
targety = targetNewYpos;

// ************************************** YOURS ENDS HERE ******************************

if (m_CurDist > m_MinDist)
{ m_ShouldAccel = true; }

if (m_MinDist < 150)
{ m_MinDist = 150; }

if (m_CurDist < m_MinDist) // Glom on mode.
{ m_MinDist = m_CurDist; }

if (m_CurDist < 250.0)
{ m_ShouldFire = true; }
}

////////////////////////

Yes, the code was close. It would hit great if the computer was not moving or was moving very little. If, however, the computer (the shooter) was moving quickly, then it was not so accurate. Also, yes, your assumed conditions were all correct.

You mention:
-- Did you add code that adds shooter velocity to my calculated shot speeds?
Where would I add this code? I am not sure. That is probably the problem in fact. Can you show me in the above code where I would add these numbers?

0

a121496Author Commented:

Should have added that the code after the "your code ends here" section determines an angle around the ship at which to fire. You see, the players are all facing some angle, 0-360. 0 is straight to the right, 90 is up, 180 is left, 270 is bottom.

Your code seems to calculate the speed the shot should go in the x and y directions rather than the angle the ship should fire at. As a result, I removed the last piece of your code and used instead the atan2 code to determine the angle around the ship. I know my way is slower, but it works better because then the computer doesn't cheat by being able to fire anywhere even if it isn't aiming in that direction =)

Hmm, with the code I provided, it should hit regardless of computer ship's speed. At least it seems we've got the flipping thing down for the time being. Here are just a few thoughts, and see if they ring any bells.
When the actual shot is created, activated, whatever...is there code in its construction that will add the shooter's velocity (vector, angle, etc. ) to the shot outside of the code we've been working on here? It shouldn't in this case.
Does the shooter instantly rotate to firing position, or does this conceivably take a couple of frames and THEN the shot is released? (mine would have to be released on the same frame the calculations were done).
Since you mentioned sprite positions were the center of the sprite, that's one problem that shouldn't crop up to bite us.

Let me know when you can,
David

0

a121496Author Commented:

The shooter instantly rotates to the correct position. It does not take any time to change.

But, yes, there was code in the creation of the shot that adds the computer's speed to the shot. I changed it so it didn't and it worked great! Its accuracy is excellent. And it doesn't do the berserck thing =)

Now that we have established the problem, would it be possible to modify the algorithm so that it takes the speed of the computer into account? As it stands, the computerized player's shots are not effected by its speed, but the human players are. I would like it so all player's shots are affected by the firers speed, so the physics are at least correct in that area =)

If it isn't possible, please just post an answer to the question and get the 300 points. If it is possible, please tell me the fix. Of course, I don't know either way, so you could cheat and not tell me... but that wouldn't be very nice. =)

Yeehah!
Glad we got it working well. That's a huge step! Now I'm sure we can tweak things to get the shot affected by shooter's speed. I'll have more questions to post to get info from you on this matter (sometimes it takes me a while to develop a clear picture of what's going on) :)
More to come tomorrow.

P.S. Can I get a copy of the game? Just for personal kicks and grins? I've got an asteroids variant I did a year ago (but never got to finish before the hard drive died taking my source code) that you're welcome to if you'd like to look at it. The source was relatively worthless anyhow as I was learning as I went. Some really shoddy c++ code in that puppy! No hard feelings if you don't want to send it out though.

just a note, the velocity of the bullet should be
(the speed of the ship at the time of the shot)+(The release speed) and the target should be calculated using current velocity and then aim, using the distance between the ship and it self and then firing ahead of it's target in the hope to hit it. well just some last little footnotes.

//back to Pythagoras.A squared + B squared = C squared
//Reduce shotXv and shotYv to where their total is 1
//////////////////////////////////////////////////////////////
to:
/////////////////////////////////////////////////////////////
}//end for

//back to Pythagoras.A squared + B squared = C squared
//Reduce shotXv and shotYv to where their total is 1}//end for
/////////////////////////////////////////////////////////////////////

then:
option 1)
replace these two lines toward the end of the block of code:
//////////////////////////////////////////////////////////////////////
shotXv=sqrt(shotXv*Csquared);
shotYv=sqrt(shotYv*Csquared);
//////////////////////////////////////////////////////////////////////
with:
/////////////////////////////////////////////////////////////////////
shotXv=sqrt(shotXv*Csquared)+shooterXv;
shotYv=sqrt(shotYv*Csquared)+shooterYv;
////////////////////////////////////////////////////////////////////
or
option 2)
Reactivate the code you had originally that adds the shooter's velocity
to the shot. Hope you just commented it out. =)

The intent of this version is that the shot maintains a speed of 6.5 in relation to the firing ship. If for some reason the shooter was moving backwards at 6.5 pixels per frame, the shot would appear as sitting still on the screen.

Since we currently can hit the target quite well, we adjust our aiming point by subtracting (shooter velocity) *( frames it takes shot to intercept). When we then add the velocity vector of the shooter to the shoot, our target should still be in big trouble =)

Under option 1) , I think it was, the new code should be:

float Csquared=6.5*6.5;
shotXv=sqrt(shotXv*Csquared);//new
shotYv=sqrt(shotYv*Csquared);//new
//shotXv and shotYv now contain the vectors for
//the ship to aim its gun at i.e.
/*
float aimAtX=shotXv;
float aimAtY=shotYv;
*/
//now we adjust shot velos so the bullet arrives at the target
//which might be somewhere other than where we're physically aiming
shotXv+=shooterXv;//new
shotYv+=shooterYv;//new

David

0

a121496Author Commented:

Shoot, it appears you missed one of my comments:

Date: Sunday, January 17 1999 - 12:26PM PST
"By the way, dvest, I am using angles rather than vectors. Accordingly, I commented out your algorithm's last lines and replaced them with

targetx = targetNewXpos;
targety = targetNewYpos;

Then, below all that code, it calculates the angle around the ship that it should fire at. I don't think this should affect the results any though."

The changes you are suggesting involve changing code that I had commented out. Is there a way to change the code in the loop to accomplish the same thing? I have accepted your answer either way.

What I am trying to do is determine the exact point that the computer should shoot at. This would be the absolute best. I do not want to use vectors because that would mean I would have to get rid of a bunch of code and replace it with something else so it knew where to accelerate to =(

at a speed of 6.5, then the shooter velo should be added to the shot.
Will that work for you?

0

a121496Author Commented:

Okay, that makes sense. Unfortunately, I tried it and we are back to the berserck mode thing =( I think Otta was right originally that the atan2 function is returning the incorrect sign. Would anyone happen to know how to correct the error?

// # signs indicate the quadrant the target is in relative
// to the shooter. At least they should...
if (targetx > m_PosX)
{ if (targety > m_PosY) // #4
{ angle = atan2 ((targety - m_PosY), (targetx - m_PosX));
angle /= DEG2RAD;
angle = 360.0 - angle;
}
else // #1
{ angle = atan2 ((m_PosY - targety), (targetx - m_PosX));
angle /= DEG2RAD;
}
}
else
{ if (targety > m_PosY) // #3
{ angle = atan2 ((targety - m_PosY), (m_PosX - targetx));
angle /= DEG2RAD;
angle += 180.0;
}
else // #2
{ angle = atan2 ((m_PosY - targety), (m_PosX - targetx));
angle /= DEG2RAD;
angle = 180.0 - angle;
}
}

DEG2RAD is defined as .01745329252, which I am certain is correct.

What could be done to the above code that would correct the sign error (presuming that is the cause of the berserck problem)?

OK, now I'm stuck again. Let me go through what I think is going on.
1. We started with the berserk problem.
2. We then got to where targeting was stable, but didn't take into account shooter velocity.
3. Next we got to where the speeds of both were taken into account and the accuracy was excellent, but the firing ship wasn't facing the most appropriate angle.
4. Finally, we had code to tell the firing ship where to aim for, but this time adding velocities to the shot resulted in berserk mode all over again.

It seems as if analyzing the actual changes between 3 and 4 would give us the answer.We ought to be able to work something out. I'd like to continue to help with this. If you are interested, we could discuss it over Instant Messanger or work something else out..

We can of course continue to work here, but the delay between post/response can be a drawback.

Let me know what you think,
David

0

a121496Author Commented:

Thank you for your offer to help more, unfortunately at the time I am very busy. I will try to get back to you next week and at that time we can see what can be done. BTW-I think I forgot to say that you can have a copy of the game. I am keeping a list for those who are interested.

0

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

What happens at the edge of the screen? Does player wrap-around? Does the shooter or its shots? Hopefully no! (just kidding).

Also, at first glance I'm a little stuck on the idea that the shot's speed is constant, yet the shooter's speed is factored in. Say the ship is coasting heading 0 degrees and shoots at 90 degrees. I'm picturing this as slowing down the shot's horizontal motion to add some to it's vertical to achieve the "screen speed" of 6.5/frame. Let me know if that is what you want, or if you have other ideas in mind. Thanks!