Finite state-machine example

Finite state-machine example

Working on our Ecosystem student project, I deemed it appropriate to use a finite state-machine to dictate the logic of our animals. An implementation of the theory can be found here, although it makes little sense without the explanations from this article.

A finite state-machine (FSM) is a way to graph and control AI behavior. While it is less commonly used in game development vs behavior trees (which facilitate more complex behaviors with longer sequences of actions), it is perfect for simpler constructs such as this one:

As seen in the illustration, the nodes in the graph represent behaviors, while the edges represent transitions between these. An edge can be either uni- or bi-directional, which dictates whether or not the transition is one-way. Another thing to note is that the same FSM graph can almost be used for both herbivores and carnivores. The almost being really important, because FSMs are supposed to be inheritable – but if the carnivore inherits the graph shown above, it’ll have access to functions that aren’t relevant to it. In order to solve this problem, an enum is implemented to indicate the animal type within the FSM itself. This can restrict graph transitions depending on the type, plus the use of enum (vs boolean) leaves the system open for future additions of animal types.

To further elaborate on the design of the graph, note the Survival Priorities written in the upper left corner. The order of is loosely based on the two lowest tiers of Maslow’s hierarchy of needs:

  1. Flee
  2. Eat
  3. Sleep

This list describes the restrictions of the graph. If the animal is fleeing, it may do nothing else until it is done. That is why all of the edges leading to the “Fleeing” node are uni-directional. Likewise, if the animal needs to eat, it cannot sleep. This leads to the “Awake” node, which is a form of idle state between “Hunting” and “Sleeping”, which the animal will transition to when it is done hunting.

To better illustrate this concept, we need some descriptions slapped on the graph edges:

As visible in this illustration, bi-directional edges actually consist of two “uni-directional” ones. This is due to how the circumstances are different, depending on which end of the bi-directional edge the AI is located (eg. what behavior is currently being executed). For example, when a herbivore AI is executing the “Awake” behavior, the following checks are made in the listed order, to match the Survival Priorities list:

  1. It looks for predators
  2. It checks for its hunger parameter
  3. It checks for its fatigue parameter

Let’s say that the hunger parameter is too low. The AI will then transition into the “Searching” behavior. While it is executing this, it looks for targets to eat – plants in this case. If a predator is spotted during this process, the AI will transition into the “Fleeing” behavior. Otherwise it will continue to search until a target is spotted, transitioning into the “Hunting” behavior. The Hunting node is a bit interesting, as the same behavior will be used for both animals, seeing as they simply need to pursue a target until close enough to consume it.

In the case of the AI beginning to execute the Fleeing behavior, a middle node called “Recovering” has to be transitioned across, before it can resume its normal behaviors. Whether a recovery phase is necessary has yet to be tested, as it may be good enough if it simply transitions back into its Awake behavior directly from Fleeing.

Passive behaviors (eg. “Seeing”):

It is important to mention that not all behaviors are listed in this FSM graph, due to their non-restrictive nature. This specifically relates to the AI recording details about the environment (or “Seeing”). So long as an AI is not sleeping it will record the locations of any object it comes across, complete with redundancy checks and heat mapping (see sensory systems and memory for elaboration). This information will be used when performing the “Searching” behavior.

Pseudocoding the FSM:

Below are the pictures of the pseudocoding process of the FSM. Please note that the statement seen in the “Awake” case, where the system checks whether or not the animal is a herbivore, should be present in the “Hunting,” “Searching” and “Recovering” cases as well. These changes appear in the transcribed version below:

Enum type {Herbivore, Carnivore}

Enum behavior {Awake, Sleeping, Searching, Hunting, Fleeing, Recovering}

Switch (behavior):

————-

Case behavior.Awake:

if(type == type.Herbivore)

//Herbivores check viewcone for Carnivores

If Carnivore is spotted

Set behavior to behavior.Fleeing

Weight-based random between Awake, Sleeping, Hungry (Searching/Hunting)

Idle behavior

————-

Case behavior.Sleeping:

if(isSleeping)

Increase energy

Weight-based random between Awake, Sleeping

Else

Begin sleeping

————–

Case behavior.Searching:

if(type == type.Herbivore)

//Herbivores check viewcone for Carnivores

If Carnivore is spotted

Set behavior to behavior.Fleeing

if(isSearching)

If target is spotted

Set behavior to behavior.Hunting

Else

If path over

Request new path

Else

Continue searching

Else

If useful memory exists

Create path

Else

Request new path

—————-

Case behavior.Hunting

if(type == type.Herbivore)

//Herbivores check viewcone for Carnivores

If Carnivore is spotted

Set behavior to behavior.Fleeing

if(isPursuing)

If target is visible

Path to target

If target is close enough

Kill target

Else

Set behavior to behavior.Searching

—————-

Case behavior.Fleeing

If predator in range

Follow escape vector

Else

Set behavior to behavior.Recovering

—————-

Case behavior.Recovering

if(type == type.Herbivore)

//Herbivores check viewcone for Carnivores

If Carnivore is spotted

Set behavior to behavior.Fleeing

if(recoveryTimer =< 0)

Set behavior to behavior.Awake

Else if predator in range

Set behavior to behavior.Fleeing

Update recoveryTimer

Else

Decrement recoveryTimer

From each of these cases, an assortment of functions can be derived. But one thing that is important to consider – which does not really stand clear from the pseudocode – is that the various booleans described (eg. isPursuing, isSleeping etc.) should be reset to false whenever the “set behavior to” function is called. This is due to how these booleans describe whether or not the action associated with this behavior, is actively being executed. If the AI transitions to a different behavior, it is no longer performing the action it was just doing and will have to indicate that as well.

It could be argued that each of the AIs should have their own FSM graphs, which would save the extra type check. However, seeing as this is an iterative process and that changes to the core would then have to be applied to two graphs instead of just one, it is better kept as it is until the core has been tested.

Code:

For once, there really isn’t much to be said about the code. Instead of outlining everything one function at a time, this is a very specific solution to a very specific problem, and should not be considered an easily reuseable package file. Instead, look at it as a demonstration of how the FSM design can implemented, which really is just a bunch of switches turning on and off, to ensure that the transitions occur as they should.

Consider it an exercise, try to look at the FSM graph and see how it reflects in the project’s “Query” coroutine. The only thing you’ll see in the Unity project, is that it outputs its current state to the console. You can swap between the two types of animals from the drop-down menu, but everything simply runs on a latticework of true-or-false logic

Comments are closed.