Avoiding Collisions

[DM6]

Trying to write AI to keep an enemy ship from colliding with asteroids in a top-down Asteroids-style space game. Physics engine is integrated with verlet's method (a la Jakobsen). Trying a dynamical solution instead of a search. My method is to predict the future positions of the asteroids and ship and add the velocity vectors of the asteroids with which a collision is predicted.

(updated code)
void astgame::ShipAI(int t)
{
float m, n, o, p;
float dist[theRoids.size()];
float ang[theRoids.size()];
int temp[9] = {0,-1,-1,-1,-1,-1,-1,-1,-1};
for (unsigned int i = 0; i < theRoids.size(); i++)
{
m = theShip.pos[0] + t*(theShip.GetPosDiff(0));
n = theShip.pos[1] + t*(theShip.GetPosDiff(1));
o = theRoids[i].pos[0] + t*(theRoids[i].GetPosDiff(0));
p = theRoids[i].pos[1] + t*(theRoids[i].GetPosDiff(1));
dist[i] = getDist(m,n,o,p);
ang[i] = getAngle(m,n,o,p);
if (dist[i] < 100)
{
// Add the asteroid's index if it is closer than 100 pixels
temp[temp[0] + 1] = i;
temp[0] += 1;
}
}
float tx, ty;
for (int j = 0; j < temp[0]; j++)
{
tx += dist[temp[j]] * cos(ang[temp[j]]);
ty += dist[temp[j]] * sin(ang[temp[j]]);
}
float targetangle = 3.*pi/2.0 + atan2(ty,tx);
if (targetangle < 0) targetangle += 2.0*pi;
if (targetangle > 2.0*pi) targetangle -= 2.0*pi;
int dangerFlag = 0;
if (temp[0] != 0) dangerFlag = 1;
if (dangerFlag && theShip.angle > targetangle)
{
theShip.turning = 1;
theShip.thrustOn = 0;
}
if (dangerFlag && theShip.angle < targetangle)
{
theShip.turning = -1;
theShip.thrustOn = 0;
}
if (dangerFlag && (theShip.angle - targetangle)*(theShip.angle - targetangle) < .01)
{
theShip.thrustOn = 1;
theShip.turning = 0;
}
if (!dangerFlag)
{
theShip.thrustOn = 0;
}
}

Ship behaves as though it has some semblance of awareness, but I think my angles are messed up. Can someone tell me what I'm doing wrong?

Many thanks
-Duncan

[NicholasFrancis]

A few things spring to my attention:

* the second if should be reverset (> instead of <)
* The way you calculate your targetangle seems wrong: you want it to center around the ship. try sth like targetAngle = atan2(tx,ty) - theShip.angle

[FCCovett]

One thing I did for AI of my space combat game was to calculate the cosine of the angle between the velocity/heading vector (V ship) and the distance difference vector between the ship and the target (S target - S ship), by using the dot product between those two vectors. That cosine is very useful because its sign tells you if the ship is approaching or distancing from the target.

With a little trigonometric trick, I would calculate a cosine of an angle that would tell me how much the ship ought to steer to avoid touching the edges of the asteroid (assuming the asteroid was spherical), based on the distance between the ship and the target, and the radius of the target.

Next, I would consider the ship's speed, its maximum turn rate, its distance from the target, the time for impact, and those two cosines, to determine if the ship should change its velocity vector, and in which direction. Then, you need to compose the velocity vector with another vector, normalize the resultant, and multiple by the scalar speed, to get the new velocity vector. It's a bit involved, but it works very well, especially in a 3D space.

To see the ship AI in action, you may download the game for free from http://www.angelfire.com/mac2/yexi/

[DM6]

One thing I did for AI of my space combat game was to calculate the cosine of the angle between the velocity/heading vector (V ship) and the distance difference vector between the ship and the target (S target - S ship), by using the dot product between those two vectors. That cosine is very useful because its sign tells you if the ship is approaching or distancing from the target.

With a little trigonometric trick, I would calculate a cosine of an angle that would tell me how much the ship ought to steer to avoid touching the edges of the asteroid (assuming the asteroid was spherical), based on the distance between the ship and the target, and the radius of the target.

Ah, yes I see! Thank you. Very helpful. Would you be willing to share your trig trick? I cannot download your game; I think the link is broken.

-Duncan

[FCCovett]

Weird. I just did a download now. It's on AngelFire and the badnwidth quota is very low. Sometimes, the file is not available because of the quota has been exceeded. Anyway, try again from http://www.angelfire.com/mac2/yexi/YexiOSX.dmg

I have to find my notes, but I am leaving in a while for the whole day. I hope you can wait until tomorrow (Sunday). Sorry about that. ;)