Ok here’s a puzzler for those of you that like geometry.
You have an AI agent, lets say it’s a mouse, and this mouse is being hunted by three cats. Now the mouse needs to know which direction is the best direction to head in, given the position of the three cats.
You could simply take the centroid (the mean position) of the three cats and tell the mice to head away from this position. However what if the mouse was already quite close to one of the cats?
The ideal escape direction would be the one that would maximizes distance from all three cats after they move toward the mouse’s current position. If you were really close to a cat this direction would be almost directly away from that cat… if you were far away from all cats the escape direction would be almost directly away from the centroid.
I can draw it on paper and intuitively see the best option for the mouse, but explaining mathematically is making my brain hurt right now. Any suggestions?
Edit: A simple solution would be for the mouse to only concern him or herself with the closest enemy… however even a mouse is smart enough to account for a couple of enemies.
In theory, the mouse would take focus of the multiple enemies in the order of necessary priority. The closest cat is how the mouse decides the main escape route(s), the second closest cat can eliminate some routes if the mouse’s escape direction puts them in danger of getting closer to another cat. In this case, the mouse would angle their escape based on the position of the third cat so that it is definitely heading immediately away from the closest threat, and still moving away from the longer term threats.
The degree of the angle or effect of the direction the mouse takes that the second or third cats have would also be based on their proximity to the mouse. This would need to be capped so that if two cats pincered a mouse at nearly the same distance away, the cat would shift up to 90 degrees left or right (likely based on the proximity of the third cat).
That is at least one theory on how it could be handled. I don’t have the time atm to write up actual formula’s, but there is at least an example of theory.
As ezzerland stated, a believable and simple-to-implement solution would be based on a priority queue.
So you have three cats, you compute flee vectors flee_0, flee_1, flee_2.
Then compute weights for the 3 vectors based on the distance to the cats. One key thing to understand is that the way you want to implement the algorithm, it will almost always be convergent… That is, the mouse will pretty easily corner himself in between 3 cats and be unable to run away. If you do implement an “optimal” path solution, whatever it may be, remember to throttle the routine so you don’t calculate the optimal path every frame, or the mouse will keep cornering himself.
Instead, you should calculate the escape path every 1-5 seconds, and stick with it for a random amount of time.
This will average the directions of the cats towards the mice. He’ll probably get eaten if he’s surrounded by the cats in an equilateral triangle, but if their movement speeds are the same I think in all other cases would result in a trio of hungry cats.
I may be wrong, though. I’m a guess-and-check programmer.
Yes this is probably what makes the most sense to me as well. But I have another thought…
Yes I realized that as well. I would probably not be recalculating every frame, but you can avoid this situation I think by taking into account the mouses current velocity…(basically you incorporate some maximum acceleration/deceleration).
My idea after thinking about it for a while:
If you graph it on paper, and use 2 cats instead of 3, then the problem becomes much simpler. If the mouse is equidistant between the two cats then it’s escape vector should be perpendicular (in either direction) to the line created by the two cats. If the mouse is closer to one cat then the angle of the escape vector would increase in the direction further from the closer cat.
I cant be sure without graphing it, but I think the mouse’s trajectory would form an arc that flattens into a straight-line where both cats are equidistant to the mouse… Assuming the mouse runs at the same speed as the cats, they should never be able to catch the mouse.
Now any extra cats you add on top of this have to be taken into account. If you have three cats all in a line then the cat which is furthest from the mouse can be ignored and you the above “two-cat-method” should work. So the other scenario is that the three cats form a triangle. If the mouse is outside of the triangle then the furthest cat can once again be ignored, as the mouse will not be getting any closer to that cat when it flees the closer two. If the mouse lies on one of the edges of the triangle we also use the “two-cat-method” but the mouse will ensure the escape direction does not take it into the triangle. In practice you would probably never be exactly on the edge of the triangle anyways.
The third and most complicated scenario with three cats is that the mouse is surrounded by the cats (which is I think what you guys assumed when I asked this question!). So the mouse must choose which two cats it wants to thread between to escape the trio. I have to go to sleep now and I cant really think about how to mathematically make this choice… again it looks simple when I draw it on paper, so there’s probably a neat and tidy mathematical formula for it. Of course one of the influencing factors would be whether or not escaping between those two cats takes you into yet another triangle of cats…We’ll see…
I don’t see how this could work for dynamic agents, but maybe I am misinterpreting what you’ve said. I am using the AStar pathfinding system for some of the AI as well. For example with this mouse scenario, the mouses first order of business is to escape being surrounded by cats, then he will head to the closest “safe-zone” which are static and specific to the level. I use AStar for the mouse to find his way to the closest safe-zone but the mouse wont head toward a cat to get there (unless he thinks he can make it there before the cat grabs him).
Are these influence maps you speak of static or are they updated as enemies move around?
But the biggest gap wouldn’t be the best choice if it was a certain distance further from the mouse than a closer albeit smaller gap…
Perhaps I am overthinking this. Obviously a mouse does not consciously make these calculations, but it does seem like animals intuitively make optimal mathematical decisions in these sorts of cases… I think Ezzerland’s idea of simply weighting the influence of that a cat has on the mouse’s direction by the distance the cat is from the mouse makes the most sense, and is possibly what is going on inside the brain of the mouse.
Just to complicate matters more, are there walls and other objects the mouse should avoid? Just an escape vector might cause problems if it forces the mouse straight into a wall. If there are obstacles, you will probably need some sort of pathfinding system for finding a way around the obstacles (like a waypoint or navmesh system). It might be possible to use a pathfinding system for this problem, by properly weighing waypoints/navpolygons depending on cat proximity. The objective of the mouse would then be to move to the node with the best score, using the path with the best score. I guess this idea is similar to AngryAnt’s suggestion with the influence areas.
Yes in my reply to AngryAnt I mentioned I am already using the A-Star pathfinding system. I hadn’t thought that I could actually alter the weighing of the waypoints based on the cat proximity. The problem would be that weighing the waypoints simply increases the heuristic cost of traversing that point, it doesnt say “if you go this way you might get eaten”. I guess it might still work out though… and it would mean the mouse would try to make some bold escapes past cats when he is totally cornered.
So far this is my favourite solution. I had planned on simply giving the mouse an escape direction and then finding a safezone where the first waypoint is in this direction. I think your method will work best. Now the question is if I can access the waypoint data spatially to make the changes… Since the cats will use the same waypoints I could plot out the cats paths to the mouse, and then mark these waypoints as dangerous to the mouse, since they will likely have cats on them soon. I will have to find a way to alter the pathfinding system to include multiple heuristic costs depending on the agent’s position in the food chain.
@Antitheory:
Yes the very point of influence maps are indeed that they are dynamic. Since we’re talking bitmaps here, they are extremely low cost to update and you get all sorts of optimized data operations for free (ie. relaxing influence is a simple blur).
As I mentioned, you can use this data in navigation planning. You mentioned you’re using an A* pathfinder. A simple use of influence maps here would be implementing the cost calculation doing a weight lookup in your maps. The same concept can be applied to local navigation and higher level decision logic as well.
Although I disagree with them being “simple” I will admit that they probably put less thought into it than I. However a fish is a “simple” creature as well but they exhibit complex behaviour which takes a lot of thought to code accurately.
Also I used cats/mice as an example, this is meant to be used for many different creatures (with differing abilities to sense predators).
I would dispute that mice would not care about distance. You can watch a squirrel gathering nuts in the park and you can be flailing your arms wildly and it will take no interest in you if you are 50 feet away. However if you are 5 feet away it’s a different story. Give animals some credit!