State Driven Agent Design

In most games, the code needed to make the agents appear to behave in an intelligent way will be very complex. Without some organisation, the code soon becomes labyrinthine making it incredibly difficult to read, modify or extend.

The state driven agent design pattern is one of the most commonly used techniques for solving this problem and is used by this library. To explain state driven agent design and how it is implemented and used in this library we are going to look at a simple cat and mouse simulation.

NOTE: this simulation is one of the examples included with the library example. A detailed description of the various code elements can be found in the Programming Guides.

Simulation Scenario

In this simulation we have a ‘room’ (the game domain) containing a number of obstacles and in this room there is a cat and three mice wandering about minding their own business.

Consider the cat, while it is wandering about it is looking for a mouse to chase but until it sees one it continues wandering about. As soon as it sees the mouse it will increase speed and chase the mouse until it has been caught or can no longer be seen (perhaps the mouse has moved behind an obstacle or has escaped into a mouse hole in the wall of the room).

If a mouse sees the cat or realises it is being chased it will attempt to evade the cat, either by hiding behind an obstacle or by simply fleeing as fast as it can.

If the cat catches the mouse it takes a few moments to kill it then go back to wandering about the room. On the other hand, if the cat loses sight of the mouse it will run to the last known position of the mouse all the time looking for the mouse. If it sees a mouse it will start to chase it but if it reaches the last known position without seeing a mouse it goes back to wandering the room.

When using state driven design the first task is a number of distinct states for each entity. The cat has at least four states

  1. cat-wander state
  2. chase-mouse state
  3. seek-mouse state
  4. kill-mouse state

and for the mouse there are at least 2 states

  1. mouse-wander state
  2. evade-cat state

They say “a picture is worth a thousand words” and just to prove it here is a picture that shows all the states and state transitions for the cat and the mouse.

state transition diagram

Each state is represented by a named box and each state transition is shown by an arrow with a describing the cause of the transition. Notice that the diagram does not show the inner workings of each state because there is insufficient space and attempting to include it would confuse the diagram and negate its purpose.

In this simulation all cat and mouse movement is controlled using steering behaviours, and since the game domain contains obstacles they are all using the obstacle avoidance steering behaviour no matter what else they might be doing. For that reason we will ignore this steering behaviour and only consider the steering behaviours that have to be switched on or off when transitioning between states.

Let us start by considering the cat-wander state. At each world update cycle we check whether the cat sees a mouse, if it doesn’t then we continue using the wander steering behaviour to control its movement. On the other hand, if it sees a mouse then we want to change to the chase-mouse state and we no longer want to use the wander steering behaviour. In fact the chase-mouse state requires the pursuit steering behaviour to be switched on.

If you follow the arrows in the state transition diagram you will see that eventually we end up back at the cat-wander state when we will require the wander steering behaviour to be switched back on.

Hopefully you can see that for any state there are three sets of actions.

Actions to perform on

  1. entering the state
    • these are used to initialise the agents fields and switch on any steering behaviours needed.
  2. updating the state
    • what should be done with the agent on each world update cycle. An action may result in a change of state for this agent.
  3. exiting the state
    • used to ‘tidy up’ the agent before changing to the next state. It is usual to switch off any steering behaviours switched on in the enter and update sections of this state.

This table documents the actions for the cat-wander state.

State CatWander                                                                                                   
Enter set maximum velocity to wander level
switch wander on.
Update if the cat sees a mouse then
    change state to chase-mouse state
Exit switch wander off

In the kill-mouse state we have an interaction between the cat and a mouse (not pleasant for the mouse but makes the cat happy). To enable interactions the library provides a means to pass information between entities.

This communication is implemented by the creation, sending and receiving of telegrams. A telegram comprises of several pieces of information -

  • the entity ID of the sender
  • the entity ID of the receiver (this maybe the same as the sender!)

  • an integer value that uniquely identifies the message type. These should be defined as constants by the user

  • a delay time in milliseconds. This is the time the telegram should be stored before sending to the receiver entity.
  • any additional information that the receiver might needed to perform any actions initiated by receiving this telegram. This is optional.

So now we can say the state has four sets of actions

Actions to perform on

  1. entering the state
  2. updating the state
  3. exiting the state
  4. receiving a telegram

When the cat catches the mouse it will transition from the chase-mouse state (switching off the pursuit steering behaviour on exiting) to the kill-mouse state. The kill-mouse state is interesting because on entering it, it sends two telegrams

  • the first is sent to the mouse telling it to die.
  • the second message is sent to the cat (i.e. itself) with a 2 second delay (when the telegram is received the cat changes to the cat-wander state).

The kill-mouse state has no actions in the update or exit sections. So nothing will happen until the second telegram arrives when the cat will change to the cat-wander state. The following table summarises the kill-mouse state actions.

State KillMouse                                                                                                   
Enter set velocity to zero
increment number of mice killed
send DIE message to the mouse
send NEXT_MOUSE message to self with 2 second delaye
Update     
Exit     
Message ID Action
NEXT_MOUSE if there are mice left
    change to cat-wander state
else
    reset the simulation to start again

We have already said that the mouse has at least two states, the mouse-wander and the evade-cat state. The problem here is that the mouse should DIE when it gets the telegram no matter what its current state. We could duplicate the telegram processing code in both states, but this is bad practice and tiresome if the entity has a lot of states. The solution is for an entity to have a global state, in this state the update section actions are executed every world update cycle and is in addition to the transient states we have discussed so far. In this simulation the mouse global state has just one action which is to process the DIE telegram sent by the mouse. So now the mouse needs three states

  1. mouse-wander state
  2. evade-cat state
  3. mouse-global state

Creating the code for your state

In any game or simulation it is likely that there will be

  • an agent type with many states (e.g. the cat)
  • many agents of the same type who may in the same state (e.g. the mice)

So the program executes there will be many (possibly thousands) state transitions every second. Since the state is going to be implemented as Java class, it could cause the creating of thousands of objects, all of which will need to be garbage-collected by the Java runtime.

To avoid the inevitable performance hit on the program caused by object instantiation and collection we have to obey the following strategy –

  • a single object will be responsible for managing a particular entity/state combination
  • this single object will be shared by all agents of a particular type, when in the same state.

In object orientated programming it is possible to design a class so that only a single object can be instantiated; this is called the singleton design pattern. To simplify the source code we will avoid using the singleton pattern and in our sketch we will create a single object for each state at setup, and then use this object when required. If you want to see the singleton pattern in action then look at the source code for the Simple Soccer example.

Skeleton State Class implementation
public class MyStateClassName extends State implements Constants {

	public void enter(BaseEntity user) {
	}

	public void execute(BaseEntity user, double deltaTime, World world) {
	}

	public void exit(BaseEntity user) {
	}

	public boolean onMessage(BaseEntity user, Telegram tgram) {
		return false;
	}

} // End of class

Any state class you develop must extend the State class and have the four methods show. Miss any part and your program won't run - you will get a syntax error.

The class definition has no attributes because the state object is being shared by many entities. Each of the four methods has a parameter called user, which is the game entity we are currently processing

Notice the four methods match the four sets of actions we mentioned earlier. Since a state is created for a particular entity type, it is necessary to cast the parameter, user, to match the entity type, this enables methods specific to the entity type to be called, for instance the lookForMouse method, it only exists in the Cat class. Here is the class for the cat-wander state

public class CatWanderState extends State implements Constants {

	public void enter(BaseEntity user) {
		Cat c = (Cat)user;
		c.maxSpeed(CAT_WANDER_SPEED);
		c.AP().wanderOn();
	}

	public void execute(BaseEntity user, double deltaTime, World world) {
		Cat c = (Cat)user;
		c.lookForMouse();
		if(c.chasing != null)
			c.FSM().changeState(chaseMouseState);
	}

	public void exit(BaseEntity user) {
		Cat c = (Cat)user;
		c.AP().wanderOff();
	}

	public boolean onMessage(BaseEntity user, Telegram tgram) {
		return false;
	}

} // End of CatWanderState class

I suggest that you look [here] the complete state transition diagram and state descriptions for this simulation. It will certainly help when you examine the source code for this sketch.

So now you know about state driven agent design and have seen how a state might be implemented we need a mechanism for managing the state transitions. The mechanism is the Finite State Machine (FSM).

Managing an entity's state with a FSM

Any game entity can use a finite state machine (FSM) to set and change its state, but not all of them will need one. For efficiency reasons, newly created entities do not have a FSM, if the entity needs one then it must be added with

entity.addFSM();

The FSM is aware of three states, the global current and previous states. At every world update cycle the update method of the global state (if any) will be executed then the update method of the current state (if any) is executed.

FSM update flowchart

The FSM has many methods that can be used to set, change and test the different states, for instance the following methods can be used to set the initial values of the states.

entity.FSM().setGlobalState(a_state);
entity.FSM().setCurrentState(a_state);
entity.FSM().setPreviousState(a_state);

To change the current state use -

entity.FSM().changeState(a_state);

or to revert back to the previous state use -

entity.FSM().revertToPreviousState();

These are the most commonly used methods but there are others which get or test the various state types, you should look at the API of the FiniteStateMachine class for more details.

In the cat and mouse simulation there are 7 states and when the sketch runs it creates an object of each one with the following code.

// 4 states for the cat

CatWanderState catWanderState = new CatWanderState();
ChaseMouseState chaseMouseState = new ChaseMouseState();
SeekMouseState seekMouseState = new SeekMouseState();
KillMouseState killMouseState = new KillMouseState();
// 3 states for the mouse
MouseGlobalState mouseGlobalState = new MouseGlobalState();
MouseWanderState mouseWanderState = new MouseWanderState();
EvadeCatState evadeCatState = new EvadeCatState();

So if we want the cat to chase the mouse we would use -

cat.FSM().changeState(chaseMouseState);

Even a simple scenario like this one can be difficult to code since the implementation for the state class will need to reference classes you may not yet have created. For instance, in the CatWanderState class we will want to code to that uses the ChaseMouseState. If we write the code before creating the class then we have a syntax error and our sketch won’t run. The best strategy I have come up with is to create a skeleton class (see earlier code) for each state before creating any code for the state's logic. Although the states won’t work, at least the sketch will run and you can add and test the state logic code in stages.