Theory
This page details the theory behind the AI control system developed for my final year project at university. The AI controller has two distinct phases, first decision making and then behaviour execution.
Decision Making
For the decision-making phase, I created a control architecture based around utility theory.
Utility theory can be stated as follows: Every possible action that a person could carry out is considered based on the percieved 'utility' of carrying out that action. A person's behaviour can therefore be explained as them carrying out the actions that provide the highest utility.
This theory is not specific to game AI systems and has been used in many different fields to predict the behaviour of real people using probability models and collected data.
A decision modelling system using utility theory assigns a 'utility function' to each action in the set of possible actions. This function operates on the input data to calculate the utility value of carrying out the associated action. This an arbitrary unitless measure of the perceived benefit, normalized to a specific range (usually 0 to 1). After the utility value of every possible action is calculated, the action that produces the highest utility is carried out.
Below is a diagram showing a basic utility theory based decision model:
Utility theory is the backbone of the AI architecture in The Sims, a hugely popular game series. This is confirmed by information made public through various talks and interviews given by the developers.
The Sims was one of the main references I used while researching the topic. Similar games such as Dwarf Fortress, Rimworld, and Prison Architect were also used as references. These other games show similar need-based AI behaviour, but I could not find enough information to state whether they were based on utility theory or not. However, from the information presented to the player about the characters and their needs, along with the corresponding character behaviours, a utility theory based architecture would be a suitable implementation.
Here is an excellent talk on utility theory that takes an in depth look at the use of utility theory in games: Improving AI Decision Modeling Through Utility Theory [GDC vault]
For my prototype, I chose to include three basic needs: the need for water, food, and social interaction. The values of these needs increase over time to simulate hunger, thirst, and loneliness. These values are input into utility functions and the resultant utility values are used to choose which behaviour to carry out.
The need for social interaction uses a utility function that basically makes it the default behaviour when other needs are low. The need also increases over time leading to AI needing to take a break to seek social interaction, but never gets so high that it takes priority over extreme hunger or thirst. Below is a diagram showing the social utility function I used. The x axis shows the input, the raw need value. And the y axis shows the output utility:
Behaviour Execution
Every need has a specific task associated with it that can be carried out to fulfil that need. To carry out these tasks behaviour trees are used.
I won't go into too much depth on how behaviour trees work, but basically a behaviour tree is composed of control nodes and action nodes. An action node carries out a single discrete step of a task. A control node can have any number of child nodes and controls which of them are executed. There are two main types of control node: sequence nodes and selector nodes. The sequence node executes each child node, in order, until one fails or the sequence completes. The selector node executes each child node, in order, until one is successful.
The following website has a nice overview of the general concepts behind behaviour trees: Behavior trees for AI: How they work
Below is the simple behaviour tree created for the AI socializing behaviour. The sequence nodes are executed in order, left to right.
To reduce thirst and hunger the AI must search for food and water. Below is the behaviour tree I created for the AI to get a desired object from the map. To explain the overall behaviour simply: it starts by setting the wanted item tag, then checks if an item is already being held. If no item is held then find the desired item on the map, get a path to it, follow it, and pick it up. If an item is being held and it is the desired item then use it, otherwise drop the held item.
The player can influence the AI indirectly by issuing jobs. Jobs have a set importance value so the AI agents will evaluate whether to carry out the job task in the same manner as the need based tasks. Below is the behaviour tree related to job execution. In this behaviour tree there is a new node type that I did not mention early for brevity, a decorator node. This is a node with a single child that it always runs but modifies the return value of. In this example, if 'get job position' fails then 'cancel job' is run. However, cancel job should be guaranteed to succeed, so the failer returns a fail state to the parent node after running cancel job and breaks the sequence.
Self Reflection
Looking back on this, years later, I think that behaviour trees would be more appropriate for games with scripting support. For example, this would allow an enthusiast (modder) to use simple building blocks to create a completely custom behaviour that was not in the released game.
The best solution is often the simplest one.
With that in mind, the decision making system is simple, it avoids complex logic around edge cases that can arise with binary logic (such as finite state machines). And elegantly handles this kind of task selection based on continuously varying inputs.
However, the use of behaviour trees may be an over-engineered solution for this particular use case. These same behaviours could very easily be handled using simple if-else style logic and functions, which I think would also be easier to program, tweak, and understand.