Building a Better Wizard

I write a lot about the artificial intelligence in BrainWorks, but that's not everything I program. Seven years ago I created a Quake 3 mod called Art of War. It's a class-based teamplay game, not so different from Team Fortress in that respect. Each class belongs to a faction with its own play style-- there was a faction with strong assault classes and weaker defenders, another with stronger defense and weaker assault classes, and so on. But even the heavily defensive faction needed one competitive assault unit. It just needed abilities that were "in theme" for the flavor of the faction. The resulting class, the Wizard, became a stealth attacker. When upgraded, it could blink through walls and turn invisible, making it ideal for hit-and-run guerilla warfare tactics but terrible for an all-out overrun of the enemy base.

Since each class had three upgrade levels, I was looking for a third ability for the Wizard that was in theme for the stealth assault play style. I decided to try homing missiles. The idea was that the wizard could shoot fireballs that would navigate through corridors and eventually home in on enemy structures. The wizard could assault the enemy base without even being inside it, forcing the defenders to track down the wizard and kill them. That's a very different gameplay situation from defending a swarm of attackers, and variety makes for good gameplay.

Given a choice between doing something the standard way and the excessive way, I usually choose excessive, and it was no different for these homing missiles. First let me explain the standard algorithm for homing projectiles.

• Repeat every 50 milliseconds:
• Check for possible targets in the missile's cone of view.
• If there are no targets, keep heading forward.
• Otherwise, turn a bit towards the target closest to the missile's forward direction.

That's about it. You can write that in 15 lines of code, and they are reasonably effective. The big problem with these missiles is their lack of memory. They can only latch onto a target that fits in their field of view. If the target can duck around a corner, the missile will forget about them and keep moving forward into a wall. There's no way you could lose track of a real opponent by stepping out of sight for an instant, but the homing missiles just don't know any better.

Not being content with the standard solution, I fortified homing missiles with some industrial strength awesome! These seeker missiles locked onto a target when it was fired and remembered that target's location (even if it went out of view). Obviously the seeker does a standard turn towards the target when it can get line of sight. When the seeker can't view the target, however, it employed the equivalent of sonar to get a navigational reading on its surroundings. The seeker would look in front of itself for walls, pillars, and other obstacles, trying to find large open hallways and rooms. It considered every direction that had sufficiently large space. From that list of possibilities, the seeker picked the direction that was most in line with the target's current position.

Now it's still possible for the seeker to get caught in a corner or alcove. Abstractly this is a local minima: something that appears to be an immediate improvement but is not useful for reaching the optimal goal. To combat this problem, the seeker kept track of how much free space it wanted. Remember, it only considers directions that have enough open space. By modifying thd definition of "enough", the seeker could control the tradeoff between getting to the target and getting to a wide-open area with lots of navigation options.

Whenever the seeker spent time turning, it increased the amount of space it wanted, making it favor open areas (and deprioritize finding the target). And whenever it went straight, it decreased how much space it needed (prioritizing finding the target). The result was that when a missile got stuck in a corner, it would start desparately searching for any hallway it could find, just to get somewhere else. When it found one, it would "relax" a bit and be a bit pickier in the next area. This is a form of simulated annealing.

This entire bit of code took about one week to write and was around 500 lines of code. I tested it for about an hour, tweaked some numbers, and it just worked. Watching it was incredible, as you could see the seekers do amazing things. They would seamlessly turn down narrow hallways with sharp turns, open doors, fly up and down ledges. Think "precise robotics control on a remote control missile" and you'll have the basic idea.

I was really excited to try this out in the next build of Art of War, because I wanted to see how this would affect the play style of the Wizard. To my dismay, it was a total disaster. The homing fireballs ended up being far too good. A wizard could shoot a fireball anywhere on the level and they would automatically find and kill enemy structures. In fact, a team of wizards could launch an assault by standing in their own home base, and there was just no way to defend against that. To balance the class, I had to remove all the cool homing missile code.

Of course, I wasn't willing to let good code go to waste...