🔒 Locked

Yet Another NPC AI thread

Started by Diragor Jul 28, 2000 at 3:26 PM 28 replies 9.7k views

Original Post

Jul 28, 2000 at 3:26 PM

Looks like the last thread kind of wrapped up at the end there, and I want to get some opinions on a kind of new idea related to what was discussed in that post. I don''t know if that has already been done, but I haven''t heard anybody talking about anything quite like this. I haven''t put any of this to practical use yet, I''ve just been thinking about it and discussing it with someone by e-mail. The idea is a system for NPC behavior, probably most compatable with an adventure game or RPG. It''s pretty much like the "needs" stuff discussed in the previous thread, only more dynamic and complex. The system is based on something I guess you could call Priority objects. A Priority data structure would include information about a state of being, possible actions related to that state, and some kind of numerical expression that represents the relative importance of this Priority. Each NPC would have a list of priorities, starting with a "default" priority that gets carried out when nothing else is happening (eg. "whittle wood"). Most NPC''s will always have a self-preservation priority that will shoot to the top of the list in certain circumstances. In a given situation the priority list will be traversed from top (most important) to bottom, and each priority will have a chance to determine the actions of the NPC. Each priority will also have a chance to modify its own importance based on the situation. This idea can also use the scheduling ideas from the last thread to introduce new priorities to the queue. Here''s an example, using completely arbitrary numbers where necessary. Our NPC is Bob. It''s about 9pm and Bob is sitting in a pub having a drink. We go through the priority queue and the first time we go through the list and reassign priorities. The first priority is "get drunk" with a value of 15. Well, he''s already drunk and the more he drinks the less he cares about getting drunk. This priority has been decreasing for an hour or two and now it just removes itself from the list. This task is basically complete. Next in the list is "go home", which becomes more important the later it gets, so it increases its importance to 20. Bob''s personal schedule inserts a "sleep" priority in the queue at 9pm after he''s been awake for 16 hours (or something), and since he had a busy day and got drunk this priority will start at 10. After going through the list and assessing all of the values, now we start at the top again and act on the priorities. The top priority now is "go home", so we call the only associated action and Bob starts walking home. The action associated with "go home" will also look for faster modes of transportation, evaluating how much money he has and possibly checking against the value of an "actionless" priority such as "save money". There are obvious problems here and tricky situations to work around. Numeric values for the priorities will have to be carefully calculated. In the example if Bob is far enough away from his house then the calculations should have the priority of sleep overtake the "go home" priority, so Bob camps out or something. The self-incrementing and decrementing priorities can make for some very realistic behavior. For instance, the value of the sleep priority becomes higher and higher until you sleep, and while you''re sleeping it will decrease. In the morning the schedule (or alarm clock or something) will insert a "get up and go to work" priority of some sort, with a certain value. If you waited long enough to sleep then that priority will still be greater than the "get up" priority and the NPC won''t get up. Sooner or later though, the increasing "get up" priority will overtake the "sleep" priority and the NPC will get up. Priorities can be used to describe just about any possible situation and related actions. In combat priorities would include "kill enemy", "preserve self", "protect friends", all with changing values based on the situation (your health, the enemy''s might, your friends'' health). So, any comments, thoughts, suggestions?

dwarfsoft

Jul 28, 2000 at 4:36 PM

That is a great idea, and I think that it could work rather well. The other thread didn't wrap up, we all just ended up being preoccupied with our e-mailing list at http://www.egroups.com/group/NPCAI/ and haven't really discussed anything over here since. Your priority queue would need a full study, need to have increment and decrement values stored with it, so one need can increase faster than another. I am thinking that some would need to follow a function such as x^2 or somehting. I think this effect might still seem the same as if you have most values decreasing at the same time as another that is increasing.

It's a little too early in the morning for a formal oppinion, so I am just churning out ideas at the moment

. The effects of this system could be quite believable, maybe you should post this to our e-mailing list (NPCAI@egroups.com) so that the rest of the crew can make their voices known

-Chris Bennett ("Insanity" of Dwarfsoft)

Check our site:
http://www.crosswinds.net/~dwarfsoft/
Check out our NPC AI Mailing List :
http://www.egroups.com/group/NPCAI/
made due to popular demand here at GDNet

Edited by - dwarfsoft on July 28, 2000 5:38:00 PM

Nazrix

Jul 29, 2000 at 11:02 AM

Diragor,
That's a really great idea and has a lot of potential.

dwarfsoft,
Yeah I agree...some of them will have to jump up in the list faster than others...like eating and drinking would rise faster than most others...

Plus, maybe the environment could change the things on the list. Like, if it suddenly starts snowing, then the NPC may put "find shelter" on the list...

Also, it could add a lot of personality to each NPC. Like, Bob may have "getting drunk" high on the list while another NPC has "getting drunk" not even on the list. Obviously, Bob is a big drinker.

Very nice idea

It's a lot better than a hard-coded schedule like "go here at 9:00 and here at 10:00"

Although, do you think that there should be some sort of scheduled capabilities added?

Like, if the NPC had to meet the player at a certain time, you could put the meeting very high on the list...but I don't think that you could guarantee that the NPC would get there at the right time. The NPC then may be late which would actually make things more realistic, but may be annoying...especially if the NPC is a few hrs late.

For instance, if the NPC is supposed to meet the player at a certain place. So, that is put into the list at pretty high priority. On the way, the NPC gets hungry. Then the "eating" priority would probably be higher than the "meeting player" one.
Then, what if the NPC does not have food with him/her. Then, the NPC has to stop somewhere to get food, and is 1 or 2 hrs late (game-time) to meet the player. I suppose it depends on the game itself (how loose and non-linear it is) whether that's ok or not..but it could be a problem.

"The road of excess leads to the palace of wisdom." --William Blake

"The road of excess also just ends up making me tired because I'm too lazy" --Nazrix

Edited by - Nazrix on July 29, 2000 12:04:08 PM

Edited by - Nazrix on July 29, 2000 12:12:04 PM

kressilac

Jul 29, 2000 at 11:17 AM

Its not too far off to take those needs and transform them into dynamic quests for those players that want to help out the NPCs. Again this applies to RPGs but could be used in other types of games as well.

Kressilac

Diragor

Jul 29, 2000 at 4:54 PM

Yes Nazrix, scheduling is part of the idea. It gets a little complicated when it comes to that, though. Each character would need to keep his own personal schedule and there probably need to be a global schedule as well. The schedules, environmental effects and interactions with other characters could place priorities in a character''s queue.

Here''s an example that kind of incorporates all of those effects. An NPC (how about Bob again) meets another character in the morning and agrees to meet the character later that night at 9pm. The result of that interaction is a new item in Bob''s personal schedule that will insert a "meet person" priority in his queue a certain amount of time before the meeting is suppsoed to occur (to allow travel time, which is another matter). Depending on the importance of the meeting, a certain value will be assigned to that priority. Let''s say it''s a matter of fair importance, and we''ll give it an arbitrary value of 200. So Bob goes about his business for the day, and he has a lot of important work to get done. His "work" priority will stay at a high value until the work is completed. Let''s say the work value is 150, less important than the meeting but more important than everything else. Around 6pm Bob''s schedule inserts an "eat" priority (based on the calculated time since his last meal, not the clock time), and since it''s just dinner time it will be a fairly low priority because he won''t starve if he eats a little bit late. Let''s say the "eat" priority starts at about 40. The "eat" priority keeps increasing as time goes on, but his work priority stays at 150 until it''s complete.

Just before 8pm, Bob''s work is finished and his "eat" priority is getting up over 100, so it''s definitely the most important thing now. Bob runs across the street to get something to eat. If you want to micromanage here, you could always have a permanent "eat" priority in the queue and just have it reduce as food is consumed and increase by small amounts otherwise, but we''ll just say that he eats and that priority is taken out of the queue. Just as he finishes eating, some rowdy drunks start messing with him. Bob tries to avoid conflict, but these guys are hell bent on getting into it. He''s ushered outside for an all-out battle. As soon as the conflict starts, priorities such as "self-preservation" and "defeat opponents" (or whatever) get stuck in the queue at super-high priorities. There''s a whole mess of priorities and logic going on during something like this, and it could be handled in a number of ways, but anyway... in the middle of the battle Bob''s schedule inserts the "meet person" priority at 200, and absolutely nothing is done about it because of the huge importance of defending himself against injury and death. The importance of the meeting could increase as the time of the meeting gets closer, then when the fight ends he could possibly take certain steps to get there faster. Scheduled activities could also have a value that represents how long a priority will stick around after the scheduled time has passed. For instance, let''s say the fight ends half and hour after the scheduled event is supposed to take place, but the event is still in the queue, so he''ll go but he''ll be late. But if a scheduled event has a lapse time of one hour, then one hour after the scheduled time passes it will be removed from the queue whether the event has taken place or not.

Oh, and if you were wondering what happens next, Bob bravely vanquishes his enemies and makes it to his meeting with seconds to spare

. Hooray for Bob! Oh damn, I meant to have a snowstorm keep him from reaching his meeting to demonstrate weather effects. Oh well, you get the picture.

dwarfsoft

Jul 29, 2000 at 8:27 PM

I have to say that this system is BRILLIANCE. There are obviously bugs that need to be ironed out of it (not that I can think of any off the top of my head

) but there are bugs none-the-less. I have forwarded this to NPCAI and so I will see what the others have to comment on your idea. The idea is sooo simple and yet so effective. I am just wondering at what increment/decrement abilities can you set.. ie, are the incrementing and decrementing of priorities variable and how would this be implemented. I am thinking of Character scripting (not as in the old scripting sense) where the priorities list that may interest that character are listed in their script and all of the variables that modify it (when and by how much) could be stored in their as well.

Hmmm

Diragor

Jul 30, 2000 at 1:52 AM

I might actually get into starting some actual code using this stuff tomorrow, it''s getting really interesting.

I''m sure little bugs will crop up in the system but the only real issue I can think of so far is just balancing priorities. The inc/dec system for priority values just has to be carefully thought out so nobody ends up stopping to eat in the middle of a battle or something. As far as implementation goes, I''ve got a bunch of ideas but I''ve talked enough already

. I think I''ll try a few things before I type any more novels on here.

dwarfsoft

Jul 30, 2000 at 2:36 AM

One way to get around possibilities of the eating in battle glitch would be to have everything have a realm of 1000 points in its priority (we are using longs here ppl

). Basically, make it impossible for eating to increase more than xx and if it does then the PC would probably have starved to death by that time anyway. For the battle thing, have the priority at about 1000 times higher than the eating priority (we just want to disperse it to make it impossible for it to happen) while there is still anything hostile in the area. If it is only semi-hostile then you could probably halve the priority.

Basically I think there should be FLOOR and CEIL values for the priorities, ie, exception handled when it goes over CEIL (for eating: starvation, drinking: dehydration, etc.) or if it falls through the FLOOR then remove it from the queue.

Hope thats some food for thought... if the priority isn''t through the roof already

Epoch

Jul 30, 2000 at 4:43 AM

Another thing which you might need to have is linking between
each attribute.
For example ( I''ll use Bob again), Bob needs to quickly get to his dying Uncle who''s filthy rich and who hasn''t yet given Bob the pin number to his bank account. Unfortuantely, Bob''s uncle
lives in another city, which is eight hours drive from where he is.
The priority to reach his uncle is something like 200. However,
he''s just finished the night shift and has been awake for 16
hours, so he''s pretty tired, and his tiredness is a priority of 20. Of course his uncle is more important, so he ignores sleeps
and its priority increments as time passes.

Now, I find if I stay up later than I should i start to get hungry. So, his lack of sleep should affect his hungriness.
He will be more hungrier than usual because he needs to replace
the energy needed to stay awake. So for every hour the sleep
attribute will add a modifier to hungriness..

dwarfsoft

Jul 30, 2000 at 5:33 AM

The hunger should be based on the ammount of activity of a user, it could also be in the priority queue, but self modifying it, it decides what is currently happening (how much activity) modifies its own priority to suit and modifies other priorities (such as tiredness and hungriness). Seems fairly simple to implement, and of course some of the elements in the queues are going to be linked. It is simply impossible to implement completely arbitrary elements and expect it to work

.

I think that the tiredness priority is rising, though the hungriness one has faded because of beloved skittles

.

-Chris Bennett ("Insanity" of Dwarfsoft)

Check our site:
http://www.crosswinds.net/~dwarfsoft/
Check out our NPC AI Mailing List :
http://www.egroups.com/group/NPCAI/
made due to popular demand here at GDNet :)

Ingenu

Jul 30, 2000 at 7:15 AM

I like the idea, but remember it won''t be able for some of us.
I think it can be included in the NPCAI as an optionnal module, or the functions can be set public for modifications by the Game using the NPCAI code/library.

What ever I''ll think about the kind of stuff we can give the NPC to make it more human like...
Would be usefull for my game.

-* So many things to do, so little time to spend. *-

dwarfsoft

Jul 30, 2000 at 7:24 AM

Good to see you back Ingenu, NPCAI is supposed to have modules that can be switched on and off (ie, something I posted on one of our earlier threads) and therefore if it is just useless for you, you can opt to not have it

I can definitely say that the priority-schedule combination would work nicely into my game. hehe... it seems like the entirity of my game is being thought up here at GDNet, mainly because I type my ideas and get feedback as well as theive other peoples ideas

Nazrix

Jul 30, 2000 at 4:51 PM

I really like this idea a lot. It would work well in my current game as well.

Basically I'm thinking that the more need-based actions would be without a schedule (defending himself, eating, finding shelter,sleep), then the actions like meeting someone or going to work would be on some sort of schedule as well as having a priority.

Diragor, what exactly did you mean by a global scheduling system? Just curious....

Do you think it should check for a new action every frame or maybe every so many frames? Like maybe every so many frames it sees if the current action is still the highest one on the priority list. If not, it would change actions.

"The road of excess leads to the palace of wisdom." --William Blake

"The road of excess also just ends up making me tired because I'm too lazy" --Nazrix

Edited by - Nazrix on July 30, 2000 6:22:43 PM

dwarfsoft

Jul 30, 2000 at 5:09 PM

quote:
Original post by Nazrix

I really like this idea a lot. It would work well in my current game as well.

Basically I''m thinking that the more need-based actions would be without a schedule (defending himself, eating, finding shelter), then the actions like meeting someone or going to work would be on some sort of schedule as well as having a priority.

As stated earlier, I think that the actions (such as meeting someone,.. work etc) should kick in at a required time using the priority queue. The time that such happens would be based on distance from destination (if applicable) and importance of priority and time to be at the destination.

quote:

Do you think it should check for a new action every frame or maybe every so many frames? Like maybe every so many frames it sees if the current action is still the highest one on the priority list. If not, it would change actions.

It should be updated when the processor has free time. At every loop if the game has time to do updating (based on time from last update) then it should do it, otherwise it should do the low-end AI stuff

. It would still work on the "after XX frames" thing as well, or maybe a combination of the two. But it is rather early in the morning

DungeonMaster

Jul 30, 2000 at 5:22 PM

I think this need system should be very detailled to simulate acuratly NPCs, this would be lot of work for the CPU.
Moreover, the priorities will need to be thought carefully if you dont want to be surprised too much. Like your character becoming too hungry in a fight...

Still, this would give more life to your characters.

I think that i will stick to schedules for the time being. The planification part will only have to inserts actions at a specific time. Less CPU time in my mind.

"Between the time when the oceans drank Atlantis and the rise of the sons of Arius there was an age undreamed of..."

dwarfsoft

Jul 30, 2000 at 10:52 PM

Well, to combat the "hungry in battle" syndrome, you simply put FLOOR and CEIL values in. That way, certain priorities will never go over their CEIL value, and if you calculate it properly - the CEIL value would cause the NPC to die of hunger (left it FAR too long). The variables are:

START_PRIORITY for specifying what it gets inserted into the list with
FLOOR for the lowest priority value before it is wiped off the list
CEIL for the highest value before it causes an exception
CEIL_FUNC which handles the exception listed above
TIME_DELAY which is the period of time between any two updates
LAST_UPDATE is the last time it got updated
UPDATE_PRIORITY which does the updating

Thats all I can think of at the moment. I am sure that there are more that could be added to this, but I think that is the fundamentals behind the system

. It should be fairly understandable, but if you have any quibbles then please let them loose here

Cadet Random

Jul 31, 2000 at 3:01 AM

On priority value generation...

Let''s assume that there are 2 basic needs

1) Stay Alive
2) Maximise Happiness and (or possibly pleasure) Minimise
Sadness (or possibly pain)

Now, these 2 needs are both "continuous" needs, ie, they will never be "fulfilled" as such, rather they are things to continually work towards

let''s give some example priorities, say, (1) priority 1000 and (2) priority 500. These can be varied character by character, but they will remain constant generally (well, changing these values will make a broad character shift, ie, they''ll be more willing to die or wanting to find happiness more)

These will both have subneeds, and they in turn will have subneeds, etc. All subneeds'' priorities will be proportional to the parent need.

1 is a "prevention" style need, ie, prevent death. Therefore, the priority of child needs will also be proportional to the probability of death occuring soon.

Child needs that are also prevention style needs, eg "Stay away from hostiles" (or prevent proximity to hostiles if you prefer) can have a "parent triggering factor", f, from 0-1. This is the probability that this need being compromised will lead to the parent need being compromised.

The final factor is the probability of this need being compromised, C. This can either have a value determined by the game engine, or if the need also has subneeds, this can be given a value of 1 for the purposed of getting a Priority value to calculate child priorities.

So, thus far, if Pp is the Priority of a Parent need, and Pc is the priority of the child prevention need:

Pc = Pp * f * Cc

"Maximise" style needs should weight the priorities of all different subneeds to pursure by the increase in happiness it will bring, D.

Also, the priority should be proportional to the time it will take to fulfil the need, T, and the probability of success, S.

So,
Pc = Pp * [Dc / Max(D)] * [Tc / Max(T)] * [Sc / Max(S)]

Where all the maxima are taken for the subneeds of p.

Thoughts?

Sam
Space Cadet''s DJ Random, Thinker, and Geek at heart.

dwarfsoft

Jul 31, 2000 at 11:08 PM

As it seems that nobody is responding to you Cadet Random, I have to say congrats for the math. Nobody so far has even really thought about how to go about doing it (at least, I hadn''t really thought about the implementation of it

). Anways; the subneeds idea is good, but I can see it getting fairly complicated. And I am sure at some stage someone is going to suggest that those sub-needs also require sub-needs (They always do

). As yet I haven''t really tried to run the math through my head, about f though (parent triggering factor), how exactly does this have a bearing on the game and all that... I think it needs to be elaborated a little furthur. What I don''t understand is if you have subneeds in the queue, would you then NOT have the parent in the list or HAVE the parent in the list?

Maybe you explained this already, but I obviously missed it

Cheers,

-Chris Bennett ("Insanity" of Dwarfsoft)

Check our site:
http://www.crosswinds.net/~dwarfsoft/
Check out our NPC AI Mailing List :
http://www.egroups.com/group/NPCAI/
made due to popular demand here at GDNet :)

Cadet Random

Aug 1, 2000 at 4:23 AM

quote:
Original post by dwarfsoft

1) And I am sure at some stage someone is going to suggest that those sub-needs also require sub-needs (They always do ).

2) about f though (parent triggering factor), how exactly does this have a bearing on the game and all that...

3) What I don''t understand is if you have subneeds in the queue, would you then NOT have the parent in the list or HAVE the parent in the list?

(1) oh yeah! the architecture was intended to incorporate an arbitrary degree of needs, until mapping needs to actions was nonsensically easy

I''ve posted something similar on our egroup (I''m Sam - random@chello.co.nz, in case you didn''t pick that up)

(2) Well, it''s like, if there''s an enemy near by, there''s a _chance_ you will die, but it''s not 100%. let''s say there''s a 10% chance that an encounter with a hostile would result in the NPC''s death. f would then be 0.1. It''s included into the equation to reflect that, if say there was an 80% chance of an encounter with a hostile leading to death (cos the NPC is weaker than the 10% one), the priority of "stay away from hostiles" would be greater, 8 times greater. And thus, our NPC is much more cowardly

(3) Ummm, I don''t think i made this very clear cos I''m not quite sure

In a sense the act of spawning subneeds is how the architecture "fulfills" the needs, so for the purposes of action selection, they wouldn''t be on the list. But, the whole hierarchy would be kept track of for learning subneeds / changing their parameters.

Sam
Space Cadet''s DJ Random, Thinker, and Geek at heart.

dwarfsoft

Aug 1, 2000 at 4:38 AM

yeah, I did know who you were on NPCAI

. It was kind of obvious

.

Anyway, working out the f value, would that be based solely on strength/defence stats or levels (yay for those who powermaxx

.. Powermaxxing NPC''s oughto be fun) or would there be distance taken into account (the closer they are, the furthur you want to be away).

I am thinking that to make this generic, that the requirements that the priorities are based on are going to HAVE to be variable to allow for a difference between danger and hunger (I spose distance may still be useful in hunger scenario - too far away etc. but strength wouldn''t), so the function that you describe may need to be massively variable (allowing for more numbers to be plugged in, or less). Or maybe they could all be based on sub-needs and the result of the sub-needs for this makes the difference.

Is this what you were meaning about sub-needs? Such as under the parent need "Keep me safe" has child need "Keep distance from baddie" and "Watch out for str of baddie" and the subneeds are mult''d together using f to produce the parent priority?

I think that I could possibly understand this now! YAY!

Now to shoot me down, aim your rifle and fire

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.