自适应路径Astar修改

Question

我想适应由Astar算法找到的路径，以便使用此路径的对象可以正确地对更改做出反应(例如。目标四处移动)。我还试图尽可能高效地这样做，如果可能的话，不需要重新计算整个路径。

路径获取看起来有点像：

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);
   }
}

我想过随着对象的移动，通过在当前路径的末尾添加新的Node来修改路径std::vector<Node> path。然而，这将是有问题的，因为如果目标正在关闭，修改后的路径将需要移动到他旁边，移动到旧目标的位置，然后开始向后移动到新位置。或者，我认为每5-10次移动都会重新计算路径。有没有更好的方法呢？

Answer 1

解决这类问题的标准方法是navmeshes，它包含大量预先计算的信息，以快速进行更新。有关更多详细信息，请参见示例here。

还有许多关于a星导航on the gamedev stackexchange的有用问题。