Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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.

share|improve this question
2  
What are the goals of the A.I.? It's pretty hard to figure out an A.I. implementation without a goal. –  bummzack Dec 19 '11 at 12:58
    
the goal is to kill the other agents. –  Asher Einhorn Dec 19 '11 at 14:33
    
In games, players like their AI opponents to behave consistently, complex solutions like a network may be fancy from a tech perspective but may make the AI unpredictable (in a bad way) for a player pitted against it. There's a reason many game AIs boil down to a finite or hierarchical state machine. –  chaosTechnician Dec 19 '11 at 20:00
add comment

3 Answers 3

up vote 8 down vote accepted

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.

share|improve this answer
    
+1 for Behaviour Trees. So simple, but they're a great level of abstraction. Reusability is awesome, and you can always start simple and make it more complex (selectors with priority functions etc.). –  Michael Dec 19 '11 at 15:18
1  
The trivial set of conditions can highly benefit from fuzzy logic. –  Aleks Dec 19 '11 at 19:13
1  
That wouldn't be much use without applying fuzzy logic throughout the whole system because ultimately you'd still only get the same few discrete values out. The difference between 'very healthy' and 'averagely healthy' is not very important if the possible outcomes are a binary choice of fight or not-fight - may as well have an explicit threshold. –  Kylotan Dec 19 '11 at 22:42
    
I didn't realise people actually still used HFSM's. pretty cool. –  Asher Einhorn Dec 20 '11 at 15:50
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.