Adaptive path - Astar modification

Question

I want to adapt path found by Astar algorithm so object using this path could properly react to changes (ex. target moving around). I also try to do this as efficient as possible, without recomputing whole path if possible.

Path accusition looks somewhat smiliar to:

class Astar
{
   void findPath(std::vector<Node> &path)
   {
      std::vector<Node> open;
      std::vector<Node> closed;
      //find path
   }
}

class Foo
{
   std::vector<Node> path;
   Astar astar;

   void findPath()
   {
      astar.findPath(path);
   }
}

I thought about modyfing path std::vector<Node> path by adding new Node at the end of current path as object moves. This however would be problematic because if target is closing, modified path would require to move next to him, move to the old target's position and then start moving backwards to new postion. Alternatively I thought about to every 5-10 moves recompute path. Is there better way to do this?

Answer 1

The standard approach for this kind of problem are navmeshes, which contain a lot of precomputed information to make updates fast. See for example here for more details.

There are also many useful questions regarding a-star naviation on the gamedev stackexchange.