• Create Account

## Pathfinding: hunting

Posted by , 25 January 2010 · 589 views

I'm still playing around with the AI. This weekend I got an issue with pathfinding: How to let a hunter follow its prey without recalculating a navigation path frequently ?

Well, I think I got it. My assumption is, that the hunter is able to follow the prey step by step. With that assumption I can create a path by tracking the movement of the prey, because if the prey was able to walk a certain path the hunter will be too.
I know that this approach has it's shortcoming. If the prey has abilities the hunter has not, like jumping over a barrier etc. But there are two reason the assumption is acceptable. First, it is not realistic, that a hunter is able to follow a prey around the whole map. Once the distance is too great, the hunter has failed and will pickup an other task. The second point is, that if the hunter is not overcoming a barrier a quick A* could help him, if it is not helping, he will abort the hunt.

The idea is, to start with a A* (Figure 1) and create an initial path to the prey. Now, while folling the path, the hunter will expand the path by checking, if the prey leaves a certain area of the last position in the path (Figure2). Once he has left it, the hunters path will be expanded with a new node(Figure 3).

In Figure 4 you can see a path expansion of 4 nodes. An optimization would be to check, if the prey re-enters an area of any node but the last one. In this case the hunter can take a shortcut and the according nodes can be disposed.

How good it will work depends on the choosen radius. I think I will give it a try :)

I believe that a hybrid approach of steering behaviors combined with a "scent" node path that decays over time might be a way to solve this problem. The prey would leave a path like you described only the nodes would decay over a set amount of time and disappear. The hunter would move around fairly randomly until it "overlapped" a scent node and then it could follow a more specific trail to the enemy. This has the advantage of the fact that you can always have the hunter follow the strongest scent node. To avoid the hunter doing weird behaviors you could implement steering behavior like in Open Steer and do some path avoidance by "sight". Certain terrain could impose a movement cost on the path (like A*) but then you can also have certain terrain improve the decay rate of the nodes. For example if the prey crossed a river then the trail would essentially vanish because water could be resistant to having a scent node established within it.

At least that is my two cents, I have never implemented such a system but it seems like it could work in theory.
Your idea would imply, that every potential prey have to track its own movement. To scent a prey sounds like a neat idea, but I think that my approach is easier. In my case the prey calls attention to the hunter and the hunter starts following the prey. I got a locked hunter-prey scenario where the prey tries to flee and the hunter tries to keep up, that's all I need at the moment.

S M T W T F S
123
4 5678910
11121314151617
18192021222324
25262728293031