Legacy GM AI: Modeling imperfection

D

Dramier

Guest
Some quick background:
I'm developing a game with one of the emphasis of design being sophisticated AI.

Currently I have a simple ecosystem modeled on a map that is 120 cells by 120 cells. Each cell represents 1 meter or roughly three feet. In this map I have a randomized procgen terrain consisting of dirt, grass, trees, rocks, bushes and water cells. The rocks and trees are non-passable. The exterior edges of the map are blocked solid with walls so nothing can leave the map on purpose or accidentally. I have two entities with AI in the form of a behavior tree. The first is a pig and the second is a wolf. Both entities have hunger, thirst, and fatigue and they active search for food and water and sleep when tired. They both can remember the last place they found water or food and return to it when necessary. They also have hitpoints and can die. When either entity dies it drops meat. The pigs eat grass, the wolves eat meat by hunting and killing pigs or eating already found meat on the map. Both entities have full line of sight and can recognize each other on sight. Pigs flee wolves 95% of the time, the other 5% they actually fight back. Wolves have a 95% chance of attacking each other and a 5% chance of fleeing.

The problem:
Everything is working splendidly at this point. In fact, that's actually the problem. I'm trying to figure out how to model the wolves hunting behavior. Currently since they are faster and stronger than the pigs on average, they always catch them. In nature, most predators are only successful something like one in seven times at best. I can't figure out how to implement some way of making the pigs escape. Basically the pathfinding is too perfect and generally the pigs can't escape because of it.

I would greatly appreciate any suggestions.

For the curious, the reason I'm modeling this behavior is because it is a building block for the AI that the humanoid entities in the game will use and I'm starting with simpler creatures. I'm also using simpler creatures to model just how complex the AI can be and still run a reasonably large map and alot of entities. Right now on that map at 120x120 it handles around 5,000 objects in the terrain with an unknown max amount of entities at a steady 60FPS. Resolution is 1280x1024 and can be zoomed in and out. Stress testing has yielded that it maxes out at around a 480x480 cell map with around 100,000 entities active not including terrain of about 20,000 objects. My machine is fairly powerful so I don't think that's an 'average' result to expect, but the goal is to have a map size of roughly 1200x1200 with a few thousand entities. It's currently unoptimized with no "off-screen" deactivation of objects, and the memory footprint is around 100mb with about 20% CPU load. Obviously the bigger maps increase that substantially. If you have any other questions about it feel free to ask. I've included a screenshot just so you can visualize what it looks like, no really needed but just trying to be polite.

ss.jpg
 

Yal

šŸ§ *penguin noises*
GMC Elder
Basically the pathfinding is too perfect and generally the pigs can't escape because of it.
AFAIK prey's most effective strategy of getting away is changing directions when the predator is really close, so they can't react in time; while they're overshooting, turning back, and giving chase again, the prey gets ahead a bit and might lose line-of-sight with the predator under fortunate circumstances. (Rabbits and bunnies are masters of suddenly changing directions, but I guess pigs could do it as well). You could model this by having wolves have some sort of "turning inertia" when they're running, so they cannot change direction too abruptly - but pigs can, so in the right terrain they'll be able to get away. (Just make sure wolves don't have turning inertia when they're just walking around or they could have really awkward moments trying to reach stationary stuff...)
 
A

anomalous

Guest
Domesticated pigs don't survive in wolf country, your simulation is correct. That's why farmers uses fences, guns, and dogs. Make them wild pigs for a better chance of survival.

You could do adults/babies, and have wolves chance of attack increase the further a baby is from adults. Babies stray or get spooked and go the wrong way, etc.

And if attacked, the adults have an x% to defend baby and chase the wolf off (based on distance and # of wolves?) And as you already have, some minor chances of adults killing a wolf, or the wolf taking on the adult (the more hungry they get?). Its hard to tell where to stop adding detail, because there is no end is there?
 

ph101

Member
Looks interesting and fun. I think one key thing you are missing unless I missed it is population growth - the pigs need to breed! Your system is similar to a classic population modelling which i maytbe you have already seen for interest: http://ccl.northwestern.edu/netlogo/models/WolfSheepPredation
http://ccl.northwestern.edu/netlogo/models/WolfSheepPredation
You could have them breed when they meet, or just randomly duplicate. As an aside maybe you could take it further simlulating how much energy each animal has, how long they live for, how much grass they eat, then having grass grow in adjacent tiles too.

More specific to what you asked for, couldn't you give a percentage chance the pigs escape the jaws of the wolf? The wolf could have a cool down time, where it needs to rest between attacks. I think its good to think hard about optimisation from the off like you are. Some things you probably already thought about, is how frequently an object needs to pathfind and if they need to pathfind for every type of movement (not sure if it turn based or what, or the speed of cycles). Technically you could do away with the thousands of objects, store them all as "data points" in a grid and be drawing tiles. Then with one object run through the grid, and execute the necessary ai needed from each location if you see what I mean. I'm just cautioning having lots of objects is risky as your project is likely to grow a lot and if you had a solution like that from the beginning.. it possibly might run better, just some thoughts!
 
M

mekaerwin

Guest
Another option would be to randomize the detection code a little so that pigs see and react at different distances. Then you could implement an acceleration to your pigs and make them faster in the long run to the wolves or make it where the wolves run out of steam. Either way the pig makes it away if the wolf is detected in time or else the wolf's already at top speed and gets the pig as it accelerates. Just a variation on the turning inertia mentioned above. There are many reasons predators get the kill when they do, but they are discrete and you can map most of them out then choose which to implement based on effect desired or ease of implementation.
 

TheouAegis

Member
I'm with anomalous and Yal on this one. You're giving the prey not enough credit and the predator too much credit. Why won't a lion attack an adult elephant? Because an adult elephant would kill it. Why don't eagles with their keen vision capture bunnies every time? Because bunnies can change direction faster than an eagle can. What does an owl have that an eagle doesn't? Stealth evolution. Why do dolphins huddle fish together before eating them? Why do great white sharks attack from below? Why haven't giant squid been killed off entirely by sperm whales? Why are pigs actually respected in some cultures? Because in every situation the prey has some means of either out-maneuvering, out-smarting, or out-fighting the predator.

As anomalous pointed out, many predators will not even attempt to kill adults unless they are injured, because a healthy adult is either too dangerous or too fast. In the wild, predators don't have the luxury of storing up tons of calories like humans, so they can't afford to waste energy chasing down healthy prey. And adult prey will cluster around young prey because the mere presence of an adult increases the risk factor greatly. As Yal said, there are many variables you'd need to consider with how the predator can move and how the prey can move.
 
Didn't read everyone's replies cause I'm super short on time, but another idea is to give the predator units less stamina then the prey units. Apologies if this has been mentioned.
 
D

Dramier

Guest
AFAIK prey's most effective strategy of getting away is changing directions when the predator is really close, so they can't react in time; while they're overshooting, turning back, and giving chase again, the prey gets ahead a bit and might lose line-of-sight with the predator under fortunate circumstances. (Rabbits and bunnies are masters of suddenly changing directions, but I guess pigs could do it as well). You could model this by having wolves have some sort of "turning inertia" when they're running, so they cannot change direction too abruptly - but pigs can, so in the right terrain they'll be able to get away. (Just make sure wolves don't have turning inertia when they're just walking around or they could have really awkward moments trying to reach stationary stuff...)
I just finished implementing this last night. With the pathfinding, the wolf targets the pig and "locks on" to that location when it initially begins the chase. Based on some arbitrary values the pig can sometimes break the initial flee path and chart a new path. This does a decent job of simulating that sudden dart or turn, and I found that it looks fairly life-like and leads to more predation failures. The only time it really looks odd is when a super fast wolf (they have random spawn in speed rates) manages to reach the pig right at the turn point and this strange shuffle combat ensues. A side effect that is inconsequential but it looks pretty funny.

Domesticated pigs don't survive in wolf country, your simulation is correct. That's why farmers uses fences, guns, and dogs. Make them wild pigs for a better chance of survival.

You could do adults/babies, and have wolves chance of attack increase the further a baby is from adults. Babies stray or get spooked and go the wrong way, etc.

And if attacked, the adults have an x% to defend baby and chase the wolf off (based on distance and # of wolves?) And as you already have, some minor chances of adults killing a wolf, or the wolf taking on the adult (the more hungry they get?). Its hard to tell where to stop adding detail, because there is no end is there?
Well, I'm not intending to simulate pigs exactly. I just happened to have a sprite for a pig on-hand and not a sheep. =P We could consider these sheep in pigs clothing! I have already considered breeding but have not yet implemented it in this version. I had it in a previous version and it definitely made a huge difference. I had many problems however with population explosions because my rates were too close to bacterial growth. But yes, I get exactly what you are going for in where do you stop adding detail? It is in fact the point that brought my last experiments with AI programming to a screeching halt. I was using a modified state machine and it became impossible to figure out where the logic was derailing.

Looks interesting and fun. I think one key thing you are missing unless I missed it is population growth - the pigs need to breed! Your system is similar to a classic population modelling which i maytbe you have already seen for interest: http://ccl.northwestern.edu/netlogo/models/WolfSheepPredation
You could have them breed when they meet, or just randomly duplicate. As an aside maybe you could take it further simlulating how much energy each animal has, how long they live for, how much grass they eat, then having grass grow in adjacent tiles too.

More specific to what you asked for, couldn't you give a percentage chance the pigs escape the jaws of the wolf? The wolf could have a cool down time, where it needs to rest between attacks. I think its good to think hard about optimisation from the off like you are. Some things you probably already thought about, is how frequently an object needs to pathfind and if they need to pathfind for every type of movement (not sure if it turn based or what, or the speed of cycles). Technically you could do away with the thousands of objects, store them all as "data points" in a grid and be drawing tiles. Then with one object run through the grid, and execute the necessary ai needed from each location if you see what I mean. I'm just cautioning having lots of objects is risky as your project is likely to grow a lot and if you had a solution like that from the beginning.. it possibly might run better, just some thoughts!
Breeding is a correct approach, and I addressed that in the above reply. I have simulated the energy, lifespan, food consumption, caloric usage, body fat percentages, all of that and alot more in the previous iteration and I think for this round I am going to negate going that far. I'm really attempting to establish stress testing for GMS and basically figure out the relationship between how complex my AI can be versus how many active objects I can have and still get a framerate that is feasible. But yes, you are spot on and adding those details was very enjoyable and it was fascinating to watch an ecosystem simulation happen.

As far as the object optimization, this is EXACTLY what I'm studying. I tend to focus on optimization on day one and as I develop I have a running checklist of say 10 to 12 things to add or fix. As I work, I build the next list but keep it seperate and include bugs. Then when the current list is done, I stop and optimize as much as possible. I am struggling to find a way to convert existing objects into tiles because it appears that a grid large enough to hold the map causes unique memory problems. I'm not sure if it's due to a syntax error or logic error, but when the map is generated it uses a grid to do so and leaving that grid in place when the map is drawn causes an out of memory crash when cell map size goes over 120x120. I have plans to experiment with the grid and see if I've errored somewhere next, which I suspect I have. Otherwise I must figure out a way to convert as many objects as possible to tiles. I've already eliminated around 10,000 objects in the current 360x360 map, but it only gained about 6 to 8 frames which means on an "average" computer it would not run. I still have around 56,000 objects in existence before I start spawning animals, so I've got work to do. If you have more expanded ideas on conversion, or know of references to threads or pages dealing with the subject I'd absolutely love to have them. I especially adore resources like Amit's page, if you are familiar with it.

Another option would be to randomize the detection code a little so that pigs see and react at different distances. Then you could implement an acceleration to your pigs and make them faster in the long run to the wolves or make it where the wolves run out of steam. Either way the pig makes it away if the wolf is detected in time or else the wolf's already at top speed and gets the pig as it accelerates. Just a variation on the turning inertia mentioned above. There are many reasons predators get the kill when they do, but they are discrete and you can map most of them out then choose which to implement based on effect desired or ease of implementation.
I had not considered acceleration as a medium of escape. I don't think in fact I've ever simulated that because I normally don't think much in the way of physics when dealing with 2D implementations. It's a flaw that has bit me a number of times. I think that might be a good branch to add to the "how prey escapes" tree, but for this workflow I may leave it out since I'm not dealing with any other physics yet. But a great suggestion, thanks!

I'm with anomalous and Yal on this one. You're giving the prey not enough credit and the predator too much credit. Why won't a lion attack an adult elephant? Because an adult elephant would kill it. Why don't eagles with their keen vision capture bunnies every time? Because bunnies can change direction faster than an eagle can. What does an owl have that an eagle doesn't? Stealth evolution. Why do dolphins huddle fish together before eating them? Why do great white sharks attack from below? Why haven't giant squid been killed off entirely by sperm whales? Why are pigs actually respected in some cultures? Because in every situation the prey has some means of either out-maneuvering, out-smarting, or out-fighting the predator.

As anomalous pointed out, many predators will not even attempt to kill adults unless they are injured, because a healthy adult is either too dangerous or too fast. In the wild, predators don't have the luxury of storing up tons of calories like humans, so they can't afford to waste energy chasing down healthy prey. And adult prey will cluster around young prey because the mere presence of an adult increases the risk factor greatly. As Yal said, there are many variables you'd need to consider with how the predator can move and how the prey can move.
This is correct. I've adjusted my predator's behavior in preparation to add hunting strategy. The wolves will soon have multiple strategies. One is simply hiding in place and waiting until prey gets very close. The second is since predators in the real world often stake out water holes, I plan on having wolves hide around water holes and ambush. The third strategy is the straight sprint/run down option. I haven't started this behavior yet, so it will be a few days before I get it working. But the point brought up about healthy/sick animals is very very important as I plan on adding the Dungeondweller type of "perceived" strength and danger evaluations to help the behavior tree utilize this type of real world approach. Unfortunately I will have to add a roughly simulated disease system or some way of impacting the prey's health to get the desired result. As I replied above to the response about how much detail is enough, I'm having to figure out where my lines in the sand are drawn.

Didn't read everyone's replies cause I'm super short on time, but another idea is to give the predator units less stamina then the prey units. Apologies if this has been mentioned.
It has been brought up, and I've done this approach before, but don't apologize I appreciate any and all input. Never know when somebody mentions something in a way that sparks a new thought or makes me see something in a different and more useful way.

Thanks for all of the replies, it has been very helpful. I hope this wasn't too long of a reply, but I wanted to extend the courtesy of replying to all of the posts and just returned home and had the opportunity. I have a few days to decide on how I want to approach the problem and definitely will weigh in all of the responses here to figuring out my plan of attack. In the meantime I have to make a 360x360 cell map get 60FPS with 50,000 objects or there's no point in having the AI at all. Once I get that nailed down I will be starting back on the AI, and if there's interest here I will post my results. While searching last night, I came across a wonderful discussion on exactly this topic of imperfection in AI programming on the old Gamemaker forums, and I'd like to leave that link here so anyone else interested in the subject can browse it. http://gmc.yoyogames.com/index.php?showtopic=385771

I will keep checking this while I'm working, so feel free to ask questions or pose more suggestions. It is greatly appreciated!

Edit: Clarified that the link I posted was about AI programming, not about object optimization.
 
P

Practicaljoke09

Guest
Hi. I'm very new to the GameMaker community, but not to biology.

To the reproductional problem I'd try to add some resource(food/space) that slows down or lowers the reproductive rate when reached. Maybe every individual needs (room_width/50)*(room_height/50) space to live in in order to reproduce? It doesn't have to be a physical resource, or even a visible, but something needs to lower the fecundity as theres more individuals. All species are held back by some kind of resource. Even bacteria(mostly space or sugar in labs). So far it's only us humans that's ignoring that we have a lack of resources to keep all of us alive and healthy in the future.

I agree with most comments on how the prey can escape its predator. You could probably add an infinite number of factors but I'd absolutely think of acceleration and spotting as two variables to take in account. Spotting/searching for predators is one defence mechanism that's cruical to improve survival rate of an attack or to prevent an attack entirely. If a flock of birds spots a hawk it can either flee in advance or be ready to dodge the strike. It can also signal to the predator that they know of it's presence and that it's no use for it to waste it's energy on trying, since they all are ready to react and make the chase or fight harder.
Acceleration is important and the reason why an ambush is a viable strategy. If the prey can't see the attacker coming it has less time to react.
I would divide the act of hunting into 4 phases: spotting, reaction time, chase and fight.
Spotting- depending on how far away or how many predators that is spotted, the prey react to or ignore the threat.
Reaction-time between spotting and action. That can perhaps vary between young inexperienced, adult or elderly individuals(3 stages of the lifecycle?).
Chase- Acceleration, changing course(multiple times? with big enough turn, maybe decrease speed and force more acceleration) and lunge(maybe a path that the predator "commits" to when close enough, where if the prey changes course it probably will result in a miss and resume chase? Like your path the wolf "locks on" to, but at the end of the chase).
Fight- When chase is successful it ends up in a fight. Easiest would be to add a % of fail or success(you know.. Fight for life your life, no rules), where predator could be stunned so that the prey could escape or the prey would be killed.

Hope my comment could be helpful somehow.

As a first "big" project I'm actually trying to making some sort of RTS with a lot of these mechanisms myself, so this sounds very interesting to me :)
 
K

Kululu17

Guest
Hi - I have played with this type of problem on a much less sophisticated level, but a couple of simplified ways of dealing with it are:

A. Have a delay to the pathfinding to simulate inertia - so you would have the wolf target where the pig was, but say not reset to where the pig currently is until a certain time passes (in steps). That way you could have the pig reset every 6 steps, but the wolf would reset every 10 steps. One advantage to this, is for a static target, it would not result in the weird behavior described above.

B. Have an attacking mode with a delay, which also simulates inertia. So if the wolf is within a certain distance, it stops and goes to attacking mode, but the attack is not effective until a certain delay has passed. If the prey is still with the attacking distance, the attack is effective, otherwise the wolf goes back to pursuing mode. With some randomness in the preys direction this will result in some successful and some unsuccessful attacks.

C. Have an endurance for the prey set higher than the predator. So if the wolf can't catch the pig after a certain period of time, it would slow down a lot, and give the pig a much better chance to escape (this is also similar to many predator/prey situations where the prey has greater endurance).

D. Have certain types of terrain favor the prey - for example tall grass where the predator may loose track of the prey, or dense shrubs where a predator can't maneuver well. If the prey happens to be close to a favorable terrain when the chase starts, they have a much better chance of escaping.

It may not be true to biology, but, by playing with the exact values for the above parameters, I have been able to get prey to escape some of the time.
 
Top