Implementing AI state stack

Hello! I’m writing an article about organizing your AI code with an AI state stack. Examples are in Java. Take a look and make a comment!

Without proper organization, AI code can get messy, even for a simple game: unit state saved in a million ways, endless if-elses and switch-cases. It becomes hard to maintain, and even if it works, it will be “don’t touch” code, where a small change can make it collapse.

A good way to split your AI code is to create an AI state class for every action that a unit can do, like walking, fighting, building, gathering resources, etc. Unit class would be like

public class Unit {
public int x, y, type, health, etc…;
public AIState currentState;

    public update() {
            if (currentState != null) currentState.update();
    }

}

where update() is called by the game engine on every frame or turn. So a Unit can be in one state at a time. AIState base class:

public abstract class AIState {
public Unit unit;
public AIState (Unit u) {
unit=u;
}
public abstract void update();
}

For example walking state:

public class AIGoTo extends AIState {
Target target;
public AIGoTo(Unit u, Target t) {
super(u);
target=t;
}
@Override
public void update() {
// move towards the target on unit update
unit.moveTowards(target);
// when the target is reached, clear AI state
if (u.reached(target)) unit.currentState=null;
}
}

Now if you want a robot Unit to walk somewhere, set

// Unit robot; Target destination;
robot.currentState = new AIGoTo(destination);

The robot will then move towards the destination on unit update as long as it reaches it. You will have AIState’s subclasses for different task, like attacking, retreating, digging, wandering, etc. For example attacking could work like this:

unit.currentState = new AIAttack(unit, enemyUnit);

In AIAttack’s update() you move the unit towards the enemy until it’s close enough to attack. If enemy gets killed or out of reach, set Unit’s currentState null.

This solution is good enough for small games. Instead of having all the AI code in Unit’s update function, it will be split in AIState’s subclasses, including related data, like references to move target or target enemy. But when the game gets more complex, even the AIState’s can bloat. Also, the AI tasks include similar features. For example, when your units do something, often times they have to go somewhere to do it. In AIAttack you have to move towards the target similar way as in AIGoTo.

Some AI engines use state machines to manage this, but for me a stack of AI state’s has been easier solution. Instead of having one AI state at a time, the game world creatures have stack of AI states, topmost being the one to call. Unit class would look like this

public class Unit {
public int x, y, type, health, etc…;
public Stack stateStack;

    public update() {
            if (!stateStack.empty())

stateStack.peek().update(); // update the topmost state
}
}

AIAttack implemented in stack style, update() could look like this:

public class AIAttack extends AIState {
Unit enemy;
public AIAttack (Unit u, Unit e) {
super(u);
enemy=e;
}
@Override
public void update() {
if (unit.isCloseEnoughTo(enemy))
unit.attack(enemy);
else
stateStack.push(new AIGoTo(unit, new Target(enemy)); // ***

            if (enemy.isDead()) 

unit.stateStack.pop();
}
}

In AIGoTo, instead of nullifying the state, the current state would be popped, when the target is reached. Now, when you want a unit to attack another unit, following will happen:

  • call unit.stateStack.clear(); unit.stateStack.push(new AIAttack(unit, enemy));
  • on next update AIAttack.update() is called
  • not close enough? push AIGoTo (***)
  • next update and following updates AIGoTo is called, until enemy is reached
  • finally reached the enemy: pop unit.stateStack in AIGoTo update()
  • next update AIAttack.update() is called. Enemy being reach the unit can attack it.
  • etc…

More complex example could be for example a unit building a wood house:

  • AIBuildHouse: Got wood? No? Chop wood!
    • AIGatherWood: Close to a tree? No? Go to tree!
      • AIGoTo: Go until you reach the tree. Then pop state.
    • AIGatherWood: Close to a tree? Yes? Start chopping!
      • AIChopAction: chop chop chop. Pop state.
    • AIGatherWood: Got wood? Yes? Pop!
  • AIBuildHouse: Got wood? Yes? Build the house!
    • AIBuildWoodHouse: building
  • AIBuildHouse: Done? Good!

I’m not sure if that makes any sense if you weren’t familiar with the idea before. Write a comment or tell about your solutions! There’s a lot of details you have to take into consideration when you implement that kind of a AI state stack, but as this post is quite lengthy already, I think I write about them later :slight_smile:

State machines only work in very very simple situations. See: GOAL and behavior trees.

As already stated, state machines (even ones that use push down automata) are limited. Your example is fairly simplistic and quite frankly not the best.

If people wanted to learn about state machines, there are already properly written articles out there. Like this one.

No offence intended, just call it as I see it.

as usual i have to point to http://www.ai-junkie.com/books/toc_pgaibe.html

very descriptive and practical introduction into FSM and goal-driven AI.

That example in gameprogrammingpatterns is almost the same solution, except programmed in that hairy C++ style.

My solution is simplified version of that one presented in Programming Game AI by Example. Good enough for most cases, and more light-weighted.

No.

It’s explained more clearly and that “hairy C++” style makes no difference. Your version is completely dumbed down, this does not make it simple, it makes it less functional.

No offence but I don’t think your article is well written, formatted or approached correctly at all. Like I said, there are already better written articles on the subject, written by people that have written such things before.

Also coming into a community and instantly posting articles is a bad idea, we don’t know you, you don’t know us. You have no credibility from our perspective and vice versa, therefore anyone criticising your work is going to result in a pointless argument (hopefully you don’t take my replies in a bad way).

[quote]Good enough for most cases, and more light-weighted.
[/quote]
You complain about how messy AI code can get and how important it is to keep it organized, yet you post an example that is “good enough”. Also it’s not light weight, it’s severely lacking functionality.

Ok, it’s not for you then. Some people have find it very useful, though.

Please use the [[icode]code[/icode]] tag to enclose code samples. That helps readability since the code will then be syntax highlighted.