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

Question

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!

Answer 1

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.

Answer 2

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'.