What happens when you throw a grenade at someone? Do they just stand there, glassy-eyed? Or do they roll out of the way and go for cover? Which option feels more lifelike? More real?
The goal of Game AI is to help players suspend their disbelief and feel more immersed in the world. They logically know that the NPC’s they are firing at are fake, but they want to believe that they are real. They should feel satisfying and lifelike enough to be interesting targets. They need to be smarter than a sack of bricks or there is no point shooting at them. The bad guys should follow their basic instinct to preserve life and limb by getting the heck out of dodge.
Projectile Motion
Humans have been chucking things since time immemorial. They intuitively understand how objects move through the air. Baseball and football players can estimate where a ball will land at a glance. Cliff jumpers understand that by giving themselves an initial horizontal velocity, they can clear obstacles. Any child playing monkey in the middle will quickly figure it out. Unfortunately, computers aren’t much for intuition. Fortunately they do like math and the math behind projectile motion is basic physics. Galileo worked it out in the 16th century.
Projectile motion is simple to model by separating the x and y components of velocity. The majority of the projectile motion information is provided by chapter 3 of the textbook Sears & Zemansky’s College Physics.
The example I built is in two dimensions, but adding in a z component does not change anything. Calculating movement in the x, or z direction is simple. Barring air resistance which I won’t be addressing here, objects will move at a constant rate based on the initial x velocity they were given. Air resistance can be safely ignored for our usages since it will be negligible over the short time scale we are looking at. In the x direction the distance formula is simply:
X = v0xt
Where v0 is the initial velocity in the x direction and t is the time. This is the same formula as the z direction
Calculating movement in the y direction is slightly more complicated as gravity is an acceleration not an velocity. Gravity (9.8 m/s^2) is a constant acceleration. The rate of change does not vary, but the velocity and therefore distance traveled does. The formula for movement in the y direction is:
Y = v0yt – .5gt2
Where V0 is the initial velocity in the y direction. g is acceleration due to gravity and t is the time spent traveling.
These formulas work great if your goal is to determine the landing point of that cannon ball you just fired, but seeing if a bullet hits a given target will take some algebra.
Finding the Impact Time
Attempt 1: Solving for Y
When we determine that a bullet is within range of an enemy (we could check every bullet against every enemy but that would be SLOW!) we need to determine if it will hit the target. In my 3D tech demo implementation, which you can find on my GitHub page, I used a simple sphere collider set to trigger mode around the enemies to determine which bullets to worry about. Since Unity already does optimizations under the hood related to collision detection this is fast enough to work. The solution you use to determine which projectiles to worry about will be based on the structure of your game.
Most of the information in this section is based on the textbook Artificial Intelligence for Games Ian Millington and John Funge which talks about predictive physics in chapter 3 section 5.
At this point we know:
- B – the bullet’s current location (x, y, z) – In my demo this is given by the collision objects transform. Your mileage may vary.
- V0 – the bullets current velocity (x, y, z) – Given by the rigidbody attached to the bullet
- T – the location of the target (x, y, z) – Given by the targets transform
- g – the Acceleration due to gravity – Currently set as a constant in code, though it should be imported from the world settings
Using this information we can solve the y formula for the time when the bullet reaches the position of the target, then use that time to determine the future x and y positions of the enemy. By rearranging variables, the formula for y position will start to look like something familiar from high school: a quadratic.
0 = -.5gt2 + v0yt – y
We know how to solve that! Bring in the quadratic formula.
This formula has a few caveats. Firstly, if 4 * a * c is larger than b2 then the term under the radical will be negative. Since it is impossible to take the square root of a negative number, no solution exists. So if the initial velocity is small, there may be no solution.
We aren’t out of the woods yet though even if the term under the radical is positive, the result of the formula can still be negative. Since time can never be a negative number (if you invent time travel, let me know!) a negative result must be discarded.
Finally the formula can result in two solutions. This may be a bit confusing: how can two different times result in the same value of y? The square of any number, positive and negative is always positive. Both -32 and 32both equal 9. So when we take the square root of 9 how do we know if it should be -3 or +3? We don’t. So we need to solve the formula using both options. This is what the ± symbol means. We get two results. Visually, it is easy to see that an object moving on a curved trajectory can have multiple points with the same y value.
Since the quadratic formula can give us 0, 1 or 2 real solutions for y, we must test all solutions that result to see if they are inside our target. Once we find a time for y, finding the position at the x and z position is trivial. Just plug in t and you are good to go!
Approach 2: The one that works
After implementing the approach I found that it kinda worked about half the time. I needed something more reliable. Despite everything I tried I was unable to find a way to solve for y which created the desired result. Frustrated, I decided to simplify things by trying a 2D example. Solving for y still produced demonstrably wrong results. So I decided to try a different approach. Instead of solving for t in terms of y as the textbook suggested I solved for t in terms of x instead. That proved far simpler. Since there are no squared terms to worry about, the math is much easier. It is simply:
X / vx = t
That’s it. The results are very reliable except in cases where the bullets are shot vertically. Once you have a result for t use that value to calculate the y location using the standard formulas above. Check if the result is inside the enemy and you are done. I did not test this approach in 3D but I see no reason why it should not work.
Collision Detection
In my example, I used circular enemies and simply checked if the projected position was within their radius, however, with different shaped enemies you should use the collision detection technique of your choice. You can adjust the size of the enemies colliders to make them more or less sensitive to postental hits depending on the game feel you are aiming for (pun intended). Dodging out of the way of a close but ultimately missing bullet will appear more natural then staying as a sitting duck for a bullet that looks to be on a collision course. Conversely, enemies that always perfectly dodge with inhuman reflexes aren’t very fun as players may find them too hard to hit. Tune the hit sensitivity, speed of dodging etc based on what feels fun for your game.
Moving Enemies
Very few NPCs in games sit perfectly still until something interacts with them. Most follow patrol patterns, move randomly, flock, or gather resources. If you predict hits based on the current position of a moving object then the results will always be inaccurate as the enemy will be in a different spot by the time they are in danger. You can use the current velocity and acceleration of the enemy to predict its future position and the bullet’s position relative to that. Use the same interpolation techniques used to cope with lag in networked games such as linear or quadratic interpolation based on movement pattern. The direction and speed of the enemy could change rendering the predictions inaccurate, though. Rember, in game AI, though, everything is smoke and mirrors. Enemies don’t need to be perfect, they just need to feel good.
“Real” world examples of predictive physics
Dodging
Once you determine the hit location of the bullet the enemy can use any method it wants to get out of the way. In my example I simply calculate a vector perpendicular to the projected velocity of the bullet. That way the enemy will dodge to the side. This method works pretty well in most cases. In your game, use the flee/dodging algorithm of your choice. Maybe you want NPC’s to teleport. Maybe they should have mad ninja moves like in GTA5. Be careful to tune the dodging though. Players are quickly frustrated with seemingly psychic NPC’s. They feel unfair and unfun. You may want to check if bullets are visible before dodging. NPC’s shouldn’t have perfect knowledge of the game world.
Presentation
Acknowledgements and Links
This blog post was created as part of the final project for the Game AI class at Champlain College. Please feel free to to comment with math corrections. Thanks to Dean Lawson for teaching AI and Thomas Schicker for doing such a wonderful job teaching Physics.
The code for the project can be viewed on my GitHub.
