# General info

**Disclaimers:**
* The below is subject to change
* This is all (currently) sloth's opinion, which can be wrong ¯\\\_(ツ)\_/¯ I've prototyped most of this to some degree.

---

# tl;dr

Going from bottom to top on implementation:

**Operators:** These are what are run every single tick for an NPC that do the actual work. They should only deal with actual world state.
**Primitive tasks:** These are wrappers around operators, so there can be many primitives that implement the same operator. Essentially it adds preconditions and effects to a specific operator, e.g. "MoveToDownedPlayer" and "MoveToFood" could use the same "MoveToEntity" operator but they're using it for different targets. The reason for this is primitives deal with an *abstracted* world state rather than the *actual* world state, e.g. "EquippedItem" may be changed as the planner is running.
**Compound tasks:** These get 'decomposed' further and further until a final plan consisting of only primitive tasks is obtained. The different types of compound tasks are:
* **Selectors:** Goes down a list trying to find the first task where it's preconditions are met. This list can be comprised of primitive or compound tasks, e.g. "KillEntity" could be "RangedCombat" then "MeleeCombat"
* **Sequences:** A sequential list of primitive tasks, e.g. pickup item would be "MoveToEntity" and "PickupEntity"

**World states / Blackboard (interchangable)**: These are representations of the world used for planning e.g. nearby players:
* sensors (event-driven states, e.g.. hunger, health, inventory) and
* daemons (states queried every n milliseconds). Given something like "nearby players" is potentially expensive to run you'd normally cache the results for n milliseconds. You may also have additional requirements for this, e.g. if the player isn't in LoS you may drop them from this list.
* Additionally, Horizon: Zero Dawn used group blackboards so agents in the same group could share data with each other (e.g. nearby players may be used group-wide so if 1 NPC spots a player then all the NPCs may go attack)

**Planner:** Typically this is given a selector task and will try and obtain a list of primitive tasks to run. Planners don't run every tick, typically 5hz or lower.
**Agent / AI Processor**: This will handle whether a new plan needs to be obtained, as well as running the current primitive task / operator. It should also handle stuff like barking at appropriate times.
**Group manager**: An overall director for agents; could handle all of an NPC type station-wide or a particular smaller group. Could also potentially manage groups (e.g. having a commander AI and squad AI). This isn't exactly concrete as something like a utility AI could be used instead, but it does make it easier to give dynamic orders, e.g. an admin could give every AI a "Kill players" selector task and they would all try to do it in their own way.

# The current state of SS13
Currently most (all?) SS13 bots use Finite State Machines (FSMs). This means that it has a set of discrete states it can be in.

From vgstation:

//Corgi
#define IDLE 0
#define BEGIN_FOOD_HUNTING 1
#define FOOD_HUNTING 2
#define BEGIN_POINTER_FOLLOWING 3
#define POINTER_FOLLOWING 4

A corgi can only be one of the defined states and its entire behavior set is based on that.

FSMs are very useful for simple behaviors because they're easy to setup and are useful for simple entities such as the goombas from Mario.

They also suck for trying to create more in-depth behavior. Try adding 10 common behaviors (e.g. "attack player") to all NPCs and start crying.

**Go beyond**
NPCs have generally been a second-rate citizen; after all SS13 is a multiplayer game, and byond already runs like hot garbage.

With SS14 a clean slate is possible and to create an NPC with the ability to do more we need to move beyond FSMs because they're unmaintainable when you add a significant number of actions. Some alternatives (probably the most common ones) are listed below for reference purposes.

Keep in mind that most actual games use some combination of techniques to do what they want, e.g. FFXV uses a FSM combined with a BT, Tomb Raider uses GOAP with sequence tasks, etc.

---

**Finite State Machines**

As seen in:
* SS13
* Mario

As outlined above

---

**Behavior Trees**

As seen in:
* Halo
* Alien Isolation (they have a MASSIVE one which can be seen on the wiki)
* Almost all FPS

Should be self-descriptive; you go down a tree in order of highest priority node to least priority looking for a task that can be done successfully.

BTs tend to include different node types such as: Selector nodes (that form the tree structure), Sequence nodes (multiple tasks in run consecutively), parallel nodes, action nodes (the actual task to be done) etc.

Recommended consumption:
* AI Arborist: Proper Cultivation and Care for your Behavior Trees

---

**Utility AI**

As seen in:
* Guild Wars 2
* The Sims

Essentially each action that can be taken has numerous scorers that affect the "utility" of that action, and from the list of actions the highest one is chosen. [There's a simple chart on gamasutra for this](https://www.gamasutra.com/blogs/JakobRasmussen/20160427/271188/Are_Behavior_Trees_a_Thing_of_the_Past.php), though the score would be weighted from 0 - 1 and you would also include preconditions (see the recommended video).

It tends to be very designer focused on tweaking scores.

Recommended consumption:
* Building a Better Centaur: AI at Massive Scale

---

**Goal Oriented Action Planner (GOAP)**

As seen in:
* F.E.A.R (invented for by Jeff Orkin)
* Tomb Raider (2013)
* Transformers: War for Cybertron

Pathfinding for AI. Throw a bunch of nodes at an AI, e.g. 40, then work backwards / forwards to the start / end. Each node along the way has preconditions before it can be done and effects that it applies to the running world state.

If you had infinite processing power this would probably be the AI to use. There are some efficiencies you can gain, e.g. Tomb Raider used sequence tasks a lot to cut down the search space, but for a massive game like SS13 where you expect a large number of nodes over time it's probably not feasible.

Recommended consumption:
* Three States and a Plan: The A.I. of F.E.A.R.

---

**Hierarchical Task Network Planner (HTN)**

As seen in:
* Guerilla Games (Horizon: Zero Dawn, Killzone)
* Transformers: Fall of Cybertron (yes they went from GOAP to HTN for the sequel)

Somewhat of a bastard child of GOAP (it was made in response to GOAP) and Behavior Trees and leans more on the Behavior Tree side of the fence.

There's 2 types of tasks: Compound and Primitive

**Primitive** tasks are somewhat of a wrapper around operators which are actions can be taken e.g. Pickup Item, Use Melee Weapon, etc. These contain preconditions before the task can be met, effects that it has on world state (e.g. letting you pass variables through to future tasks), and an operator.

So essentially you can have 1 operator implemented in 2 different primitive tasks (each with different preconditions and effects).

**Compound** tasks are comprised of multiple other compound / primitive actions. Most HTN literature describe these as having "Methods" (i.e. a selector) and "Subtasks" for each method.

For simplicity it's better to break this up into "Selector" tasks and "Sequence" tasks (like a BT).

The main difference from a BT is how the planner is, e.g. how are new plans treated when one is already running, how far into a sequence do we check the preconditions, etc.

Recommended consumption:
* GameAI Pro Chapter 12: Exploring HTN Planners through Example
* Hierarchical AI for Multiplayer Bots in Killzone 3 - Game AI Pro

---

# What to use?
tl;dr HTN / Behavior Trees, at least for getting concrete actions

The hard part is how do we decide what root task to run through. "Pure" HTN would have a single task that encompasses the entire domain of actions for a single NPC which is not ideal as it'd be hard to give one-off task to NPCs. Same with using utility AI (although utility AI would be better than a single task encompassing everything)

For Horizon they used managers for groups of AIs that would dole out tasks which seems easy to prototype, at least compared to utility AI. Worst-case scenario we re-use the tasks and go a different route.

See the tl;dr for more

# What needs to be implemented for NPCs

**Blackboard / World state**
This is a representation of the world for the AI. Essentially different data sources need to be combined together for AI use, e.g. a "Nearby Players" state would get all nearby entities with players attached.

HTN typically has sensors (event-driven states) and daemons (actively polled states that may be expensive to do every tick so they're run occasionally).

**A Planner**
Given a specific task it will be decomposed into a series of primitive tasks to do.

**AI Handler**
This will listen for daemon updates and trigger new root tasks as required, as well as specify the priority for tasks.