Archived

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

Practical solutions to the 'Dumb NPC' problem

This topic is 5028 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Ok, we all see plenty of people post on here about how NPCs are stupid in many games. We also see a subset of those people say that developers are stupid for making them that way, but in fact it''s very hard to create computer algorithms that can simulate millions of years of evolution, thousands of years of cultural development, and a decade or two of personal learning; the 3 main sources of information that allow real humans to act they way they do. So I''d like to have some intelligent discussion on how to get around this problem, based on practical and implementable building blocks, rather than the usual pie-in-the-sky discussion. To start, I''ll highlight what I think are some of the symptoms of a ''dumb NPC'', in the hope that removing enough of the symptoms will allow a player to pretend the NPC is intelligent. Oblivious to danger. Ever played an RPG where, for some reason, a monster has strayed close to town, and is hacking lumps out of you while local farmers mill around as if this is normal and not a threat? I have. ''The autocue''. NPCs in many games have scripted lines to deliver hints, plot development, and so on. Sadly, they often repeat the exact same line each time you speak to them, and worse still, 100 different people might say the same thing, with a slight change to the subject matter. How can you believe someone is real when what they say is so obviously scripted? Amnesia. This follows from the last point. I hate it when NPCs forget you already talked to them. Real-world people remember who they spoke to - within reason - and adapt their conversation accordingly. They may also adapt their behaviour. However many NPCs don''t care if they already argued with you, or if you shot them before leaving the area, or if you were the one who liberated their town on your last quest. Do they have no lives? I''m currently playing Might and Magic 6 where I see peasants happily marching around at 3am. In all fairness, M+M6 doesn''t have any indoors areas where they would go, but to see them out and about at that time just drives home how fake the settlement is. Real people have families, jobs, hobbies, and schedules. They don''t walk around randomly 24/7/365. Ok, that''s 4 symptoms. Doubtless there are others. Now here are my suggestions for starting to fix the above. Being oblivious to danger should be simple to fix. Most non-player characters in the game will be flagged as either aggressive or peaceful, and peaceful characters should fear aggressive characters of a similar or higher strength level. The action to take to resolve a ''fear'' state should be to run away, which is a simple reverse-pathfinding algorithm. Additionally, aggressive monsters shouldn''t only attack players; they should attack whatever is a valid target, which is probably any other character of a lower strength level than themselves. If you don''t want your key NPCs getting killed this way, flag them as important and have death just knock them unconscious for a bit. The autocue problem is a little harder. Obviously the important lines have to be written as you probably want your best writer to make every word count. But if you have any sort of generic text, it might be worth creating a basic Backus-Naur Form grammar that can easily generate a wide variety of potential sentences. An approach that goes the other way might be to reduce conversation to being symbolic, so that deficiencies in the language are never shown. Amnesia is easy to treat if you give each NPC a few flags to mark key events with. eg. It''s important to set aside a flag so that an NPC can greet you differently the second and subsequent times they see you. This is a useful guide to any player who is trying to make sure they''ve talked to someone before. Also have the NPC check the player''s achievements list. Don''t talk about the goblins at the keep if the player completed the "eradicate all goblins in the keep" quest already, or at least thank the player. NPCs should also remember if you injured them, and either be aggressive towards you or at least be less positive in their communication. It only requires 1 bit of storage to remember whether you''ve hurt a given NPC or not, and not much more to store a little angry message for that NPC to show you when you next talk to them. Giving NPCs lives and a schedule is not quite as straightforward. But it''s perfectly possible, and was done with 10 year old technology too, in games like Ultima 7. A starting point is to ensure your game has a sense of time. Then, have your NPCs maintain a list of what they''re doing at any given time, and where they''re doing it. This reduces the problem down to a basic pathfinding issue to get from place to place, and maybe 10-30 different scripts for various types of activity such as sleeping, wandering, drinking in the tavern, enjoying archery practice, and so on. Have your NPC check roughly every hour or so whether they''re in the right place or not. If not, set them off walking and check back in a minute. If they are, make sure they''re doing the right thing. Now you have NPCs that wake up at 6am, go to their shop at 7am, work on the forge all day, wander to the tavern at 6pm, drink there until 10pm, and then go home to sleep. Wouldn''t that feel much more like a real person than the ''permashopkeeper'' we see too often? I''m interested in any opinions on the things I''ve raised above, or any other symptoms we could address, and indeed in any attempted solutions for them. [ MSVC Fixes | STL Docs | SDL | Game AI | Sockets | C++ Faq Lite | Boost
Asking Questions | Organising code files | My stuff | Tiny XML | STLPort]

Share this post


Link to post
Share on other sites
Just depends on what the game developer wants to do... one of the old Ultima games that I played on the Apple II addressed just about all of those... at night, the shops were locked and people were off the streets... if you wanted in a store, you had to break in... if you were rude to someone, they remembered it...

Some of the newer games (like Splinter Cell) address the dumb npc problem.. (ok, ok, it''s not an rpg if they find a body, they pull out their gun and start looking for you...

I think the answer is that yes, all of these things could be addressed, but it might bog down the cpu... course, if they effectively covered several of those on the Apple II... Course, if you''ve got a larger arena with more people, and they''ve all got to remember if you''ve treated them nasty, if they''ve heard anything, etc.... it gets more complicated.

But nothing you mentioned *couldn''t* be addressed.... I guess the question is why don''t more games address those things... which I think is what you asked? ;-)

I guess none of the address the intelligent conversation complaint... that just requires a lot of scripting.... Deux Ex did a good job of that, if I recall correctly... but it''s been quite a while since I played it...

-Ascent

Share this post


Link to post
Share on other sites
Well, I think the autocue problem is also a subjective thing. Although it doesn''t add more to the game necessarily, it''s annoying when you can no longer review the information that an NPC has given you when playing a game like an RPG. That''s probably something to keep in mind too.

The "not sensitive to danger" thing is probably best by giving them some kind of attitude towards hostiles and having them respond to hostile creatures. This way, you could have some NPCs run away and others stand up and fight.

Share this post


Link to post
Share on other sites
I think its more of a problem of time and money. If your game is already behind, what are you most likely to cut out? It would probably be something that would have minimal impact on the gameplay. Only really good designers realize that NPCs are the player''s main link to game information. Without NPCs, most games would fall to pieces simply because the player would have no way to figure out quest, or get information about the villians.

Share this post


Link to post
Share on other sites
quote:
Original post by ShadowWolf
Well, I think the autocue problem is also a subjective thing. Although it doesn''t add more to the game necessarily, it''s annoying when you can no longer review the information that an NPC has given you when playing a game like an RPG. That''s probably something to keep in mind too.


Yeah, a good journal system is important for many games. There''s little reason why entire conversations can''t be logged in there. Also, an NPC changing what they say doesn''t necessarily have to mean the information is gone forever. It might just be that you get a briefer description the second time around.

quote:
Original post by Ascent
But nothing you mentioned *couldn''t* be addressed.... I guess the question is why don''t more games address those things... which I think is what you asked? ;-)


To be honest, I''m not really interested in debating the current standard of games like many people are. If I cite them, it''s as a point of reference so that people can see what I mean. No amount of complaint on here will change much in the commercial world. So what I am interested in, is showing and developing practical solutions to these problems so that the developers here on Gamedev.net can apply them to their own games.

[ MSVC Fixes | STL Docs | SDL | Game AI | Sockets | C++ Faq Lite | Boost
Asking Questions | Organising code files | My stuff | Tiny XML | STLPort]

Share this post


Link to post
Share on other sites
quote:
Original post by ShadowWolf
Well, I think the autocue problem is also a subjective thing. Although it doesn''t add more to the game necessarily, it''s annoying when you can no longer review the information that an NPC has given you when playing a game like an RPG. That''s probably something to keep in mind too.
That''s right. But what is the reason we are missing this important information? This why I sometimes miss important information:
1. I pressed ''X'' (a button to close a dialog window) just 1 milisecond after the window that contains the important information appear. As a result, I would see a ''blink'' on the screen, and I was like "WTF was that?"

Why did I do it? I was going to close the dialog window just before that window. However, due to some reason that I do not know, the dialog window (that I was going to close) autocloses itself and pop a new window (that contains the information). Therefore, instead of closing the window I intended to close, I closed the window I didn''t want to close.

Solution: make it consistent. Give players the control to close every dialog window in your game. Don''t make some dialog windows autoclose themselves.

2. I forget what he said. NPC said something, I was "OK." A second after I was like "what did he say?"

Solution: create a log or some kind of journal that will autorecord every important information that you receive. Wizardry 8 did this quite nicely. Most importantly, let players aware of this journal since early game so they know where to look for when they got lost.



Back on topic, dumb NPCs. I was thinking about this not a while ago, but my primary focus was another symptoms.

It''s so quiet here
This is somewhat related to "Do they have no lives?" symptom. Every RPG, I literally mean every, that I have played haven''t addressed this issue. From the beginning of the game to the end of the game, I keep seeing the very same people wandering the very same town. Some keep saying the very same words, and doing the very same thing. It is a village they said, but I only see 10 people living in that village. Some don''t even move around. When you enter a (the so-called crowded) city, you only see 15 houses. You head to the market, what do you see? Nobody. There are only 5 people around you, and they seem have no purpose being there other than to tell you something about their city. Where is everybody else? What are they doing? The city is dead. Where is the joy of entering a crowded city, people move around, too busy to talk, you hear murmurs all the time, you keep bumping on people. The only RPG I have played that gives me the feeling of entering a ''city'' is only Ishar 2 because they have so many houses (you can''t enter them all) and it''s huge. It feels so different if you just came back from a dungeon, "yes, back to the city." You need a map if you don''t want to get lost. Too bad the only thing it lacks is people.

Solution: create a system that generates a random NPC with random order. This sytem will randomly create an NPC for every x second (depending on how crowded the city is and what time it is), give them a random order (head to the market, go to harbor, go to house X). Don''t allow players to chat with this NPC. Or you can have an ignore level. If it''s above a certain threshold, it will not talk to players at all. This NPC is meant to populace the city and nothing else. So you will have a city that is alive, dynamically changing, and doesn''t look the same as the last time you visit it.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
quote:
Original post by Kylotan

Oblivious to danger . Ever played an RPG where, for some reason, a monster has strayed close to town, and is hacking lumps out of you while local farmers mill around as if this is normal and not a threat? I have.
...
Being oblivious to danger should be simple to fix. Most non-player characters in the game will be flagged as either aggressive or peaceful, and peaceful characters should fear aggressive characters of a similar or higher strength level. The action to take to resolve a ''fear'' state should be to run away, which is a simple reverse-pathfinding algorithm. Additionally, aggressive monsters shouldn''t only attack players; they should attack whatever is a valid target, which is probably any other character of a lower strength level than themselves. If you don''t want your key NPCs getting killed this way, flag them as important and have death just knock them unconscious for a bit.



I suggest that each NPC be given a "safe place" or two. A place that, given their character, they might feel safe. This place might be their house or a townhall or the actual town itself (if they''re outside it.) When they run away, they should do one of the following: run to a crowded area; run to their safe place; if that isn''t safe enough, run to the town-specific safe place, or fight. However, a check should be made to make sure they won''t be trying to run through some sort of direct danger... ie the enemy they are running from. In this case they could choose a different safe place or failing that run directly away from the enemy even into a possibly unsafe area (kinda like a person who panics and runs deaper into a jungle.) If they have nowhere to run, they can cower or fight.

Share this post


Link to post
Share on other sites
quote:
Original post by Kylotan
''The autocue'' . NPCs in many games have scripted lines to deliver hints, plot development, and so on. Sadly, they often repeat the exact same line each time you speak to them, and worse still, 100 different people might say the same thing, with a slight change to the subject matter. How can you believe someone is real when what they say is so obviously scripted?


In most games, in order to talk to NPC, you only need to press a button and the NPC will happily tell you whatever it wants to tell you. In real life, it''s not the same. You need to provide a question if you want to talk to someone and expect something from him. So provide a list of questions that player can choose from. After a question has been asked, remove that question from the list. If the list is empty, player can no longer chat with that NPC.

Share this post


Link to post
Share on other sites
I''ve thought about this before and decided one solution to the problem is to have a knowledge base. The knowledge base containts all the information local people might know, as well as things people all over would know. There would also be subsets of the knowledge that is limited to certain kinds of people. So if you goto a village and talk to a villager he might talk about the poor harvest, or mention the dragon thats being terrorizing people at the captial. You could even use precepts to have the NPC derive rumors, by combining similar facts in the knowledge base.

Example:
fact1 - A asian man has been staying at the the inn all week.
fact2 - Several Villagers have been found murdered over the last week.

The villager when asked about rumors could combine those two facts together to create "If you ask me the asian man is responsible for the recent murders."



-----------------------------------------------------
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
quote:
Original post by TechnoGoth
I've thought about this before and decided one solution to the problem is to have a knowledge base. The knowledge base containts all the information local people might know, as well as things people all over would know. There would also be subsets of the knowledge that is limited to certain kinds of people. So if you goto a village and talk to a villager he might talk about the poor harvest, or mention the dragon thats being terrorizing people at the captial. You could even use precepts to have the NPC derive rumors, by combining similar facts in the knowledge base.

Example:
fact1 - A asian man has been staying at the the inn all week.
fact2 - Several Villagers have been found murdered over the last week.

The villager when asked about rumors could combine those two facts together to create "If you ask me the asian man is responsible for the recent murders."
Nice. You could then modify the knowledge base after certain quests have been completed, like in Kylotan MM6 example goblins in the keep. That way NPCs would adjust accordingly.

[edited by - alnite on February 22, 2004 10:59:37 PM]

Share this post


Link to post
Share on other sites
Oblivious to danger:
One of my favorite things to do in M&M 7 was to lead the dragonflies back to the city, where they would kill all the civilians and at least a few of the guards, and I could steal all their stuff (there were a few good things you were supposed to trade for). Not much to say about solutions here; it''s pretty easy to think of ways to fix this.

''The autocue'':
The solution to this problem I''ve been pondering for a while involves treating knowledge as a state of a cellular automaton, as in Conway''s Game of Life. The cells would be the NPC''s. When one person has a bit of knowledge and others do not, that person spreads the knowledge. When everyone a person knows has the knowledge, the person stops talking about it because it''s old news.

Amnesia:
I suggest taking solutions from games like Civilization. The enemy rulers have opinions of and stances toward you, inherent dispositions and values, and so on.

Do they have no lives?
It''s also worth thinking about having NPC''s talk to one another. Even in games with people moving about, they tend not to congregate to chat. People do that in small towns, or so I hear.

This one is the most bothersome. In GTA 1 and 2, there were a limited number of cars that could appear on screen at once. If you stopped cars by blowing one up in the middle of the street, you could see this, because eventually no more cars would drive up to get stopped by the blown up car. I can envision a similar scenario for an RPG. NPC''s appear out of sight of the PC, walk through the player''s line of sight, and walk out again. At night, fewer appear and more disappear. Couple this with opening and closing times for shops (when shopkeepers would appear, walk out of sight, and disappear). It''s not the perfect solution, but it''s a pretty cool one.

Something that bothers me more, though, is that there tend to be only 20 people in villages and 50 people in cities, with corresponding numbers of houses. I think we''ve had a discussion on solutions to that problem though (I think it was a thread you started: how to generate a city algorithmically).

Share this post


Link to post
Share on other sites
I made a "level" for Neverwinter Nights some time ago, that tried to address exactly these problems. One of the first thing I tried to fix was filling the streets of the (quite big) city with life. To do so I would create random NPCs and let them wander around for a radnom time, maybe go to a seller (it was a market place), talk to him and leave the area.

What I soon found out was that the amount of NPC needed to create a real city life was jsut too much for the engine. So I had to reduce the frequency with which people were spawned, which diminished the realism a bit. This might not be a problem for games specifically designed for this kind of thing, but constant spawning/deletion, creation of random waypoints etc of NPCs is not a cheap task.

To cure the city''s people from their naivety I used the faction systen of NWN a lot. It basically assign each NPC to a faction or group. The player has a certain attitude towards the group, which can change over time. I used it to alter the NPS''s behavior towards the player. Depending on what missions he took the friendliness of each faction changed.

There were also some NPCs that lived in the area. They would have regular lives, going home (or at least o some house they considered theri home ) at night, going to work i nthe morning. Additionally I planned on using a data base of rumours to give people something to talk about.

As far as I got, I really was quite cool to walk through the streets. From all angles people where talking and shouting prices to each others, or simply exchanging greetings...

The reason I didn''t finish this module was the complexity that evolved from such simple ideas. The game is just not build for this and the system got more and more complicated, and it just did not feel "elegant" any more to me. So I gave it up.

I don''t want to discourage anyone, because when designing your own game all these thing can be build in from the beginning. And I guess I''ll try them again some time in a game. But it''s not easy, even more so because I''d like to include all those features into one smooth system and not (like I did with the module for NWN) make patches for every single issue.


------------------------------
There are only 10 kinds of people: those that understand binary and those that don''t.

Share this post


Link to post
Share on other sites
quote:
Original post by TechnoGoth

I''ve thought about this before and decided one solution to the problem is to have a knowledge base. The knowledge base containts all the information local people might know, as well as things people all over would know.


The problem is, how are you going to represent that knowledge base? Storing facts as English sentences is gonna make it next to impossible to derive any kind of meaning from. On top of that, your villager murder idea involves a guess, which implies some sort of probabalistic inference system. How would you implement it?

Knowledge representation is one of the main problems holding AI back because nobody really knows how to do it properly yet.

quote:
Original post by Flarelocke
When one person has a bit of knowledge and others do not, that person spreads the knowledge.


In a way, spreading the knowledge is the easy part (but sometimes overlooked by many games, I agree). The hard part is ensuring that everybody will have something to say and yet to have none of them speaking the exact same words.

quote:
I suggest taking solutions from games like Civilization. The enemy rulers have opinions of and stances toward you, inherent dispositions and values, and so on.


I was personally thinking of some sort of faction system similar to Everquest and other online RPGs. NPCs would inherit a base level of feeling towards another group from their town/country/race, and specific actions would be able to influence it further from the norm. And yes, some basic personality trait statistics would be good. I once posted about how 3 or 4 basic traits such as Bravery, Aggressiveness, Helpfulness, and Might could work together to produce a variety of interesting archetypes.

quote:
Original post by grbrg
What I soon found out was that the amount of NPC needed to create a real city life was jsut too much for the engine.


Of course, it would help if the game was designed for hundreds of models on screen at once. It''s like when Quake came out; because it was all true 3D it could only present about 1/10 as many monsters at once as Doom did. That was such a disappointment to me!

It would be possible to render distant NPCs as sprites instead of as models, which would be a start. And I''m not sure how CPU-intensive the scripting for the NWN characters would have been, but it''s possible to automate much of this in some sort of schedule manager so that it''s very light on CPU usage.

If you look here someone talks about recreating Ultima 7 using Neverwinter Nights, and failing because it couldn''t handle the NPC schedules. This is technology from the last couple of years failing to simulate a game from 11 years ago. This is also therefore one of the few examples where using a pre-built engine is possibly a bad idea, as they really weren''t built with massive living and breathing worlds in mind. Hopefully we can address these issues and bring such great designs back into the present.

[ MSVC Fixes | STL Docs | SDL | Game AI | Sockets | C++ Faq Lite | Boost
Asking Questions | Organising code files | My stuff | Tiny XML | STLPort]

Share this post


Link to post
Share on other sites
quote:
Original post by Kylotan
The problem is, how are you going to represent that knowledge base? Storing facts as English sentences is gonna make it next to impossible to derive any kind of meaning from.
Surely you can't store facts as English sentences because language is used to express the knowledge. Moreover, you are going to have some problems translating it to other languages.

I haven't put too much thought on this idea and haven't read much about it, but I think it is adequate if we adapt the traditional approach of using nodes to represent objects in the game in the knowledge base.

Each object in the game is represented as a node in the knowledge base. Goblin is a node, Keep is a node, Ship is a node. Then there is a connection that connects two nodes together. This connection will define how the nodes are connected. For example:

Goblin --- Keep

The connection between Goblin and Keep defines in such a way how the two are related. Goblins could be attacking the Keep. Goblins could be occupying the Keep. Goblins could be coming from the Keep. Goblins could be abandoning the Keep. In order for the NPCs to express this connection in English sentences, we can use a map (or multimap if you want more option), where the key is the connection, and the value is a string. If you are using multimaps, you could store different strings to express the connection. The connection will extract the string from the map, attach Goblin and Keep in the string, and create a meaningful sentence. For example:

The connection defines that Goblin in the Keep, so the string is:
There [goblin] in the [keep]

The information of how many goblins and where the keep is located is stored in each individual node. And the connection will extract this information. So the end result is something like this:

There are 50 goblins in the Keep south of the city.
There are 100 goblins in the Keep north of the city.

or, if you use multimap:
[keep] filled with [goblin]

The Keep north of the city filled with goblins.


You can add more nodes. Let us add a third node, for example, City. As you can see, I have used the City to define the location of Keep. So the connection between City and Keep defines location. Or if you prefer, you can connect City with Goblin, and the connection between them might define assault or raid, i.e. Goblin raid City. So the sentence is:

Goblins in the Keep south of the city has been raiding the city.

As I mentioned above, this is just a crude idea, I believe there are still many weaknesses with this system.

[edited by - alnite on February 23, 2004 3:50:50 PM]

Share this post


Link to post
Share on other sites
This thread has so much going on it''s terrifying. I''m just going to respond to the "algorithmic city" idea.

Didn''t Stronghold do this at some level? You had this big wad of "citizens" and when you built a bakery one of them would put on an apron and go there to be a baker. If things got rough, you could draft the baker, and he''d walk over to the garrison and get a uniform and a spear. In that game, individual citizens would last for years and years. You could follow the career of Hob Gadling as he works in the mill, then becomes a hunter, then serves as an archer, then returns to become a brewer, and then volunteers for the infantry and gets stabbed to death defending his house. That''s pretty sweet.

I think players would enjoy getting to know the bartender or shopkeeper, and if they heard he had lost his business and was beggin on the streets, they might toss him a few coins, for old times'' sake. You could even have an NPC "buddy list", and if you build up a rapport with them they might give you a friendly discount or let you into the VIP room. I know such games are mostly about monster stomping, but a good social element might be fun, too. Especially if you had a means by which to employ NPCs or enlist their services.

You could be a ship captain, and responsible for hiring a crew. Players would be disinclined to do menial tasks in-game (although they''re fairly enthusiastic about monster-stomping, which is as menial as it gets), and so you''d recruit NPCs. The Miller''s son, the Farmer''s nephew, and perhaps a few grog-swilling hands from the saloon, and you''d be off. NPCs might even acquire support skills in this way. Remember tracking down and recruiting Blitzball players in FFX? Expand on that idea, and you''ll have a general feeling for what I''m talking about here.

Random name generation is a simple thing, and you could incorporate the elusive "gossip" feature (if it''s ever figured out) to give each NPC a unique knowledge base and familiarity with the character.

Share this post


Link to post
Share on other sites
The knowledge base is a good idea. Even if you only implemented a rudimentary version of it, taking into account only certain key actions (like big player quests), you could get a lot more dialogue out of it.

Another problem that has always irked me is, along with NPCs being oblivious to danger, the NPC's disregard for player actions - and not things like completing a quest assigned to you, but everyday things. Like, running into a farmer's pig pen and killing all of his pigs while he wanders in circles in his yard, and then talking to him only to have him give you the latest weather forecast. Or (the thing that bothered me more than anything in a lot of Squaresoft games), barging into someone's house and rummaging through their underwear drawers with no reprecussions. Things like this really break up the immersion of the world... Ultima 7 fixed a lot of them, I think. I distinctly remember getting caught stealing from someone's house, killing the guy, and running for my life through nearby fields to get away from the town guard.

Edit:
Iron Chef, I love the idea of recruiting the crew of your ship (or whatever) from the local populace. The possibilities for that are endless... son of the miller gets killed because you screwed something up and the miller hates you because of it, etc.

[edited by - SantaClaws on February 23, 2004 4:17:40 PM]

Share this post


Link to post
Share on other sites
I can''t think of any offhand... Black and White 2 does something like it but you''re so far removed from the population in that that it doesn''t really apply.

Another thing that I forgot to mention in my previous post that bothers me about NPC behavior in most RPGs is the fact that NPCs never move. Everyone sits around in their town and does their thing, stores are miraculously kept restocked, etc. Icewind Dale had one scene where you come across another party of NPC adventurers in one of the dungeons, and I REALLY liked that. I wish more games would do it.

Even if you didn''t have the NPCs do very complex things outside of their normal town behavior, how cool would it be to have NPCs who transported wares from one city to different towns, so that as you''re going along the road to a city or dungeon you come across wagons or what not going along the road? Along the same idea, you could also have NPCs such as bandits or hostile creatures that would adapt to the paths taken by the suppliers, and try to waylay them along the transit routes.

Share this post


Link to post
Share on other sites
alnite, what you''re speaking of sounds much like a basic semantic net, which is one of several standard methods for knowledge representation in AI circles. Assuming you had a standard GameObject entity (that encompassed at least characters and objects), you could then come up with a number of Relationship objects. Then, all knowledge of this type can be expressed in terms of 2 GameObjects and 1 Relationship object. (Anyone who''s used the Prolog programming language or done much work on logic systems might recognise this sort of thing.)

Sample relationships:
"Is located at"
"Killed"
"Healed"
"Completed quest"
"Is friendly towards"

You could even have a weighting for each relationship, to indicate the degree to which it is true. The "Is Friendly Towards" link between Humans and Elves might be 90% while for Dwarves and Elves it might only be 20% in a stereotypical fantasy world.

I think this system is pretty workable, and a designer can sit down beforehand and dream up a list of relationship types and their accompanying affect on other game mechanics. Then there just remains the arduous task of producing the default knowledge set for the world (which can be alleviated by heavy use of inheritance) and adding triggers to the game to change the knowledge base.

SantaClaws, I can see a way in which your problem can be solved with the above system. Implement an "Is Owned By" relationship. When an object with an "Is Owned By" relationship is destroyed, reduce that owner''s "Is Friendly Towards" relationship with the object''s destroyer. On its own, this would be overkill to just prevent the random killing and theft of objects. But since it fits so well into the above system, I see no reason why it couldn''t be done that way.

[ MSVC Fixes | STL Docs | SDL | Game AI | Sockets | C++ Faq Lite | Boost
Asking Questions | Organising code files | My stuff | Tiny XML | STLPort]

Share this post


Link to post
Share on other sites
Kylotan - yeah, something like that would work really well for a lot of the problems that you see crop up. A basic version of it would fix a lot of the inconsistencies you see, and make a version of our current level of NPCs that doesn''t have as many flaws that so quickly break the immersiveness of the world.

I implemented something like this for a different (non-RPG) project, and it ended up being pretty flexible. When it started getting really fun was with the addition of emitter objects. Something like this could greatly benefit a lot of RPGs, too. This is straying more into the AI area, but oh well. I''m pretty sure the Sims used or use a system like this - the entities in the world broadcast what needs they can satisfy. So the NPCs who had a need could look around at nearby objects and try to find something that could satisfy that need.

If you took these two concepts and combined it with a time sensitive way of looking at the data, you could get a really powerful, extendible system. For instance, let''s take the situation I was talking about before where there would be suppliers who would travel along trade routes to deliver products to different locations. Their caravan would broadcast that it could satisfy the need of the bandits, and would be attacked if it went by somewhere that the bandits were hiding. The more it got attacked, the more it''s relationship of safety towards that trade route would go down, until eventually it would choose a different trade route instead. To take it even a step further, if the caravans stopped coming along the road, the bandit NPCs might try to satisfy a need to find the caravans, and if there was a shady character in a nearby town who broadcasted the ability to satisfy their need for information, they may be able to learn from him where the caravans have started travelling instead - and move there to continue the logical cycle.

You could extend this system to allow for automatic job/quest creation for the players, too. The more "reputation" a player gets for doing things well, the more he might broadcast the ability to, for instance, provide protection for someone or something. So a caravan that is getting attacked repeatedly might approach the player and ask him for help guarding them along their route.

Share this post


Link to post
Share on other sites
@SantaClaws:
You should play Uncharted Waters New Horizon by Koei (1994). It's a trading renaissance game. You control ships and sail around the world. You will see other NPCs roaming around, telling you where it's going (if you ask), what it's doing. Some NPCs with stronger stats (fighter-type NPCs) will sometimes hunt other NPCs down, some "protect" weaker NPCs (they don't literally protect. they just sail close enough that if you attack the weaker NPC, they can join the battle and attack you). There are merchant NPCs too (the weaker ones), and their job is trading, investing, etc. There are other NPCs hunting you down, mainly pirates. So, you will never feel safe when you are sailing. There will be always somebody out there trying to kill you. Even if you kill it, the game will respawn another one.

@Kylotan:
That's right, if done appropriately, semantic net can be a useful approach. It can be used to implement all kind of relationships (emotional,location,etc) in all objects (including players) in the game. The only problem is to have NPCs say different things. Suppose we only have one universal knowledge base, and we have 100 NPCs extracting information from the same knowledge base, the probability of two or more NPCs saying the exact same words is high, depending on how big the knowledge base is and how many NPCs that does this. This probability can be minimalized by providing more sentences for each kind of relationships (and let NPC randomly selects a sentence), but the chance of NPCs using the exact same words is still there.

Having more knowledge base doesn't solve the problem either. It rather narrows it down to a lower system. Suppose each city has its own knowledge base, but if the city is large and has 100 NPCs, it will still happen. If we put a knowledge base for each individual NPC, which is I think the correct way to solve it, and since this knowledge base has to be unique, what information do we put in? How do you randomly create information, like "my mom is sick" "my sister went to city X"?

[edited by - alnite on February 23, 2004 5:46:43 PM]

Share this post


Link to post
Share on other sites
I''ll have to check out that game... it sounds interesting.

alnite, I didn''t realize that you were talking about creating a way for all of the NPCs to (hopefully) have a unique way of saying things. That gets a lot harder, but I think it''s still achievable. I agree that giving the NPC it''s own "memory" is the right choice - for certain things. Obviously you can''t have a huge knowledge base for each NPC, so for common events (like the enemy sieging a town), there would be a shared database, and then for things that affect an NPC more directly you could add something to their database specifically. For instance, if goblins attacked a castle, everyone nearby might know about it from the shared database, but a father whose daughter was killed by the attacking goblins might have an additional item in his personal knowledge base that could result in some personalized dialog about the situation.

As for the problem of randomly creating the information - I say you don''t. I love worlds that can run themselves, at least to a point, and it''s not THAT difficult to do a simple implementation of such a system. The scale for something like an MMORPG could make it more difficult, but I think it''s still definitely possible. If you give the NPCs basic needs and consequences when the needs go unsolved, something like this could happen.

Say, working from the example you provided, an NPC in a city has a hunger need but doesn''t have any money, so they can''t satisfy it by normal means. So the NPC resorts to one of the much lower "hunger satisfying" entities nearby and eats trash out of a garbage pile. The NPC gets sick because of it, and this NPC happens to have a mother relationship to another NPC. That NPC''s database is updated with the state of it''s "friend" NPC, so that when the player talks to the child, it can be translated into a sentence like "My mom is sick." If you go further and track the fact that the player might be able to help with a problem like that, you could also have the NPC ask for help.

I think the biggest problem with a database system like this is that, like you said alnite, because you''re generating sentences from states, you can''t put as much personality or differentiation into the NPC conversation, except by providing a wider source of material to choose from. Of course, in most RPGs the NPCs in question wouldn''t be saying much anyway, but it''s still an annoying flaw to me.

Share this post


Link to post
Share on other sites
quote:
Original post by SantaClaws
Say, working from the example you provided, an NPC in a city has a hunger need but doesn't have any money, so they can't satisfy it by normal means. So the NPC resorts to one of the much lower "hunger satisfying" entities nearby and eats trash out of a garbage pile. The NPC gets sick because of it, and this NPC happens to have a mother relationship to another NPC. That NPC's database is updated with the state of it's "friend" NPC, so that when the player talks to the child, it can be translated into a sentence like "My mom is sick." If you go further and track the fact that the player might be able to help with a problem like that, you could also have the NPC ask for help.
Or, the sick NPC could broadcast to all nearby NPCs that it's sick, then the NPCs around it could add that information to its knowledge database. So, if you ask a nearby NPC, it might say "she looks sick."

So, instead of generating random information when it's created (you are right SantaClaws, don't), NPC should gather information from its surrounding and create its own database. It will be more dynamic.

edit: But then I have to worry when she becomes no longer sick. And what if the NPC is no longer around the sick NPC? it shouldn't say "she looks sick" anymore, but rather something else or delete that information.

quote:
I think the biggest problem with a database system like this is that, like you said alnite, because you're generating sentences from states, you can't put as much personality or differentiation into the NPC conversation, except by providing a wider source of material to choose from. Of course, in most RPGs the NPCs in question wouldn't be saying much anyway, but it's still an annoying flaw to me.
That's right.

edit:
I think the shared knowledge base is still doable, but individual knowledge base is more complicated to implement. We have to convert each possible action and state to information that NPC can store.

[edited by - alnite on February 23, 2004 7:09:45 PM]

Share this post


Link to post
Share on other sites
Okay, my first recommendation to the smart NPC issue is that VoiceActing for NPCs is given up on. Unless you have a group of philantrophic talent, or the Ocean Studios in Vancouver, you can''t afford it.

Next, NPCs don''t neccessarily need to talk. For example, go out and try to talk to a random person on the bus. You''ll get a lot of "Yeah, right, okay, whatever, heh, hrm, oh yeah!" and not much actual dialouge. This is because most people don''t know how to handle strangers, and the player is definately a stranger in most cases.

Third, the only NPC that needs to be doing anything is the one that the player is following around. I suppose if you''re delibrately trying to find an error in the logic of the progammers, you''ll find it. But all you really need is a Truman Show like intelligence, where most NPCs are circling the block, and any one in particular that has been within the player''s field of focus for too long will start adapting some activities to perform so it doesn''t look like he''s doing nothing.

Fourth, it works just as well to draw the player''s attention away by having an NPC distract the player. You run a good chance that the player will become more interested by the NPCs actually doing stuff, like the small child playing with the ball that asks the player to also play, or the flirty girl thats actually a pickpocket. What a perfect way to get an NPC to get away from the player if another one is running defense.

And last, keep an extensive list of dismissive statements that are polite enough, but different so that the NPCs being harrassed by the player can convince him that I have plenty to say, but am looking to get away and wont be saying anything useful any time soon.

I really liked Truman Show.

Share this post


Link to post
Share on other sites
I think a general knowledge base would be more effective then then a NPC specific one. By using relations and compounds sentences you could achive all the effects of an indivual KB.

For instance, bob''s mom is sick.
Woman(lynn); //Lynn is a woman
Man(bob); //Bob is a man
Mother(lynn, bob); //Lynn is the mother of Bob
Health(lynn, sick); //Lynn''s health is sick

with those for facts in the KB an NPC could derive that Bob''s mom is sick.

Bob would say "My mother is ill".
another predicate
Friend(bob, sid); Bob is Sids friend
would mean that talking to Sid could create the phrase.
"Bob''s mother is ill"

you could even take it a step further by allowing for the creation of dynamic rumors, and like all rumors these are most likely untrue.

So you create the predicate:
Rumor(P1,P2);
P1=Health(lynn,sick);
P2=Arrival(Gypsies);

Could be used to create the rumor "Lynn got sick shortly after the Gypsies arrived"

While it all sound good from a design point of view and would be intersting to see done, it would take a lot of work to implement effectivly.


-----------------------------------------------------
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