From Mike Kulas, Programmer:
Today, I’m going to show you some videos of the new “leading” code. Through the most recent demo, robots have not been leading the player when they fire. They will always try to point at the player and fire at that point. If the player is moving fast left/right/up/down relative to the robot, unless the robot is very close to the player, the projectiles will almost all miss.
Have a look at the videos and then I’ll get a little bit into the math and how we balance around a new feature that affects difficulty.
In order for the robots to lead the player, they have to make certain assumptions. The key assumption they make is that the previous second of the player’s movement is a good predictor of what is to come. So if the player moved 8 meters in a certain direction in the previous second, the robots will “predict” that the player will be 8 meters farther along in the same direction one second later. This will often not be the case, but, empirically, it’s not a bad predictor. If we wanted to get very advanced we could have the robots conclude that the player is circle-strafing and assume that will continue into the near future. That would result in a different predicted location. Even better, a robot might observe that the player is headed towards a powerup, or perhaps a key or a door to exit the battle. In multiplayer a human does this effortlessly. Maybe we’ll think about that later…
For now we’re just solving the problem of leading with the assumption that what the player did in the past second is what will occur over the next several seconds. The math behind this is actually quite tricky. In fact, I don’t think there’s a “closed form solution” to it. It’s not just a matter of determining when two objects with known velocity will collide. Other things come into play, notably that the robot has a limited rate of turning. Compounding it, the robots will slow down their rate of turn as they near their desired orientation.
Fortunately, the math doesn’t have to be perfect. The player and the projectiles have size — we are not trying to get a vector to collide with another vector. Also, we don’t want to hit the player with every projectile. In fact, we compute a pretty good direction we want to fire and then we reduce its accuracy based on difficulty level and the particular robot involved. As with other properties, the ability of a robot to predict where the player is headed will vary.
We had leading code in Descent 2, but we cheated. We didn’t address the problem of limited turn rates. We just solved the problem based on the velocity of the player and the projectile and fired the projectile at the predicted collision point regardless of the robot’s orientation. If the player was moving in a jerky manner, some robots would be spewing projectiles in wildly varying directions.
One thing about the robots being a little “smarter” in how they aim is that it’s an opportunity for the player to exploit this “intelligence”. A good pilot will probably be able to make a robot miss more often by exploiting the fact that it wants to lead. So we’ll probably need to modify the leading behavior to account for that. Possibly switching in and out of leading will be enough. However, it’s not necessarily good to push the “skill” of the AI too far. The purpose of a good AI is not to own the player — it’s to challenge and reward the player. I finally got around to writing the leading code because it bothered me that the player could zip through robot-infested rooms without taking any damage. (Or doing any.) That will be harder now, but if players figure out how to beat or exploit the leading, it’s another layer of depth to the game and that’s what a feature should offer.