• Announcements

Archived

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

NPC AI in RPG's

59 posts in this topic

quote:
Original post by _rpg_guy

You started to lose me once you started talking about the "Principle of Maximum Expected Utility." I have no idea what that is. (I''ll do a web search after I finish this post.) It all sounds very cool, but I have to understand all of it before I can program it. I''m still at least a month away from starting to code the AI portions of my game, but probably more. Gotta run. Keep the good ideas rolling!

Sounds to me like Q-Learning and W-learning, where an agent
takes time to learn about the best possible option from all the possible options, then chooses which one to take based either on their own gain or on the expected loss to others, depending on how you want the agents to play. It was design for a collaboration system but I''m sure it''s relevant.

There''s a Reinforcement Learning paper by Mark Humphrys on this at:
http://www.cl.cam.ac.uk/users/mh10006/

On the greater scheme, the communication between NPC''s is an extremely complex problem both in terms of speed and resources. The only viable way I can see of doing it is via a central database that agents can only view through rose-tinted spectacles, and need memory retardation. Agents would also need beleifs of their own however, as there is no point storing the I heard Albert saying something about Cheap Swordfish'' in the central database.

Unless the game is very long, or there are very few characters, there is little or no danger of the characters knowing everything. The memory retardation is mainly to keep processing per agent down, and to help them focus on what is important to them.

Any a good database would be constantly growing anyway, by adding the Bongo killed a dragon'' type of information, as well as updating certain information on where people are, who''s dead or alive, how powerful people are etc...
0

Share on other sites
With regard to information sharing, we''ve been developing something along the lines of the following:
1) distribution of the message: Close friends, Acquaintences, General Public.
2) Accuracy upon repeating: Very accurate, downplay, exagerate.
3) Type of message: Boast, rumor, decree
4) Duration: Day, Week, Legend

For example, NPC A (from the lovely town of A) is in a pub and overhears NPC B (from that haven of surly fishmongers, village B) stating that that his village market sells fish at 40% less than the going rate. NPC A adds this to his list of known info (as does everybody else in the pub) with the settings of General Public, downplay, boast, day assigned to it, as well as who/where it was said. Later, at yet another pub (A is for Alcoholic, apparently), he hears somebody discussing fish, he repeats that village B sells fish at 10% below cost.

The NPCs share messages the same way that PCs do. If a message is Close Friends, it is whispered. Otherwise, it looks a bit like hanging about the bank in UO. When an NPC no longer has any info about the topic at hand, they will say a random rumor they heard, stirring up yet another long winded bar conversation. They will pick out key words (cities, known nouns, etc...) to use as a determination as to whether or not the rumor is relevant.

So far, we''ve got a pretty good simulation of a bunch of drunks in a bar. Still need to work on relevance...
0

Share on other sites
I would love to see better AI in NPC, for years have I been tossing up wether or not to write the ultimate RPG with contenant sized maps that zoomed into precise detail, characters that would run the show all round the playground, and numerous sub-quests buried into the main quests, but every time I sit down to start coding it, I scoff at the damn machine, sure games have come a long way since the days when I first learnt how to program(back in the days of the microbee and the commodore PET) but I''ve got to be honest, even with cutting edge technology, I think it will take yet another 10-20 years before computers are capable to produce my dreams.
I love multiplayer games, and assume that even with NPC AI you still are planning to incorporate multiplayer.
One last thing that I have to say, I kinda figured a way to create maps of 4096x4096 blocks that span 256x256(these values are aproximate) tiles in relatively little memory, if anyone is interested in chatting about this I''m happy to discuss my ideas, my e-mail is kothos1@dingoblue.net.au
I think what people need today is a bit of laterality, most games I see are linear, you compleate one part and go on to the next, it would be so easy to incorporate a kind of pick-a-path into some games that it bogles me over that they don''t do it, how many times would you be able to play a game with this incporporated, and it is just the tiniest little bit of extra work.
Anyway I wish you the best if you are indeed thinking on working on that Inverse Parser, if I remember rightly they got quite good before castle wolfstein caused that quake in the games market.
0

Share on other sites
suggestions:

information will tend to circulate between freinds, within a guild, where they work, etc. npc stats could include what ''sectors'' the npc belongs to and how high they are in the heirarchy.
global game information could be indexed by knowledge level so a 1st level (or equivalent) would probably never have access to the same info that a guildmaster would.

this would also help limit the spread of information. a hacker might know that Xcorp is about to overhaul it''s security systems, but a dealer would most likely not.

gaurds for instance would be very interested in theives guild information but care little about temple issues (unless a member of that temple or a adversary guild) and would ''remember'' certain things better.

none of this is new, just tossing out a few ideas.

AND FOR THE LOVE OF EVERYTHING DIGITAL A LOCKPICKER CANNOT BECOME A BETTER LOCKPICKER BY KILLING ANOTHER CITY GAURD!!!!
hehe...
laters,
b

0

Share on other sites
UNLESS! the city guard happened to have a little ''Guide to Lockpicking'' stowed away in his backpack :p
0

Share on other sites
Speaking of NPC AI whey dont they get mad whaen you barge in their houses like in games like Lunar 2 and Final Fantasy. And they only walk back and forth. Weird stuff man....lol
Geek
0

Share on other sites
quote:

Sounds to me like Q-Learning and W-learning, [snip]

Not quite. The Principle of Maximum Expected Utility (MEU) assumes you have a utility function defined over domain states. The MEU then provides a means for choosing actions in light of this utility function.

Q-learning (and other forms of reinforcement learning) presume that the utility function is implicit in the reinforcement values returned by the evaluation portion of the algorithm (which takes states/actions as input). That is, considering these ''rewards'' over all states constitutes a utility function.

Tim

0

Share on other sites
quote:
Original post by Anonymous Poster

So far, we''ve got a pretty good simulation of a bunch of drunks in a bar. Still need to work on relevance...

Sounds interesting. Perhaps you could consider including a ''context'' variable that has the same scope as the ''distribution'' variable. There would be one context value per conversation going on. The challenge for the player is to deduce the context of a discussion between NPCs and conversely, the challenge for an NPC talking to a player is to determine the context of their discussion (this is an active research area).

Once a context is defined, then relevance should be fairly trivial to deduce.

Tim
0

Share on other sites
hmm... i think i should say something because i was in charge of coding AI for moonpath (Dream Dust Oy:s RPG) an the thing is that i coded for 8 months and didn''t get anything else but 200 000 lines of MATRIX (my script lanquage that i had made for AI coding0) and that is over 1 000 000 lines of C++ and still i didn''t get them to be intelligent. so after 8 months of 20hour days i got burnout. and that was the end on moonpath. AI was only 10-20% finished so it had got to big. think about it. 10million lines of C. not even newest computers can handle that. so the starting point should be to make good AI not perfect ai that simulates everything.
0

Share on other sites
quote:
Original post by Anonymous Poster

[snip] ...so the starting point should be to make good AI not perfect ai that simulates everything.

Okay, I'm sure I'll cop a flame or two for this one... but...

Scripting your AI is definitely NOT the way to go when you want to imbue your agents with behavioural traits or decision processes that appear intelligent. Scripts are useful for small domains where you can meaningfully right down rules of actions... if condition then action .

Scripting of a storyline or high level actions (like take a trip to another town) would be reasonable if they are integral to the story line, but unfortunately most game producers think everything can be solved with a script. Oh, and a script is NOT AI, its PI (programmer intelligence!).

If you have a large, complex, dynamic domain a script just wont cut it.

This is why we aren't seeing an advancement in game AI that keeps apace with processor and memory advancement... people are using tools that were appropriate 10-20 years ago to make the games of the future.

My \$0.02 worth.

Tim

Edited by - Timkin on June 6, 2001 4:57:52 AM
0

0

Share on other sites
quote:
posted by KaneBlackflame
I have to agree scripting is not the way to go. A few monthes ago, I implemented an NPC AI design I have been working on for a while.....*snip*

interesting....
and how did you display the results without graphics.
it would be interesting to see a demo of that, assuming thats possible of course

I would say that scripting shouldn't be dismissed so rapidly, even with good ai you still often need methods of triggering events, at least in games you do.

however, a few lines of good propagating self-contained ai can be worth 10's of thousands of lines of equivalent scripting code.

good scripting can give you, as the world creater, a good way of directly controlling a hundreds of bots.

"Bad Day... F**K it!" -Stephen Baldwin (Usual Suspects)

Edited by - Nutter2000 on June 7, 2001 7:25:12 AM
0

Share on other sites
I must reform what I said...pure scripting isn''t the way to go...to be honest, all of the motor functions were scripted actions. THe simulation ranthe whole toen a few times a second, but the toen was never bigger than 132 people...I throttled the "game" area so not enough food could be made for a population much more than that. If the next demo goes well, I''ll post a well grown demo if you want. I''m still a few weeks away, but I would be happy to show it after it get it running again. It''s not as interesting as I lead on...I had a log file printed of all actions taken...I let it run for 10 minutes my first run and stopped it to make sure the log file was working and found a huge! log file of sleep, eat, move...I ended up only logging certain events like going to certain places or doing certain things, and these went to separate files. When a distaster happened, I had everything be logged during the event, that''s how I saw my ''hero''...but most of the time, nothing but simple everyday stuff goes on...the trends and paterns that emerge though would surprise you...On some levels, humans are actually reasonable! I had never thought this until I saw my "families" doing what we do...someone goes to work, someone gets food for the house or cares for sub NWebs, sub NWebs do stuff that makes them happy. I don''t know, most of it was pretty un-entertaining, but it did show me a good path...a set of NWebs to decide which script to run may provide a viable solution to mobile NPC''s...of course, conversation is a little harder...
0

Share on other sites
KaneBlackflame, what exactly is an NWeb? Something like Neural Nets?

The RPG I''m working on uses a form of event driven behavior. Right now, it''s just a real-time battle system, where you control your character''s movement and aiming. When you walk, depending on your stealth rating, you may make noise. Then all people within the range hear it and react. They all have a list of known things and have preferences (like A will attack enemy before he''ll heal himself, B will heal a fallen friend before attacking..). They forget after some time and move on after a while.

I also think that EVERY NPC doesn''t have to want to travel. I think it would make things easier if only a few NPC''s actually deviated a lot from their normal routine. I plan on doing something like Naz was talking about, the NPC''s have agendas (just as the soldiers earlier) and go about their business.

--I don''t judge, I just observe

Stuck in the Bush''s, Florida
0

Share on other sites
quote:
Original post by KaneBlackflame
I must reform what I said...pure scripting isn''t the way to go...to be honest, all of the motor functions were scripted actions.

ahh yes, now it becomes a little clearer.
to be honest that was my point, I think that it''s very difficult to get good NN or none-scripted methods to do the basic functions, or at least with much success over a large spread of agents. Also I don''t beleave that we "randomily" learn to do stuff like that in real life, babies seem to have the instinct to walk and know how to walk, and I don''t think it''s just from watch adults. but still thats another issue.

I''m a big fan of using Networks, or fuzzy logic to facilitate state changes I think that is often a nice happy medium that gets the best from both worlds!

I for one would be interested in seeing a demo.

to get back on topic, a set of networks or other more flexible systems could be used for changing which set of mood scripts, e. angry, scared, etc. and influence the conversation that way.

for example, the player needs to get a key from a guard, now depending on how the guard is feeling, he may or may not give you the key. The player needs to influence the guard in certain ways, if he makes him happier as regards the player than he''s more likely to give him the key.

in terms of how to do that, you COULD have say a network which takes inputs on current mood, player actions, etc, this modifies which script set the guard uses at that time. Then only certain scripts could have the token-trigger to get the guard to give the player the key.

"Bad Day... F**K it!" -Stephen Baldwin (Usual Suspects)
0

Share on other sites
From everything posted here, here's my take with both points from others as well as myself.

Most importantly, I'd have to say that such advanced AI would be too hard to make or not perceived by the players as it should have been by the designer (as always).

Firstly every message should be categorised and given properties.
Not just properties like their lifetime before being conveniently forgotten. And NPCs don't forget things that fast so let's not talk abuot limits of computers yet. Messages should have the follwing properties:

1) Sensitivity - Secret, Private and Public
2) Link (or thread) - some news are updates of others, therefore new information should overwrite their old ones and for this to happen, they'd have to have a thread.
3) Belief in information - how much the NPC supports this piece of information.

Secondly, each NPC must have a list of close friends, normal friends and the-guys-you-gossip-with. This determines the information that they exchange with each other. Being a close friends, they may exchange secrets with each other unless the game does not allow it so.

Thirdly, each NPC must have a list of favourite activities, or rather, regular activities. And a time frame shall be associated with each activity. The venue must also be included. Other things might affect it like the NPC does not have enough gold coins to order beer at the local pub.

Lastly, each piece of information must have a question. What I mean is that whatever the NPC knows, the player can ask. But the player may have other questions that the NPCs do not know of and thus they may have a default piece of information. It should say something like 'I do not know'. But when it learns more, it get overwrited and he might say something else.

Okay now that everything is said, I can then proceed to write how everything fits in together which none of you have been successful at. I will attempt nonetheless.

Since each NPC has regular activities like work, NPCs in their immediate area are public figures to them and all of them excahnge public information which they keep. They will compare their information and see how much belief they each have and thus it will determine whether new information overwrites the old and what information is passed around. Or it might transform it. Also, they take into consideration the honesty and charisma of the NPC giving them the information. Maybe, if everyone says so, then the NPC might submit to all and believe what they say. Again, this depends on their belief in their information.

Also the idea that each NPC draws their basic knowledge from a database is very good. But can the information in the database be altered? If it can then, how fast can the information be spread throughout the world.

And missing are other details. Information do not only be gathered from other people. They are gathered from events, posters and the internet (okay, maybe not in a fantasy world, but you get the idea). How do they get the information. The events themselve must store a "message" that is passed to the NPCs who witness it.

This is such an old post but it still is valid. But still, the limits of today's computer might still hinder such a game. There could be shortcuts and everything and simulating such a "interactive" would be costly to the CPU. Interactive indeed!

However, even if the game succeeds somewhat, there is still a chance that the player messes it all up and is obliviuos to the living and almost breathing world that his character is in. As mentioned earlier, the player almost always do not think like the designer and thus difficulty arises.

Also, this just came to me. No one has talked about how NPCs react to information passed to them. You might have talked about bread-wielding bakers attacking dragons but how does it work?

Edited by - Darkor on June 8, 2001 9:40:28 AM
0

Share on other sites
quote:
Original post by Darkor

Also the idea that each NPC draws their basic knowledge from a database is very good. But can the information in the database be altered? If it can then, how fast can the information be spread throughout the world.

The concept is that the database is how the world state vector is stored at any time. Think of any current game. At any time there is a list of objects currently in the world and information regarding their individual states. The game update cycle includes information about how to update the state of each object (or at least each dynamic object). All of this can be stored in the same database. It is just that a part of that database is actually a knowledge base that contains a set of logical propositions relating to the objects in the world, the relationships between them and the way things change. A part of the game update cycle is to compute the affect on the knowledge base of any changes in the world during the last update and then any changes in the world that the knowledge base infers.

For instance, NPC_Baker_3 is passed information that his daughter has been eaten by a dragon. The knowledge base may have a particularly obvious proposition saying that "If X knows that X's_daughter was eaten by a dragon then X gets extremely angry and upset". If we add the information "NPC_Baker_3 knows that his_daughter was eaten by a dragon" (because this information was given to NPC_Baker_3 during the update cycle) then the logical conclusion is that NPC_Baker_3 undergoes a state transition to "angry" and "upset".

Our database can have other rules that govern the world. For instance, you could include Newton's first law, "Every object will continue to move at it's current speed and in it's current direction unless a force is applied to it". This wouldn't be the most efficient way to update those objects that do, or do not, have forces applied to them... but you get the picture (I hope)!

quote:
Original post by Darkor

Also, this just came to me. No one has talked about how NPCs react to information passed to them. You might have talked about bread-wielding bakers attacking dragons but how does it work?

See above. Basically motivations are hidden within logical propositions.

I hope this stimulates a few more ideas or comments.

Cheers,

Tim

Edited by - Timkin on June 12, 2001 10:50:38 PM
0

Share on other sites
quote:
Original post by Timkin

The concept is that the database is how the world state vector is stored at any time. Think of any current game. At any time there is a list of objects currently in the world and information regarding their individual states. The game update cycle includes information about how to update the state of each object (or at least each dynamic object). All of this can be stored in the same database. It is just that a part of that database is actually a knowledge base that contains a set of logical propositions relating to the objects in the world, the relationships between them and the way things change. A part of the game update cycle is to compute the affect on the knowledge base of any changes in the world during the last update and then any changes in the world that the knowledge base infers.

For instance, NPC_Baker_3 is passed information that his daughter has been eaten by a dragon. The knowledge base may have a particularly obvious proposition saying that "If X knows that X''s_daughter was eaten by a dragon then X gets extremely angry and upset". If we add the information "NPC_Baker_3 knows that his_daughter was eaten by a dragon" (because this information was given to NPC_Baker_3 during the update cycle) then the logical conclusion is that NPC_Baker_3 undergoes a state transition to "angry" and "upset".

Our database can have other rules that govern the world. For instance, you could include Newton''s first law, "Every object will continue to move at it''s current speed and in it''s current direction unless a force is applied to it". This wouldn''t be the most efficient way to update those objects that do, or do not, have forces applied to them... but you get the picture (I hope)!

See above. Basically motivations are hidden within logical propositions.

I hope this stimulates a few more ideas or comments.

Would Timkin, or anyone else here, for that matter, care to comment on this topic which is essentially an exploration of the mechanical details of such a logical system.

Despite some overly pessimistic individuals and uninitiated ones giving feedback on the topic, it is a pretty worthy discussion. And I believe I have devised a classification method to determine the nature of particular axioms (recursive, etc.) and construct optimized data structures for the axioms which enable the system to not fall into the trap of a recursive graph search.

The system being discussed is first order logic with functional unification, enabling event or situation calculus for planning, truth maintenance, logically consistent beliefs, and efficient inference.

0

Share on other sites
For those of you who haven''t read my article on Badcontent, check it out.
Here''s the link Next Level 2. This article pretty much sums up my stance on conversation systems, and I believe that it is completely implementable (well, at least I''ll find out when I try to implement it). It''s similar to previous posts (global information, memory, etc.) The actually interface would be a search engine similar to a "inverse parser", combined with the graphical interface I discuss in the article.
0

Share on other sites
quote:
Original post by bishop_pass

Would Timkin, or anyone else here, for that matter, care to comment on this topic which is essentially an exploration of the mechanical details of such a logical system.

Okay, I will first be honest and admit that formal logics are not something I know an awful lot about. I was an applied mathematician before coming into AI. (I was also heavily into physics and philosophy as an undergrad!).

However, I think I understand what you are asking. You want to solve the equivalent problem of determing whether or not there exists a path between two nodes in a bidirectional tree structure, that is not fully connected (i.e., it is not the case that all nodes in one tree map to nodes in the other). Correct?

This is out of my field however I might be able to run your solution by a couple of people (we have a great lunch time discussion group that meets each week. I know that one of the group members has some expertise in this area.) Would you mind if I discussed it with them?

Cheers,

Tim
0

Share on other sites
Timkin, yes, that is basically the problem: graph search. I believe this problem is considered NP complete, or whatever. NP stuff is NOT my field of expertise. Anyway, with heuristics, theoretically it can be fast *most* of the time.

Yeah, go ahead and ask your associates, that would be great. However, I am not looking for the type of answer which says: "Oh, that problem can''t be solved reasonably, give it up." I would prefer an answer worded more like: "Yeah, that is a tough problem, but some of the better results are being acheived by such and such methods..."

0

Share on other sites
quote:
Original post by KaneBlackflame
Hey, I had to try it) but I hope to start a new community in a few weeks with some expanded morals I have been adding. Dynamic AI can be made. I hope the age of static NPC''s will be over soon.

I would love to see some more information on this, perhaps a demo or a web-page detailing what you did - keep us posted!

This sounds much like the necessary foundation for a "living" world

- However, what we probably need to do with todays technology is to "simplify" this into something that doesn''t acctually modell every small action/decision of every mobile (unless we are talking of a very small world) - Leaving us processor time to handle players, more important decissions, such as knowledge management, graphics (if single-player scenario) or connections (in multiplayer scenario)

- However, these "small" decissions usually impact the bigger events in the world in some way - so we probabbly don''t want to ignore them.

Any ideas on how to generalize these everyday things such as suppy and demand on food and other stuff and breeding etc?

cheers,

J
0

Share on other sites
Correct me if I''m wrong, but, didn''t Wizardry 4 have something similar ? If I remember correctly, the game allowed the player to type text into into a textbox while interacting with npcs and the program would then try to find ''meaning'' in what the player typed. This was of course, a very primitive form of what you are talking about. Also, I believe Wiz4''s npc interaction system was keyword based.
0

Share on other sites
Ok, I kind of forgot those outside my circle do not know exactly what a Neural Web is. A Neural Web is my attempted improvment upon a NN. There are no "hidden" layers in webs, as I create them node by node by hand with a SDK I built. I can add trees of nodes and train them, but I never refer to them as hidden or outside my area of direct influence. All nodes or groups of nodes are named. i.e. "Sadness" or "Hunger" In many cases, end results are fired back at inputs to create a constant flow of life in a network. This ensures a kind of "for every action, there is A reaction" situation, keeping the entities active. Also, some nodes cause functions to be called, imitating a form of motor neuron. With many long nights of tedious node planting, weight calculating, and hours of testing, you can very successfully implement my design theories to create entities that will function and interact with each other in a strictly controled environment. As far as implementing this in a game or other application now that must function in real time, I think we are a ways off from that in computational power. The only thing I have come up with to semi solve this problem is a form of layer detail. Alow me to explain : A player is in a town. The player cannot see anything in the next town, so all movements and actions there can be approximated, i.e. assume that everyone successfully completes their daily routine. This way, we free up a lot of processor time when approximating the rest of the world, allowing more time to properly simulate the current area or town, as well as simulate any important events going on elsewhere, such a plot lines and feuds. I hope that came out as clearly as I had hoped.

I would love to post a site, but I don''t have the time, and the only content I can provide is thesis statements, technical notes, and LOT''s of logs. I would rather wait till I have my demo working again before I post a zip file of my stuff. I would love to hear your comments and thoughts for improvement.
0

Share on other sites
Hail and well met! Sorry for posting after so many others but I had an idea This may have been answered or mentioned already but I don''t have time right now to read all the replies and I''ll forget by later. What if you used your idea, the inverse parser. Example then I''ll explain:
You: How do I kill a goblin quickly?
***I realize this isn''t a normal question but *shrugs* oh well
The guard may have a few responses, such as:
1-To kill a monster enter attack mode and double click the victim
2-If you kill a goblin you may get a bounty
3-A sword will kill quickly whereas a mace will kill slowly
-----------------------------------------------------------------
Now the guard would be "confused" so he can say that he isn''t sure what you mean and will list all 3. The user will select what he wanted to hear. The game will remember that response. That is the key, ''specially if its a MMORPG. It will save all the responses to that question and the guard will begin to respond with the most common answer. It would seem like our virtual friend is learning

Hope that helps, or sparks somebody''s interest

Pinch me... See if I''''m still asleep... *pinch* Owe! Mother f*****... Yep, you were still asleep.
0