Sign in to follow this  
Norman Barrows

whats an easy way to implement this behavior?

Recommended Posts

i have  a new kind of AI behavior i want, that i've never needed before:

 

"do normal AI, while avoiding an area"

 

the specific case is doing normal predator or non-predator animal AI in Caveman 3.0 while staying away from campfires.

 

i discovered that "campfire nearby" and "taking missile fire" are not mutually exclusive conditions, and therefore require separate AI variables to avoid conflicts. so a change to the "flee from campfire" code is called for.

 

off the top of my head, it would seem that after deciding on a "move" the AI would have to then check to see if that "move" would place it near a campfire. if so, it would have to choose something else to do.

 

but the more possible "moves" the AI has, the more checks are required.  skyrim has one type of AI (hostile) with two basic moves: attack and flee. caveman has at least a few more than that - perhaps as many as six different possible moves each for about six different types of AI. it would be a whole lot nicer if i could do one check in one place, rather than 36 checks in 36 places.

 

simply having an animal flee if withing 50 of a fire results in the critter oscillating between flee and close at a range of 50 feet, assuming their target is near the fire.

 

using a flag or state variable to flee at 50 and stop fleeing at 75 (or whatever) results in oscillations back and forth at ranges of 50 and 75 feet.

 

is one check per possible move the best approach, or should i go to a lower level and prevent targeting of entities near campfires altogether, or something else?   is a separate AI state for "i can approach no closer" behavior required?

 

as i said, i've never had to write "avoid area" behavior AI code before - flee from area, yes. but avoid area while doing other stuff - no.  so whats the easiest way to do this?

 

i want to keep it as simple as possible.

 

EDIT:

simply ignoring targets near a fire won't necessarily work. if the target is not near a fire, and the critter should flee from the target, away from the target might be towards a fire.

Edited by Norman Barrows

Share this post


Link to post
Share on other sites

I won't call this the simple way, but in my game each agent allegiance has an overlay on top of the terrain that contains threat and discomfort information. The layers are added together to form the move graph. Nodes/edges are considered blocked when discomfort or threat is high, and the agent does not have the correct "stance" such as reckless/bold.

The move map values and stances are used throughout the code, and when the agent is standing still or doing other tasks, the threat/discomfort values are periodically sampled and can trigger a fleeing behaviour.

This system has been very costly to develop and requires a lot of CPU and memory resources, but it produces very realistic behaviours.

 

off the top of my head, it would seem that after deciding on a "move" the AI would have to then check to see if that "move" would place it near a campfire. if so, it would have to choose something else to do.

 

 

The threat/discomfort check should be done as part of the accessibility checks like you are probably already doing to determine if the terrain is blocked.

 

 

but the more possible "moves" the AI has, the more checks are required.  skyrim has one type of AI (hostile) with two basic moves: attack and flee. caveman has at least a few more than that - perhaps as many as six different possible moves each for about six different types of AI. it would be a whole lot nicer if i could do one check in one place, rather than 36 checks in 36 places.

 

 

 
Yes, place the check at the base of the call hierarchy. All AI systems should do the check, all the time. If some code ignores the discomfort value, you will see dithering.
 
 
is a separate AI state for "i can approach no closer" behavior required?

 

 
You should use a new "stance" flag, for instance with 3 values: Fearful, Normal and Bold which is parallel to the AI states.
An AI state like "Attack" will set the stance to Bold, meaning that the move code will ignore threat and discomfort.
Other AI states like Eat and Sleep will set the stance to Normal so the move code will avoid/panic when in threatening situations. When fleeing, the Stance is also Bold, otherwise the agent will be unable to move. After escaping the danger, the stance is reset to Normal.
Fearful is a stance that can be used to simulate low morale, it simply means lower tolerance for threat and discomfort.
Edited by captain_crunch

Share this post


Link to post
Share on other sites

I have been using a modular influence map system at my last 3 clients (SOE for EQNext, ArenaNet for GuildWars 2, and now Pixelmage on Hero's Song). I wrote an article about it in the book Game AI Pro 2 and will be speaking about it at next year's GDC AI Summit.

 

The short version is that you project influence from things out into the world by propagating it into a grid -- falling off in value the further you are from something. When characters decide when to move, pick locations to move to, or even pathfind to new locations, they can look up values from the influence map system. They can determine things like "how much threat am I under right here?", "where is a low threat spot nearby?", or "what is a path I can take that has the least amount of threat?" By having different maps for different factions or hazards, you can combine them in meaningful ways to get a total value.

Share this post


Link to post
Share on other sites

i may have just thought of a simpler approach.

 

the effect of an influence map would be to basically mark the area around a campfire as "impassable".

 

so why not just make the campfire a special kind of collide-able object with a really big radius? the effect would be the same.

 

this would be somewhat akin to embedding the influence data in the standard terrain collision map. so the collision map becomes the influence map.

 

its really not that different - add the influences to a copy of the collision map instead of adding collision data and influences to a separate influence map. the resulting map is more or less the same.  so it still an influence map.

Share this post


Link to post
Share on other sites
You definitely don't want to do that in such a binary fashion, and you don't want to lose that much area in general. If a creature becomes surrounded by all hostile-controlled space, they will be paralyzed.

Don't make the area impassable. Make it cost more, by some reasonable factor. If the only way to escape is through a dangerous area, you should still allow creatures to use that path.

Also try not to make things black and white in your passability constraints/path costs. Subtle shades of danger can be a powerful way to represent risky but not impassable areas. Many shades are better than just a couple, because you can then distinguish between "I'd rather not go there" and "that will definitely wreck my shit."

Share this post


Link to post
Share on other sites

Don't make the area impassable. Make it cost more, by some reasonable factor. If the only way to escape is through a dangerous area, you should still allow creatures to use that path.

 

 

 

The problem with this is that it allows agents some distance away to path through the danger zone. This will look stupid because as soon as they reach the area, fleeing will be triggered and they will run away. Only to pathfind the same path again, and stay dithering at the edge.

I think blocking areas is better. It will keep everyone away and if the agent finds itself in a blocked area, it should immediately trigger panic/fleeing which allows it to ignore the blocked area until it is in a safe spot. 

Share this post


Link to post
Share on other sites
Don't insist on treating everything as a binary constraint. Agents shouldn't run just because they can see a very slightly dangerous thing 30 feet away, for example.

If your agents can build a threshold of "discomfort" before triggering the flee behavior, they can occupy moderately dangerous areas for brief periods before switching to a different mode.

Moreover, if your agents don't hard-edge all their decisions, they can choose to evade a nasty area if and only if it suits them more than any other available decision. So they might choose to risk a dangerous spot to go attack a really promising target, for example.



Locking things to binary constraints is a surefire way to get brittle, exploitable, and unrealistic behavior. Real creatures are rarely so black and white.

Share this post


Link to post
Share on other sites

You know how in a movie, some people might get surrounded by fire and then they realize that the only way to get out of the situation is to dash through the least fiery area? That's what happens when you have degrees of danger.

Share this post


Link to post
Share on other sites

Predators often have their own predators, and prey of course do

 

SO most active animals will have things they will seek (their goals) and others (like their predators) avoid.   So such behavior decisions will be common to many of your animals/intelligent objects

 

Campfires and the humans around them would be classifies as a threat (to some) and be rated with  some threshold sensor range and threat magnitude relevant to the beasty who is concerned/sensitive about this and checking for cues

 

You might be able to do a consolidated/shared   'influence map' for large numbers of certain beasties  (for certain different  'threats' types).   The granularity can be cruder (bigger grid squares) depending on how accurate it needs to be.

 

and if required do partial rebuild (or update) sections of it on an interval (round robin to spread it out if its alot of processing). 

 

It may not change that fast - or it might be allowable to have the changes/revisions  be driven/forced by movement activity to accelerate particularly active sections/areas of the mapping when needed.

 

Something like that (a basic influence map check) might also simply be a filter for early culling, leaving the objects who would run more costly/accurate processing to drive their behavior.

Share this post


Link to post
Share on other sites

>>  If a creature becomes surrounded by all hostile-controlled space, they will be paralyzed. Don't make the area impassable. Make it cost more, by some reasonable factor. If the only way to escape is through a dangerous area, you should still allow creatures to use that path. Also try not to make things black and white in your passability constraints/path costs. Subtle shades of danger can be a powerful way to represent risky but not impassable areas. Many shades are better than just a couple, because you can then distinguish between "I'd rather not go there" and "that will definitely wreck my shit." 

 

 

hmm...   a good point.    so fires should have a flux density field - so to speak.  well that's definitely an influence map if i ever heard one.

 

this is why i like posting before i implement. make sure i don't overlook something.

Share this post


Link to post
Share on other sites

>> Predators often have their own predators, and prey of course do

 

i may have managed to get it all down to just two basic types of AI for animals:  predator, and non-predator. and predator is just non-predator with a hunting mode.  so the two basic driving AIs are "fight or flight" and "hunt", with "graze" as the "i'm not doing anything" or "idle" behavior. and fight or flight or hunt are both "fight/hunt if they aren't bigger (by weight)". so for a non-predator, negative influences on the influence map would be any critter that outweighed them, terrain obstacles, and campfires. and all 50 some odd animal types have unique weights. for predators in hunting mode, it would be any critter that outweighed them, or whose hit points (based on weight) was more than the combined hit points of the pack (also based on weight) for pack attack AI. turns out almost any predator will pack attack if the pack odds are favorable while individual odds are not, and the payoff in food is enough for the whole pack. the pack can even be two different species on rare occasions, such as grouper and moray. but i don't get into inter-species cooperation hunting. 

 

but you see the problem with this. each type of critter will have its own influence maps. fortunately, there's seldom more than half a dozen species in visual range at a time.

 

i may be able to mark the center of an influence with the critter weight/hit points, and simply ignore those influences that are not heavy/strong enough to worry about. but that would require something more like a bsphere cull than a grid map to work.  still lots to think about and figure out.

 

but its starting to look like i may need to re-engineer the AI around influence maps.

 

>> So such behavior decisions will be common to many of your animals/intelligent objects

 

pack hunting (which is rare), and flock are the only two behaviors where critters of the same type share the same goal.   all animals of the same type will share the same threats.

 

but you allude to the goal influencing things.    should the influence map just be negatives, or should it also have positive weights, for things like the goal? if positive as well, you'd have a map that did a circular gradient out from the goal as positive influence, and a number of small square or round negative gradient areas scattered across the map, representing things such as dangerous animals, campfires, etc.  in general this would seem to make the AI choose "more towards the goal" in the case of ties.

 

one negative influence map per animal type active is not that bad. but one for each animal?  whats the word Dave? is it doable? if anyone around here can answer that one, its you. (or anyone else whose has done this before). is an influence map for each entity, including the influence of a dynamic goal, doable?   500 entities? maybe more? i've hit 500 active in playtesting already.

 

>> You might be able to do a consolidated/shared   'influence map' for large numbers of certain beasties  (for certain different  'threats' types).   The granularity can be cruder (bigger grid squares) depending on how accurate it needs to be.

 

unfortunately, it looks like one map per critter type, and one map for campfires, as the base types from which the final influence maps will be summed.  so not a whole lot of sharing there.   same species can share maps, they can all use the campfire map to make their maps. that's about it. and campfires aren't really that common. its a lot of work to keep a fire going 24 by 7 ! <g>.

 

>> It may not change that fast 

 

campfires won't change unless they go out or someone lights a new one. but hostile critter threats (when present) will change continuously as the critters move about.

 

perhaps this is the question to ask:

 

given that the AI must look around and determine nearby threats to avoid, is is faster to do it with an influence map, or by iterating through the list of active entities (all of which are in visual range?

 

if you use a map, you must update it when the entities move, but the lookup is fast. an iteration is required when first constructing the map. updating wouldn't be that bad. you have a single routine add_influence(location, amount). to move a critter you add_influence(old_location,-amount), then add_influence(new_location,amount). and all add influence does is add or subtract weights to the map squares. you could have an automatic falloff rate, or an explicit radius you pass to add_influence, and just lerp from amount to 0 at the cutoff radius. so the hit for update would not be that bad: a bunch of adds with indirect addressing. by using large int values (basically fixed point), it might be possible to use ints instead of floats for even faster updates. so maps are looking pretty good so far.

 

if you use iteration, you have to loop at least to last_active in the list, if not MAX_LIST_SIZE. and you have to skip over inactive and dead animals. the list is referenced by other lists, so entries can't move without "pointer fixups" required. thus the inactive field, and there you're basically looking for closest threat, so you can defend your space against it, hunt it, or run if its bigger.

 

but using maps to find closest threat target doesn't really work so well. they are more for once you've got your target and know where you want to go, whats the safest way to get there?

 

so it would seem that iteration should determine target, then an influence map should be used by A* to determine the path to target. and the influence map would have terrain, hostile critters, and campfires on it. when an entity was added to the simulation you'd call add_influence to add it to the influence map. when it moved, you'd call add_influence(old_location,-amount), then add_influence(new_location,amount) to move it. and call add_influence(location ,-amount) when it died.

 

whew! influence maps and optimized A*. looks like i got my work cut out for me.

Edited by Norman Barrows

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this