语境

我正在尝试开发一个简单的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秒。我创建了一个最终值来缩小和缩小矩阵的大小，但是，stil花费了很多，实际上是无法玩的。

（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.
(...)