I''m looking for some thoughts on my A.I. system. I want to see if anybody has any ideas for improving or expanding this. For the purposes of this post, I am concerning myself only with large-scale A.I., meaning the long term plans of my NPCs. What I''m not concerned with is stuff like NPCs deciding "I''m out of bread so I''m going to the bakery". I am also excluding NPC-PC interaction from my definition of large-scale A.I. The easiest way to describe my A.I. system is that all characters compete for resources. NPCs are motivated by their own personal desire for (a) specific resource(s). The aquisition of one resource always requires the possession of another resource. If a character does not possess the required resource to obtain his desire, he checks to see if he has the means to acquire the required resource. I call this checking for the means to aquire successive intermediate resources a need chain. I have an expanded definition of "resource", as you can see below, so that characters with little or no possessions aren''t necessarily screwed, they may be able to use some personality attribute to eventually get what they want. Here''s what the resource hierarchy looks like: _ _ Stores (all resources which take up physical space) _ _ _ _ military troops _ _ _ _ _ _ militia _ _ _ _ _ _ mercs _ _ _ _ land _ _ _ _ _ _ Nation, Province, City* _ _ _ _ _ _ estate** _ _ _ _ liquid (easily added to and subtracted from) _ _ _ _ _ _ purse (wealth in coins) _ _ _ _ single discreet objects _ _ _ _ _ _ character*** _ _ _ _ _ _ weapon _ _ _ _ _ _ precious gems _ _ _ _ _ _ misc items _ _ Innate (personal qualities/attrributes) _ _ _ _ Body parts (may have at least one additional "owner") _ _ _ _ _ _ ear _ _ _ _ _ _ heart (desire for a heart indicates infatuation) _ _ _ _ _ _ head (desire for a head indicates a desire to kill) _ _ _ _ prestige (sum of local land holdings, local rep, and wealth) _ _ _ _ charisma _ _ _ _ poltical office _ _ _ _ sword arm (indicates character''s over-all fighting ability coupled with weapons currently in possession) *Desires for nations, provinces, and cities are reserved for entire civic populations, and such a desire indicates impending war. **Any built-up land, such as a shop or home, or property of exceptional value, such as a mine. ***Desire for a character equates to a desire to capture/kidnap Heres a sample need chain: Desire to command a miltia requires gaining a specific political office. Gaining the office will require the ear of the official responsible for appointing the office holder. Gaining the ear (requesting and receiving an audience) of said official requires a local prestige above a certain minimum value. Local prestige could be gained by buying a large estate (which requires a purse of a certain value) or perhaps by capturing a wanted criminal (which requires a sword arm above a certain value). Let''s assume that the character has enough money to buy a sizable estate. His plan is then to work backwards through the chain. He buys the estate, automatically increasing his local prestige, which he uses to gain an audience with the official in question. Depending on factors such as the official''s relationship with the current office-holder, the character may or may not receive the appointment. It is not guarnteed that a character will ever have the means to obtain any one desire, but each character will have multiple desires, so hopefully at any one time they will be able to find something to work on. Also, as time goes by and a desire remains unfullfilled, the desperation for that resource increases, which has an effect on the make-up of the need chain. When a resource is queried as to what is required to obtain it, it takes into account the desperation of the character (as well as one or two other personality traits) when determining what resource to return as the gain means. For example, a violent character might use his sword arm resource under the same circumstances where a non-violent character would use a purse resource. As desperation increases, it becomes more and more likely that a sword arm is required (desperate character resorts to violence) or that charisma is required (desperate character resorts to begging (maybe I should rename "charisma" to "tongue" or something similar)) What I''m asking for (besides general comments/critisism) is if anybody sees novel or unique ways of constructing needs chains using the resources I have listed (or by expanding the resource list). Although I consider the sample need chain I provided to be fairly complex, most of my need chains consist of the character immediately using either money or violence to obtain what he wants (in boring single-link need chains). I think the more complex the need chains can get, the more interesting the game can be. If the player knows that most NPC actions are just a prelude to some bigger but unknown goal, it can''t help but make the experience more interesting. Thanks in advance, Sean

Hmmm... I''m going to move this to the AI Forum, as it seems more appropriate.

--------------------
Just waiting for the mothership...

Seems like quite a complex system. I would have two suggestions - both of them abstract enough that you may well tell me I have no clue what Im on about. Fair enough - I probably have none. Still, in absence of other replies, heres mine:

1) Your system is complex. It has agents constructing complex need chains, and making many ''high-level'' decisions. I think dealing with the AI will get very hairy when you get down to the low-level AI stuff like ''move there'' ''take this'' ''do that''. Lots and lots to consider. What if the agents did not nessecarily need long ''need chains'', but instead just had a multitude of needs ranging from immediate to long term.

Then, the agent for example gambles for his need for money. Winning a large sum, the agent realises that with money he can buy food and satisfy his urgent hunger. Once done, it realises that without any other needs that require money, the money can be used for a need which was previously not possible -- buying entrance to a select club. Once there, the agent spots an influential individual. The agent then identifies a need for being influential (and thus needing to know other influencial agents), and walks up.

Very ad-hoc. Benefits of such a method is there is no long term planning as such - only long term needs. Some of which can die off in time as the agent ''loses hope'' or interest. Thus culling the list a little. The reliance herein is on emergent behaviour running its course and the die of chance rolling numbers that will make the agent appear more intelligent than it is.


2) Keep your current ideas, but be very sure to construct a good diagram (UML maybe for relationships and arrangements?). From this, write *simple* classes with easy to use interfaces. I dont know how much coding you have done before, but when developing a complex system, unnessecary complexity in an interface just multiplies the needed complexity in the other components. In a recent little bit of AI I coded, an AgentClass had an attached AgentPlanner which made Plan constructs that were given to Agents to follow. Keeping the interfaces simple made the task complete in much less time than I had anticipated. Furthermore, it is easily extendable.

And in a final few words - try figure the ''core'' backbone to your system and get a simple version of it in place and written with a good programming style and interface. Then go out for all the details. Tackling a large system as one big unit sees it taking much longer to get to completion, if ever, than it needs.

*yawn*. Ive even bored myself! Goodluck!

regards,

GeniX

www.cryo-genix.net

Take a look at BDI agent architectures. BDI is an acronym for Belief_Desire_Intention.

It''s pretty interesting stuff and may be just the thing you need. Here''s a link to get you started:

http://www.csd.abdn.ac.uk/~tnorman/publications/atal95/bdi.html

Also it may be worth having a look at Bayesian networks. They are not that easy to get your head around (well, that is if you have a head like mine ;0)) but are a very useful tool to have in your belt.

http://www.cs.berkeley.edu/~murphyk/Bayes/bayes.html
http://www.gpfn.sk.ca/~daryle/papers/bayesian_networks/bayes.html

Good luck! Let us know how you get on...



Stimulate

quote: but be very sure to construct a good diagram (UML maybe for relationships and arrangements?). From this, write *simple* classes with easy to use interfaces.

quote: I think dealing with the AI will get very hairy when you get down to the low-level AI stuff like ''move there'' ''take this'' ''do that''.

I actually have most of this already coded and working, and I already know how I''m translating it to the lower-level stuff.

quote: What if the agents did not nessecarily need long ''need chains'', but instead just had a multitude of needs ranging from immediate to long term.

I plan on incorporating other motivating factors besides desires for the listed resources. This would mostly be personality stuff like homesickness or the need to be the center of attention or a need for acceptance (I did originally try to define all of these as a desire for a resource, but some of these really stretched the concept). If I understand what you are getting at with your example, I think these other motivating factors address that point.

You have a point about the number of fixed desires falling off as the game progresses and NPCs either give up on or satisfy their desires.(although I''m not sure if you consider this good or bad). In the context of my game, it would be detrimental if the NPCs became less and less active, since the whole point of the game is player interaction with NPCs. Perhaps the personality traits can be used to spawn semi-random desires when a character runs low on things to do. On a side note, I''m thinking of letting the program run a game year or so before the player starts, activating NPC desires on random days, so the player really has no way of guessing how far along an NPCs plan may be just by looking at how many game days have passed. This will have the side effect of producing some fullfilled desires which will be current events other NPCs can talk about.

quote: Goodluck!

Thanks!

Sean

quote: Take a look at BDI agent architectures. BDI is an acronym for Belief_Desire_Intention.

BDI seems to be what I''m interested in, but unfortunately (as stated above), I''ve already got the foundation of the system designed and coded.

I guess that I gave the impression that I''m just starting out on this AI venture (I''m guessing because I''m not known here and I gave a greatly simplified summary of my design). As much as I appreciate people taking the time to respond, I''m not looking for advice on getting a foundation built. What I''m looking for is possible improvements or expansions to what I already have. I would be more than happy to post a detailed description of how my system works if anybody wants to see it. I didn''t do that in the first place because I originally posted this in the game design forum and I was only asking for creative ideas regarding the need chains. But now that I''m in here with the AI guys, if there''s any interest in the system as whole, I am certainly open to suggestions about it. I''m very happy with what I''ve got done and will jump at the chance to discuss it if anybody cares (just ask my long-suffering wife).

Sean

quote: Original post by Sean99
What I''m asking for (besides general comments/critisism) is if anybody sees novel or unique ways of constructing needs chains using the resources I have listed (or by expanding the resource list).

From my reading of your initial post your needs chain describes a set of goal and sub-goal states your NPC is trying to achieve. Assuming this, then I presume an NPC might start out with a single goal - Become Lord of All - and you seek a way of building the appropriate needs chain to achieve this goal, which might involve satisfying several sub-goals, creating new needs in the chain. Is this correct?

If it is, then you might consider using Partial-Order Planning as a means of building your needs chains.

If I have misinterpreted what you require, then ignore the above and please elaborate on your specific needs.

Cheers,

Timkin

quote: From my reading of your initial post your needs chain describes a set of goal and sub-goal states your NPC is trying to achieve. Assuming this, then I presume an NPC might start out with a single goal - Become Lord of All - and you seek a way of building the appropriate needs chain to achieve this goal, which might involve satisfying several sub-goals, creating new needs in the chain. Is this correct?

Your description of how my AI works is correct, but I''m still not sure that I''m getting across what I''m asking for help with. I have the mechanisms in place for building the needs chain. For each type of resource listed in my original post, I already have a method coded which will return the what resource is required to acqire it.

Maybe I should try to explain this from scratch with another example, using some code (I''ll try to keep the code to a minimum). The Resource superclass has the virtual function gainMeans, which takes a pointer to a charcter and a pointer to a desire. For example, a simplified form of gainMeans for an Object looks like

Resource* Object::gainMeans(Character *c, Desire *d){    int willUseViolence = c->violenceLevel + d->desperation;    if(willUseViolence > someThreshHold){                return genericSwordArm;    }    else{        genericPurse->setValue(this->getValue());        return genericPurse;    } }     

(I dereferenced "this" for emphasis on where getValue() is coming from). For non-unique resources which may have virtually any value (like Purse in this example), there exists generic versions which exists solely for the gainMeans methods. The calling functions immediately capture the value which was just set so that the required value is not lost. This is just a side note that I''m just mentioning so that nobody gets hung up on wondering what the genericPurse is all about.

The main thing I want to point out with this example is that the gainMeans function doesn''t care anything about what needs chain it may be a part of (it doesn''t care what the overall goal is or what comes before it in the chain). It''s only job is to determine what comes next in the chain, given a character''s personality and desperation. What I was asking for is creative ways for each different type of resource to decide what it should return as it''s gain means, given the character''s personality, desperation, and maybe some other factors which I haven''t thought of. That''s why I felt it originally belonged in the design forum. Although, as I said, as long as I am here now, I don''t mind discussing any other aspects of the system

Sean

I really like your way of modelling NPC decision-making, and look forward to seeing it in action . Some ideas/questions (sorry ''bout my english):

- I think information should be a resource. Eg, an NPC desire the Holy Handgrenade of Antioch. The player tells him that the Knights who say NEE knows where it is but won''t tell. The knights wants the head of the killer rabbit, so the NPC could go hunt it down and hope they''ll be pleased and tell him the secret.

- How is charisma gained? (winning fights probably).

- Some more personal qualities - business/bookkepping skills f.ex - owners of an estate needs to employ somebody with those skills. This should solve the problem of short decision chains - the resolution of one chain makes several others emerge.

- How does the NPCs formulate their desires? Could you make this proces biased in some way to make the characters choose more dramatic, complicated desires?



---------
"It''''s always useful when you face an enemy prepared to die for his country. That means both of you have exactly the same aim in mind." -Terry Pratchett

quote: I think information should be a resource.

I actually do have have an information resource. I left it out of my list for the reason that information as a resource implies that a single resource could reqire more than one gain means, causing branching in the needs chain. As a quick example, NPC Fred wants The Holy Grail. Fred queries the Holy Grail as to it's gain means. The Holy grail replies that Fred needs a strong sword arm *and* knowledge as to it's whereabouts. This is where the chain needs to split off to two different branches, one each for the sword arm resource and the knowledge resource. I hope to eventually achieve the complexity of branching in the needs chain, but I'm not prepared to deal with that for a while.

There is one other resource I left out of the hierarchy which is related to information, and that is magic. I don't know how well this is going to work, but I plan on having spells being able to mimic the various other resources. It would be very easy for a spell to just record that it is mimicing a resource of type X with a value of Y, and allow it to be used accordingly. But that's a subject for another post.

I have, IMHO, a pretty neat work around for incorporating individual character knowledge into the decision-making process. The gainMeans function is never called on the actual resource which is desired (if it is a specific, non-generic type of resource). It is called on a copy of the object which represents the character's best belief of the state of the object. These copies are of various degrees of accuracy, which, in part, make up the character's knowledge base. If the character's best belief about a desired resource's location is too vague, he just has to wait until he runs across more specific information. He won't actively seek out this information, unless he is in the presence of the player (I've got some neat conversation routines, including characters figuring out "ok, I know the Holy Grail was last seen somewhere in France, and George here just came back from France, so let me ask George if he's heard anything.", but it's just not worth it to do this for every off-stage NPC)

quote: - How is charisma gained? (winning fights probably).

Winning fights would increase prestige, if anything. Some resources, such as charisma, are not gainable. They exist only as a (usually last resort) tool to obtain something else. These return NULL from the gainMeans function and that would signify to the character that he currently has no way of obtaining that particular desire. Other resources only make sense as an end goal and never turn up as a tool, such as the heart resource. Still other resources only make sense as an intermediate tool, such as the ear resource (ears have gain means, but they are never the end goal of plan).

quote: - Some more personal qualities - business/bookkepping skills f.ex - owners of an estate needs to employ somebody with those skills. This should solve the problem of short decision chains - the resolution of one chain makes several others emerge.

It sounds like you're refering to day-to-day activities, which isn't my concern right now. I'm more interested in epic, grandiose planning. I'm not giving this AI to every NPC. I'm trying to create the motivations and actions of the movers and shakers of the world.

quote: - How does the NPCs formulate their desires? Could you make this proces biased in some way to make the characters choose more dramatic, complicated desires?

That's one of the things I'm asking about myself.

Thanks for the reponse. Your comments and questions indicate I've finally made myself clear. I was starting to worry that I was incapable of expressing these ideas clearly (I hope that doesn't sound like I dig at anybody who responded previously, I'm sure that the fault is mine when several people aren't sure what I'm talking about)

Sean

[edited by - Sean99 on May 30, 2002 5:58:43 PM]