Android寻路算法

Question

上下文

我正在尝试开发一个简单的 2D 游戏，其中一些 "zombies" 会追我。

我计算路径的想法如下（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)最优化solution/algorithm/flow来计算这个

(3) 在我的手机中，游戏屏幕的分辨率为 1700 x 1440，因此我的代码需要 15 秒。我创建了一个最终值来缩小所有内容并降低矩阵大小，但是，仍然需要很多，实际上无法播放。

(4)还有其他需求吗？也许添加线程？我不知道那是否可行...

我的代码（调试代码已删除）

代码

private void expandAllFrom(int x, int y){ // x and y already scalled down
    nodes = new ArrayList<Point>(); // "nodes" is a global variable //
    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];

    // Check limits of screen
    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) Add 0 position to expand node list.
(2) Expand 0 by setting 1 values arround it. Then add them to expand node list.
(2) Expand 1 by setting 2 values arround it. Then add them to expand node list.
(...)
(X) Expand 2 by setting 3 values arround it. Then add them to expand node list.
(Y) Expand 3 by setting 4 values arround it. Then add them to expand node list.
(...)

Answer 1

这就是breadth-first search (BFS)，用来求单源最短路径。您要计算的数字与每个网格单元格所在的级别完全对应。好的是，通过正确实施 BFS，您不需要这些数字。只需在玩家位置开始 BFS 程序，然后让每个僵尸走向他们当前所在单元格的 parent-pointer。

Answer 2

如前所述，你所做的就是breadth first search, which is a special case of Dijkstra's algorithm。为自己找到答案干得好！

问题是，BFS的时间复杂度是O(V+E)，其中V是节点数，E是边数。在您的情况下，它将按照地图大小的顺序排列，具体取决于地图的稀疏性（即有多少个 X-es）。对于大小为 1700x1440 的地图，无论如何都是数百万的数量级。

如果僵尸的数量不是太多，一个一个计算每个僵尸的最短路径会更快（你仍然可以共享和重新使用僵尸之间扩展的节点），使用变体具有启发式的 BFS。例如，jump point search is optimized for uniform cost mazes (jump point search is a special case of the A-star algorithm).

这里的思路是取一个起点（僵尸的位置）和一个终点（玩家的位置），计算它们之间的最短路径，先展开离目的地较近的节点。这里越近意味着到端点的近似距离越小。到达节点的距离是已知的，A星会选择起点到该节点的距离加上该节点到终点的近似距离之和最小的节点。由于您允许对角线移动，因此距离近似值不能是 Manhattan distance，也不是欧几里得距离，因为近似值必须是实际距离的下限。你可以拿例如。最大（│x-x'│，│y-y'│）。跳跃点搜索通过利用地图的迷宫结构进一步改进了这一点，以排除更多节点。

This site 以动画形式展示了几种此类算法，以便您了解这些算法的工作原理。

这种方法的好处是你不会搜索整个地图，只搜索僵尸和玩家之间的一小部分。这可能已经比任何全尺寸 BFS 算法快几个数量级。要显示加速有多么显着，请查看以下图片。搜索仅探索标记的节点：

另一个好处是，你可以在运行宁时间和'cleverness'僵尸之间做出妥协。你要做的就是不运行这样的算法一路走到终点。您可以在预先定义的步数后停止，并仅获得路径起点的近似值（通过查看起点和下一个最有希望扩展的节点之间的最短路径）。因此，根据您有多少时间进行计算，您可以得到最优或次优的僵尸。

Android寻路算法

Android path seeking algorithm

java

algorithm

android

artificial-intelligence

上下文

问题

我的代码（调试代码已删除）

代码

说明