First Causes

In recent years, I've come to realize the most formative event in my life occurred when I was three years old. My parents took us kids out on a walk, and for reasons that aren't clear to me, we didn't take the dog alone. My parents put him out on the deck so he could get fresh air, but kept him on a leash tied to the deck so he wouldn't run off and get lost. When we got back an hour later, I ran ahead to the house and discovered the body of our dog hanging from the deck. He had jumped over the railing to follow us and accidentally hung himself on his leash.

This would have been a traumatic experience for any child. I'm certain that if my parents had found the body first, they would have tidied things up a bit and told me a good lie to lessen the blow of what actually happened. But I found him first, and the memory is firmly etched in my mind. As my three year old mind tried to make sense of the situation, I was confronted by an overwhelming sense of loss and waste. I wasn't just sad that my dog had died. I was particularly hurt by how needless the death had been. If my parents had taken my dog along, left him in the house, or tied him to a low post on the deck staircase, none of this would have happened. I didn't blame my parents for not thinking of this. It was just an unlucky situation that could easily have been avoided.

I didn't recognize it until decades later, but that experience framed the rest of my life. It wasn't framed with an objective or a rationale, but with an emotion:

I despise waste.

I've lived my entire life in a constant struggle against inefficiencies and minimizing potential risks. I work hard to prevent problems before they occur. For example, when I get out of any car and shut the door, I always try the handle to make sure the door is locked. I always check that I bring my wallet with me when I take my keys and vice versa. If I have to be somewhere in an hour and it will take forty minutes to get there (including the margin of error), I find something to do for exactly twenty minutes.

I think this is why I was attracted to computer programming as a profession, and why I'm so good at it. Good programming means you can teach a computer to do menial tasks that would otherwise cost a human lots of time. I'm anal about error checking and commenting in my code because I absolutely do not want things to go wrong. Carefulness has become a way of life for me, so "clean" programming is second nature. Many programmers complain that writing good code takes a lot more time than sloppy code, but I don't agree. I've been writing good code so long that it's actually faster than writing "bad code".

As the story left off last week, I had finished writing the most impressive homing missiles ever. And for game balance reasons, I couldn't use the work the way I wanted to. Obviously this pushed my buttons about wasting time and effort, so I designed a Quake 3 game modification (aka "mod") using the homing missiles. Thus Seeker Quake was born. As this was released over eight years ago, it's a bit hard to find sites where you can download it, but I believe it's still available from this site.

The PlanetQuake article does a good job of summarizing the game, but here's the basic gist. Each player starts with a rocket launcher and gets one seeker shot active at any point in time. When you shoot, it selects a random person with higher score than you and mercilessly tracks them down. They can try to outrun it, but they absolutely cannot hide from the seeker. While your seeker is active, all other rocket shots act like normal rockets. And of course, you can use any other weapon available on the level too.

It's a pretty simple twist but it has a really interesting effect on game balance. I tried games with four to eight players on it of varying skills. On a typical level with a point limit of 20, the scores would probably range anywhere from -2 to 20. But in Seeker Quake, final scores were generally in the 13 to 20 range. The best player still pretty much always won and the worst player always lost, but the range was much tighter. Seekers act as handicapping mechanic, as the best player got targeted with a lot more seekers. He has to work harder to maintain his edge. Meanwhile, the worst players on the level have almost no seekers targeting them, so they have more time to catch up.

Here's the bottom line: When a bunch of players with widely varying skill play Seeker Quake, everyone has a good time and everyone is challenged relative to skill. The game is a total blast.

My life hasn't been all cupcakes and roses. But I've worked hard to turn bad situations into good ones. I'm glad I've taken the time to do so.

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...