AI Framework

AI Framework

Ok, I'll try to explain in a few paragraphs, what the new AI code framework is about and how it can be used. I'll start off with a sketch of the current AI components (click to enlarge):

Subsystems

Each AI has four distinct Subsystems: Senses, Movement, Communication and Action. Each Subsystem can perform one single Task at a time.

The idea behind the Subsystems is that the AI should be able to perform several Tasks at the same time. Previously, many things in the script were handled via eachFrame loops, each of which had to “remember” calling the standard routines, like SensoryScan, which was tedious. The Subsystem approach is there to provide four Task slots which correspond to a logical part of the AI. Hopefully, this should allow for a more “high-level” programming of the AI’s behaviour.

For example, an attacking AI has several Tasks to perform: chase the enemy, watch out for his position and attack him when he's near enough. Translated into the Subsystem framework this would be: Push a ChaseEnemyTask into the Movement Subsystem, a CombatSensoryTask into the Senses Subsystem and the CombatTask into the Action subsystem.

The Subsystem::PerformTask() must be called by the Mind class only (see Mind). Subsystems can be enabled or disabled. Disabled subsystems return FALSE when calling PerformTask(), which is important feedback for the calling Mind class (Disabled Subsystems are skipped when iterating over them each frame).

To allow for serial task processing, each Subsystem has its own TaskQueue which gets exectuted, one Task after the other.

When a Task is finished, the Subsystem is calling State::OnSubsystemTaskFinished() and passes the ID of the subsystem along. This should make it easier for monitoring the various subsystems in State::Think.

Note: The four subsystems are identical, i.e. the movement subsystem is technically equal to the senses subsystem. I only named them to make assigning tasks in the code more obvious (GetSubsystem(SubsysMovement) is more intuitive than GetSubsystem(1)).

Subsystem Interface

The most recent documentation of the public Subsystem interface can always be found in the Subsystem.h header file. A short pseudocode summary is shown here:

class Subsystem
{
  // Performs the currently active Task (returns TRUE if the subsystem is active and the task was performed)
  bool PerformTask();

  // Adds a Task and makes it the active one. The previously active task is pushed back in the queue. 
  void PushTask(TaskPtr);

  // Finishes the currently active task. Next time PerformTask() is called, a new Task is picked from the queue.
  void FinishTask();

  // Replaces the foremost Task with the given one.
  void SwitchTask(TaskPtr);

  // Adds the given Task to the end of the queue.
  void QueueTask(TaskPtr);

  // Removes all Tasks and disables this subsystem.
  void ClearTasks();

  // As the name states
  void Enable(); 
  void Disable();
  bool IsEnabled();
};

Mind

Each AI has a Mind, whose purpose is to control the Subsystems. The Mind is always in a certain State (e.g. Idle, Combat, Searching).

The Mind::Think() method is called from idAI::Think(), hence it happens each frame. The Mind::Think method doesn't do much, but passes the call to its currently attached State::Think() instead, as supposedly most of the thinking is depending on the current State the AI is in.

At any rate, the Mind picks exactly one of the four AI Subsystems and calls Subsystem::PerformTask(). Note that only one of the four subsystems is called each frame, so the calls are interleaved over the frames. The Mind increases its subsystem iterator each frame, disabled Subsystems are skipped. If all four Subsystems are filled with Tasks, each Subsystem gets called every fourth frame - if only one Subsystem is enabled, it gets called each frame.

The abstract definition of a Mind is defined in AI/Mind.h, the standard implementation is the BasicMind class. In principle it's possible to swap an AI's Mind with a different implementation (perhaps a DrunkenMind or something like that). If this concept doesn't work out, one could also remove the intermediate Mind class and replace it with the BasicMind implementation.

The Mind holds its very own StateQueue, similar to the Subsystem's TaskQueue. States can be pushed/switched and ended. When switching to a new States, the Mind class calls State::Init() once. This gives the State the opportunity to plug the right Tasks into the Subsystems and do some other one-time setup processing, whatever this might be.

Mind Interface

The interface is extensively documented in the Mind.h header file, a short summary is shown here:

class Mind
{
   // Gets called each frame by idAI::Think.
   void Think();

   // Pushes the current state, the previously active one gets postponed.
   void PushState(StatePtr);

   // Switches to the given state, the previously active one gets cleared.
   void SwitchState(StatePtr);

   // Ends the current state (gets destroyed next round) and a new one is picked from the queu
   void EndState();

   // Clears all pending States and falls back to the default state.
   void ClearStates();

   // Returns the currently active State
   StatePtr GetState();
 
   // Returns the reference to the AI's memory (is always owned by this Mind class)
   Memory& GetMemory();
};

Note: It's possible to call SwitchState/PushState/EndState/etc. during one State's initialisation. It is ensured that the current State object is not being destroyed immediately (to avoid destroying objects in the middle of code execution), this happens at the beginning of the next Mind::Think() call. The same holds for the Subsystem Push/Switch routines - the current Task doesn't need to fear self-destruction when calling these methods.

State

A State implementation must derive from the abstract base class (ABC) in AI/States/State.h. A State handles all incoming stimuli and takes the appropriate action. All the decision algorithms are encapsulated within a certain State.

Further description see AI State.

Task

A Task can be plugged into any of the four Subsystems and gets performed each time the Subsystem::PerformTask() method is called. (this calls Task::Perform()). When the Task is about to be performed for the first time, the Subsystem invokes the Task::Init() call to give it a chance to do some one-time processing (setting up walk paths, scan the environment, whatever).

More information: see AI Task

Coding Paradigm

Here are some general notes about the coding style I used for implementing this framework, maybe this helps understanding my decisions.

Namespace

All Mind/State/Task and related classes are in namespace ai. Obviously, this is to avoid naming conflicts with other classes in the global namespace.

Resource Management

All the Tasks/States/Mind/Subsystem classes are allocated using boost::shared_ptrs, no raw pointer whatsoever. This saves me from using any manual resource management, as everything is reference-counted by the boost routines.

For instance, the State class defines its accompanying shared_ptr like this:

typedef boost::shared_ptr<State> StatePtr;

Once this is defined, new States are created like this (see also IdleState::CreateInstance())

StatePtr state(new State);

This follows the RAII design pattern. I took care that the StatePtrs are held by the Mind class only, and the TaskPtrs are owned by the Subsystem they're attached to, but it really doesn't matter much.

Library

One might wonder why I wrote the templated Library<class Element> class. I did this to make saving/loading easier. Once the AI class is restored from the savefile, all the states and tasks must be instantiated and put into place. To make identifying the classes easier, each Task/State class must provide a unique string identifier, which gets saved into the idSavegame file. When the class must be restored, this string identifier can be used to acquire a new class instance from the Library.

Behind the scenes, the Library maps the names of the classes to callbacks:

// The Element class can be a Task or a State, this is the shared_ptr typedef
typedef boost::shared_ptr<Element> ElementPtr;

// Define the function type to Create an Element Instance, matches ElementPtr CreateInstance();
typedef boost::function<ElementPtr()> CreateInstanceFunc;

// The actual map
typedef std::map<std::string, CreateInstanceFunc> ElementMap;

Two singleton Libraries exist, one for States, one for Tasks:

typedef Library<Task> TaskLibrary;
typedef Library<State> StateLibrary;

The Tasks/States register themselves at DLL load time with the singleton instance of the respective Library class. An example can be found in the IdleState.cpp file. The boost::function callback points to a static member method of the State/Task class in question.

idStr vs. std::string

Although I'm not a fanboy of the homegrown idStr class, I used it almost everywhere just for the sake of consistency. However, for the Library class I fell back to std::string for a good reason, as the idStr class is unsuitable for use as key in std::map. The implicit cast to const char* implemented by idStr and the lack of the operator< method performs a pointer-comparison when used as key in the std::map, and the string lookups fail.

Why so many idAI* owner arguments?

Due to the restriction of raw pointers imposed by the Saving and Restoring guidelines, all entity pointers must be stored in idEntityPtr classes. To avoid calling _owner.GetEntity() all the time (which performs a lookup in the huge gameLocal.entities array), I decided to pass the pointer along the call chain, wherever possible. This is potentially faster than constantly looking up the spawnid in the entities array. Also it makes the use of assertions easier.

Assertions

I use assertions a lot at the beginning of functions. Assertions are removed from release builds and therefore won't have an impact on performace there. Also, I refrained from using too much

if (owner == NULL)
{
  return;
}

in each and every function, because

assert(owner != NULL);

is shorter and allows the function design to be more strict.

For instance, I'm asserting non-NULL owner pointers in every Mind::Think() method, because the owner is the one who is calling the Mind in the first place. Each method down the calling chain is getting an idAI* owner pointer passed along (see above) and these methods are encouraged to assert non-NULL pointers as well. If NULL-pointers are encountered, the program state is probably seriously screwed up anyway, so it's better to let the coder know that there is something amiss (the hard way, by letting the program crash).

Just checking for NULL pointers via IF and calling RETURN only looks like it was more stable, but in the end you'll have to fire up the debugger in any case to find out why the hell your Task class is not performing.