# Integrating an AI state machine with actions that take more than 1 tick

Background: I'm having a problem conceptualising something which seems to be pretty fundamental. We have, what I believe to be, a traditional 'game loop', which runs at 60 fps and iterates through each entity calling it's update method (and later on its draw method). Although probably irrelevant, we're developing the game in Objective-C (for iOS / OSX). Currently an 'Entity' can be assigned a 'Controller', and the controller's 'update' method is called every frame. We would like to introduce a state machine for our AI system.

I understand the concept of having events trigger changes in the current state and we have a base state object with the following methods (heavily inspired by Mat Buckland's AI Book);

@interface KTBaseState : NSObject {
-(void)enter;
-(void)update;
-(void)exit;
}


The chapter suggests that the 'enter' method might involve entering a mine, and the execute method involves mining. However, we're developing a real time game, and 'entering a mine' is not an immediate action - it might take a few animation frames showing the guy disappear. Equally, it suggests that, on a state transition you call;

[oldState exit];
[newState enter];


But I would also envision exiting the mine to take a few frames, after which I guess the 'enter action' of the new state would then be allowed to enter / start (say, putting the bag of gold on his shoulder). When the guy's started walking - it's easy to push him around in the state's update method.

Any advice on how best to implement these 'actions' that take longer than the state transition would be greatly received. I thought about implementing some kind of action queue, but I'm not sure exactly how that would work...

1. Some actions would be 'immediately interruptable' (walking -> being hit) but others wouldn't (mining -> walking around).

2. You could end up with a massive queue of actions - when all the guy needs to do is run away!

3. In the walking state 'update' method, I would really just want to call "moveTo(destination);" every frame - would you implement this as another 'action', or just push the sprite around the screen?

Sorry for the long text with no specific list of questions. I'm seeking advice on how to approach this problem and I wanted to make sure I was clear in describing what's not clear in my head!

• I think you have done too much coupling with AI management and graphical rendering. Consider to use two state machines or use a hierarchical state machine framework. The AI shold not be interested in transient graphical problems. Jul 7, 2011 at 5:33
• @FxIII That's a great idea. I was thinking of having the AI fire 'changeAnimation' messages to the entity, but having a second State Machine that determines what animation routine the sprite is in is perfect; it means I can just push a state to the animation box and not worry about it. I guess character movement (pushing a sprite from A->B) could be done in the same way. A baseEntity could either be in a 'walking' or 'running' state (where it attempts to move towards a fixed point) or a 'stationary' state, so that the AI doesn't need to worry about what it's doing every frame. Jul 7, 2011 at 7:41
• Read about behavior trees, they handle that very well. Sep 1, 2015 at 13:39

The basics are there, but I think you want to break them down a little bit more.

State - Find Something To Do
Enter - Nothing
Execute - Pick something to do from a big list of options weighted however for this AI personality
Exit - Transition to new state (For this example its 'Enter Mine')

State - Enter Mine
Enter - Start playing an enter animation
Execute - While animation is playing, wait. If Failure, transition to new state 'Find Something To Do' (To figure out how to react to what happened) else Exit
Exit - Done playing the enter animation - Transition to new state 'Mining'

State - Mining
Enter - Find something to mine
Execute - Transition to state 'GoTo', If successful Mine
Exit - Transition to 'Find Something To Do'

State - GoTo
Enter - Calculate path to location
Execute - Move towards path, validate path
Exit - If made it, return successful event, if didnt make it return failure


Now clearly I could keep breaking this down, and just for reference say the 'Find Something To Do' was at the top of it all and one of the random things it picked to do was go mine something..

The point is to break enter/execute/exit down to a complete task, whatever it may be, and build up the overall logic that you want.. Also note that when dealing with animations you may want to break out the animation logic from the AI logic. For instance the enter mine state would OnEnter start the animation, OnExecute Check if the animation is running still and if it is done, then go to OnExit which would then look for something to mine.

EDIT: To address 2), As with anything that can be in a queue or a stack you are going to want a way to wipe it out. Example would be being attacked. Regardless of what you were going to do, you will want to survive and react to being attacked in whatever way possible. Generally with a state machine this shouldn't be a problem as you are just moving from state to state, some of which can be interrupted and others that should not be able to. But if you do want to put in a queue or stack of some sort, do include a logical way for wiping it out when the situation arises.

I hope this helps.. If not feel free to comment and I will try to tailor this more to what you are trying to understand.

• Most useful, many thanks. I think it was the animation that was confusing me the most and as you say - pushing the actual sprite animation to a completely different area will clear that up, and then just waiting for the animation to finish in execute would work well. Just out of interest, I can think of 3 ways to implement 'baseActor.moveToward(x,y)'; 1. Just update the position directly when you call the method (i.e. When state update occurs), 2. Set target and move toward it in baseActor.update(). 3. Add an action to a list for the actor and call update() on each. Are any of those bad ideas? Jul 7, 2011 at 0:27
• None of them are bad ideas and I am glad I helped. Look at the + and - of each, but really, the best choice is the simplest one that solves the problem at hand. Jul 7, 2011 at 22:15

As has been said, decoupling the AI logic from the visual logic would be a good thing, because while they are related, they definitely don't want to be closely tied. There are certainly situations where you don't want to move to a new AI state until some visual things have happened, but that is a specific case of the more general problem: that you don't always want to be doing something every frame.

Most times you start out coding AI in an immediate way: every tick you ask the entity what it would like to do this tick, and it considers all its options and makes its decision (keep moving, accelerate, turn around, fire, etc.). You'll quickly run into the limitations of that. In general, you want your AI state machine to be able to simply (and cheaply) do nothing, until 'something else' happens. That might be a timer elapsing, an animation completing, or some other trigger (perhaps from other entities in the world).

Moving to a state machine is the first step towards a more flexible system. But in general I think you want to get away from the notion of 'per-tick' updates for your higher level logic. Higher logic doesn't tend to operate in terms of a regular update cycle like that. It works in terms of events and actions. Actions will very rarely take only one frame to complete. Some may be instantaneous, some may take many ticks. Your systems shouldn't care, and should support all types. It should be possible to tie actions to events occurring, so that your actor can make new decisions based on the fact that an event has occurred.

A queue of some sort is a good way for the actor to maintain memory of 'what am I doing/thinking' between ticks. That's not to say it must blindly work its way through the queue though. It should regularly be looking at its immediate circumstances and re-evaluating. Some circumstances might cause it to junk everything in its queue and replace it with a new set of actions ("Run away!"). Sometimes it might just want to slot in a high priority action at the head of the queue ("bend over and pick up this thing that just landed at your feet, then continue"). Other times it might put in the new action at the end of the queue.

So don't think of a queue like a list of orders to be followed, think of it like a prioritised to-do list that the actor wants to tackle. There are lower level subsystems that put each order into practice (e.g. the queue holds 'go to A'), and a lower level path-finding system actually translates that into a 'how do I move this tick'.