Proper ogre aiming

Today we’re going to revisit a classic problem: getting ogres to aim properly – varying their attack to correctly hit enemies at different distances and elevations. Previous attempts I’ve seen at solving this problem work by varying the projectile’s speed in order to affect a hit. This seems like an unfair advantage for the ogre to have – the player can only fire grenades at one speed and must vary her angles to score direct hits. We will try to create a function which calculates angles for the ogre to fire at, and then change the ogre grenade code to use those angles.

First we need to think about the velocity vector of the grenade at the moment it is launched, and split it into components. To simplify a bit, we imagine that the ogre is facing due east, so that the grenade does not move in the x axis at all. Instead we can think in two dimensions: the _y component of the vector is the grenade’s horizontal speed, and the _z component is the vertical speed. For example:
'0 600 0' is a grenade firing exactly horizontally
'0 0 600' is moving straight up
'0 315 315' is moving at a 45 degree angle.

In general, the vector vel looks like…

'0    600*cos θ    600*sin θ'

…where θ is the angle of elevation: the angle above or below the horizontal that the grenade launches at.

We’ve entered the realm of motion of a projectile, which is a classic bit of first-year mechanics. There are many good online resources and textbooks which cover the topic, so I’ve linked to one of the more friendly ones here rather than take any of this post up with the ideas. We skip straight to the following equation:
eq1

Here y and z are offsets from the launch point of the grenade in the corresponding directions, and g is the strength of gravity for the projectile (so usually 800 in Quake). This equation predicts which points the grenade will move through, given the angle we launch it at.

We can flip this idea on its head though: if we specify the y and z offsets for the point we want to hit (e.g. the horizontal and vertical offset from the ogre to the player), then we are left with an equation which only contains θ. When we perform the substitutions of y, z and g and rearrange a little we end up with…
eq2
…where Aand C are numbers we can calculate. If we can solve this equation, then we have calculated the angle to fire at! There are only two problems…

Problem one is that sometimes this equation has no solution! In particular, the maximum range for a projectile occurs when the angle of elevation is 45 degrees. If a grenade fired at this angle falls short of the player, there’s no angle that gets a direct hit. It doesn’t bother us a great deal that sometimes the shot can’t hit directly; the bounce from the shot might help, and the ogre can fire a long shot on a hope and a prayer. We just need to anticipate the possibility that the calculation might fail. We can use the discriminant
eq3
…to test when the equation has no solution.

Problem two is that the equation is still complicated, even after all the rearranging we’ve done. To solve it exactly we must calculate a square root (which isn’t supported directly in QuakeC) and then an inverse-tangent (which can be simulated by clever use of the vectoangles function). This doesn’t really play to QuakeC’s strengths.

Instead we can solve the equation using iteration. This is a technique based on trial-and-improvement. We begin with a good guess at the angle we want to fire at, and then feed that guess into another equation, which will spit out an angle that’s (hopefully) closer to the correct firing angle. Again, we’re not going to do all the maths behind the equation here, but for the curious we are using the Newton-Raphson method.

So the mystery Newton-Raphson tells us that if x is a good guess for tan θ, then…
eq4
…is an improved estimate. The following code gives us a function which will perform this improvement once on a given θ and target point:

//speed an ogre grenade is fired at
float OGRE_G_VEL = 600;

//fixme: get the correct gravity strength for the level
float grav = 800;

//a default angle to fire at if the enemy is too far away
float OGRE_DEFAULT_ELEVATION = 30;

//uses QuakeC builtins to calculate tan of angle
//WARNING: uses makevectors! This overwrites the v_forward... globals
float(float theta) tan =
{
  local vector ang; //temporary used to calculate trig values
  ang = '0 0 0';
  ang_y = theta; //assign theta to the yaw to simplify reasoning
  makevectors(ang);
  return v_forward_y / v_forward_x;
}

//inverse tan function
//takes two parameters, numerator and denominator
//this copes better with denominator 0 and gets quadrant correct
float(float y, float x) atan2 =
{
  local vector ang; //temporary used to calculate trig values
  ang = '0 0 0';
  ang_x = x;
  ang_y = y;
  return vectoyaw(ang);
}

float(float theta, vector dest) IterateElevation =
{
  local float a, b, c; //constants in the equation to be solved
  local vector ofs; //displacement we wish the projectile to travel
  local float y, z; //horizontal and vertical components of ofs
  local float tan_theta; //trig values of the angle theta

  //calculate how far we are firing
  ofs = dest - self.origin;
  z = ofs_z;
  ofs_z = 0;
  y = vlen(ofs);

  //find the coefficients of the quadratic in tan(theta)
  a = 0.5 * grav * y * y / (OGRE_G_VEL * OGRE_G_VEL);
  b = -y;
  c = a + z;

  //check if the destination is too far to reach
  if(b*b < 4*a*c)
    return OGRE_DEFAULT_ELEVATION;

  //calculate the tan value of the given theta
  tan_theta = tan(theta);

  //reuse ang to create the improved firing direction
  theta = atan2(a*tan_theta*tan_theta - c,
                      2*a*tan_theta + b);

  //constrain the values to stop anything too mad happening
  while(theta > 90)
    theta = theta - 180;
  return theta;
}

Let’s get the preparatory stuff out the way first. There are a few constants there to explain what might otherwise be magic numbers, and make it easy to tweak e.g. grenade speed. There are also two trigonometric functions here, tan is what you’d expect. You may not be instantly familiar with atan2. It is an inverse tan function which takes a separate numerator and denominator for robustness (see the link for details).

IterateElevation is the main part, which follows a 4 step plan:

  1. Work out what A, B, C are
  2. Convert θ into tan(θ)
  3. Run Newton-Raphson on tan(θ) to get improved tan(θ)
  4. Convert tan(θ) back into θ

If you want to spot exactly where each bit occurs you should not skip the following technical note: Because the Newton-Raphson method gave us a fraction with numerator and denominator, we can put the two halves of it straight into the atan2 function, which saves us worrying about dividing by zero etc.

So that’s the magic part over, time to connect it to our ogre. We start by making some changes(in highlight below) to OgreFireGrenade so that it fires the grenade at a given elevation:

void(float elevation) OgreFireGrenade =
{
  local entity missile;
  local vector ang;

  self.effects = self.effects | EF_MUZZLEFLASH;

  sound (self, CHAN_WEAPON, &quot;weapons/grenade.wav&quot;, 1, ATTN_NORM);

  missile = spawn ();
  missile.owner = self;
  missile.movetype = MOVETYPE_BOUNCE;
  missile.solid = SOLID_BBOX;

// set missile speed
  ang = self.angles;
  ang_x = -elevation;
  makevectors (ang);

  missile.velocity = v_forward * OGRE_G_VEL;

  missile.avelocity = '300 300 300';

  missile.angles = vectoangles(missile.velocity);

  missile.touch = OgreGrenadeTouch;

// set missile duration
  missile.nextthink = time + 2.5;
  missile.think = OgreGrenadeExplode;

  setmodel (missile, "progs/grenade.mdl");
  setsize (missile, '0 0 0', '0 0 0');
  setorigin (missile, self.origin);
};

Finally we need to change the ogre’s firing sequence to make use of all this new code:

.float attack_elevation;
void() ogre_nail1	=[	$shoot1,		ogre_nail2	] {
ai_face();
self.attack_elevation = IterateElevation(OGRE_DEFAULT_ELEVATION, self.enemy.origin);
};
void() ogre_nail2	=[	$shoot2,		ogre_nail3	] {
ai_face();
self.attack_elevation = IterateElevation(self.attack_elevation, self.enemy.origin);
};
void() ogre_nail3	=[	$shoot2,		ogre_nail4	] {
ai_face();
self.attack_elevation = IterateElevation(self.attack_elevation, self.enemy.origin);
};
void() ogre_nail4	=[	$shoot3,		ogre_nail5	] {
ai_face();
OgreFireGrenade(self.attack_elevation);
};

The idea is that we calculate the firing angle over the frames preceding the attack, and store the estimated angle so far in attack_elevation. Note that the ogre’s AI is deliberately imperfect here. Firstly, we settle on the final elevation one frame before we attack, so shots may be adrift when fired at a moving target. Secondly, we update the target point each frame. This is probably more accurate than keeping it fixed at each frame, but it does have a side effect. The initial guess we feed in was calculated from last frame’s target point, so if the target has moved a lot the initial guess may no longer be any good!

In all, this means that the ogre is excellent at hitting a stationary target at any elevation, but one moving – particularly on the vertical – will be tracked with lower accuracy. Once you’ve got this much working, there’s lots of scope to play about with the AI and make it fun. Some possibilities:

  • Change the target point for the shot – perhaps aim for the feet to maximize range and bounce, or lead the player’s movement.
  • Look at allowing the ogre to make “drop shots”, where some of the time he goes for the higher arc to hit the player.
  • Let the ogre “remember” a good target angle if he scores a direct hit, and use as the basis for the next calculation
  • Try and detect places where well-aimed shots are glancing off obstructing geometry, and have the ogre change aiming tactics
  • Have a better back-up strategy where the player is out of range
  • Resolve the “fixme” comment about the function’s ability to cope with non-standard gravity…

One thing I’d recommend starting with is looking at how the ogre fires shots at a player who is a long way below. In my experience the ogre kept missing shots when they hit the ledge he was standing on and bounced over me. Tweaking where the grenade fires from might be a good fix. Go play now, but if you’ve got any questions or want to see me explain any of the glossed-over maths bits again, please leave a comment!

Advertisements

2 thoughts on “Proper ogre aiming

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s