Jump to content
  • Advertisement
Sign in to follow this  
priyesh

help me understand utility AI

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

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

Recommended Posts

I've been designing a survival game while taking inspiration from the NPCs of RimWorld and Prison Architect. (And to some extent more AAA examples like The Sims, as well as rougher examples like Dwarf Fortress).

It seems like a utility or needs based AI might be a good way to help the AI manage a variety of goals, and lead to some dynamic behaviors.

Pardon my meanderings, but I'm trying to understand how this works, and if utility AI is even the right approach

FOOD

Let’s just say I have a “hunger” function that helps AIs manage their food supply.

On a basic level, hunger gets low enough (high enough?) then the character should eat from their food supply.

But what if they have no food? Obviously they should look for some. But you’d be pretty dumb if you waited until you had absolutely no food before you started looking.

The answer is that the AI should look for food BEFORE they’re out of food.

So now my utility function isn’t hunger. My character is going to eat regularly and this can be an automated (unintelligent) behavior. My utility function should be supply.

My utility function for supply: as my food supply goes down, the utility of food goes up. At a certain threshold, it pushes a character to look for food.

But is that dumb as well? The real key is if I have enough food to make a safe journey.

So I design the supply function as: only look for food if I don’t have enough to make the journey.

But this sounds a lot more like a very static behavior tree than a utility function. The agent isn’t really figuring anything out so much as I’m figuring it out for him, and hard coding it.

What am I missing?

RETREAT

Another example I’m having trouble with…

I create a utility function for retreating from battle. On a basic level, it compares the defending NPC’s hitpoints to the attacking NPC’s damage per second. If the threat of death is high enough, then flee.

But an NPC shouldn’t flee if it can kill the enemy before the enemy kills them. So I factor that into the function. Compare the NPC’s “time to die” against another NPC’s “time to die”. Maybe scale the function so the difference matters more when my time to die is small, but allows more uncertainty and risk taking when my time to die is big.

But then I need to factor in the other idiots on the battlefield. Being surrounded by a friendly militia is no reason to flee, whereas I’d feel differently if I saw an enemy army coming over a hill.

What happens if alliances and relationships can change? I suppose an NPC could walk into a trap, thinking they are safe around their friends, when actually it’s a mutiny waiting to happen.

But some smarter NPCs should be able to estimate the threat by looking at the souring mood of their estranged allies and say “I’m going to get out of here before it gets really ugly”.

Does this make my utility function for retreat so convoluted that it no longer represents anything? I’m not sure I understand the best way to do this.

Share this post


Link to post
Share on other sites
Advertisement

A player doesn't see the code, he/she only sees what the AI actually does, ie the result of those computations. If a simple if-tree does the job, it's fine. I'd throw in some random, to get a little variation in behavior. For example, there is some x% chance it will go find more food, where x increases as the supply decreases.

Note that it is unlikely a player will see any pattern in AI behavior even without random, as there should be enough other problems in the game to distract him/her :)

 

For longer term planning-ish things, you can take a look at planners, where you attach points to each option that you have, and throw it all in an A*-like routine to find an order of next actions to do.

 

As for true intelligence, nobody managed that so far, so at some point any AI relies on hard-coded rules in some way eventually. It's thus mostly a matter of sufficiently hiding that from the player.

Edited by Alberth

Share this post


Link to post
Share on other sites

In The Sims there are a set of motives.  The player sees six or eight of them, but there are a bunch of hidden motives never visible to the player. It slowly grew over time, at the end of The Sims 3 I seem to recall into the hundreds. There are also the sets of buffs/debuffs, including an enormous number of hidden ones, added for all kinds of subtle and non-subtle conditions.

 

Every object's interactions had a score function that looked at the motives chosen by designers. Some of the core interactions had score functions attached to hundreds of conditions, motive levels, and buffs. You see the hunger motive, and that gives an incentive to eat. You see a "hungry" buff added when the sim gets a little more peckish, and that adds yet another number to the score.  An additional buff when starving not only makes it more likely, but is also a default test in most interactions that causes non-nourishing interactions to be rejected or cancelled.  A starving sim will drop out of nearly every interaction except the few marked as things you can do while starving, like travel to location or eat or die.  But a sim that is merely hungry just gets a big multiplier to drive the motive up into the hundreds, then into the thousands, far outweighing nearly every other activity preference.

 

Another example is the sim's fatigue motive. It isn't visible, but when exercising the sims acquire or lose fatigue. Get too fatigued and the invisible motive kicks in, causing the sim to reject the action even if it isn't visible to the player.  A fatigued sim won't run home from the gym, but a sim that isn't fatigued and has a buff for running may prefer to jog home.

 

As for your retreating function, it sounds like similar motives could easily be used. Maybe a buff when surrounded by 3+ allies ("military support") , and another buff when surrounded by 10+ allies ("feeling invincible"), and maybe another for special orders ("last stand").  You might have a buff added when fighting if you are doing more damage than you are taking ("winning fight"), and conversely, a buff when you are taking more than you are giving ("losing fight").  The the character's motivation for leaving the fight (low HP, losing fight buff) gets compared against the motivation for staying in the fight (feeling invincible, last stand) to determine if they fight to the death or flee with the last shred of HP.  You could even put in combinations: last stand + losing fight + feeling invincible means that since there are 10 other people around you should back off and let others fight. 

 

 

Sometimes there are games that rely on machine learning, artificial neural nets, and other adaptive and training algorithms, but I feel they are best avoided. Those are difficult to tune and hard to make fun. Game designers just see a random-looking set of training data results and cannot adjust them in meaningful ways. 

Share this post


Link to post
Share on other sites

What am I missing?

 

You're missing the fact that you're attempting to be more intelligent than most of these games are. :) In the first case, you're mostly talking about simple planning behaviour, where the need for X causes an agent to consider several actions to see which ones might satisfy X, or which might open up successive actions to get to the same goal. That's a reasonable approach but is not necessary in most cases. Frob has pointed out how, with a few simple hard-coded rules from the developers, a single motivation or need can increase the desire to perform the action most likely to solve that need.

 

In the combat case, you seem worried about the complexity of the retreat utility, but why? Put in as many factors as you feel are relevant. The hard part is balancing them together, and then balancing them against other potential actions.

Share this post


Link to post
Share on other sites

In The Sims there are a set of motives.  The player sees six or eight of them, but there are a bunch of hidden motives never visible to the player. It slowly grew over time, at the end of The Sims 3 I seem to recall into the hundreds. There are also the sets of buffs/debuffs, including an enormous number of hidden ones, added for all kinds of subtle and non-subtle conditions.

...

 

As for your retreating function, it sounds like similar motives could easily be used. Maybe a buff when surrounded by 3+ allies ("military support") , and another buff when surrounded by 10+ allies ("feeling invincible"), and maybe another for special orders ("last stand").  You might have a buff added when fighting if you are doing more damage than you are taking ("winning fight"), and conversely, a buff when you are taking more than you are giving ("losing fight").  The the character's motivation for leaving the fight (low HP, losing fight buff) gets compared against the motivation for staying in the fight (feeling invincible, last stand) to determine if they fight to the death or flee with the last shred of HP.  You could even put in combinations: last stand + losing fight + feeling invincible means that since there are 10 other people around you should back off and let others fight. 

 

 

The breakdown of the Sims makes a ton of sense and lines up with some very surface level breakdowns I've read. It's crazy to think the most detailed explanation I've read was in a reply on a forum post less than a day after I asked.

Also thanks for applying it to my example. This is supremely helpful.

 

A player doesn't see the code, he/she only sees what the AI actually does, ie the result of those computations.

 

 

In the combat case, you seem worried about the complexity of the retreat utility, but why? Put in as many factors as you feel are relevant. The hard part is balancing them together, and then balancing them against other potential actions.

 

I like how The Sims shows you what an NPC's motives are. Now that I understand that The Sims is actually way more complex "under the hood" and only reveals a few of the key utility functions, I should just figure out which utility functions to reveal, and which to leave "under the hood".

 

My last question is the best practice for manage multiple behaviors from the same utility function. For example, what if I wanted the "retreat" motive to trigger three different behaviors: "call for help", "take cover and heal", "get the actual hell out of there". Would I just wait until the "retreat" motive becomes high enough and then trigger some kind of behavior tree or planner, which would then decide from that list of three actions? Or could I do this entirely from utility just based on different thresholds? Or is this the reason that I might separate the  "retreat" motive into separate utility functions for summoning vs healing vs retreating?

Edited by priyesh

Share this post


Link to post
Share on other sites

what if I wanted the "retreat" motive to trigger three different behaviors: "call for help", "take cover and heal", "get the actual hell out of there"

 

There are many ways to approach this.

 

One way would be to have a concept of a high level activity ("Retreat") which contains a sequence of low level actions ("Call for help", "Take cover", "Heal", "Leave the area"). If you have a lot of systems that tend to have these sequences or something similar, there is a good argument for using utility systems to pick basic high level activities and for behaviour trees to handle the individual actions.

 

Another way would be to incorporate these behaviours into the utility system. The desire to call for help will be affected by whether there is anybody around to hear it. The desire to take cover will depend on whether there is any available. The desire to flee the area will depend on how dangerous the current area is. Once you feed these into the system, you have a variety of different ways to respond to the current situation.

Share this post


Link to post
Share on other sites

Since I (and Apoch) am buried at GDC right now, I'm glad we have people like Kylotan and Frob to help. Thanks guys... it's getting to the point where I can't answer every utility question myself!

Share this post


Link to post
Share on other sites
But this sounds a lot more like a very static behavior tree than a utility function.

 

no - when "go get groceries" gets a high enough score, that's what you do - just like in real life! i just got back from a run to food king myself! <g>   That's how all behaviors in a utility system work. A properly programmed one is REALLY efficient, pretty much always making the "best" move -  so good in fact, apparently the scores are sometimes kept close to introduce some random behavior other than "best move always".  IADaveMark could probably tell you more about that.  I think there may be something on Gamasutra about that as well. I remember seeing something somewhere.

Does this make my utility function for retreat so convoluted that it no longer represents anything? I’m not sure I understand the best way to do this.

no, it just makes your scoring formulas a bit more complex and in-depth - probably leading to "better" choices.

this can be implemented using a number of different systems. i personally handle such things with a hierarchy of decision trees and/or state machines.  similar to a utility system, but instead of scoring all possible moves, then selecting the winner, you consider the moves one by one from most to least important, and take the first move that is appropriate.   considering moves in order from most to least important is akin to assigning higher scores to more vs less important moves in a utility system. IE you get the same basic results.

>> Or is this the reason that I might separate the  "retreat" motive into separate utility functions for summoning vs healing vs retreating?

think about the situation. you're in a firefight. its not going well.  what rules apply?

1. if you have backup, call for help.  

2. if you're taking fire, seek cover.  

3. if you need to heal, try to heal. i say try because you may be out of potions or mana or whatever.

4. if you're way outnumbered / outgunned, retreat.

so there are the rules for four different behaviors: call for help, seek cover, heal, and retreat. 

they can be implemented via a utility system, if-then-else statements, or whatever.

with my ai, i would first do the call for backup, if i had backup, and hadn't already called them.   then it depends on whether you can heal and move at the same time. if you can heal and move at the same time, i would try to heal if necessary, while seeking cover or retreating if needed.  if you can't heal and move, then retreat to heal would probably come first, followed by retreat from superior forces, followed by seek cover if taking fire, followed by non-retreat behaviors, such as reload or attack.   Note that retreat from superior forces takes precedence over seek cover from taking fire. unless you want to get REALLY smart - and take cover until a break in the fire, then retreat.   This is actually quite easy. instead of triggering a "run away!" behavior, and perhaps getting shot in the back - you trigger a "covered retreat" behavior that uses the algo:  if taking fire, seek cover, else retreat, until reached safe area.

 

as you can see, often you may want to do multiple behaviors simultaneously, such as issuing orders, moving, and healing all at once. i often find it best to have a little AI system for each set of independent behaviors.  I also find it helps to have an overall AI system that determines general moves, and then lower level AI systems that implement the general moves in the best way possible. for each of these systems in the hierarchy, i select the most appropriate (and simplest possible) AI type, which is usually a decision tree for prioritized behaviors, or a finite state machine for non-prioritized (IE random sandboxing type) behaviors. but utility systems are a perfectly valid option as well - perhaps a main system, with subsystems, and a few small side systems for certain behaviors that can occur in parallel.  so a main utility system may choose heal over attack, then a healing utility sub-system might decide spells vs various potions in the player's inventory, or whatever - IE how to heal.

Edited by Norman Barrows

Share this post


Link to post
Share on other sites

Getting some incredible feedback here. It's greatly appreciated. While I have so many brilliant people, I wanna ask...

How do you handle "two birds, one stone" types of problem solving using utility AI? That is, there are two completely different utility functions competing for an NPC's attention, and in isolation, they will act on the highest one. But in actuality, there is a solution that allows them to maximize their utility in aggregate: doing both.

Imagine something inspired by the Nemesys system from Shadows of Mordor. The AI calculates the utility of fighting different peers for status, and ranks them:

  • Fight Captain Cameron: 70 (not a sure thing, but fairly good chance of beating him and rising up)
  • Fight Captain Donald: 60 (almost as good)
  • Fight Captain Ernest: 30 (too tough)

But in addition to fighting for rank within the military... there is also the issue of fighting for rank within your family. Sort of a Game of Thrones / Crusader Kings fight for succession.

  • Kill Brother Adam: 65 (some risk, but still good)
  • Kill Brother Donald: 58 (slightly less good)
  • Kill Brother Garth: 20 (very easily goes wrong)

Now, on a very superficial level, the best chance to rise in the military is to challenge Cameron, and the best chance to rise in the line of succession is to murder Adam. But there's a two-birds-one-stone solution here: challenge Donald -- a rival captain and also your brother. Challenge him for military rank, and then fight him until death/exile for your birthright.

Challenging Donald doesn't make sense when you consider those goals separately, because he doesn't have the highest utility for either goal. But when I consider them together, I might realize that two fairly challenging fights doesn't have as much utility as going for one slightly harder fight.

This might not be the best example, but I can think of others. There's a high utility on combat training, but right now I'm starving, so there's a higher utility on finding food. But in theory, if I hunted a wild boar, it might take me a little longer to find food, but I'd also get my combat training in.

Another example: there's a high utility on recruiting an ally, but I have so many enemies that the utility of eliminating an enemy is higher. But in theory, there is one enemy who hates me over a misunderstanding that could be cleared up, and then he might be willing to hire himself out as my ally. I could eliminate an enemy and gain an ally within the same interaction.

Is this where a planning-AI needs to come in?

Edited by priyesh

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!