如何利用C++中的寻路算法让敌人追赶玩家？

Question

我正在使用 SDL2 和 C++ 制作游戏。我的问题是我正在尝试使用寻找路径算法（A*）来创建一个追逐玩家的敌人。我的想法是获取玩家每个时刻和矩形的更新，然后在玩家和敌人之间创建路径。问题是：这使得我的游戏非常滞后。这是因为我每次都会创建路径。谁能帮助我这个想法，让我的游戏运行得更快？

void Engine::update()
{
    Astar::Vec2i v{int(player->GetOrigin()->X/16), int(player->GetOrigin()->Y/16)};
    Astar::Vec2i e{int(enemy1->GetOrigin()->X/16), int(enemy1->GetOrigin()->Y/16)};
    auto path = generator.findPath(v, e);
    for (auto &co : path)
    {
        std::cout << co.x << " " << co.y << std::endl;
    }
    // to get the rect of the enemies and player and then create path
}

Answer 1

如果仅当该算法处于活动状态时才发生滞后，则它应该是导致滞后的原因（在进行任何优化之前确保是这种情况）。

由于算法太慢而无法运行每个价格变动，以下优化可能会有所帮助：

• 将敌人分成X个大小相等的小组。每个刻度仅更新一组。 （例如 3 组，因此在第 1 个刻度时，仅计算第 1 组中的敌人，在下一个刻度时计算第 2 组中的敌人，...在第 4 个刻度上再次更新第 1 组）。
• 仅当敌人在先前路径上移动了至少距离 D 时才更新 A* 算法。 （也许这个距离取决于到玩家的剩余距离，例如 `D = std::min(playerDist*0.2, D_MAX)）
• 无需在每个周期进行完整更新，只需将玩家移动添加到之前的计算中，并仅每 X 个周期进行一次完整更新。
• 检查您的 findPath 函数以查看是否可以对其进行优化（例如，使用上次运行的预先计算）

还有更多选项...（例如多线程和后台任务...）

Answer 2

首先，我认为对于普通的敌人AI来说，没有必要每帧都调用findPath。你可以用适当的速率来做到这一点。

A* 算法是为静态环境设计的，但显然你的玩家会不断移动，这意味着 findPath 调用的每个结果仅对当前帧有用，这是一个巨大的浪费。

您可以查看D*(Dynamic A Star)算法，它是针对动态环境设计的，更适合您的需求。但执行起来仍然非常昂贵。

如果你的敌人AI不需要非常精确的路径，你可以用一些更简单的算法替换A* findPath。比如这个.

你可以查看Navimesh，它是现代游戏中流行的解决方案。它的主要思想是将你的游戏地图划分为一系列区域。像 A* 这样的算法找到了区域的路径，像我上面所说的简单算法将引导智能体到达区域中的目标点。

寻路是一个复杂的话题，这里只是我的观点。我的英语不是很好，如果有错误请原谅。希望可以帮到你。