Things in the Attic

Most every child has spent an afternoon rummaging through the attic at their parents or grandparents. Maybe it wasn't an attic for you. Maybe it was the basement or the garage, or just through some boxes shoved in a closet. But the basic experience is the same. You probably found a lot of mundane things and a few things whose existence is a mystery. "Dad, why do you have spare band saw belts in the basement? We don't own a band saw!" And if you were like me, you found one or two things where you couldn't even figure out what it was for. "Grandpa, what's this hunk of metal for?" "Oh, we used that to crank the windmill for water on days when it wasn't windy."

Of course... It seems so obvious now...

Programming can be like that attic too. You never know what things you'll find rummaging through the source code. For BrainWorks, the "attic" is ai_lib.c. Here's a partial list of the stand alone function:

• A bunch of functions that compare two values
• A function that returns the index of the first bit set of an integer
• A function that computer integer exponents of decimal numbers
• An assortment of semi-complicated vector math operations
• A function that tests ray intersections with a bounding box
• Binary search functions with optional insert on search failures

And there are some more complicated structures as well, such as:

• A rudimentary memory manager
  
• A hash table implementation (also known as a map)
• Timed Value Lists (a kind of priority queue)
• Octrees (a tree that organizes points in space for search)
• Index Subset Iterators (a highly specialized list iterator)

If you're not a programmer, you're probably thinking, "What on Earth is that stuff?" And if you are a programmer, you're probably wondering, "Why on Earth does he need that stuff?" From time to time, I'll come back to things on this list and explain how they were useful in designing AI.

But for now, I'll take a brief look at the memory manager and the hash table. The hash table is used to track dropped items and the memory manager handles the data in the table. Dropped items are things a player drops on the ground when they die, such as weapons and powerups they had. Without getting into too much detail, the AI code needs to track all dropped items so bots can consider them for pickup, and the code needs to know extremely quickly whether a dropped item is still there. That means the code needed the specialized storage structure of a hash map, since its so fast to read data from it.

One of the constraints of programming for Quake 3 is that the server absolutely cannot allocate any memory at run time, and there are generally no useful library functions. So if you need a widget_extractor() or a cog_spinner(), you have to make it yourself. While other languages have hash maps, Quake does not, so I had to write one. And writing the map required a memory allocator, or at least a good simulation of one.

All of that just so bots can pick up the quad damage someone dropped when they died! Good AI is worth that trouble.