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:

• Although the set of rules might be short, and each of the rules very simple, that doesn't necessarily mean the behavior that results from the character following the rules is simple at all. That is, we can often capture extremely sophisticated behavior with some simple rules.
• We can usually evaluate the rules extremely quickly so there should be no problem obtaining real-time response from our characters.
• There is no need to worry about various knowledge representation issues that arise when characters start thinking for themselves. That is, the characters are not doing any thinking for themselves; we have done it all for them, in advance.

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:

• The biggest problem is thinking up the correct set of rules that leads to the behavior we want. It can require enormous ingenuity to think of the right set of rules and this can be followed by hours of tweaking parameters to get things exactly right.
• The difficult and laborious process of generating the rules will often have to be repeated, at least in part, every time we want to effect even a slight change in the resulting behavior.
• Since the behavior rules are deterministic, once an action is chosen, there is no way to reconsider the choice. There are many cases when a cognitive character could use its domain knowledge to quickly anticipate that an action choice is not appropriate. An autonomous character has no ability to make such judgments and, regardless of how appropriate it is, must blindly follow the predefined behavior rules that pertain to the current situation.
• When there are many rules it is quite likely their applicability will overlap and they could give conflicting suggestions on which action to choose. In such cases some conflict resolution strategy must be employed.

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