Are there any algorithms to compute a "flee" path? Essentially, it is a flee behavior that uses path finding as opposed to steering. Given a current position, enemy position, and maximum search radius, I would want to find a point in the radius that is as far away from the enemy as possible. My distance traveled is also important, so I actually want to minimize the distance I travel, and simultaneously maximize the distance from the enemy. What would be a technique to accomplish this? Could this be done simply by changing the heuristic of my A* algorithm? The goal position would instead become the position I want to flee from. The heuristic would then award a lower value the farther I move away from the goal. Does A* allow the heuristic to be negative? I'm not sure how the search would terminate in this case, though... With a normal A* algorithm, you would terminate once the goal node has been removed from the queue. But in this case it seems a little tricky to guarantee an optimal path. Thanks.

The point of fleeing is to go in the direction that is away from what it is that you are fleeing from. In an open environment, obviously the steering behavior is best as you noted. However, in a closed, building-type environment, that doesn't work quite as well.

Obviously, you are not capable of selecting the point on the whole map that is farthest away from your pursuer. Nor is that really necessary. One suggestion would be to select a particular range away from yourself and choose a point on that circle that is in the opposite direction from the pursuer. Think "large scale fleeing". Then, check to see if that point is accessible on a valid path from your current location. That point isn't really your target... just a temporary one. You can select new ones as needed.

The problem that occurs is finding a point that is validly acceptable. That might be tricky. One method would be to use Dijkstra to do a flood fill. Then, by sorting the filled nodes by "distance from my pursuer", you can choose a valid point. I would say that using a flood fill range that goes out as far from you as you are from the pursuer would be a good starting point.

These methods might be a bit expensive, however. Honestly, I'm just pulling these out of the air at the moment. Figured it was a starting point.

Perhaps some investigation into exactly what problem it is that you are trying to solve would be more helpful. What behavior are you looking for and what behaviors are you trying to avoid (by avoiding steering)?

In the short term, and disregarding ties, a particular node in a graph is a good node to flee to if and only if the shortest path from the pursuer's node to that node passes through your current node. In the long term, the problem basically comes down to minimax -- at times, it's important to run directly toward your pursuer, in order to get out of a dead end.

In situations where you and the enemy see each other all the time, it's some form of minimax, as Sneftel pointed out. However, if there are parts of the map where the enemy will not be able to see you, or you won't be able to see the enemy, this becomes a much more interesting problem. For instance, you could take some side street from which there are several possible paths, if the enemy is following you from far enough behind that he won't know which one you took. Or you could enter a mall full of people because you'll be harder to see there.

I don't have a good proposal for what algorithm to use, but I'll think about it. I guess it will have to be a pretty general planning scheme (like Monte Carlo Tree Search), although something easier combined with some heuristics could do the job.

There were two threads on this forum a while back about "Zombie AI" which dealt with this same question. You might want to look at those.

Thanks for the replies.

In this thread, http://www.gamedev.net/community/forums/topic.asp?topic_id=547802, Alex seems to suggest that my original technique of using a pathfinder with a flee heuristic is a valid approach. Could someone elaborate on this?

Playing with the heuristic of my A* as Alex suggested worked out very well, actually. There were a few other modifications to get better behaviour, such as the setting of end conditions and cost calculation adjustments, but overall it works well. Thanks for the feedback. :)