Goal oriented NPCs

5 views
Skip to first unread message

Kevin Ausman

unread,
Jun 21, 2001, 5:22:29 PM6/21/01
to
I'm a relatively new IF coder (although I have a great deal of prior
programming experience), and was very intrigued by the Reactive Agent
Planner for TADS by Nate Cull
(http://www.ifarchive.org/indexes/if-archiveXprogrammingXtadsXexamples.html)
as a method for introducing goal-oriented decision-making for NPCs. I can see
that there are some things that need to be fixed with it, certainly (e.g.
mykey was miscoded as key, and NPCs can take objects from other NPCs), but
upon first glance and some practice coding, it seems highly promising to me.
Yet, I was suprised to discover that when I looked through the usenet archives
for this and other IF newsgroups, I saw pretty much no references to the this
library. Does it not work in real-game situations? Are there better approaches
out there?

Thanks in advance!

Kevin

Sam Thursfield

unread,
Jun 24, 2001, 10:07:18 AM6/24/01
to
There's also a version for Inform, at (I think)
http://ftp.gmd.de/if-archive/infocom/compilers/inform6/library/contributions/rap11.zip
or something.

I thought it was a neat toy, but I didn't really understand how it
worked, and it was kind of simple to do anything worth putting in a
real game with it.

If Nate (or someone else) did some more work on it and gave more
explanation on how it worked I might...

golrien

Guy Hasson

unread,
Jun 25, 2001, 9:11:49 AM6/25/01
to
If you're looking for goal-oriented NPCs, check out the algorithms for
creating true NPC interaction here: http://guyhasson.20m.com/.

Drek T. Monger

unread,
Jun 26, 2001, 11:35:33 PM6/26/01
to
guyh...@hotmail.com (Guy Hasson) wrote in message news:<30b7991a.01062...@posting.google.com>...

> If you're looking for goal-oriented NPCs, check out the algorithms for
> creating true NPC interaction here: http://guyhasson.20m.com/.

Er,

A noble effort, but ultimatly it's just a Mad-Lib that picks different
sentences depending upon few simple qualities. HAB, in contrast,
chooses actions in an attempt to reach an end goal.

In addition, any character growth is entirly pre-programmed. To use
an example for your webpage, there's no chance of the wife convincing
her mother-in-law that her husband is an ok guy.

To create "true" NPC interaction

1: A "Higher Soul" that determines what the NPC's purpose is.

2: A recursive and adaptive algorithm for picking realistic goals (and
subgoals) in the game world that will further the "Higher Soul's"
ultimate quest

3: An algorithm that develops and tries plans for achieving multiple
goals at once, without seeming schizo. Many possible plans are
discarded, determined by the evolving personality of the NPC and
changing circumstances in the world.

4: A knowledge set. The NPC's plans should be based on it's current
set of knowledge. The NPC should be able include information
gathering as a subgoal (or step in a plan). The knowledge set should
be capable of being in error. Actions are a part of the knowledge
set. For example, a dog knows how to bark, can be taught to roll
over, and learn where his fooddish is.

The knowledge set should be somewhat nueral net-ish; some knowledge
should be associated to other pieces of knowledge, prompting a set of
actions in certain situations.

5: Finally, an implementation of actions. What effect do the actions
have both in the game world and on the screen?

I suggest we all try to start simple. A semi-realistic kitten,
parrot, robobuddy or goblin might not make for gripping drama--but
then I don't think that AI yet has the tools to create gripping drama.
Even Galatea (which comes close to gripping) is ultimately a hollow
sentence picker.

One the biggest problems is the pipe of information between player and
NPC. With simplier NPCs, the pipe is narrow in real life and so is
easier to model in game.

Dennis G. Jerz

unread,
Jun 27, 2001, 12:57:09 AM6/27/01
to
"Drek T. Monger" <drekm...@hotmail.com> wrote in message
news:177bc553.01062...@posting.google.c

> Even Galatea (which comes close to gripping) is ultimately a hollow
> sentence picker.

But 1) the sentences are picked in response to player actions, not randomly
(although chance may paly a role that isn't immediatly obvious); and 2) the
character Galatea incorporates the limitations of the IF world -- when she
runs out of responses to a prompt, the PC "notices", and the game makes that
disappointment part of the game.

This is a matter of clever writing, not a great leap in AI.

--
Dennis G. Jerz, Ph.D.; (715)836-2431
Dept. of English; U Wisc.-Eau Claire
419 Hibbard, Eau Claire, WI 54702
------------------------------------
Literacy Weblog: www.uwec.edu/jerzdg


Guy Hasson

unread,
Jun 27, 2001, 8:41:54 AM6/27/01
to
drekm...@hotmail.com (Drek T. Monger) wrote in message

> > If you're looking for goal-oriented NPCs, check out the algorithms for
> > creating true NPC interaction here: http://guyhasson.20m.com/.
>
> Er,
>
> A noble effort, but ultimatly it's just a Mad-Lib that picks different
> sentences depending upon few simple qualities.

I think there's some confusion here. My idea is not about creating
AI. It's not about creating neural nets. It is about creating true
to life NPC *interaction*. Through interaction you get believable and
full NPCs. Real people, characters, NPCs, don't live on their own.
You understand things about people by seeing how the react to their
environment or to different people, or by how the act on these people.
Believable characters are formed through *interaction*.

There was no attempt to say that my idea is AI. In fact, I said that
it isn't AI, it just gives the illusion of AI. The characters can't
think for themselves.

The interaction, though, is true-to-life, true-to-the-moment (even as
each moment offers something else, and as each moment comes from and
differs from the moment that came before), reveals things about the
characters, and advances the plot. I'll explain that in a minute.

As to the 'mad-lib' and sentence-throwing - I think you miss the
point. The point, again, is NOT creating characters, but INTERACTION:
meaning, that the characters will respond accordingly, taking into
account the action performed on them by the other NPC, the mood of the
other NPC, their own mood, the other NPC's goal, their own goal, and
so on. If the responding NPC's mood is different, is s/he was
recently stepped on or is satisfied with him/herself the reaction (and
the action that follows) will be different and it will FIT. That's not
sentence-throwing, that's a rare agility.

And all this, without the writer needing to sit down and write a
dialogue for each and every possibility! The writer wrote CHARACTERS
which are defined through their moods, the actions performed on them,
their goals, their personalities, and the way they act and react to
each of the other characters. (Also, the sentences said are never just
'information' or just 'sentences', they are ACTIONS, they are an
attempt to influence - and sometimes they are REACTIONS - an effect of
actions performed. Each one of these either advances the purpose of
the player or delays it.)

In addition, I think that your desire to achieve AI, characters that
would be independent no matter what game they're thrown into, takes
away from the art aspect of I-F. You need specific NPCs in specific
games in specific situations. Throwing three random AI-true-to-life
'characters' together to see what happens isn't I-F and isn't art.

As to goals: Obviously, each NPC must have a goal, or s/he would have
no reason to perform any action! (I mention that there.) Having the
computer 'choose' a goal seems arbitrary to me. The game should be
what the writer needs it to be!

But I think I hear a bigger misunderstanding here between the lines.
With interaction-based games, the goal of the player is
people-related. You have to get something out of the NPCs. (Getting
one thing can then lead you to wanting to get soemthing else or to
another place with other NPCs or to getting a piece of information -
the sky's the limit.) *Interaction* between NPCs constantly leads you
either closer to your goals or away from them. Thus the tension of
every scene (and even every move) is formed - anything you do either
gets you closer to achieving your goal or farther away from it. This
is a point I think not many people get yet, because the idea is so
different from what we're used to in I-F games. (This, by the way, in
answer to your question about actions, is exactly the purpose of
actions.)

Obviously, it doesn't have to be just one puzzle or trying to get just
one thing out of one NPC. But one step at a time. To get X you need
to get Y. To get Y you need to get Z. And so on.

Remember: Words are never just words. They must never be only
information (or, worse, idle words with no information). Words
perform actions. Words - all words - try to achieve a purpose.

Guy

Drek T. Monger

unread,
Jun 27, 2001, 10:25:20 PM6/27/01
to
guyh...@hotmail.com (Guy Hasson) wrote in message news:<30b7991a.01062...@posting.google.com>...
> drekm...@hotmail.com (Drek T. Monger) wrote in message

>Throwing three random AI-true-to-life


> 'characters' together to see what happens isn't I-F and isn't art.

The characters would be neither random nor true-to-life.

There is an art to creating characters, further an art to creating
characters that will interact in intresting ways both with each other
and the PC. The author is responsible for 100% of the character's
existance: how is it not "art"?

I submit that a great deal of fiction is written not by the author but
rather the author's characters.

> Having the
> computer 'choose' a goal seems arbitrary to me. The game should be
> what the writer needs it to be!

The goals and possiblities are all ultimately generated by the author
(or at very least selected by the author).

The idea of allowing the computer controlled NPCs to choose their own
subgoals creates greater depths by allowing for changes in the game
world, and changes in the NPC (ie, character growth).

> That's not
> sentence-throwing, that's a rare agility.

Sorry, it's sentence-throwing.

Until AI catches up with my dreams, sentence-throwing is required at
some level. Computers still can't generate (or parse) believable
natural sentences. All modern NPCs have to be sentence throwers at
some level.

Galatea is a sentence thrower with some clever rules and clever
writing.

RAP is a sentence thrower with goal seeking rules.

Your system is a sentence thrower with some very basic rules. But,
those basic rules may chunk in the right game and produce a superior
experience...I dunno.

I'm putting my money on the evolution of RAP, although I'm positive
that emshort and/or her cult will create some intresting sentence
throwers in the interm.

> This
> is a point I think not many people get yet, because the idea is so
> different from what we're used to in I-F games. (This, by the way, in
> answer to your question about actions, is exactly the purpose of
> actions.)

Your next thought betrays you.

>
> Obviously, it doesn't have to be just one puzzle or trying to get just
> one thing out of one NPC. But one step at a time. To get X you need
> to get Y. To get Y you need to get Z. And so on.

You are still thinking in terms of puzzles. True interaction is
hopefully not a puzzle for you. When I'm talking to someone, I'm
usually not thinking, "Hmmm, what magical items can I squeeze out of
this dude?"

How can I set up characters, setting, and a bit of plot and allow
someone to roam about the enviroment doing anything they want while
maintaining the integrity and believablity of of the enviroment?

That's what I find so noble about Galatea. The effort was made to
create a story that the player helped to write. There was no "right
answer" in Galatea or set path: just possiblities and an impressive
collection of end-game fates.

Galatea can't do much to direct her own fate--either in the game or in
the code. That's what I want to change. I want NPCs to step off
their predetemined paths, their pedastals, reach out and try to shape
the world around them.

If the PC decides to ignore the plot threads I've set up and create
his own adventure, the world should react believably. The plot
threads should be character driven: they arrive through the actions
the NPCs take to achieve their own goals. The PC is just another
character, able to set up "plot threads" and dabble in the "plot
threads" of others.

These are lofty goals that I doubt basic simple rules (or even clever
simple rules) will ever attain. The most important milestone is a
collection of NPCs that (to a degree) think for themselves.

Kevin Ausman

unread,
Jun 28, 2001, 3:55:09 PM6/28/01
to
guyh...@hotmail.com (Guy Hasson) wrote in message news:<30b7991a.01062...@posting.google.com>...
> If you're looking for goal-oriented NPCs, check out the algorithms for
> creating true NPC interaction here: http://guyhasson.20m.com/.

Yeah, I'd already glanced at that. That doesn't seem to be so much a
goal-oriented NPC scheme as a conversation/mood simulator. Fine for
its particular niche (I imagine it might work for a costume-drama
style offering), but not quite what I'm personally interested in.

For example, I could imagine RAP working well for a criminal
investigation style game, where the perpetrator has particular rules
about committing crimes (e.g. only when there aren't witnesses),
hiding evidence, avoiding capture, etc. With this kind of scheme, the
perp could do all of these things in a non-hard-coded, rudimentally
responsive way as the player character tries to figure out what is
going on and catch him.

Anyway, I'd like to thank all of you for your responses!

Drek T. Monger

unread,
Jun 28, 2001, 9:50:28 PM6/28/01
to
kdau...@yahoo.com (Kevin Ausman) wrote in message news:<e20c0667.01062...@posting.google.com>...

> For example, I could imagine RAP working well for a criminal
> investigation style game, where the perpetrator has particular rules
> about committing crimes (e.g. only when there aren't witnesses),
> hiding evidence, avoiding capture, etc. With this kind of scheme, the
> perp could do all of these things in a non-hard-coded, rudimentally
> responsive way as the player character tries to figure out what is
> going on and catch him.

It would be really intresting if the perp and MO where choosen
randomdly from a list of possibilites at the start of the game. Each
NPC would have some signiture clues that they ditch at the crime scene
for the PC detective to find.

In addition, it would be cool to be able to ask NPCs, "Where were you
during turn 43?" or even "Where was NPC #3 during turn 43?" Certain
NPCs might cover for the criminal if they have a relationship or
implicate an innocent NPC if they hold a grudge. It would be up to
the player to sort out the relationships between the NPCs and
determine who was lying.

Sounds really cool. No idea how to code it...

Anyone have any ideas?

Andrew MacKinnon

unread,
Jun 29, 2001, 9:19:03 AM6/29/01
to
"Drek T. Monger" wrote:

More likely "Where was Joe at 8 o'clock on Thursday?"

--
Andrew MacKinnon
andrew_mac...@yahoo.com
http://www.geocities.com/andrew_mackinnon_2000/

Kevin Ausman

unread,
Jun 29, 2001, 11:15:44 AM6/29/01
to
drekm...@hotmail.com (Drek T. Monger) wrote in message news:<177bc553.01062...@posting.google.com>...

> It would be really intresting if the perp and MO where choosen
> randomdly from a list of possibilites at the start of the game. Each
> NPC would have some signiture clues that they ditch at the crime scene
> for the PC detective to find.
>
> In addition, it would be cool to be able to ask NPCs, "Where were you
> during turn 43?" or even "Where was NPC #3 during turn 43?" Certain
> NPCs might cover for the criminal if they have a relationship or
> implicate an innocent NPC if they hold a grudge. It would be up to
> the player to sort out the relationships between the NPCs and
> determine who was lying.
>
> Sounds really cool. No idea how to code it...
>
> Anyone have any ideas?

That's precisely the kind of thing I had in mind. For this to really
work, I imagine you would need to have each actor have a memory. The
easiest way to start off figuring out how to code this, I think, would
be to start with a simple kind of memory, perhaps of object/actor
location. The current RAP uses a preprocessing step to generate a map
to help with the actors navigating the game. You could set up a
similar preprocessing step that scans the code for objects/actors and
sets up a memory in each memory-enabled-actor for where each was last
seen and when it was last seen there (maybe only for moveable objects
to cut down on memory requirements; the default would be no knowledge,
but this could be overridden for particular characters/memories at
initialization time). Then, each turn, these memories would get
updated based on actor/player/object movement into actors' spheres of
observation. Once the kinks in this are worked out, you can add other
kinds of memories (concepts, etc). You obviously have to have ways to
querry the actors for this information. Once that is set up, it seems
pretty straightforward to set up a new kind of RAP goal of determining
information; these actors can either find out where something/someone
is by searching themselves, or asking other actors that might have
seen it.

Incidentally, the rudamentary memory I describe above would help
improve the basic RAP by keeping each actor from having omniscience
about the location of keys, etc.

Now, if only I had the time to tackle something like this. Sigh.

Sean T Barrett

unread,
Jun 29, 2001, 12:00:46 PM6/29/01
to
Kevin Ausman <kdau...@yahoo.com> wrote:
>For example, I could imagine RAP working well for a criminal
>investigation style game, where the perpetrator has particular rules
>about committing crimes (e.g. only when there aren't witnesses),
>hiding evidence, avoiding capture, etc. With this kind of scheme, the
>perp could do all of these things in a non-hard-coded, rudimentally
>responsive way as the player character tries to figure out what is
>going on and catch him.

Since you didn't seem to get any real responses on the "does it
not work in real game situations" question, I'll offer you a
reasonably well-considered guess: "no, it does not". Now, I've
never actually used it (or its Inform equvialent), but I've thought
a lot about using that sort of thing, and I've worked on commercial
action/adventurers that used *incredibly simple* goal-driven AIs,
but incredibly minimal planning.

Here are the obvious sorts of problems with using something like
RAP. They are likely outcomes, not things that are doomed to be
true, though.

You'll end up with a toy, not a game. There's no
guarantee of fun--you don't want AIs that are smart, you want
AIs that are fun to interact with. Without a pretty huge effort
into a "gamemaster AI", all of these clever NPC actions may be
invisible to the player, and result in a scenario that the player
can't win due to lack of information--information that you would
normally carefully hand-construct into the system. Without a
very clever "storywriter AI", the story will be weaker than that
of hand-designed IF.

None of those things are fatal--you may well be able to make
a fun toy, and some people are more interested in immersively
exploring a believable world than experiencing the best possible
story.

But I think the medium of text is going to be biased to story; you're
far more likely to see this stuff done in 3d first-person games
(although even that seems unlikely due to the "toy vs. game",
the "fun", and the "lack of information" problems). In point
of fact, this is one of the things I've considered trying
to pursue--but only in the 3d first-person arena, not in my IF.

SeanB

Drek T. Monger

unread,
Jun 30, 2001, 3:19:27 AM6/30/01
to
> Incidentally, the rudamentary memory I describe above would help
> improve the basic RAP by keeping each actor from having omniscience
> about the location of keys, etc.
>
I've thought a bit about about your little murder mystery with goal
seeking NPCs.

One nice bit of data to store in the "mind" of the NPCs might be who
told the NPC the information contained in his head, with mutltiple
versions of the facts contained in each NPC. That way, if an NPC is
lying or otherwise feeds misinformation to another NPC, the target has
a chance of figuring out who a liar is.

For simplicity, I'm imagining a matrix of facts. To borrow from Clue,
each NPC has stored a list of locations, people, and murder weapons.
For each location at each time for each information source (including
the PC) the NPCs store the relationships between the objects:

For Ms. White:
3:00 AM The Library: The gun was in the room. The body was in the
room. Ms. White was in the room. I saw this with my own eyes. Flag:
Lie_about_Murder

3:00 AM The Foyer: The gun was in the room. The Player-Detective
told me this. Flag: Hearsay.

3:00 AM The Foyer: The Gun was in the Foyer. Ms. Red was in the
Foyer. Ms. Red told me this. Flag: Conspiracy_Lie

3:00 AM The Foyer: Mr. Blue was in the Foyer. The Candlestick was in
the Foyer. The Secret Video Tape told me this.

In Inform's object tree, each of these facts would be an object (Fact)
as a child of the NPC. Or, to conserve object space, each location or
time would be it's own fact object.

> Now, if only I had the time to tackle something like this. Sigh.

I think I'm going to start simple. Instead of using RAP itself, I'm
going to use a simplier semi-RAP that I might code one of these days.

In my semi-RAPish design, the possible emotional states, possible
actions & plans, relations between characters, and possessed knowledge
will all be stored as children objects to the NPC. A property in the
NPC's object points to (for example) the current emotional state.

To add knowledge to a character you move an object of class
"Knowledge" to be a child of the character. You can do this the same
way you move any object into a location, either via hard coding or
during execution. For example, a video tape (when played in a VCR)
contains a bunch of knowledge objects that are copied and moved to
whomever views the tape.

Another method chooses which of the emotional
states/actions/plans/goals to select for the NPC each turn. The
action/plan objects themselves contain a "method" called execute,
which is run with a parameter of the NPC itself. The actions objects
change the world and print out text messages. For actions more
character specific than opening a door or moving south (like talking)
each will have to be implemented seperatly for each NPC...otherwise
they can be reused.

This means each action is a class derived from the Action class,
except in the character specific cases.

Each type of information stored in the NPC's mind has to be a class
derived from the Information class, so that it can be easily
reproduced. For example, there could be a class "What's Was in X
Location at Y Time". The Informaiton class would include a property
for the source of the information. That way, multiple copies of the
the same type of fact can be kept, the one that the NPC believes would
be determined by relationships between the NPCs and possible sources
of information.

Relationships could also be stored as child Information objects, one
for each person or even thing (if someone has a special relationship
with an inanimate, like Ms. White hates Mr. White's collection of
porn). If Ms. White says to Ms. Red "I hate my husband's porn
collection.", Ms. Red gets a copy of this relationship object, with
White stamped as the source. Red can later tell the PC: "Ms. White
says that she hates Mr. White's porn collection.". If Mr. White turns
up dead, this factiod is suddenly important (at very least as a red
herring).

Which brings up another idea, an information object that indicates
that someone has been asking questions or talking smack about someone
else. When the PC asks Ms. Red about Ms. White, Red can then tell Ms.
White that the PC is being noisy, perhaps lowering Ms. White's
apprisal of the PC and creating a situation where the complex nature
of the interactions can be exposed to the player:

"Dectective, Ms. Red tells me that you've been asking questions about
me," says Ms. White.

The player's real life jaw goes slack.


Imform's limits might present some difficulties if the Information
class if implimented in it's ideal form: I will probably have to do
something marginally clever to get it to work the way I want it to.

All of the above is meant to make it easier to code complex NPCs.
I'll know for certain in about a week. Probably next Saturday I'll
post a link to some working Inform source (although it won't be a
murder mystery).

Er, maybe.

-dm

Reply all
Reply to author
Forward
0 new messages