在 Java 中寻路，在每个方块上踩一次

Question

我目前遇到了在地块地图上寻路的问题：我有一个 ArrayList<ArrayList<Byte>>，它确定 list.get(y).get(x) 处的地块是否被阻挡，以及起始位置。现在我想知道是否有一条路径，从原点开始，遍历 each 个非阻塞瓦片 once，如果有，我想要打印出说明，例如 'NWWEW'。我已经通过使用 floodfill 检查每个未阻塞的图块是否连接到所有其他图块（因此，应该只有一个区域连接的非阻塞图块），但是我仍然需要了解如何继续 'path-but-each-tile-only-once'-事情。

如果有人有任何想法或算法，我将不胜感激

编辑： 好吧，我想我已经明白了，但是由于问题已经关闭，我不得不在这里写下解决方案：

（感谢@Jack 为我指明了正确的方向）首先，程序检查当前瓦片是否可行走；然后它将被标记为已访问，并且将如何访问它的方向添加到方向字符串中。之后，我为每个方向递归调用此函数，直到 total-directions-string 的长度等于 整个地图上可访问图块的总数 - 1。如果不相等，则去掉自身被访问的方向returns到上层

代码：

public static void findPath(int x, int y, String direction){

    if(pathFound)
        return;

    if(map.get(y).get(x) == 0){

        map.get(y).set(x, (byte) 1);

        directions += direction;

        findPath(x, y-1, "N");
        findPath(x, y+1, "S");
        findPath(x-1, y, "W");
        findPath(x+1, y, "O");

        if(directions.length() == totalFreeTiles-1){
            pathFound = true;
            return;
        }

        if(directions.length() > 0)
            directions = directions.substring(0, directions.length()-1);

        map.get(y).set(x, (byte) 0);

    }
}

Answer 1

不确定我是否理解正确，所以这就是我认为你想要做的：

您的 Matrix X * Y 有障碍。你不在乎如何，但你想知道是否存在从地点 A 到地点 B 的方式，它会引导你通过矩阵，准确地触摸每个瓷砖？对不起，如果这很明显，但我想重复一遍，因为我第一次读它是 "Iterate through the matrix ones and give me any path".

对我来说，这听起来像是一种回溯算法。 https://en.wikipedia.org/wiki/Backtracking

你从位置 X（比如左上角）开始，然后迈出一步。然后您的接受方法检查：

(a) 这个磁贴被屏蔽了吗？ (b) 我已经来过这里了吗？

如果这两个条件 return 都为假，则您踩到该图块并将其标记为 "stepped on"。如果您对其中任何一个问题的回答是 "yes"，您可以尝试不同的拼贴。如果没有剩余的图块，则转到上一个图块。如果你到达目的地，你已经找到了一条路径，你可以打印它。如果你回溯到你的原点，没有更多的步骤，那就没有办法了。

Answer 2

您可以通过实施回溯算法来实现目标。

我会使用两个全局变量：结果字符串（我们称之为 "direction" 初始化为空）和一个三态类型的矩阵（我们称之为 "matrix"）。即：

尚未访问的磁贴
磁贴已经访问过
磁贴被起始参数阻塞

然后实现一个例程，给定一个瓦片和到达它的方向，递归地探索相邻的瓦片。例程应该这样做：

如果磁贴已被访问或阻止，则 return
如果图块可见，则将矩阵[当前图块]标记为已访问
通过添加到达此图块的方向更新 "direction"
如果没有更多的免费方块，则打印 "direction" 您就赢了
否则递归调用所有 8 个相邻图块上的例程
然后从 "direction" 中删除最后一个方向，将矩阵 [current-tile] 标记为尚未访问并且 return

作为例程的原型，我建议使用索引矩阵，这样您就可以轻松检查矩阵边界

在 Java 中寻路，在每个方块上踩一次

Pathfinding in Java, stepping on each tile once

java

algorithm

path-finding