AI and State Machines

Deterministic - display a completely predictable behaviour (with 100% certainty)

Stochastic - display some level of uncertainty in their behaviour, and we want the game to do different things as the game progresses

Graph of decisions and their possible consequences, used to create a plan to reach a goal.

Can be done with games with discrete states, with the initial state being the root.

For incredibly large trees, limit how far the tree generates and keep generating every decision that needs to be made.

Any device that stores its current status and whose status can change as the result of an input.

Only for AI with a simple set of actions, such as units in a game.

The addition of lag to a FSM transition between cause and effect, giving a reaction time to the objects

How long the state must be active in a FSM before a transition can happen

AI will use world metadata to cheat, with extra collision volumes defined in the world with tags to define safe spaces for the AI to go to

How an AI figures out how to get from point A to point B, avoiding places it cannot fit or move through

2D/Simple 3D: Tile or grid system

Complex 3D: Navigation mesh

Typically has a different mesh per type of AI to account for sizes

Represented as a graph, with nodes being the tiles/meshes, and edges being the connectivity between the areas

Dijkstra's Algorithm, however looks at a LOT of nodes given the nature of navigation.

A* Algorithm, the same as Dijkstra but with a heuristic as well to show how close the node is to the destination, either in Euclidean or Manhattan distance.
-Open List: Holds the set of nodes that might be considered when trying to find the best path, includes all expanded node's edges
-Closed List: Where nodes go when they're expanded, so all the nodes considered in the best path

Where the AI holds all the nodes inside a matrix, generated at runtime, and does a lookup across this to do pathfinding.

A form of AI decision making where the AI is given a set of actions, which have 1+ effect and 0+ prerequisites, and a goal to reach.
Typically, the AI builds out a plan to do that task using a reverse graph, taking all the ways the goal could be attained by a single action and building back from it in order to reach it from the current state, meeting the prerequisites of the action.

A state in the world that the AI is trying to reach, such as opening a door, or killing an enemy.

An algorithm to keep together large amount of AI without need for direct player control

Uses a simple set of rules to keep all objects (BOIDs) together

Separation: If neighbouring BOIDs get too close, apply a force to separate them

Alignment: Looks at nearby neighbours and applies a force to move in the average direction

Cohesion: All BOIDs apply forces to slowly move towards the average position of nearby neighbours, while stragglers pick a random BOID to move towards.

Avoidance: Objects defined as avoiders are split apart from if they get close to the BOIDs