doom AI Archives - Helldorado Team

A couple of weeks ago we released ARThings, please check it out when you get a chance. Like we mentioned previously this project began as an academic exercise to build something more interactive with ARCore, but to bring this Doom experience to ARCore we had to invest time to learn the inner workings of Doom’s AI/Game Logic system. Below is some light commentary on this experience, including some insights and lessons learned.

Picking a Doom Source Port

To port the Doom AI game logic we had to pick a Doom source port. We narrowed down the list to 2 contenders:

There’s pros and cons with each of these but ultimately we settled with Linux Doom. By doing so we could deal with less complexity. The ZDoom codebase is much more modernized but quite extensive – it not only runs Doom but also Heretic, Hexen, Strife and other “Doom clones”. Learning ZDoom meant going through a much more extensive and technically sophisticated codebase. ZDoom’s AI and gameplay code architecture was revamped to include ACS, a flexible scripting system that developers could use to extend gameplay and AI behavior without having to write additional code to be compiled with the master codebase.

Having settled with Linux Doom, we unzipped the codebase and immediately faced with an even bigger challenge – working with legacy code. Doom was written in the early 90s, and as such the code was meant to push the limits of the hardware of that era (i386, i486, etc). If you get some time, I recommend reading Fabien Sanglard’s Game Engine Black Book, he does an amazing job describing the technical limitations id Software’s faced when developing Wolfenstein 3D. These limitations drove the technical direction of both the Wolfenstein 3D and Doom codebase.

So we went deep into the Doom source code. After studying the source code for a couple of days we encountered these technical pain points:

Reading C – Doom’s code is not Object Oriented. Functions are grouped into source files based on functionality. The code can be hard to come to terms with if you’ve been writing OO code for a while.
Absence of Floating Point arithmetic – To cope with CPU’s lack of floating point arithmetic during the mid-90s Doom uses Fixed point arithmetic. The gist of this is that floating points are represented using 32-bit integers. 16 bits for the integer portion and the remaining 16 for the fractional part.
Angles are represented using Binary Angle Measurement (BAM) – This is new territory if you’re used to storing angles as doubles (or floats) when working with computer graphics or trigonometric calculations. in BAM, angles are represented using the full range of values of a 32-bit unsigned int. The challenge with this is that some languages do not support unsigned int as a primitive data type (Java for instance). You have to provide your own wrapper functions when performing computations that result on unsigned integers. Another challenge with BAM is that to perform trigonometric calculations you have to provide your own special purpose sin/cos/tan lookup tables.
Usage of C function pointers – These are used heavily in the code, sometimes to mimic Polymorphism. C function pointer code can be hard to port with the right architectural approach, especially if the language you are porting to implements similar functionality using a different programming paradigm. Again, using the Java example you can accomplish this using Lambda expressions and Method References.

The Basics – Understanding Mobjs and States

Let’s now get to the basics. To understand how the Doom AI works we need to understand how objects, or Things (mobjs), are represented in the codebase. Things are monsters, items, pickups, fireballs, projectiles, or anything that is represented by a sprite in the game. For example, when you shoot a monster and you see a blood effect rendered as a sprite, the blood effect is a mobj.

Things are represented by the mobj_t struct defined in p_mobj.h. mobjs and have attributes such as (x,y,z) position, (x,y,z) momentum (used to simulate physics) and many other object properties.

Side note: The Doom coordinate system treats Z as the vertical “up” axis, as opposed to the Y axis. If you are coming from the OpenGL world this might be hard to stomach.

For the purposes of AI, a mobj (I’ll be using mobj and Thing interchangeably) functions as a finite state machine. Through its lifespan a mobj will cycle through various states as determined by the core engine AI logic. A mobj’s current state is kept as a reference to a State object:

state_t* state;

The declaration of state_t is defined in info.h and all state definitions in the game are stored as a global array:

typedef struct
{
  spritenum_t	sprite;
  long		frame;
  long		tics;
  // void	(*action) ();
  actionf_t	action;
  statenum_t	nextstate;
  long	        misc1, misc2;
} state_t;

extern state_t	states[NUMSTATES];

The state object has the following attributes and characteristics:

sprite – Sprite to use to render the mobj for this state
frame – Animation frame to use for this state
tics – How many tics to run this state for (We will explain the concept of tics in the next section)
action – Pointer to the function to run when transitioning to this state
nextstate – State to transition to when this state is over
misc1 – Miscellaneous attribute
misc2 – Miscellaneous attribute

The list of all state numbers for all the different types of mobjs in the game are defined in the statenum_t enum in info.h.

To decide what states correspond to each mobj type there’s a structure called mobjinfo_t in info.h that contains this information. The engine stores this as a global array as well:

typedef struct
{
    int	doomednum;
    int	spawnstate;
    int	spawnhealth;
    int	seestate;
    int	seesound;
    int	reactiontime;
    int	attacksound;
    int	painstate;
    int	painchance;
    int	painsound;
    int	meleestate;
    int	missilestate;
    int	deathstate;
    int	xdeathstate;
    int	deathsound;
    int	speed;
    int	radius;
    int	height;
    int	mass;
    int	damage;
    int	activesound;
    int	flags;
    int	raisestate;
} mobjinfo_t;

extern mobjinfo_t mobjinfo[NUMMOBJTYPES];

Let’s provide an example with one of the Doom monsters, the Zombieman.

Here’s how the Zombieman’s mobjinfo is defined in the info.c file. Note that the Zombieman’s mobj type is MT_POSSESSED:

mobjinfo_t mobjinfo[NUMMOBJTYPES] = {
   .
   .
   .
   {
	// MT_POSSESSED
	3004,		// doomednum
	S_POSS_STND,	// spawnstate
	20,		// spawnhealth
	S_POSS_RUN1,	// seestate
	sfx_posit1,	// seesound
	8,		// reactiontime
	sfx_pistol,	// attacksound
	S_POSS_PAIN,	// painstate
	200,		// painchance
	sfx_popain,	// painsound
	0,		// meleestate
	S_POSS_ATK1,	// missilestate
	S_POSS_DIE1,	// deathstate
	S_POSS_XDIE1,	// xdeathstate
	sfx_podth1,	// deathsound
	8,		// speed
	20*FRACUNIT,	// radius
	56*FRACUNIT,	// height
	100,		// mass
	0,		// damage
	sfx_posact,	// activesound
	MF_SOLID|MF_SHOOTABLE|MF_COUNTKILL, // flags
	S_POSS_RAISE1	// raisestate
   },
   .
   .
   .
};

The attributes in the mobjinfo object define the states to transition to and the sound effects to play for a particular mobj type when entering the following core mobj states handled by the engine:

Spawn State – state to transition to when the mobj is spawned in the game. This is the “idle” state where the monster just stands and does nothing, checking its field of view until it spots a player to chase and attack.
See State – state to transition to when the mobj spots an enemy (in this case the player) and should chase it. Inside the code this is sometimes referred to as the “Chase” state.
Pain State – state to transition to when the mobj takes damage
Melee State – state to transition to when the mobj is ready to perform a close range melee attack. Only applies to mobjs that perform melee attacks. For the Zombieman, notice that the meleestate attribute is “0”, which corresponds to the NULL state, since the Zombieman doesn’t have a melee attack.
Missile State – state to transition to when the mobj is ready to perform a ranged attack. Only applies to mobjs that perform ranged attacks such as a Zombieman firing his rifle or a Cacodemon belching a fireball.
Death State – state to transition to when the mobj is killed
XDeath State – state to transition to when the mobj is killed via explosion (gibbed)

Now let’s look at the complete list of Zombieman state definitions as defined in info.c:

state_t	states[NUMSTATES] = {   
    .
    .
    . 
    {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_RUN5
    {SPR_POSS,2,4,{A_Chase},S_POSS_RUN7,0,0},	// S_POSS_RUN6
    {SPR_POSS,3,4,{A_Chase},S_POSS_RUN8,0,0},	// S_POSS_RUN7
    {SPR_POSS,3,4,{A_Chase},S_POSS_RUN1,0,0},	// S_POSS_RUN8
    {SPR_POSS,4,10,{A_FaceTarget},S_POSS_ATK2,0,0},	// S_POSS_ATK1
    {SPR_POSS,5,8,{A_PosAttack},S_POSS_ATK3,0,0},	// S_POSS_ATK2
    {SPR_POSS,4,8,{NULL},S_POSS_RUN1,0,0},	// S_POSS_ATK3
    {SPR_POSS,6,3,{NULL},S_POSS_PAIN2,0,0},	// S_POSS_PAIN
    {SPR_POSS,6,3,{A_Pain},S_POSS_RUN1,0,0},	// S_POSS_PAIN2
    {SPR_POSS,7,5,{NULL},S_POSS_DIE2,0,0},	// S_POSS_DIE1
    {SPR_POSS,8,5,{A_Scream},S_POSS_DIE3,0,0},	// S_POSS_DIE2
    {SPR_POSS,9,5,{A_Fall},S_POSS_DIE4,0,0},	// S_POSS_DIE3
    {SPR_POSS,10,5,{NULL},S_POSS_DIE5,0,0},	// S_POSS_DIE4
    {SPR_POSS,11,-1,{NULL},S_NULL,0,0},	// S_POSS_DIE5
    {SPR_POSS,12,5,{NULL},S_POSS_XDIE2,0,0},	// S_POSS_XDIE1
    {SPR_POSS,13,5,{A_XScream},S_POSS_XDIE3,0,0},	// S_POSS_XDIE2
    {SPR_POSS,14,5,{A_Fall},S_POSS_XDIE4,0,0},	// S_POSS_XDIE3
    {SPR_POSS,15,5,{NULL},S_POSS_XDIE5,0,0},	// S_POSS_XDIE4
    {SPR_POSS,16,5,{NULL},S_POSS_XDIE6,0,0},	// S_POSS_XDIE5
    {SPR_POSS,17,5,{NULL},S_POSS_XDIE7,0,0},	// S_POSS_XDIE6
    {SPR_POSS,18,5,{NULL},S_POSS_XDIE8,0,0},	// S_POSS_XDIE7
    {SPR_POSS,19,5,{NULL},S_POSS_XDIE9,0,0},	// S_POSS_XDIE8
    {SPR_POSS,20,-1,{NULL},S_NULL,0,0},	// S_POSS_XDIE9
    {SPR_POSS,10,5,{NULL},S_POSS_RAISE2,0,0},	// S_POSS_RAISE1
    {SPR_POSS,9,5,{NULL},S_POSS_RAISE3,0,0},	// S_POSS_RAISE2
    {SPR_POSS,8,5,{NULL},S_POSS_RAISE4,0,0},	// S_POSS_RAISE3
    {SPR_POSS,7,5,{NULL},S_POSS_RUN1,0,0},	// S_POSS_RAISE4
    .
    .
    .
};

Before diving deeper into these states, let’s go back and cover the tics concept that I mentioned briefly.

Gametics and Thinkers

Doom doesn’t manage the concept of game updates in terms of milliseconds since the last game update. A gametic is the equivalent of a single game update – basically one iteration of the Doom game loop. During this iteration the engine performs one frame update and executes basic game loop activities such as capturing input, executing gameplay logic and rendering to the framebuffer.

Doom’s engine is clamped at 35 tics per second (35 iterations of the Doom game loop every second), so a single tic should take no longer than 1000/35 = 28.57 milliseconds. This is the behavior of Vanilla Doom, however some source ports have removed this technical restriction and allow uncapped framerates.

To understand the game loop, lets look at some code. The Doom main game loop makes a call to the G_Ticker() function in g_game.c. A call to P_Ticker() (defined in p_tick.c) is made as long as the game is running a level (gamestate=GS_LEVEL):

//
// G_Ticker
// Make ticcmd_ts for the players.
//
void G_Ticker (void) 
{    
    .
    .
    .
    // do main actions
    switch (gamestate) 
    { 
      case GS_LEVEL: 
	P_Ticker (); 
	ST_Ticker (); 
	AM_Ticker (); 
	HU_Ticker ();            
	break; 
	 
      case GS_INTERMISSION: 
	WI_Ticker (); 
	break; 
			 
      case GS_FINALE: 
	F_Ticker (); 
	break; 
 
      case GS_DEMOSCREEN: 
	D_PageTicker (); 
	break; 
    }
}

P_Ticker() handles game updates for the following:

All Players in the game (via a call to P_PlayerThink)
Mobjs (via call to P_RunThinkers)
Other things that we don’t care about right now

//
// P_Ticker
//

void P_Ticker (void)
{
  .
  .
  .
  for (i=0 ; i<MAXPLAYERS ; i++)
	  if (playeringame[i])
	      P_PlayerThink (&players[i]);
			
  P_RunThinkers ();
  P_UpdateSpecials ();
  P_RespawnSpecials ();
  .
  .
  .
}

Let’s digest all of this for a moment. You might think that to run game updates for all mobjs in the game you would just call an update() method passing the mobj as a parameter and do this for every single mobj in the game.

Doom handles game updates for mobjs a bit differently. Every mobj in the game has a Thinker object that manages the execution of game updates per frame for that specific mobj. The structure of a Thinker object looks like this (declared in d_think.h):

// Doubly linked list of actors.
typedef struct thinker_s
{
    struct thinker_s*	prev;
    struct thinker_s*	next;
    think_t		function;
    
} thinker_t;

As mobjs spawn in a level, their Thinkers are created and added to a doubly linked list (hence the prev and next pointers). This happens in the P_SpawnMobj() function (in p_mobj.c):

//
// P_SpawnMobj
//
mobj_t*
P_SpawnMobj
( fixed_t	x,
  fixed_t	y,
  fixed_t	z,
  mobjtype_t	type )
{
    .
    .
    .

    mobj->thinker.function.acp1 = (actionf_p1)P_MobjThinker;	
    P_AddThinker (&mobj->thinker);

    return mobj;
}

Likewise, as mobjs are removed from a level (for example a projectile mobj hits a monster and needs to be removed after the explosion), their Thinkers are removed from the doubly linked list (P_RemoveMobj function in p_mobj.c):

//
// P_RemoveMobj
//
mapthing_t	itemrespawnque[ITEMQUESIZE];
int		itemrespawntime[ITEMQUESIZE];
int		iquehead;
int		iquetail;

void P_RemoveMobj (mobj_t* mobj)
{
    .
    .
    .
    
    // free block
    P_RemoveThinker ((thinker_t*)mobj);
}

Every Thinker object has a reference to a function (attribute think_t function) that executes an mobj’s game updates. This function is P_MobjThinker() in p_mobj.c:

//
// P_MobjThinker
//
void P_MobjThinker (mobj_t* mobj)
{
   // We'll go through this code later
}

P_RunThinkers() simply iterates through each mobj’s Thinker and executes its Thinker function – P_MobjThinker():

//
// P_RunThinkers
//
void P_RunThinkers (void)
{
    thinker_t*	currentthinker;

    currentthinker = thinkercap.next;
    while (currentthinker != &thinkercap)
    {
	if ( currentthinker->function.acv == (actionf_v)(-1) )
	{
	    // time to remove it
	    currentthinker->next->prev = currentthinker->prev;
	    currentthinker->prev->next = currentthinker->next;
	    Z_Free (currentthinker);
	}
	else
	{
	    if (currentthinker->function.acp1)
		currentthinker->function.acp1 (currentthinker);
	}
	currentthinker = currentthinker->next;
    }
}

We can think of P_MobjThinker() as the function called for each game state update for each mobj. This function will take care of movement, physics simulation and cycle between AI states.

We can summarize the above behavior with the following pseudocode:

G_Ticker() // g_game.c
{
	switch(gamestate)
	{
		case GS_LEVEL:
			P_Ticker() // p_tick.c
			{
				P_RunThinkers() // p_tick.c
				{
					// Iterate through all thinkers in level (linked list)
					foreach(thinker in thinker linked list)
					{
						function = thinker.function;
						// Execute thinker function
						// Runs P_MobjThinker() function in p_mobj.c
						function.run();
					}
				}
			}
	}
}

In the next article we’ll continue our deep dive into Doom AI game logic and the technical details of P_MobjThinker().

While you wait for the next article we recommend reading:

Doom Monster Behavior

Tag: doom AI

Doom AI Game Logic Explained, kinda

Picking a Doom Source Port

The Basics – Understanding Mobjs and States

Gametics and Thinkers