Contents

Making Them Think

Predefined Behavior

Goal-Directed Behavior

The Middle Ground

A Simple Tutorial: Maze Solving

Discussion

Notes and References

Predefined Behavior

There are many convenient techniques we can use to predefine a character's behavior. In this article, however, we are more interested in techniques for which the character's behavior is not completely determined in advance. Therefore, we shall not attempt a comprehensive survey of techniques for predefining behavior. Instead, we shall take a brief look at two particularly popular approaches: reactive behavior rules, and hierarchical finite-state machines (HFSM).

Reactive Behavior Rules

We will use the term reactive behavior when a character's behavior is based solely on its perception of the current situation. What we mean by this is that the character has no memory of previous situations it has encountered. In particular, there is no representation of its own internal state and so it will always react in the same way to the same input stimuli, regardless of the order in which the inputs are received. A simple way to encode reactive behavior is as a set of stimulus-response rules. This has a number of important advantages:

The use of reactive behavior rules was also one of the first approaches proposed for generating character behaviors, and it is still one of the most popular and commonplace techniques. Great success has been obtained in developing rule sets for various kinds of behavior, such as flocking and collision avoidance. As an example of a simple stimulus-response rule that can result in extremely sophisticated behavior, consider the following rule:

Believe it or not, this simple "left-hand rule" will let a character find its way through a maze. It is an excellent example of how one simple little rule can be used to generate highly complex behavior. The character that follows this rule doesn't need to know it is in a maze, or that it is trying to get out. It blindly follows the rule and the maze-solving ability simply "emerges". Someone else did all the thinking about the problem in advance and managed to boil the solution down to one simple instruction that can be executed mindlessly. This example also shows how difficult thinking up these simple sets of reactive behavior rules can be. In particular, it is hard to imagine being the one who thought this rule up in the first place, and it even requires some effort to convince oneself that it works.

We can thus see that despite some of the advantages, there are also some serious drawbacks to using sets of reactive behavior rules:

It is often easier to write a controller if we can maintain some simple internal state information for the character. One popular way to do this is with HFSM that we discuss in the next section.

Hierarchical Finite-state Machines (HFSM)

Figure 2. The WhichDir FSM

Finite-state machines (FSMs) consist of a set of states (including an initial state), a set of inputs, a set of outputs, and a state transition function. The state transition function takes the input and the current state and returns a single new state and a set of outputs. Since there is only one possible new state, FSMs are used to encode deterministic behavior. It is commonplace, and convenient, to represent FSMs with state transition diagrams. A state transition diagram uses circles to represent the states and arrows to represent the transitions between states. Figure 2 depicts an FSM that keeps track of which compass direction a character is heading each time it turns "left".

As the name implies, an HFSM is simply a hierarchy of FSMs. That is, each node of an HFSM may itself be an HFSM. Just like functions and procedures in a regular programming language, this provides a convenient way to make the design of an FSM more modular. For example, if a character is at coordinates (x,y), Figure 3 depicts an HFSM that uses the FSM in Figure 2 as a sub-module to calculate the new cell after turning "left", or moving one cell ahead.

Figure 3. HFSM that uses the WhichDir FSM

HFSMs are powerful tools for developing sophisticated behavior and it is easy to develop graphical user interfaces to assist in building them. This has made them a popular choice for animators and game developers alike.

HFSMs maintain much of the simplicity of sets of reactive-behavior rules but, by adding a notion of internal state, make it easier to develop more sophisticated behaviors. Unfortunately, they also have some of the same drawbacks. In particular, actions are chosen deterministically and there is no explicit separation of domain knowledge from control information. This can lead to a solution which is messy, hard to understand and all but impossible to maintain. Just like reactive-behavior rules, there can also be a large amount of work involved if we want to obtain even slightly different behavior from an HFSM.

________________________________________________________

Goal-Directed Behavior