java - Android寻路算法

Question

上下文

我正在尝试开发一个简单的 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 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 过程，然后让每个僵尸朝它们当前所在单元格的父指针迈出即可。