Sunday, January 13, 2013

I'm Coming in With the Flag

I got so excited about my success with modding Sauerbraten and adding XInput support that I decided to add the gamepad code to AssaultCube as well. Because Cube1 and Cube2 engines are similar in many ways, doing so was a breeze (took me a bit to figure that the Y axis is reversed in AssaultCube but other than that it worked great). Since my last post I also made some enhancements to the controller code, such as the ability to bind buttons and triggers to arbitrary script code. Actions can now be bound to the analog trigger half-presses which is extremely useful for engaging the aim-assist code. Yeah, I wrote my own aim-assist to compensate for the game controller's lack of precision and maybe it is best I do not elaborate any further on that, the fine line between aim assist and aim bots being a controversial one.

Controller in hand and cold beer in reach, I sat down for a single-player session of AC only to realize that the AI is not as capable as Sauerbraten's and the bots have many limitations. For example they cannot play Capture the Flag (CTF) and cannot navigate the underground sewage system in the ac_aqueous map. It also seemed a little strange that the AC bots use a configuration file with a syntax of its own instead of using the powerful Cubescript language.

I could not pass the challenge and decided to look into writing my own AI code. I have never tackled this kind of stuff before. As a professional programmer I worked with compilers, debuggers and touched databases; I worked for Amazon.com and for Microsoft (yeah, I did write a few thousand lines for Windows 8, guilty as charged). But I have no game development experience, aside of a lame Python implementation of Reversi I wrote a few years back.

Naturally I got very excited about experimenting with an AI system. My goal was to come up with playable, good-enough code that could coexist with the current AI. I did not want to overhaul the entire bot code and disturb other parts of the game that depend on it. I just wanted to add a side-by-side AI, and I must admit the thought of having the two AIs fight each-other while I spectate crossed my evil mind. I aimed for keeping the code small and compact, in the minimalist tradition of the Cube engines.

I decided to use a waypoint system for navigating the maps, similar to what the existing bots use. I am aware that better systems can be devised (http://www.ai-blog.net/archives/000152.html) but I wanted to keep the code very simple. The waypoints are created by a greedy algorithm that tries to span trees to cover the entire map using a collision detection scheme. A second pass ads a few more edges and attempts to connect together unconnected sub-graphs. This work is not spread across several frames so depending on how fast (or slow) the computer is the game may seem to "freeze" for a short moment when it loads the map. I added a variable named wpxautosave which when set causes the waypoints to be written to a file named the same as the map (plus the .wpx extension). This file is automatically loaded if present, so the short "freeze" inconvenience can be alleviated this way. I preferred this over a more complicated code that spreads the work over several frames.

The problem I grappled with for many weekends is that using the game physics for collision detection is not a precise business. Trying to move the player's character on all possible edges in order to validate them is expensive. Cutting some corners (pun well intended) may yield graphs that are incorrect and cause the AI to bump into walls. On the other hand, being too conservative may end up in disconnected graphs. I decided to go with a hybrid approach were waypoints can be generated automatically (with a somewhat conservative take on collisions) but also manually, by running over the map and dropping waypoints in Sauerbraten's style. This way, if I have time to kill I can make my own waypoints (manually and accurately) for a given map, or if I just want instant gratification I let the machine generate them, and more are added as I play. The latter approach has an interesting side-effect. As new waypoints are added, the bots appear as they "learn" new ways around the map. I added a variable (exposed to the user via Cubescript) to limit the growth of the graph, and thus the computational effort required for path finding during game play.

The bots use the Dijkstra algorithm for their path finding instead of A*. I thought this was more convenient in situations where they are not interested in finding their way from point A to a specific point B, but rather to the nearest of any points that satisfy certain criteria (any health pickup, or any Kevlar or helmet, or any ammo pickup, for example).

I wrote the code using Visual Studio 2010 to take advantage of the C++11 features that it supports, such as lambda functions. I guess GCC would've worked just fine but these days I have no compelling reason to boot up Ubuntu, thanks to how badly Gnome 3 managed to disgust me; but that's a story for another day.

Each bot implements a simple state machine in the form of a stack of std::function<void()>. The function at the top of the stack represents the current state; when it is popped off the stack the bot returns to executing its previous state. If the stack is empty, it executes an idle() routine. The stack is populated by the think() routine, which sets a long term goal and optionally some short-term goals, following the wisdom of the Quake Arena AI design. In a Team Death Match game, the long term goal is to seek and engage enemy units. In a CTF game the goal is to locate and retrieve a flag.

Because the collision detection is not perfect and because of using a waypoint system for navigation, the bots may get stuck every once in a while. I added some heuristics to resolve the collisions by jumping, crouching, or rotating around the obstacle which so far seems to work well with solid obstacles but requires more future tweaking for things such as link fences or light posts; overall I am pretty pleased with the result and last night I was able to play CTF on ac_aqueous with the bots chasing me through water underground.

And I could not resist wiring in some sound bytes since they are already present in the game. Your bot team mates will complain when shot at accidentally, or may brag about their kills.

For the curious and courageous that want to play with the code: first, get the latest AssaultCube 1.2 source from http://sourceforge.net/projects/actiongame/. Then get my hacks from my SkyDrive:
http://sdrv.ms/VEU0f0 and http://sdrv.ms/VEU12G and follow the instructions in the comments at the top of the ai.cpp file. Adapting the code so that it builds under Linux is possible but I have not tried it, VisualStudio 2010 is the only environment under which I built the code. You can also grab the Windows binary file from here and overwrite your AssaultCube 1.2 (make sure you get the latest bits from sourceforge, the mod may not work with older versions).

Currently there is not a lot of magic in the bots decision making process. It is by and large driven by their health, armor, ammunition, who they may cross paths with, and plain randomness. I plan to experiment with genetic algorithms once I get a good feel for the quality of the existing code (got a couple of bugs to address before I move on).

There are other interesting features in the relatively small code (around 2600 lines of C++), such as team collaboration. The bots ask for help when attacked or when going for the enemy team's flag. I could go on and on about how much fun I had with this experiment. But I've a game to play!