Model of Game AI (re-created from the book of Millington and Funge)

Last week, as part of the lecture “Game Technology” at TU Darmstadt, I gave a lecture on game AI. My focus in game development was not squarely on game AI before, so some of the material was also new to me. I used the excellent book by Ian Millington and John Funge as the basis for the lecture, and now wanted to have a look at some real-world applications for the way they described game AI. And because I have been interested in looking at the good old source of the original Doom, I have decided to have a look at what techniques for AI the original Doom used and how they relate to the model in Millington’s book. So here we go! I have been using zDoom to be able to compile the code and step into it. The original source code of Doom is available on github at https://github.com/id-Software/DOOM/blob/master/linuxdoom-1.10.

Movement

Movement is the lowest level of AI described in the book. It is concerned only with local information, such as what objects are close to the AI, where to steer towards, and not with global information such as finding a path through the whole level. The first class to look at is mobj_t (p_mobj.h) which stands for map object. An AI gets a move direction (0-8) and a movecount by a steering algorithm. Remember that Doom did not have 3D enemies, but rather sprites, that were drawn for 8 directions (plus one “dead” state).

When an AI tries to reach the player, it will try to walk towards the player directly (choosing the closest direction) if there is no obstruction, otherwise, if the player is not directly reachable, it will choose a direction at random. The direction is followed for the duration of the move count; after this, a new direction is chosen. Due to this, enemies in Doom seem to approach in a zig-zag line. This behaviour is found in the function A_Chase of p_enemy.c. During movement, simple checks are done: does the AI bump into a wall or over a ledge, or into a door it can open? Doom therefore has kinematic steering: The movement can change from frame to frame, and does not really care about physics: the AIs don’t have to accelerate, the instantly change their speed and direction.

Pathfinding

Pathfinding is the next level in the AI model: it uses global information about the map to find a valid path from point A to B (using a variant of the A* algorithm in most cases). This one is easy. Doom has no pathfinding. An AI will not chase you anywhere. Remember, this were still the early days of the genre, and the game (with all its impressive graphics) was running on a 486 processor without graphics acceleration. As far as I found out, pathfinding wasn’t added to iD’s games until Quake 3 Arena.

Decision Making

This layer of AI refers to how individual AIs make their decisions and what behaviour they should show. Not too much surprisingly, Doom follows the majority of games and uses state machines. The following code sample shows how a state is defined.

  typedef struct {
  spritenum_tsprite;
  longframe;
  longtics;
  // void(*action) ();
  actionf_taction;
  statenum_tnextstate;
  longmisc1, misc2;
} state_t;

And here is an example from the first enemy you encounter in the game, a posessed marine:

{SPR_POSS,0,10,{A_Look},S_POSS_STND2,0,0},// S_POSS_STND
{SPR_POSS,1,10,{A_Look},S_POSS_STND,0,0},// S_POSS_STND2
{SPR_POSS,0,4,{A_Chase},S_POSS_RUN2,0,0},// S_POSS_RUN1
{SPR_POSS,0,4,{A_Chase},S_POSS_RUN3,0,0},// S_POSS_RUN2
{SPR_POSS,1,4,{A_Chase},S_POSS_RUN4,0,0},// S_POSS_RUN3
{SPR_POSS,1,4,{A_Chase},S_POSS_RUN5,0,0},// S_POSS_RUN4
{SPR_POSS,2,4,{A_Chase},S_POSS_RUN6,0,0},// S_POSS_ATK2

Here, you see two functions that define the actions for looking and chasing. Also note that the state machine also handles animation frames.

Strategic and Tactic

This level describes facilities the AI can use, for example to find good positions for covering or for synchroinizing with other AIs to follow a common strategy. Another easy one. Doom didn’t have it yet.

Execution Management

This part of the model describes how AI task are scheduled, for example dealing with managing tasks so that they are spread out well over the available frames. The basics of such a system are visible with Doom’s “thinkers”, which are functions for game objects that are called once per tic.

World Interface

Here, the model summarized methods how AIs can sense their surrounding, and whether they have perfect information or are more on the level of the player. In Doom, enemies check the visibility to the player. Some monsters are restricted seeing only the 180 degrees infront of them.

They can, interestingly, be also activated by “sound”, which propagates through sectors. This way, an attacked AI can make noise and alert AIs which otherwise could not see the player.

Content creation, scripting

For content creation, iD created the Doom editor DoomEd. Compared to today’s editors, which can allows for designers to specify state machines visually and whatnot, it did not have many ways to influence the AIs. It could set certain objects to be special cases, such as triggers.

Scripting also was not part of the original Doom engine. So all AI behaviour was hardcoded. Scripting was later added to Hexen and allowed scenes in the game to be scripted by changing many of the parameters in the game.