Best next step for game AI implementation

Question

I have recently finished a small framework that employs agents governed by a small hierarchical finite state machine, however I have quickly discovered the drawbacks of this approach. Namely the fact that increasing numbers of behaviours call for an exponentially complicated rule-base to govern the switches.

It occurs to me that there is probably a much better way of coding AI, where they have overall goals and can assess new information with regards to this.

I did some research but was a little overwhelmed by the amount of methodologies, and for that matter the lack of information about which techniques are more commonly used and which are best for certain situations.

what would be a good next implementation/methodology for a 3rd / 1st person shooter? such as a neural network or GOAP.

Answer 1

Obviously there is no "one size fits all" approach to game AI, at least not yet. There are a variety of different approaches and usually you choose one that is a good compromise between performance and control.

One increasingly popular approach, at least in shooter-style games is to use behaviour trees. These effectively give the same results as a hierarchical state machine except that instead of trying to control all the different transitions, you basically evaluate each behaviour node in turn until you find one that triggers, meaning that is the current state. The way you organise the tree lets you encode priorities, parallel behaviours, complex selection criteria, etc.

The downside is that they are basically a graphical language for AI rather than a single approach, and everybody codes them up slightly differently. On top of that, due to the naive approach requiring a lot of tree traversal, a lot of people try to optimise them by remembering where they were in the tree last time, adding external triggers to invalidate current states, etc. The majority of talks and papers on behaviour trees seem to be documenting the way that people twist them in unusual ways to get better results, so I'm not convinced that they're all that great.

But lots of people do manage ok with hierarchical state machines. As long as you have a clearly delineated hierarchy (eg. game objective/strategy/tactics/navigation/steering) it's not impractical. The hierarchical nature is meant to prevent the exponential growth, so you might want to reconsider your transitions.

In fact you can get a long way with a trivial set of conditions. eg. If healthy and no enemies nearby, explore. If healthy and enemies nearby, attack. If unhealthy and enemies nearby, flee. If unhealthy and enemies not nearby, apply health pack. 4 basic states, no explicit transitions, and easy to tweak or personalise by adjusting the definitions of healthy and nearby.

Nobody (or next to nobody) uses neural networks, by the way. They're not a very effective tool, except for learning basic AI concepts.

Answer 2

As you said, there are tons of approaches. However since you want a 3rd or 1st person shooter, I can give some specific pointers.
When doing my dipoloma thesis, I ran into a few projects:

• Jazzbot, for the Nexuiz game
• Pogamut, a similar project based on Unreal Tournament 2004 (I liked this one better).

These are frameworks for 1st person shooter bot programming. They come with academic publications and tools, so you can study the algorithms and principles used, or try out your own approaches.

Answer 3

A common step up from state machines is a utility framework. Have each state calculate a score that is its desire to run / applicability. Each time the entity thinks, he reevaluates if he is in the highest utility state, and if not, transitions to it. This way, all your transitions are implicitly defined in your utility functions.

A simple example would be a ShootEnemy state has high priority when in range and able to fire. A MoveTowardEnemy state has high priority when far away. Together, they can manage to get to the enemy and shoot him without having to know about each other.