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 程序，然后让每个僵尸走向它们当前所在单元格的父指针。