As I transition from developing systems to developing content, a larger ratio of my programming time is devote to AI programming. Note: I’m discussing classical game AI – how NPCs make decisions – not the overhyped odious tech-fad of the same name.

Most recently, I coded the logic that pilots enemy jets: how to fly, when to turn, how to avoid obstacles, when to react to the player, and how to line up strafing attacks.

I wanted to break down the choices I made in the high-level technical design, as well as my syntax tricks I employ in low-level C++ code.

Algorithms for Game AI

The most common decision-making algorithm in games is the venerable Finite State Machine, of “FSM.” This data-structure can be easily understood by way of a “box and arrow” diagram, where each box visualizes possible States that the character can be in, and the arrows represent Transitions between those states. The characters begins in a single known initial-state, and “moves” from state to state as the associated transitions are triggered. In fact, in the Unreal Engine, character animation control is coded by authoring “Animation Blueprints” – state-machines with a box-and-arrow interface.

FSMs are intuitive, and easy to debug, but not without tradeoffs. The principle downside is complexity – the number of transitions grows potentially geometrically with the number of states, and can become overwealming. In Computer Science jargon, the complexity grows “O(N²) with the number of states,” and is related to a systems principle called Metcalfe’s Law.

The conventional answer to this problem is to break the main state-machine up into a collection of “sub-state-machines” which are individually maintainable, but require extra care and QA for their concurrent interactions.

The mid-aughts, however, were a bumper decade for devising alternatives to FSMs which didn’t suffer the complexity-explosion issue. To return to CS jaron, these generally involve creating some kind of hierarchy which limits the complexity growth to O(n × log n).

The most popular of these was the Behavior-Tree algorithm, popularized by it’s use in Halo 2, from Bungie in 2005. In a nutshell, the AI controller is continuously “descending” a tree-diagram over-and-over from the root where each branch is a condition, and each leaf is a state. When the tree evaluates to a different state than your current state, you kickoff a transition. This maintains the intuitive appeal and easily-visualized tooling of FSMs, without the complexity risk. It’s probably the most popular solution amongst FPS developers, and naturally is also available in Unreal’s “Blackboard” system.

The main drawback here is that a carelessly constructed behavior-tree can tank-performance in the continuous-evaluation step, and most implementations often add several special-case optimizations for common bottlenecks.

The algorithm I find most personally-interesting is the Goal-Oriented Action Planning system developed for F.E.A.R., by Monolith Productions, the same year as Halo 2. This is a sophisticated planning system which marks up all the character “actions” with precondition/postcondition metadata which, combined with an elaborately-queryable environment database, allows characters to automatically “discover” action-sequences to accomplish goals without any explicit transitions. This enables enemies to “think on their feet” and often discover novel emergent solutions that surprise players and even designers. It is probably one of the most computationally-expensive solutions, however, but still gets a lot of use in real-time-strategy games that demand the AI to complete multi-step sequences (e.g. gather-resource -> build-factory -> attack-with-unit).

All that said, for Nigtshift Galaxy I ditched Unreal’s builtin stuff and followed the KISS principle and just wrote everything in C++. It’s still a mostly vanilla FSM, but with Behavior-Tree-inspired implicit transitions. Being more of an arcade-game, I’m not too worried about complexity-explosion, anyway.

C++ State Machines

In general avoiding Blueprints and developing gameplay with native C++ is win-win – not only is the performance (significantly) better, but I don’t have to deal with any “Blueprints From Hell” that require hundreds of tedious mouse-clicks to write, and are impossible to read. Furthermore, I’ve been coding C++ for decades, and have a high comfort-level with its quirks and warts. I limit Blueprints just to places where it’s required (like animation state-machines) or purely-decorative (like kicking-off VFX and SFX).

I’ve seen dozens of ways to represent FSMs in code over the years, often associating an object-per-state with several virtual-functions, but for Nightshift I’m using a simplified variant of an idea first-proposed by Charlie Tangora during my time at Yacht Club Games: one big switch! We declare all the states with an unnamed enum, and then shift-and-mask them together with an event-id.

/* list of states (declared in source, no header) */
enum
{
	STATE_UNDEFINED = 0,
	STATE_STANDING_STILL,
	STATE_MOVING,
};

/* list of state-events */
enum
{
	EVENT_UNDEFINED = 0,
	EVENT_STATE_ENTER,
	EVENT_STATE_UPDATE,
	EVENT_STATE_EXIT,
};

/* event structure (with per-event-type arguments) */
struct FFSMEvent
{
	uint32 ID;
	union
	{
		struct { uint32 PrevID; } EnterArgs;
		struct { double DeltaTime; } UpdateArgs;
		struct { uint32 NextID; } ExitArgs;
	};

	uint64 MakeSwitch( uint32 StateID ) const
	{
		return uint64(StateID) | (uint64(ID) << 32);
	}
};

/* shorthand macro */
#define FSM_ID( SID, EID ) ( uint64(STATE_##SID) | (uint64(EVENT_STATE_##EID) << 32) )

uint32 SomeEnemy::HandleEvent( const FFSMEvent& Event ) override
{
	switch( Event.MakeSwitch(State) )
	{
	case FSM_ID( STANDING_STILL, ENTER ):
	{
		/* code for entering the standing-still state */
		break;
	}
	case FSM_ID( STANDING_STILL, UPDATE ):
	{
		/* code for updating the standing-still state */
		break;
	}
	case FSM_ID( STANDING_STILL, EXIT ):
	{
		/* code for leaving the standing-still state */
		break;
	}
	case FSM_ID( MOVING, ENTER ):
	{
		/* code for entering the moving state */
		break;
	}
	case FSM_ID( MOVING, UPDATE ):
	{
		/* code for updating the moving state */
		break;
	}
	case FSM_ID( MOVING, EXIT ):
	{
		/* code for leaving the moving state */
		break;
	}
	default:
		break;
	}

	return Super::HandleEvent( Event );
}

Dispatching through a single virtual-function, rather than several, was inspired by a Casey Muratori talk on alternatives to “SOLID” design-patterns.

For me, there’s a lot to recommend this technique. The code is very regular and readable, and it’s easy to add, remove, or refactor states without touching any headers, which means I can still hot-recompile FSM changes while the game is running (even better than blueprints!). I can also omit empty-cases, instead of having lots of empty boilerplate handler-functions. For edge-cases that don’t naturally fit in the conventional layout, I can always add if-branches before or after the switch. A common example is using “ranges” of state IDs:

enum
{
	STATE_UNDEFINED = 0,
	STATE_IDLE,
	RANGE_AGGRO_BEGIN,
		STATE_AGGRO_TELEGRAPH_ALARM,
		STATE_AGGRO_PURSUIT,
		STATE_AGGRO_LOOK_FOR_PLAYER,
	RANGE_AGGRO_END,
};

uint32 SomeEnemy::HandleEvent( const FFSMEvent& Event ) override
{
	const auto bUpdatingAggro = 
		Event.ID == EVENT_STATE_UPDATE && 
		State > RANGE_AGGRO_BEGIN && 
		State < RANGE_AGGRO_END ;
	if( bUpdatingAggro )
	{
		/* common aggro code */
	}

	return Super::HandleEvent( Event );
}

For transitions, I return a non-zero state ID from HandleEvent. This is preferable to having a SetState() subroutine like you see sometimes, because it ensures that I’m exitting the event handler function before changing the state, so our function-stack doesn’t get “plumbing” and “logic” code interleaved. Additionally, it lets me re-run the event-handler to take multiple transitions per-update, and ensure at least one state “consumes” DeltaTime on update, which is important to avoid movement stutters.

void SetState_Internal( uint32 InState )
{
	/* exit current state */
	FFSMEvent EvExit;
	EvExit.ID = ENEMY_EVENT_EXIT;
	EvExit.ExitArgs.NextID = InState;
	const auto ExitResult = HandleEvent( EvExit );
	/* ignore results from exit-events */
	ensure( ExitResult == 0 ); 

	/* update bookkeeping */
	FFSMEvent EvEnter;
	EvEnter.ID = ENEMY_EVENT_ENTER;
	EvEnter.EnterArgs.PrevID = State;
	State = InState;
	StateTime.SetNow( World );
	
	/* enter new state */
	if( const auto EnterResult = Enemy_HandleEvent( EvEnter ) )
	{
		/* allow enter-event to short-circuit to another state */
		SetState_Internal( EnterResult ); 
	}
}

void UpdateState( double DeltaTime )
{
	/* repeatedly update until it's consumed without transitioning */
	FFSMEvent EvUpdate;
	EvUpdate.ID = EVENT_STATE_UPDATE;
	EvUpdate.UpdateArgs.DeltaTime = DeltaTime;

	int Iter = 0; /* failsafe to avoid infinite loops */
	for(
		uint32 NewState = HandleEvent( EvUpdate );
		NewState != 0 && NewState != State && Iter < 8;
		NewState = HandleEvent( EvUpdate );
	)
	{
		SetState_Internal( NewState );
		++Iter;
	}
}

uint32 SomeEnemy::HandleEvent( const FFSMEvent& Event ) override
{
	switch( Event.MakeSwitch(State) )
	{
	case FSM_ID( IDLE, UPDATE ):
	{
		if( AggroComponent->HasDetectedPlayer() )
			return STATE_AGGRO_TELEGRAPH_ALARM;
		/* ... other idle code ... */
		break;
	}
	case FSM_ID( AGGRO_TELEGRAPH_ALARM, ENTER ):
	{
		Anim->Play( AnimAlarm );
		break;
	}
	case FSM_ID( AGGRO_TELEGRAPH_ALARM, UPDATE ):
	{
		if( Anim->IsFinished( AnimAlarm ) )
			return STATE_AGGRO_PURSUIT;
		break;
	}
	case FSM_ID( AGGRO_TELEGRAPH_ALARM, EXIT ):
	{
		/* stop anim if we were interrupted for some reason */
		Anim->Clear( AnimAlarm ); 
		break;
	}
	/* ... etc ... */
	default:
		break;
	}

	return Super::HandleEvent( Event );
}

This isn’t a one-size-fits-all solution, and is largely tailored to my preferences, but it works well in practice compared to derpier things I’ve done in the past. 😅

That’s about it, lol. Thanks for reading!