Source 1 NPC AI System
In game development, NPCs often get developed using Finite-state machine or Behavior trees. These would decide what an NPC would do in certain situations. It is also common to mix techniques and create a more hybrid system. Another example would be Minecraft's Brain AI System.
This article focuses on an explanation of Source 1's NPC AI System, CAI_BaseNPC. Which appears to even be present in Half-Life: Alyx.
Overview
In Source 1's AI System, a core component of NPCs appear to be Activites, Schedules, Tasks and Conditions, that each NPC class can define.
Here we will look at some example NPCs, such as the Antlion.
Each of these have a Unique Id, which appears to be re-presented by a string within the C++ macro definition.
Imagine a conveyor belt with packages going through, where the conveyor is the tick speed.
The packages that go through the conveyor are defined by the schedule. Each package represents a task that has to be executed. The conveyor is smart and will avoid collisions and only proceed to process a package, once the other one has been processed or discarded. In between that process, each package can get discarded from the conveyor belt at any time.
Schedules
Schedules appear to define a set of Tasks.
Starting from CAI_BaseNPC::NPCThink going into CAI_BaseNPC::MaintainSchedule to CAI_BaseNPC::GetNewSchedule, to CAI_BaseNPC::SelectSchedule. After schedule thinking follows CAI_BaseNPC::PostscheduleThink, and any "Transient Conditions", such as COND_HEAVY_DAMAGE, get cleared.
Here is an example definition of a schedule from npc_antlion.
//==================================================
// Run from the sound of a thumper!
//==================================================
DEFINE_SCHEDULE
(
SCHED_ANTLION_FLEE_THUMPER,
" Tasks"
" TASK_SET_FAIL_SCHEDULE SCHEDULE:SCHED_IDLE_STAND"
" TASK_ANTLION_GET_THUMPER_ESCAPE_PATH 0"
" TASK_RUN_PATH 0"
" TASK_WAIT_FOR_MOVEMENT 0"
" TASK_STOP_MOVING 0"
" TASK_PLAY_SEQUENCE ACTIVITY:ACT_ANTLION_DISTRACT_ARRIVED"
""
" Interrupts"
" COND_TASK_FAILED"
" COND_ANTLION_FLIPPED"
)
Each defined schedule is put into schedulesToLoad. Schedules can be picked by scripts as well, but NPCs mainly define it in ::SelectSchedule. An interesting one here is SCHED_ANTLION_BURROW_AWAY since it happens depending on spawn flags, or an input CNPC_Antlion::InputBurrowAway.
CAI_BaseNPC::MaintainSchedule
This appears to be the initial function of the scheduling loop.
A major portion of logic appears in a "for loop" with a max iteration defined by MAX_TASKS_RUN.
It starts with checking if there is a current schedule active and if a current task is complete, to decide whether it should continue to the next task or not through NextScheduledTask.
NextScheduledTask - increments the ScheduleIndex
Schedule Change Switch
CAI_BaseNPC::IsScheduleValid
Afterwards it validates the existing schedule or whether the NPC is meant to change states. If there isn't a schedule, it means validation fails and exits early from CAI_BaseNPC::IsScheduleValid.
CAI_BaseNPC::IsScheduleValid- returns true as long as the current schedule is still the proper schedule to be executing, taking into account all conditions
Then it can call BuildScheduleTestBits, which appears to allow NPCs to have custom interrupt conditions through SetCustomInterruptCondition. For example the Antlion if in SCHED_CHASE_ENEMY would interrupt that schedule if it can jump.
If something interrupted the schedule, or the schedule is finished, then it would return false, meaning that the schedule isn't valid.
If schedule not valid/interrupted
If the current schedule isn't considered valid anymore, CAI_BaseNPC::OnScheduleChange gets triggered. Then it does ShouldSelectIdealState which has a lot of comments.
COND_TASK_FAILED is set?
and if the ideal state didn't change, it will try to get a fail schedule, probably from TASK_SET_FAIL_SCHEDULE. To prevent the NPC from doing the same thing again, which would just fail. This means it can set a new schedule.
Otherwise, if the NPC is supposed to change the state. Changing state means selecting an entirely new schedule.
If no Schedule
If there isn't any schedule it will select one through GetNewSchedule, similar to if the NPC was meant to change state.
Task Start and Run
The next part is where it determines whether to start or run tasks. It will only start a new task if the Task Status is TASKSTATUS_NEW. The next task is determined by the current schedule index. It can invoke CAI_BaseNPC::StartTask.
After checking whether to start a new task, the system calls CAI_BaseNPC::MaintainActivity, which appears to be for transitions in animations, m_nIdealSequence. It also reveals that there is an activity for transitions called ACT_TRANSITION.
If the task status isn't complete nor a new one, it means it should run the task, as long the task didn't fail.
It uses GetTask to get the current scheduled task.
Note: Not every task will mark itself as TaskComplete() and may take a few more frames. While running a task it will determine whether or not the "for loop" should stop through bStopProcessing.
Tasks
Tasks appear to be the actual actions that an NPC can do. Tasks or pTask can have data associated with them, and scripts appear to define behavior in ::StartTask and ::RunTask, through a switch case.
Not every Task appears to have a definition in ::RunTask, and such tasks will have a default and trigger TaskComplete.
CAI_BaseNPC::MaintainSchedule triggers the start of a Task and Running.
NPCs usually have Tasks defined in an enum in the .h file, which allows to find references easier, if they're not built by a macro.
Conditions
Conditions appear to be nothing else other than a value in a Map, which are used to take decisions, such as interrupting an activity or for certain transitions.
CAI_BaseNPC::SetConditionCAI_BaseNPC::ClearConditionCAI_BaseNPC::HasCondition
appear to be mostly used through out NPC code. These interact with m_Conditions.
Conditions are modified at various of places, such as SelectSchedule, GatherConditions and more.
e.g. GatherConditions for the Antlion to determine if it is in the water or not.
States, Activities and Memory
States are used additionally to determine what schedule to pick, for instance SCHED_IDLE_STAND when Template:NPC STATE IDLE and not moving anywhere. This would indicate being part of a State Machine pattern, while tasks almost resemble a behavior like pattern.
Activities appear to be for animations.
Memory appears to be just fields of data and are subject to be used anywhere.
Conclusion
From this at the moment, it isn't clear if there is a visualizeable graph that shows what an NPC can do or not.
Mostly because macros are used to define tasks, which make it difficult to find their definition in IDEs.
Schedules are defined using macros instead of C++, either because of limitation of the language back then or other reasons. The usage of macros would usually indicate that the code structure could be wrong and improved through classes or other statements and expressions.
Tasks are hard to trace because their Start and Run logic appear to be scattered at various of places.
npc_antlion uses SelectSchedule to clear out conditions, which isn't really what the function name isn't pronouncing out to do.
Comparison
The system seems to differ a bit from Minecraft's Brain System, while having similar terminology across the place. In Minecraft, a kind of Behavior Tree concept is built during initialization. What appears to be Schedules in Source 1, appears to be an Activity in Minecraft, while Tasks appear to be Behaviors. Minecraft uses Activities to insert Tasks, while things are tied to conditions and given a priority for the game loop.
In Source 1, conditions are scattered across the place. Additionally in Source 1 there's areas where NPCs were made to have behavior altered through scripts.
See also
- CAI_BaseNPC
- Creating an NPC
monster_dummy.cppai_basenpc_schedule.cpp- Visualizing C++ macros with -E