Archived

This topic is now archived and is closed to further replies.

Naaga

NPC communication idea & implementation

Recommended Posts

I''m interested in trying out an idea for more interactive game worlds. I do not have a game idea to go with it; this is just about world interactivity/believability. It centers around simulating communication in NPCs. Here''s a basic rundown. The system has two layers: the information layer and the translation (language) layer. The info layer determines all the information a certain NPC has about the game world. The language layer takes that information and builds the speech of the NPC with it. The info layer I picture as a tree structure. Each node in the tree stores the info available there and the connections it has to other nodes. The nodes could be people, buildings, cities, whatever. One example might look something like this.
                 world
             /           \
          city1          city2
      /       \         /      \
    bldg1    bldg2    bldg3    bldg4
 
Below the last row would be the actual NPCs. So, if bldg1 is the grocery store where a lot of people go every day, it would have access to a lot of data. When an NPC arrives at the building they share the data they have with it, and they look at what the building has and take some info with them. This is kind of a long-winded explanation, and I hope I got the point across. Some obvious problems include speed (that''s a lot of processing just for some NPC lines,) grammar (turning "DRAGON ATTACK TOWN2" into "I heard a dragon is on the loose! How could this happen??" or somesuch,) and information flow (NPC1 heard about a major event, but no one else knows until they go to the store/courthouse/bar/wherever it is they go.) This could also develop into a computation vs. scripting issue. IE, how do the NPCs decide where to go and where to transfer information? Are there any other points I''m missing? Other things I need to cover? This thread is about both fleshing out the system and how to implement it, although the implementation could also get its own thread in General Programming. Anything else I need to describe? Please, comment.

Share this post


Link to post
Share on other sites
The idea is cool, but there are some problems.

First, you have to make sure that the NPCs dosen''t share stuff they don''t want to, or shouldn''t share - like if the NPC''s wife got kidnapped and got told not to tell anyone about it - except the hero of the game, of course, when the NPC feels he deserves it. Or simple stuff such as "the key to my treasure chest is hidden under my pillow".


Secondly - and probably harder.... How is the player supposed to find the NPC he''s looking for, if that NPC (actually almost all NPCs) are out walking errands and talking to other NPCs. In RPGs up to today, NPCs stand in basically the same place during the whole game which makes them easy to find.

In a modern setting, the character could get a cell-phone and thru some interface tell an NPC to "meet me outside Town Hall, now.", but that would in a way be weird too. Plus, in fantasy RPGs - how is the dumb warrior gonna get ahold of someone?

It''s definately a good idea, like I said, but that problem needs to be solved in some really neat way.



"Some obvious problems include (...) grammar"

Actually, I just wrote a program yesterday that randomizes a greeting (the first thing the NPC say when you start talking to him), and there''s no grammar involved at all. Just a simple "if he says this word, then this is a list of the next word he can say."

Here''s some output... I think it''s 30 randomly generated lines:

---------- Run ----------
Hey man! My name is Franz Weber. What''s your''s?
Hey man! My name is Franz Weber, and I live here.
Hi there! Allow me to introduce myself. My name is Franz Weber, and I live here.
Hey, what''s up? Allow me to introduce myself. My name is Franz Weber, and I live here.
Hey, what''s up? My name is Franz Weber. What''s your''s?
Hi there! My name is none of your business, idiot!
Hey, what''s up? Allow me to introduce myself. My name is Franz Weber. What''s your''s?
Hi! My name is Franz Weber. What''s your''s?
Hi, sup? Allow me to introduce myself. My name is Franz Weber. What''s your''s?
Hey there, idiot! Allow me to introduce myself. My name is Franz Weber, and I live here.
Hey there! My name is Franz Weber, and I live here.
Hey there! My name is none of your business, asshole!
Hey man! Allow me to introduce myself. My name is none of your business, bastard!
Hi there! My name is Franz Weber, and I live here.
Hi, sup? Allow me to introduce myself. My name is Franz Weber, and I live here.
Hey man! My name is Franz Weber. What''s your''s?
Hi there! Allow me to introduce myself. My name is Franz Weber, and I live here.
Hey man! Allow me to introduce myself. My name is Franz Weber. What''s your''s?
Hey there! My name is none of your business, asshole!
--
Normal Termination
Output completed (0 sec consumed).


Now, as you can see, some of them sound a bit dumb, but there''s not anything that should be very difficult to implement, really. Most important thing to do now is to have the NPC take different feelings into the calculations.

Btw, that whole program is less than 100 lines of Python code.

Share this post


Link to post
Share on other sites
I''ve been thinking about a similar npc system.
Maybe the best sollution is to have npc dialogues that are shared ( using a random generator as posted by Srekel) and dialogue that is unique. Based on a gossip param you could give each npc a percentage of gossip it lets loose( besides this you could do checks with the players'' skills like empathy, speechcraft etc. to lift the gossip percentage a bit)

There are some practical/technical limitations to this.
For example you, as player, decide to kill person B. Person A is in range and spots you slaying mister B. He stores a gossip entry in his gossip vector: Player killed mr B. and assigns a weight to this gossip. Killing would possibly score a 100% so mr A would go running for a guard. This is possible.
But when the number of npc''s increase the complexity goes through the roof. Mr Aa steals this, mr B dances badly , mr C gets killed by D.

It would be cool to work this npc stuff out. So far my 2 cents.




Look at all the pretty colours!

Share this post


Link to post
Share on other sites
Somewhere I still have the design document I put together about 8 years ago for a similar scheme - in my scheme, information has a secrecy value (how likely it is to propagate) and a value that tracks how widely the information has spread (in a given area) Once the information spreads widely enough, it gets attached to a higher-level node (rather than the common-room of the local inn knowing about it, the entire village knows about it). How widely the information has to spread to get promoted depends on its secrecy level. To actually pick up information, ''foreign'' NPCs need to be in the same place as a local native.

There were other refinements, but it''s been a sufficiently long time since I looked at my design last that I can''t remember it all

Share this post


Link to post
Share on other sites
quote:
Original post by Srekel
Secondly - and probably harder.... How is the player supposed to find the NPC he''s looking for, if that NPC (actually almost all NPCs) are out walking errands and talking to other NPCs.
Maybe when someone tells you to look for certain NPC, they give you a description and tell you where that NPC goes frequently. Then it''s simply a matter of going out and actually searching for that person.
quote:
In RPGs up to today, NPCs stand in basically the same place during the whole game which makes them easy to find.
This is one thing I would love to see disappear.


That speech system you have looks pretty good. I was thinking about using a template design where you just insert specific words into the right slots.

"Have you heard? The [NOUN] [IS/ARE] [VERB]ing!"

Share this post


Link to post
Share on other sites
"Maybe when someone tells you to look for certain NPC, they give you a description and tell you where that NPC goes frequently. Then it's simply a matter of going out and actually searching for that person. "

It's definitely - imo - "simply a matter" if you have to do it every time for each NPC that you wanna get ahold of.

Another very similar way to do it (but less tedious for the player) is if he could ask someone "have you seen this person", and they'd ALWAYS say somethning like "yeah, he's down at the pub/at home/etc", and the NPC [u]would[/u] be there


This is really a problem that we should try to solve. Any more ideas out there?


"That speech system you have looks pretty good. I was thinking about using a template design where you just insert specific words into the right slots.

"Have you heard? The [NOUN] [IS/ARE] [VERB]ing!" "

My system is a lot easier than that. Basically, I have different words that links to a list of other words.

So "Hi" -> "there" / ", sup?" / " what's up?"
"Allow me to introduce myself. " -> "My name is"
"My name is" -> " none of your business" / "Franz Weber"

and so on. Btw, Franz isn't my real name, it's the first character we were introduced to in my first German language book in school

[edited by - Srekel on July 28, 2003 4:03:30 PM]

Share this post


Link to post
Share on other sites
Your system does work better for static information. I want to use dynamic information. I want a system that will allow for dynamic events to happen. So, maybe the king is coming through town. Maybe I would create an Event to add to the EventList and fill it up with something like {king, coming, Friday}. Then I grab the appropriate speech templates.

future, likes king: "The king will be here Friday. I can''t wait to see him!"

past, dislikes king: "That old coot was here Friday. I can''t believe people agree with that guy."

present, indifferent: "Yeah, so the king''s here, but did you see his daughter? Wow, what a hotty!"

It would be a lot of work to make it sound right though.

Share this post


Link to post
Share on other sites
That''s hopefully something that my system will be able to generate when it''s done. The interesting thing is that it doesn''t SEEM to be that difficult!

The engine would just have to take in parameters such as
- What the character thinks and feel about what he/she''s saying
- What should he want to talk about (i.e. the king comes to town, he has a quest he wants taken care of etc.)
- What kind of character it is, anything that might influence the way he talks...
- ...?

"Kaka e gott" - Me
Current project: An RPG with tactical, real-time combat and randomly generated world and dialogue.

Share this post


Link to post
Share on other sites
Right. The hard part is taking account of all that stuff with the right grammar. You need to avoid getting things like "The undeads is back again!" I think this is one of the hard parts with any natural language system.

Another issue is events. I want my information system able to handle dynamically generated events from "a dragon is attacking" to "I was just mugged" to "that new shop around the corner has some really good pie." Hopefully there''s a way to handle all these with the same event structure.

Share this post


Link to post
Share on other sites
Why is it so bad to have to run around looking for an NPC? I''d much prefer it to having all these useless NPC''s just standing around getting in my way and doing nothing important. Let''s face it, by the later parts of the game you''ll probably be able to teleport to whatever town you want, so what''s the big deal?

I''d much rather have npc''s wandering around, maybe getting themselves in trouble every now and then. Maybe one night you try to stay at an inn, but you can''t because it''s full of wandering npc''s. Maybe some wandering npc gets captured by a group of goblins and taken back to their hideout, giving you a side-quest to do that wasn''t pre-planned. Another thing I never understood about old video games was why the hell don''t you ever see people in the wilderness, only in towns or maybe rarely sitting at the entrance to a dungeon? Why are they only in important parts of the game? Why can''t you run across some random guy chopping trees in the woods? And why are there rarely npc''s standing in a shop buying armor when you walk in? Sure, maybe you''re the biggest, buffest, heroes in the world, but does that mean other people don''t need the occasional sword or healing potion?

Sure sometimes realism isn''t fun, but I think if you find the proper balance it could add a lot to a game.

If a squirrel is chasing you, drop your nuts and run.

Share this post


Link to post
Share on other sites
"Why is it so bad to have to run around looking for an NPC?"

Well, I think it would get "irritating".

Imagine returning from Bob''s quest: Take my map here, and find the hidden treasure. bring back the picture of my old goat which is in it.
And when you get back to his house to tell him, he''s not there. So you go to his job. He got fired yesterday. You go to the bar. Someone there says "I heard him say something about going to the woods for I-don''t-know how long.

Sometimes you just need to reask someone "where exactly did you say I could find that treasure chest?" because you forgot. You don''t wanna spend 10 minutes finding someone just for something simple and dumb like that.

Maybe you could have a list of "not dangerous" NPCs, and whenever you checked your map you''d see where they were. Or you''d get a simple arrow on the main "run in town"-screen pointing to the NPC.

I DO want NPCs walking around - but only if there''s a good, easy and fast way to find them.

Share this post


Link to post
Share on other sites
The information flow/dissemination aspect of this has been discussed a lot in the AI forum (I think a few people even posted simple implementations). Search that forum for keywords gossip or rumor.

Share this post


Link to post
Share on other sites
Its no fun having to track down an NPC espically when they all look a like and you only have vague directions. I remeber several times whle playing arcanum when I was suppose to talk to someone and being unable to find them, so I just gave up and moved on.

A player shouldn't be forced to do an extra "quest" after each quest just to find the person who has their reward.

-----------------------------------------------------
Writer, Programer, Cook, I'm a Jack of all Trades
Current Design project
Chaos Factor Design Document



[edited by - TechnoGoth on July 29, 2003 6:47:16 PM]

Share this post


Link to post
Share on other sites
quote:
Original post by TechnoGoth
A player should be forced to do an extra "quest" after each quest just to find the person who has their reward.

I assume you meant to say "shouldn''t"?

Share this post


Link to post
Share on other sites
So why not have a scrying spell you can use to find what town they''re in or near? Or a mystical tower you can use to scry them, or maybe you can pay a gypsy or something to do it for you. Inindo has hundreds of npc''s, and if I remember correctly there''s a way to find out where they are.

Share this post


Link to post
Share on other sites
I don''t want it dependent on magic, because I might use it in a game with no magic. I really don''t see a problem with needing to look for someone. In almost all RPGs to date, each town is a small collection of buildings with very few NPCs to keep track of. While this system would likely need more than that, I don''t see it being a lot more.

Share this post


Link to post
Share on other sites
Why not just limit where NPCs can go to logical places? The blacksmith will either be in his shop, at his house, or at a bar, but you''re not likely to find him hanging around the king''s throne room.

Share this post


Link to post
Share on other sites
it depends on how many NPC''s you have for instance if there 10 in the whole village it is not so bad but if there are 50+ in every village and they can move from village to village. Then its going to be a major chore to find them. The best thing to do would be to have key places that they go. For instance they can always found in their homes at night or at work during the day.

-----------------------------------------------------
Writer, Programer, Cook, I''m a Jack of all Trades
Current Design project
Chaos Factor Design Document

Share this post


Link to post
Share on other sites
i''m attempting something very similar in terms of two-way communications and interpretation of behaviors. the NPCs all share a common vocabulary and information pool, and their specific stats determine how well they use their vocabulary and what specific information they should posses.

90% of the NPCs in the game will be generated randomly and split up into four main groups; strangers, acquaintences, allies & enemies. the player is unknown to strangers and must make an impression in order to be remembered. once a player has made a significant enough impression on a stranger NPC he becomes an acquaintence and is saved in memory. The more acquaintences that a player has the less privacy he is afforded, and the more likely that information pertaining to the player will be spread.

All NPCs react to the events around them in different ways, according to their attributes. Some people will stay and fight, some people will run and hide. The number of NPCs to witness any given event (like a murder) and some type of abstract severity level of that event determines how quickly this information spreads.

One thing that I have been struggling with are secrecy levels of information. I want alot of different cultures and societies, and in some places you simply don''t talk about certain things. In a modern example, you don''t want to be seen walking down the streets of karachi carrying a bible and preaching. you''ll likely get arrested, or maybe shot. if the player breaks a local custom, while not in the presence of allies, then there will likely be some sort of consequences. but secrecy levels are not universal. what is taboo in topeka, kansas is not necessarily taboo in las vegas.

Share this post


Link to post
Share on other sites
Exactly what I''m talking about. I don''t think it''d be a big deal finding npc''s, if the number of them is similar to most old RPG''s I''ve played.

What I think would be neat is if each npc had some sort of schedule, however this schedule wouldn''t necessarily be static. For instance, while walking to work one day, the blacksmith may witness a murder and then have to testify in court or something. Or maybe the wandering merchant gets waylaid by bandits in between towns and ends up wandering lost and naked in the woods, heh. I''d love it if plot events happen not just to the heroes, but to everyone else too, and some events wouldn''t be scripted but just arise out of who happened to be in proximity to who and what their motives at the time were. That''s a game that could truly be different every time you play it.

Share this post


Link to post
Share on other sites
Wow, thanks for that link, Oluseyi. While i''d been thinking in narrow implementation terms, that thread underlies what I''m going for. There''s a lot of thought there that will take some time for me to go through, but I have one thought right off the bat. That thread keeps talking about ''nodes'' for developing the story. I can''t help but wonder if these nodes are really necessary, though. What is the overall purpose behind them? I mean, the nodes are supposed to be generated from the data in the system, right? Instead of taking the time to translate that data into nodes in order to generate new nodes, why not just take the sraight data and generate new data with it? Then it could be fed right back into the system to perpetuate the dynamic changes in the world.

I also like the thought of a single information database instead of small databases for each character. It would eliminate redundancy in the information, and you could just apply filters to find an appropriate subject for any character to talk about. The information could also be used in determining a character''s course of action in the story.

There''re still some things that need to be worked out. We need a system for controlling the spread and availability of information. We need for natural language based on that information. We also need a way to determine the end of the game and to present a satisfying end sequence. Does anyone have some good links on natural language processing?

Share this post


Link to post
Share on other sites
In terms of handling the locations of NPCs at any given time, just apply schedules.

An NPC can have a series of locations they can be found at any given time. If your game has a built in timing mechanism just make sure that the player can ask locals about where the npc can be found. Once you have these locations configured, just have your npc use regular pathfinding techniques to move between them, and give each location in the schedule a tolerance level for general wandering in that local.

This even allows for NPCs moving between towns; assign a "week" system to your clock and allow for more complex schedules. Might be a fair bit of work, but unless an NPC is also a wandering adventurer then the would usually follow *some* kind of pattern like this.

Actually, when I made that statement, I just thought of a way you could use this to implement some really nifty quests; this combined with your knowledge sharing information, you could have time-limited quests to stop "spies" and such.

interesting...

Share this post


Link to post
Share on other sites
quote:
Original post by Naaga
That thread keeps talking about ''nodes'' for developing the story. I can''t help but wonder if these nodes are really necessary, though. What is the overall purpose behind them? I mean, the nodes are supposed to be generated from the data in the system, right?
Not entirely. The nodes encapsulate event data, so by encountering certain conditions in the game they cause the node to be activated/included in the overall story graph/network.

quote:
Instead of taking the time to translate that data into nodes in order to generate new nodes, why not just take the sraight data and generate new data with it? Then it could be fed right back into the system to perpetuate the dynamic changes in the world.
There''s no proven approach that is the "right" way to do it, so give any number of modifications a try.

quote:
Does anyone have some good links on natural language processing?
Natural Language Processing is a rather immature discipline. Despite vast collections of data on linguistics and psychology, getting a computer to create natural-reading text from a collection of disjoint concepts and a context (time, location, witnesses, etc) is still beyond a science. I can''t remember the name of the college text we used, but it''s the "definitive" one. Try a search on Amazon or something.

I''d suggest looking at alternative output mechanisms, though. Using an iconic system that simply spits out the concept characters, leaving translation to language - with appropriate tense correction, conjugation and so forth - to the audience is simpler and is culturally portable.

Share this post


Link to post
Share on other sites
I agree with those that said that wandering NPCs make sense, but could be intensely irritating to track down. It was one (just one) of the really big flaws in the final Might''n''Magic game (9). You''d get a quest, go do it, then spend half an hour clicking on all 100 NPCs wandering around the city. And since they''re wandering, sometimes you''d get the same wrong person several times.

The idea that the NPCs can give info about where others are is good -- the "yeah, I saw X down at the pub". In fact, if you''re using information databases, it would be simple to have a "last seen" grid for all NPCs, indicating time and map location for every pair.

Even better, maybe when you start asking about person X, word gets around. Eventually one of the wandering NPCs will bump into X (or someone they talk to will see X), let X know, and X (of course wanting to know about your quest!) will come running up. You may still have to hunt around, but it would be really cool if the NPCs actually acted on their own.


In regards to NLP: were you asking about the parsing of input from the user, or the construction of sentences from raw data?

If the former, there''s a lot of stuff out there, albeit mostly on the linguistics side rather than computer side. Even the cheapo "eliza" parsers do a tolerable job in simple situations.

If the latter, I haven''t seen much. Most systems tend to use plan-based reasoning and run off of scripts. The research is mostly focused on things like automated phone systems or ticket sales, where there''s a really limited set of questions/responses that everything can be showhorned into.

But you can take some of the ideas from the newer Chomsky-derived parsing systems (government binding, etc) and apply them to the creation of simple sentences. I played with that some -- purely random sentences, but some very complex ones, with interjections, subphrases, and compound phrases.

Your bits of information probably need some context: some are items/people, some are events. You wouldn''t just have { king, coming, Friday } as an unordered set: you''d know subject, verb, object. Then pick one of a few sentence templates and plug it in.

Share this post


Link to post
Share on other sites