[MUD-Dev] TECH: Complex NPCs

Sasha Hart harts at reed.edu
Tue Apr 2 23:17:13 New Zealand Daylight Time 2002

[Sean Kelly]

> A Sims person, then, just needs to evaluate which need is greatest
> and then follow the slope to that satisfaction object.  The only
> exception is the bed, whose slope extends across the entire Sims
> world, since the need for sleep overrides everything.

Maybe someone who knows more about this kind of thing can chip in,
but this basic hill-climbing principle is quite powerful as long as
the height map (or vectors) are being maintained sensibly.

Staddon has a forage model which is based on it. He is probably not
quite right; the cool thing is the power of a simple method.

Anyway, his algorithm (which may be a knockoff of stuff from someone
who is not a psychologist) basically does only two things: it
hillclimbs, and it maintains the "height" map. The first part is
relatively easy: we have a mess of doubly-linked nodes. Each one has
a 0 to 1 value. Every tick we look around at all of the surrounding
nodes, including the one we're in, and move to the one with the
highest value.

In the second part, you "blur" the heightmap. You can manage the
scheduling and maintenance of this blur in various ways, which has a
lot of impact on the behavior and effectiveness of the model.  The
influence of high or low values flows across the links, and because
of the repetition of this blur, gradually decays into background
noise more or less exponentially (vaguely like what people who study
memory keep finding).

When the critter finds food, it sets the value of the current node
to 1.  The effect over time is gradually broader and broader
broadcast of the location. Whenever the critter doesn't find food,
it sets the value of the current node to 0. The combined effect
looks a lot like the forages seen in ants, badgers, and (with tweaks
to the blur) macaques. In brief, it wanders around until it finds
something, then checks out the area, and after a while clears all of
those nodes, "loses interest" and moves on to the next thing.

If you run it a bunch of times and keep the "map" it forms, it
solves low-grade versions of the traveling salesman problem.

Obvious downsides: if you have one of these for each critter it
could be a substantial memory investment. It is probably not the
fastest or best algorithm for, say, pathfinding. If it were not for
the background noise and variation which springs up, it would get
caught in local minima all the time. Your AI friends wouldn't
appreciate this feat :)


it doesn't require you to think through optimal solutions. it
doesn't require you to think of how animals think, or even to know
how they think at all, nor to maintain very far advanced private
representations of the world, nor to engage with full on planning
problems etc.  it just looks surprisingly like a real forage.

the critter can maintain, by breaking links, a map of connectivity
between regions and run most if not all of the classic learning
mazes somewhat effectively and very much like a maze rat does. You
can have the links laid out in any spatial arrangement you like (of
course it is irresistible to see the similarity between this spatial
model and classic linked MUD rooms.)

MUD-Dev mailing list
MUD-Dev at kanga.nu

More information about the MUD-Dev mailing list