Algorithm(s) for finding moving entities in a maze

Question

A have a maze and character that's controlled by the player and a drone who has to find him (by itself). Does anyone know an (efficient) AI algorithm for doing something like this? P.S. I know there are several path finding algorithms(e.g. A*), but as far as I know these only work for finding the path between two nodes that "don't move" (this would work if my character was standing still, but that's obviously not the case).

Answer 1

If the "start point" is where the drone is, and the "end point" is to run into the player, about the best you can do using just a "standard" algorithm is to use A* periodically and from that determine where the drone needs to move.

As you get closer to the player, you will be calculating faster and faster since the search space is, in theory, smaller.

Using this, it would be possible for the player to find a set of positions that, when moving between them causes the drone to get "stuck" just moving back and forth, but those sorts of optimizations are situation-specific and a general algorithm won't include them.

Essentially, you do have a fixed search space each "frame", but you just have to run it each frame to decide what to do.

There are likely tweaks to A* that cover minor perturbations between runs, but I don't know any off the top of my head.