• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.

Archived

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

Gollum

How to make NPC's "gossip"

67 posts in this topic

A semantic network is an advanced form of knowledge representation that, like many things, has been around for quite awhile but has not been implemented in virtually any applications. It is basically a set of nodes linked together to form a network. I have implemented them in two ways using two different style, all of which will be discussed below. I will give you two basic structs in C++: the link and the node.


struct link {
bool active; //is the link on?
char truth; //the higher, the more true
char desc; //descriptor byte
short nptr; //offset of the node in the array
};

struct node {
char desc; //describes contents of the node
bool active; //is the node on?
char idea[30]; //knowledge string
char ltot; //number of links
link links[45]; //links
};


The two ways to implement them:
1. As an array of nodes
2. As cluster of nodes, created dynamically in memory

For an array of nodes, you may use the structs I gave you and just have to write functions to add nodes, remove them, and clean house (which will be discussed later). For a cluster of nodes, change the

short nptr;

is the link struct to:

struct node *nptr;


Then use new and delete to create the cluster. Now onto the two styles of networks:

1. General links
2. Specific links

the descriptor byte in the link struct tells the relationship between the two nodes being linked. This can be specific (lives in, eats) or general (is a, characteristic. While the latter is more suited to predicate calculus than the former, the former is (probably) better suited for this game.

Now as for how this applies to NPC communication:

When NPC 1 says to NPC 2, "red is a color", NPC 2 would look for red and color in their knowledge base. If he found both, he would create an "is a" link between them. If oe (or both) was missing, he would create the missing one(s) and then create an "is a" link between them.

I admit, this approach requires more parsing than normal but I find it very useful.
0

Share this post


Link to post
Share on other sites
I love the idea of a semantic network, as it gives NPC''s (or agents, or whatever) actual understanding of the world around them, as opposed to faking it.

I guess the reason I haven''t responded is that, for my project, it would be overkill. I love talking theory, but a common malady of these forums is people talking about grand ideas, but never implementing beyond the basics. Sourceforge and the web in general are littered with projects that have incredible design docs, but never make it past version 0.0013. I know that I myself have started many such projects and never gotten even close to finishing them.

So, my approach is incremental. It''s probably less organized, and leads to constant rewrites, but it does give me the knowledge that I''m progressing. At the moment, I have a small map, which I can create with a basic map editor. I have some NPC''s, created randomly, which move to random points using vectors. I''m seriously embroiled in trying to figure out A* pathfinding. Once that''s done, I''ll move on to having multiple level maps (countryside map leads to city map, city map leads to house map, and so on). Each feature gets added as I need it or can figure it out.

I have my gossip system working on a basic level. NPC''s can gain and trade information. I know that I can add more complexity later. But at this point in the game (pardon the pun), having a semantic network in my game would be, unfortunately, absurd.

Having said that, I am learning a lot from you guys, and I may have to create a proof-of-concept program to play with the ideas, just because it sounds like so much fun. I''d also like to figure out what rules would be relevant to an RPG. MY NPC''s would not need to know that apple "is a" fruit, for example, but they would need to know that an orc "is aligned" evil. NPC''s should have a set of rules that helps them make decisions about their daily lives - when to change state, what to buy, where to travel, who is on what side in a battle, and so on. Maybe a good discussion would be what subset of semantic rules is most important in an RPG?

Please keep talking. I''m really enjoying it, and would like to contribute, but for the moment, the best I can do is listen and occasionally ask questions.

- Gollum, who is mired in pathfinding he11.
0

Share this post


Link to post
Share on other sites
Well I am working on some semantic net classes so if you want the code, feel free to leave your email, and mention it.
0

Share this post


Link to post
Share on other sites
In the gossip context you can get away with using only one semantic net representing the relevant items in the map. Each NPC has a set of links and when they communicate they exchange these links. So if npc1 ask "where is the blue key", npc2 checks the semantic net to see if one of his links is related to the blue key and if so he will tell it npc1, who adds this link to his set. Just an idea....
0

Share this post


Link to post
Share on other sites
To me it sounds kind of silly to keep track of all these NPC''s and things they know and remember it would eat up memory like crazy. You could probably do it all semi-random and the users couldn''t tell the difference.
0

Share this post


Link to post
Share on other sites
Well Mr. Anomymous, computer today have TONS of RAM. Mine has 768MB. So memory isn''t really as much of an issue to me and many other people compared to realism. Don''t get me wrong: I see your point and understand your intent, but I think that idea eliminates NPC''s gossiping if they have random memory. Also, you could make it less memory cosuming by making a unchanging common snese network, and then give each NPC a small, maybe 1024 node network of his or her own.
0

Share this post


Link to post
Share on other sites
Anon, you make a good point - these kind of routines could be very expensive if not implemented and used carefully. Probably more CPU than memory intensive - this kind of cognitve modelling tech tends to use graph and network based structures, and we all know how well they scale up

It's a question of getting value for money (or bytes/cycles, whatever). I reckon this kind of gossip system could enhance an RPG nicely (to the extent it would be noticed, at least subconciously) if used properly. Here's a few possible benefits:

* Enhancing "whodunnit" scenarios and other investigations. Eg, a murder has been committed. Using the kind of knowledge distrbution system being discussed here, the player(s) will need to engage in a more focused investigation - eg if a baker was killed, the player would need to consider the kind of people he would be associating with, investigate contacts, etc. Basically, the networking of contacts would be improved - it wouldn't be enough to randomly question patrons of an inn, for example.
* Increase the need for subtlety. Eg, the player is investigating a crime. They start asking questions all over town. Using our knowledge distrbution system, word gets back to the thieves' guild that someone is prying. They take action... This kind of thing makes the PCs think twice before asking random punters for sensitive information. PCs on the run/outlawed would have to be careful who they share information with - you never know who's going to be chatting with the Captain of the Watch... Combined with a system of alignments/motivations, this could make PCs trust certain indivduals and not others, etc. In a reguar CRPG, players think nothing of wandering around a tavern, asking prying questions to random peasants - these techniques could be a nice twist to the gameplay dynamic.
* Dynamic plot systems. Some form of information sharing system could be useful in the implementation of such a system.

While most of the above could be hard-coded or scripted, the use of AI techniques such as the cognitive modelling being discussed here will allow for differing scenarios and dynamic gameplay on a larger scale than any designer could allow for. If knowledge is distributed in a (semi)realistic manner, the gameplay will most likely differ from one game to the next. This greatly increase replayability, non-linearity, etc. One of the best things to watch in game AI is when your creations do something competley unexpceted - take on a life of their own, as it were.

Anyone else have suggestions for gameplay enhancements and possibilities provided by this kind of gossip system?

Edited by - NeverSayDie on February 20, 2002 7:21:34 AM
0

Share this post


Link to post
Share on other sites
Another idea - a more realistic reputation system. Most RPGs simply give the player/party a reutation score that goes up/down with their actions. Things could become much more interesting if this system was based on the knowledge distrubtion network. Each NPC would have their own opinion of the PC - which would increase/decrease depending on actions witnessed - and the gossip they had heard about the PC. For example, if you murder a villager in the Far North, it could be a long while, if ever, before you gain a nasty reputation in the Southern Desert. But you never know, that peddler who was in town on the day of the murder might be spreading stories wherever he goes...
This could also allow the player to be framed/defamed - that noble you insulted might start spreading nasty rumours...
0

Share this post


Link to post
Share on other sites
One of the first things that got me interested in designing more realistic games was playing Final Fantasy VII. I''ve never finished that game, even though I''m very near the end. Why? Because even when my party was tremendously powerful, we still had to fight the same crappy level 1 monsters every three paces. It took forever to get anywhere, the experience points were worth basically nothing, and why were these little wimpy monsters attacking me in the first place? All the people seemed to know I was bada$$. What, none of the monsters knew I had killed thousands of them?

If you built a real, dynamic reputation of alignment and power (which would travel theough the gossip system), everyone could react to it. Weaker creatures might leave you alone. Thieves could seek you out if you''re right for the job, or plot to assassinate you if you''re prying too much. You can become a "marked man" (or woman).

The biggest advantage of all of this is very simple. We''re talking about rolepaying games here. Changes like this will encourage you to play a role, rather than playing every game/character the same way. Plus, they will help get rid of a lot of stupid RPG problems, like the random encounters, or the fact that you have to ask every person you meet for every piece of info they have, or the fact that you can steal to your heart''s content in most games, and nobody seems to notice, much less care. In Daggerfall, you could kill someone in town, and the guards would come after you. If you ran outside the town limits and then came back, they''d forgotten!

Honestly, at this point I''m just enjoying making it work. But I think that it can help eliminate many of the obstacles to getting fully immersed in a world.

- Gollum
0

Share this post


Link to post
Share on other sites
This is really a great topic

I'm jumping back to the "decay time" posts. Some memories are more easily forgotten than others. For ex: an epic battle against a Dragon is remembered longer than Joe the Farmer dying (people forget him faster). You could implent this, but it would take even more variables/CPU power/etc because every person remembers something longer because of his/her interests, for ex: the family of Joe the Farmer would still remember him after 20 years, Jack the Baker who lives in another village and didn't know him very well won't remember him for long.

Good luck Gollum

"Control the media, control the mind"

Edited by - Terr on February 21, 2002 7:54:51 PM
0

Share this post


Link to post
Share on other sites
...so you could link the decay rate to the subject class. Statements about dragons might be remembered for a long time, so might folklore. The theft at the local bakery might get momentary gossip status but be forgotten about 3 weeks later by all but the baker.

Timkin
0

Share this post


Link to post
Share on other sites
Basically change the threshold and and decay rate. Now you need to decide which one to change. I'll get back to you on all of that...

Edited by - Puzzler183 on February 21, 2002 8:26:43 PM
0

Share this post


Link to post
Share on other sites
Ultimately I believe that much of our knowledge is forgotten when it is not used or shared. That''s simply because it hasn''t been transferred to long term memory. Using knowledge, or communicating it to others, reinforces it. Eventually this reinforcement is sufficient that we store the information in a seperate part of our brain (I''m not a neuro-physiologist so I don''t claim to know EXACTLY how it works... I''ve just read some articles).

We could mimic this in an our NPC gossip system by reversing the decay on the memory each time the NPC passes the information on, or performs an action that relies on the information. That way, while something is a ''hot topic'' of conversation, it gets reinforced and remains in memory. When other items of information compete with it for ''air time'', it will either win - staying a current topic - or lose, thereby drifting off into the ether to be forgotten by all but a few who have committed it to long term memory.

Perhaps if the decay is reversed sufficiently such that the strength of the memory increases past an upper threshold, then the memory is held indefinitely and is considered to be a long term memory.

Just a thought...

Timkin
0

Share this post


Link to post
Share on other sites
Here were my thoughts:

For reinforcement, just reduce decay rate (reduce a in your original formula). On the other hand, if somehting happens a second time, like a second war or something, decrease threshold (square it, half it, multiply it by the decay rate).

I also did some graphs on my calc and found that a should to be between one and zero but I think something like between .1 and 0 is better. The reason is that in 4 days with a at 1, the number drops extremely low (BTW I am assuming t is in game days). At .1, information was remembered for about 125 days (if I remember right), before it dropped below the same threshold. Unfortunately I can''t exactly remember my threshold value but you get the point.
0

Share this post


Link to post
Share on other sites
I''ve thought of a better way to do it. If youare using a semantic network, you can have a variable in the NPC''s personality called memory. It would be the size of their smeantic network in nodes. Hten you could have another variable in their skills called intellegence. This would be a or the decay rate coefficient.
0

Share this post


Link to post
Share on other sites
Sorry if Im dredging up this topic, but what AP had, the Interest variable is a good idea. Ive been messing around with a general experiene scheme where a character is better to do things sorta like what he knows well.
Example:
A Blacksmith can make a sword.
Two disciplies that are close to it are say, tinsmith and silversmith. Granted that they are a bit different, but after maybe a day or two the blacksmith can learn to do some stuff with the other metals, but maybe a carpenter would take a week, a cobbler 2 weeks, a weaver, a month, etc.

It would be arranged in catergories,

Workers
Raw
Metal
Wood
Textiles
Weaver
Cobbler
Food
Baker
brewer
Consumers
Soldier
Nobles
Priests

And so on. Something that fell under raw would be better done by a worker who uses raw materials, less good with textiles, and even less good with food....
What you should add into that struct is a varialbe like

short Disicpline

Say Orcs Raid Happytown, that would stick it under, well maybe that would be all.

Something like
The Elven Nation has cut off wood supplies to HappyTown!!!

Protaganist: Elven Nation
Location: HappyTown
Verb: Embargo
Noun: Wood
Disicpline: Worker-Raw-Wood

it will be a hot topic for carpenters
less so for ore workers,
bakers wouldnt care
and soldiers would tell them to STFU.

That protaganist was stuck in on the fly, BTW, but I think it works better than just location, which is bad for something like that.




0

Share this post


Link to post
Share on other sites
Just thought I ought to remind you that in a game your NPC''s dont have to REALLY converse with each other...
you see, it all boils down to perspective - if the player is playing the game then obviously the player has to be able to converse. but npc A and npc B need not really converse in order to know something.
It might not be quite what you are looking for, but I would suggest that you economise your npcs and try to approximate this exchange of knowledge, rather than really exchanging it. Rather than have an npc who knows some information, simply specify what information there is (ie happytown is raided), and how dispersed the information is, as well as time stamps etc.
Now when the player is in Happytown, obviously everyone ought to know (local news, important). If the player is in Gundringsville or wherever an npc MAY know about this information. If its important and Happytown is down the road, then let a load of the npcs have the info. If not then either only a few (as you say you can classify info) or none have this info.
Rather than exchanging info, you only need vectors between locations - which can indicate how much exchange takes place between the two, and how long the minimum exchange type is. Now whenever the player talks to an npc, you can determine what the npc knows. As you are mainly interested in gossip (ie not SUPER IMPORTANT QUEST INFORMATION) this doesnt really matter. Ok to keep things consistent whilst in a location the npcs shouldnt be forgetting and then remembering info randomly, so you might have to store some more info, but once again - only that of those npcs that the player has talked to. The rest are totally irrelevant from the players point of view. Basically its a computerised Schroedingers Cat ie until we actually examine the NPC we have absolutely no idea what state he is in, but by examining him, we automatically have assigned him a state (ie the cat is now dead).
You can expand this to the events themselves if they are random - no need to have events taking place that the player can have no knowledge of, so only when interacting do you need to determine whether there is any gossip.
Basically you dont need to simulate the entire world to get a working approximation of one, and generally its these sort of things that get in the way of good gameplay imho.
0

Share this post


Link to post
Share on other sites
I think it would be cool to be able to "overhear" (ie, see text over the character head) gossip in a tavern (maybe make it a range factor, but that really doesnt fit in with the whole isometric concept), nothing inegral to the game, but I would be sitting in the tavern (That is another thing, you guy NEVER sits down). No one does in a lot of games. People stand around all day, in an age before pediatry), see the gossip, and then the next table over, the kid says "I heard theres gnna be a war with those elves." And you look up and either take note or you go over and try to nose your way into the conversation. I guess the danger is information overflow.

Maybe the entire knowledge base would be composed of structs, but dynamic.

0

Share this post


Link to post
Share on other sites
To sjm:
Though I think you are certainly right about avoiding needless complexity, and while most games get away with far less than even what you suggest, I have to disagree with you.
Having NPC''s with knowledge that is random and non-persistent has several disadvantages compared to an NPC that stores addresses to the universal knowledge db. Here are some reasons your proposed system would be unsatisfactory (to me):

1. When you meet the same person on two (or more) occasions, their knowledge may be different every time.

2. Who has what knowledge is random.

3. You never know whom to ask about certain kinds of knowledge.

4. There is no incentive to talk to any one kind of person versus any other kind of person. With the type of system we''ve been talking about, it would actually make sense to go to taverns looking for info, because that''s where the travellers are, and they know the most info. Up until know, going to the inn for information has been an artificial construct in games. We go there because we know that''s the way games are written, not because the game world "works" that way.

Anyway, you may think to yourself (and clearly many game programmers have) that these aren''t reason enough to take on the processing overhead of gossiping NPC''s. I think there is an optimal level of complexity in how they do it, but I think the added realism definitely makes it worth doing.

IMHO,
gollum
0

Share this post


Link to post
Share on other sites
true it eliminates the purpose of npcs gossiping.. but the question is.. do you want your npc''s really gossiping or a fun game... remember, as a programmer it might be interesting as a player its probably fairly irrelevant as long as it appears that they are gossiping.. the game mechanics ought to be transparent to the user!
if you''ve got a masssive game with loads of npc''s I cant see it being really feasible having them all really interacting (I''m thinking of something big where you may well have a few 1000+ npcs in your world). they''re are surely more important uses for your cpu time... obviously its a lot more feasible with a small amount of npcs, but at some point you are going to have to generalise and approximate imho.
0

Share this post


Link to post
Share on other sites

on the topic of randomly dissapearing info, of who to ask for what, well you simply have to generalise here again - as you mentioned previously. If you can determine what sort of knowledge what sort of person has (ie treacherous in a thieves guild or whatever) you can simply check to see if this npc has access to such info (ie he is a thief or whatever) As long as you have a communication path to the npc I guess its up to the prgramming mechanics to determine when/how often an npc has info and is willing to share. This way you can eliminate the random appearance of knowledge without getting to bogged down with the implementation. I don't see how having npc's gossiping will allow a player to know who has what info, as its the npc's gossiping not the player . You simply move the random element of npcs gossiping to the random element of "whether an npc may have gossiped". Other info that might determine what knowledge an npc has is his/her hometown etc. As long as you have a simple economic model you can easily determine where an npc can come from. If an event causes a mass exodus, well you simply have one of the directional flows stronger than the other (ie all vectors out of happytown are weighted heavier because of the orcs than those entering happytown)
If you really want the information an npc has to be consistent over a period of time you will still have to store it, but the overhead of storing what npc's the player has talked to know vs what all npcs know is drastic.
I'm not saying its a bad idea to gossip - it would definately make the game more dynamic, especially if the mechanics of the world are as you say not deterministic. (ie each game is different and the orcs may not always attack happytown).


Edited by - sjm on March 1, 2002 9:33:51 AM
0

Share this post


Link to post
Share on other sites
Well, let me explain a bit more.

I brought up this idea because it is one part of my ideal role-playing game. To me, the ideal role-playing world would be one that could be randoly generated (and therfore basically infinite) and still make sense. Since the quests (for the most part) wouldn''t be written by humans, you''d have to have them naturally occur from a living, breathing world. Then your goal as a player would become much more involved. Instead of trying to figure out what the designers wanted you to do, or following the arbitrary rumor path from one town to another, things would just happen in the world, and you''d have the opportunity to react to them. Or not.

So, what would be necessary for such a game? While I don''t even pretend to know how to build it, I have a lot of ideas, and I''ll build them into my program as I can figure them out. But I imagine we''d want at least the following:

1. Lots of NPC''s.

2. A working economic model (supply and demand, which allows for shortages, starvation, etc.).

3. Some form of political simulation (i.e., different groups can decide to go to war or make peace with each other).

4. NPC''s will be divided into two main groups. "Basic" NPC''s will do little more than keep the economic model going, be able to fight, and pass along information (i.e., participate in the gossip system). Then there will be specialty NPC''s, who parrticpate in politics, are tradesmen, theives, etc. Some of them would probably be adventurers like your player.

5. A way for information to travel, so you can know what''s going on in the world, and NPC''s can know what you''re up to.

There are probably others. Does that sound like a lot? Maybe so. But I think when you break it down into smaller chunks, it''s very do-able. I have noticed some recent games, like Gothic, implementing pieces of this.

Basically, I don''t want to feel the limits of the game world. I want to feel like my actions have real effects. And I want a world that I could essentially play in forever, if I so chose.

So, in that context, I think the gossip system is pretty important.

As for storage, I think that my version of this (which is a lot simpler than what some others would propose) is pretty simple. have a universal table or database of all events worth noting. Individual NPC''s don''t store all of the info about an event, only the "address" of the info. When an event occurs, just propagate the event info address to all the relevent NPC''s. So, you would be storing one record of each event, and each NPC would have a list of event addresses. I don''t think that would be too bad.

Now, I would try to scale it so that NPC''s who aren''t on your screen (or within some distance) have a scaled-down way of deciding when/how to trade info. Two NPC''s travelling through the wilderness half a world away from your player will not have to do collision detection (to see if they meet), for instance. It''ll just be some random chance of meeting.

Hope that clears up what I''m thinking,
gollum

0

Share this post


Link to post
Share on other sites
hehe, I had a similar idea too - you know how it is, things occur like war breaks out, or the king dies or whatever and the game goes on and on - much like a "real" rpg where the gamemaster takes over this role.
As long as you aren''t really simulating each npc''s life (which is the impression I got at first) it should work, although as you say you will have to simplify, so that npc''s two worlds away aren''t really doing anything. Obviously gossip can work well as you describe in a small area (say a town or province). Perhaps you need a sort of hybrid system - npc''s really gossiping within a given location, and information flow from one location to another (as opposed to actually moving npc''s around).
0

Share this post


Link to post
Share on other sites
I think you could fake the gossip travling like sjm said, AND have it be persistant AND have npcs that know more about their specialty than anybody else. The way I would do this would be to have a list of all the information with various data about each piece of info (like where it originated, how `generally interesting` it is, what type of specialty it applies to, when it happened/was found out/etc) and then have NPCs have some kind of varous knowledge 'skills' (with higher values for the NPCs specialties). To see if an NPC knows something, you would take into account where the info originated, how long ago, where the NPC has been, how `generally interesting` it is, add in the NPCs skill in the specialty it applies to (if any), etc to get a % chance. Then, use the pointer to the NPCs struct or its ID or something else unique as a seed to a random number generator. Make a random number using that seed, and see if it falls insidde the %. If so, it knows it. If not, it doesn't. Over time, the % chance that something is known would go up and eventually everybody would know it.

The one thing prevented by using the above is that players wouldnt be able to teach NPCs direct info. You could make NPCs skills rise temporarily after talking to a PC to make it seem like the NPCs are learning, and hope that by the time the player comes back, the % will have risen enough that the NPC will know whatever it pretended to learn earlier.

Or, if you just HAVE to do it for real, use an array to store all the info and just store an array per PC of indexes to the info they know =-)
You could always just use the fake method to decide what data to add to NPCs that are off screen, so you don't have to keep track of every single 'conversation' that might take place off screen.

[edited by - Extrarius on January 17, 2003 12:03:27 PM]
0

Share this post


Link to post
Share on other sites