背景
我正在开发一个简单的2D游戏，其中一些“僵尸”会追赶我。
我计算路径的想法如下（X = 路径不可用）：
[4] [4] [X] [1] [1] [2] [3] [4] [5][3] [X] [X] [0] [1] [X] [X] [X] [5][3] [2] [1] [1] [1] [X] [3] [4] [5][3] [2] [2] [2] [2] [2] [3] [4] [5]从0开始，给它周围的位置赋值1，靠近1的位置赋值2，以此类推。这样我只需要搜索较低的索引，就可以知道到达0的最快路径。
问题
(1) 我不知道这种算法是否有名称，因此我找不到相关的资料。
(2) 计算此路径的最佳解决方案/算法/流程是什么？
(3) 在我的手机上，游戏屏幕的分辨率为1700 x 1440，所以我的代码需要15秒。我创建了一个最终值来缩小所有内容并降低矩阵大小，但仍然需要很长时间，实际上无法玩。
(4) 是否有其他需求？也许需要添加线程？我不知道这样做是否有效…
我的代码 (调试代码已删除)
代码
private void expandAllFrom(int x, int y){ // x和y已经缩小 nodes = new ArrayList<Point>(); // "nodes"是一个全局变量 // nodes.add(new Point(x, y)); while ( nodes.size() > 0 ){ Point p = nodes.remove(0); expand(p.x, p.y); }}private void expand(int x, int y){ int limXMin = x - 1, limXMax = x + 1, limYMin = y - 1, limYMax = y + 1; int value = map[x][y]; // 检查屏幕边界 if ( limXMin < 0 ) limXMin = 0; if ( limXMax > SCREEN_X_DIV - 1) limXMax = SCREEN_X_DIV - 1; if ( limYMin < 0 ) limYMin = 0; if ( limYMax > SCREEN_Y_DIV - 1) limYMax = SCREEN_Y_DIV - 1; for (int i = limXMin; i <= limXMax; i++){ for (int j = limYMin; j <= limYMax; j++){ if ( map[i][j] == 0 ) { if ( i != x || j != y ){ nodes.add(new Point(i, j)); map[i][j] = value + 1; } } } }}解释
我使用了一个先进先出（FIFO）列表。我将节点添加到其中，例如，流程会是这样的：
(1) 将0位置添加到扩展节点列表中。(2) 通过在其周围设置1值来扩展0。然后将它们添加到扩展节点列表中。(2) 通过在其周围设置2值来扩展1。然后将它们添加到扩展节点列表中。(...)(X) 通过在其周围设置3值来扩展2。然后将它们添加到扩展节点列表中。(Y) 通过在其周围设置4值来扩展3。然后将它们添加到扩展节点列表中。(...)回答：
如前所述，你所做的是广度优先搜索，这是Dijkstra算法的一个特例。祝贺你自己发现了这一点！
问题在于，BFS的时间复杂度是O(V+E)，其中V是节点数，E是边的数量。在你的情况下，它将取决于地图的大小和地图的稀疏度（即有多少X）。无论如何，对于1700×1440大小的地图，这将是数百万的数量级。
如果僵尸的数量不是太多，逐个计算每个僵尸的最短路径会快得多（你仍然可以在僵尸之间共享和重用扩展的节点），使用带有启发式的BFS变体。例如，跳点搜索针对统一成本迷宫进行了优化（跳点搜索是A星算法的一个特例）。
这里的想法是从一个起点（僵尸的位置）和一个终点（玩家的位置）开始，计算它们之间的最短路径，首先扩展离目的地更近的节点。这里的“更近”是指到终点的近似距离较小。到达的节点的距离是已知的，A星将选择从起点到节点的距离加上从节点到终点的近似距离之和最小的节点。由于你允许对角移动，距离近似不能是曼哈顿距离，也不是欧几里得距离，因为近似必须是真实距离的下限。你可以使用例如max(│x-x’│, │y-y’│)。跳点搜索通过利用地图的迷宫结构，进一步排除更多的节点来改进这一点。
这个网站动画展示了几个这样的算法，你可以感受一下这些算法是如何工作的。
这种方法的好处是你不会搜索整个地图，只搜索僵尸和玩家之间的很小一部分。这可能比任何全尺寸的BFS算法快几个数量级。为了展示加速效果有多显著，请看以下图片。只有标记的节点被搜索探索：
另一个优点是，你可以在运行时间和僵尸的“聪明程度”之间进行权衡。你所要做的就是不要将这种算法一直运行到终点。你可以在预定义的步骤数后停止，并获得路径开始部分的近似值（通过查看起点和下一个最有希望扩展的节点之间的最短路径）。所以根据你有多少时间进行计算，你可以拥有最优或不太优的僵尸。
