如何使用递归回溯器制作迷宫 java

Question

我一直在尝试使用给定的维基百科描述来编写递归回溯器，但我无法掌握如何在 java 中编写它。现在我一直在使用双 for 循环遍历所有单元格并使用 Math.random() 来帮助选择一个随机邻居。问题是我只是不知道如何获取邻居的索引并将其添加到堆栈中。如果有人能解释如何获取邻居的索引，我想我就能完成代码了。

Answer 1

在二维数组中，一个单元格可能有四个相邻单元格。例如，这是一个 4x4 网格：

     0   1   2   3
   -----------------
 0 |   |   | N |   |  
   -----------------
 1 |   | W | C | E |  
   -----------------
 2 |   |   | S |   |  
   -----------------
 3 |   |   |   |   |  
   -----------------

第 1 行位置 (x=2, y=1) 标记为 "C" 的单元格有四个相邻单元格，我已将其标记为 N、E、S 和 W。如果单元格位于您通过以下方式获得邻居：

。北邻位于 (x, y-1) .东邻居在位置 (x+1, y) .南邻居在位置 (x, y+1) .西邻居在位置 (x-1, y)

不过，您必须小心，因为如果不加以保护，这些计算可能会导致您在数组边界之外进行索引。要查看路线，您必须执行以下操作：

// check North neighbor
if (y > 0 && isNotOpen(a[y-1, x])) {
    ...
}

y > 0 检查可防止您在 y == 0 时尝试检查单元格 a[x, -1]。您必须为其他方向编写类似的检查以防止不正确的索引。

如何使用递归回溯器制作迷宫 java

how to make maze with recursive backtracker java

java

loops

stack

recursive-backtracking