[MUD-Dev] Re: Stack-Based NPC AI

[Par Winzell <zell#alyx,com>]

Richard Woolcock wrote:
> The only advantage a stack-based system has over a state-based
> system is that the former method allows mobs to 'remember'
> situations they were previously doing and go back to them at a
> later point - but for animal-level intelligence, I don't think
> that would be necessary.

I don't see the stack-based system so much as alternative to a state-based one
as extending it. Many years ago I did write a system such as what Eli describes,
for an LPMud. It worked quite well, and I was able to use it to allow our
"mascot" NPC to solve the simplest game quest.

For this, the stack is very convenient. Even so, this simple mascot grew quite
hairy when all possible permutations of events had to be taken into account.
It's very necessary to be able to do priority interrupts, like entering a brief
"panic heal" state during combat.

In a flat state machine, when such an urge is satisfied, all of the NPC's
current goals in life must essentially be reevaluated. The transitions then grow
to be very complex functions.

On the other hand, there is the danger of relying too heavily on the stack and
this can cause ludicrous behaviour. If several pushes occur, like:

 - walking down the road state [encounter monster]
 - combat state [run low on hp]
 - healing state [realize we have no gold]
 - walk aimlessly looking for trash to sell state [encounter monster]
...

(and this is what my mascot did) then by the time everything has popped down to
the basic level, we've found money, healed, and bested the beasts, an hour might
have passed and we've mostly likely criss-crossed the world several times. The
same aspect of stacking tasks that makes it easy to define behaviour in makes
that same behaviour look very silly. Infact, in my code I had to include a way
for the behaviour code itself to shortcut and wipe out the stack - essentially
throwing an exception, needing to skip up several call layers. I believe the
stack is useful but must be used with discipline.

The guys at "The Motion Factory" sell a product which includes a behaviour
programming module, consisting of a scripting language, an API to their
motion-control library (they work with 3D actors), and "Hierarchical Finite
State Machines". I have only an intuitive understand of what HFSM's are, but it
seems likely they could be help reduce the complexity growth of FSM's, and
perhaps model behaviour better than the stack, as well?
Has somebody on this list used them?

A small blurb can be found at 

        http://www.motion-factory.com/products/features_programming.html

for the interested.

Pär