Analyzing the AI Bot Library
from the Quake 3 Source Code

Looking into the AI source code of titles that have shipped is a great way to learn tricks from the trenches. This new column helps you do that by helping you study the code behind various games, for example the F.E.A.R. SDK last week.

Quake 3 Arena makes an interesting example as it is fully open-source (except the tools), and it’s a great example of a turn-of-the-century AI engine design! Seriously though, the code contains a feature-complete death-match bot AI written in plain-old C; it’s surprisingly easy to follow when you understand the syntax of the language. As well as a simple goal architecture, you’ll find some solid technology in the Area Awareness System (AAS) and the pathfinding solution too (a.k.a. routing).

Downloading and Installing the Source

Quake 3 was made open-source in 2005, so you can download the codebase freely as long as you follow the conditions in the GPL license. If you want to run the game however, you’ll need some assets which are not included. Your first option is to turn to Id Software for the code and assets:

1. Download the full Quake 3 source code from Id’s FTP server. The current version is 1.32b, which works with the latest patch.

2. To get the game up and running with all the necessary assets, you can use the full version of the game. The Gold edition is good value these days bundling both Q3-based games together.

3. It’s also likely you can get the demo levels up and running based on the version of the engine you compile. Go to Id’s download page, get the demo files and put your executable in the right directory.

Alternatively, you can also turn to the community for the source and assets:

1. Download the source from ioquake3, which is the current active codebase behind the independent mod scene. You’ll find bug fixes and improvements in the code if you want to use it further.

2. For the assets, turn to the OpenArena game. It brands itself as a completely free game based on the Quake 3 engine. You can also find more models from ioquake3’s site too.

Once the installation is finished and all the files have unpacked, you’ll have a .\code\ directory — typically within your game folder.

Screenshot 1: A sample of the files that make up the AI source code in Quake 3.

Understanding the Codebase

In the base directory of the game, you’ll find a solution file for Visual Studio called quake3.sln. (You can use the free version of VS.NET 2008 Express.) The game also builds on many other *nix platforms with a standard Makefile.

The bulk of the AI code lives in the ./botlib/ directory, with 56 files and roughly 1.1 Mb of code. The AI has its own library, but is included by the main solution. There’s also some game specific AI logic in the ./game/ folder too. Things to note about the AI in Quake 3:

• The code is plain-old ANSI C and not C++. However, it’s written in a relatively structured approach, so it should be accessible to most object-oriented developers familiar with C-style syntax. In fact, the code seems relatively noise free compared to many C++ engines out there!

• The architecture of the engine code itself has become a standard approach, basically splitting the game logic from the client and server. But what’s particularly useful here is that the whole engine is designed around support for bots as multiplayer characters, which requires good layering of the codebase.

• The AI from Quake 3 dates back to when having a dedicated AI programmer was rare. This means you should be able to understand the structure of the AI code rather easily compared to more modern engines.

As for the files, there are a few things to note:

• Files named be_aas_*.[h,c] contain the navigation code, also known as the Area Awareness System. This constitutes over 50% of the lines of code in the whole AI.

• The singe file be_ea.c provides a wrapper for all the elementary actions that the bot can perform. However, the implementation of these actions is done in the engine itself, since the players perform the same actions as the bots.

• The files be_ai*.[h,c] contain the AI logic itself, but the implementation is split over the ./code/botlib/ and the ./code/game/ directories.

• The supporting library code seems to be in files named l_*.[h,c], which is a convention used throughout the engine. In particular you’ll find code for serializing data-structures and loading simple settings from scripts.

Screenshot 2: Fast-pace deathmatch action in Quake 3 Arena.

Essential Highlights

When browsing through the code, in particular pay attention to the following components.

Area Awareness System

The bots in Quake 3 are famous for their AAS navigation system. Basically, the structure of the levels is analyzed, which is used to extract volumes of space that are navigable (e.g. walkable surfaces, swimming areas). A process then analyzes these areas for connections by simulating potential movement from each of them, and then clusters the areas together to allow hierarchical path-finding.

Routing With Caching

Quake 3 uses a form of pathfinding (in be_aas_route.[h,c]) within the AAS graph that relies on the clusters of areas. Within these clusters, the paths to common destinations are pre-calculated and stored for later use.

Stack-Based Goal Architecture

In the files be_ai_goal.[h,c] you’ll find implementation of dynamic goals using a stack. In particular, each goal has a fuzzy activation value (which can be optimized using genetic algorithms). The stack is used to keep track of things to do, which allows the AI to solve simple puzzles and prioritize its behavior easily.

Main AI Routine

At the top-level of the system there’s a traditional state machine which builds upon the the goal-based stack. You’ll find this logic in the game part of the project under the filename ai_dmq3.[h,c]. What’s amazing when you’ve become used to an object-oriented C++ approach is that everything is so simple and explicit; there’s one bot_state_t data-structure, and a bunch of global functions that implement different parts of the state machine.

All in all, Quake 3 is a great place to start for developers wanting to look into commercial AI. It’s certainly not a trivial implementation, but it’s probably as simple as you can make a fully featured AI engine and ship it in a game.

Stay tuned to AiGameDev.com for a more in-depth analysis of the Quake 3 bot’s design. In fact, there’s a whole thesis on the subject, which you can find in this thread of the forums (registration and introduction required).