Re: [Algorithms] Ideas for an AI scheme

[Ryan J. <rya...@gm...>]

Given that you mention building a "composite behavior" from the tree, I'm
assuming you are looking to build a concurrent hierarchical finite state
machine rather than a standard HFSM. In a concurrent HFSM, a node in the
tree might have multiple active child states running at once.

I've used concurrent HFSMs on multiple titles in the past. The heaviest use
of the system was from a third person shooter. The ability to reuse and
combine small sub-states to create more complicated behavior proved very
useful. For example, different behaviors of moving, aiming, and reloading
could all be built separately and then mixed and matched based on higher
level transitions (e.g. on a vehicle, hiding in cover, fighting from cover).
It was also fairly easy to append new concurrent behaviors onto an agent.

There were two main downsides to the system that I recall. The first was
related to the complexity of it all. In a non-concurrent system, you are
only in a single branch at any given time. This makes it much easier to
visualize what is happening in the agent as well as debug how you got to a
given state. It is also a bit easier to grasp the behavior design in a
non-concurrent system. By the end we had ambient animals, enemies, scripted
allies, vehicles, bosses, and so on all able to start mixing and matching
these behavior building blocks. It wasn't that fun to digest.

The second issue was related to different concurrent behaviors fighting for
control of a similar feature (e.g. movement). When new features are added,
it is easy for conflicts to crop up which require messing with the hierarchy
a bunch to work out. To alleviate this nightmare, we ended up supporting
multiple "requests" to different systems. For example, if one behavior was
telling an agent to move towards cover and then another behavior was telling
him to evade an incoming vehicle, the commands from the vehicle evasion
could be set as a higher priority. I don't think this is the best solution,
but it was much more successful in creating a stable game on schedule than
trying to constantly rework the hierarchy.

As for editing the state machines, it was all in the custom scripting
language used by the rest of the game. Having a graphical interface would
have been great, but the priority of it never worked its way high enough up
the todo list. The states were basically just data structures (similar to
the XML approach you suggest but probably much less verbose with syntax). At
least 99% of the transitions and states were written in C++ for performance
reasons although we did support scripted ones.
If you are doing a smaller indie game, I think it would be fine to text edit
stuff and the system as a whole should work. As for doing a very large scale
big budget game, I'd definitely weigh all your options. I've since become a
fan of systems where the transitions were automatically generated for lower
level AI behavior - something like a goal/action approach.
 - Ryan