Pathfinding: following a NPC

Are you sure you can't just regenerate the path every time? If you limit yourself to short paths, the search won't be too costly.

Could you not just do a "normal" A* to find the initial path, keeping the state for later (that is, the open/closed list, etc). Then, whenever the prey moves, you just move the "goal" node and continue A*. Obviously, it's going to screw up some of your heuristic calculations but you can probably start over again after every n moves.

The main problem with that is it might not find and shortcuts that it would otherwise be able to use if you recalculated the whole path every time (e.g. if the prey moves around an obstacle, you'll probably end up having the hunter follow it around, rather than taking a shortcut the other way)

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 :)

You can cache a lot of shortest paths between navigation nodes: recomputing paths frequently and exactly would then only expand a few nodes near the follower and the moving target before tunneling through a recycled path very cheaply.

The hacks you suggest are not healthy; for example, there is no predictable relationship between the location of waypoints and the arbitrary threshold radius.

Quote:

You can cache a lot of shortest paths between navigation nodes: recomputing paths frequently and exactly would then only expand a few nodes near the follower and the moving target before tunneling through a recycled path very cheaply.

There're several issues with using a waypoint path to follow your target. Even if performance isn't an issue, I got the problem of unnatural movement. The issue is, that your npc have to move to the first node in your path, sometimes resulting in moving in the "wrong" direction at start. If you recalculate the path each time, you are changing your first node frequently, if you let the follower move a short period before recalculating this issue becomes even worse.
My first appproach was to recalculate the path each time which results in a follower running past me, turning and running back to me.

Quote:

The hacks you suggest are not healthy; for example, there is no predictable relationship between the location of waypoints and the arbitrary threshold radius.

You are right here, but I can't see a problem with it. If you just take a look at the target, you don't have a predictable relationship between the location of the target and a waypoint.

Can you explain why this could be an issue ?

Quote:

Original post by Ashaman73 There're several issues with using a waypoint path to follow your target. Even if performance isn't an issue, I got the problem of unnatural movement. The issue is, that your npc have to move to the first node in your path, sometimes resulting in moving in the "wrong" direction at start.

When you say you use a waypoint system, I assume paths are computed by A* search on a graph consisting of corners and other special locations, the current position of the agent and the destination, and all segments between them that don't cross an obstacle for edges: nothing ever moves in the wrong direction, always straight towards the target or towards a corner that has to be turned.

On the other hand if you constrain pathfinding to bad waypoints, either approximate ones that aren't very close to corners or meaningless ones like some agent's past positions, the paths are correspondingly more stupid than those computed on the correct navigation graph.

Caching paths, in the context of A* search, means trading memory for computation to remember all or most previous results (not a single path), effectively augmenting the navigation graph with additional edges that, when relevant, can replace a lot of repeated work.