我试图了解生成迷宫的递归回溯算法的特定 Ruby 实现:https://weblog.jamisbuck.org/2010/12/27/maze-generation-recursive-backtracking
我已经阅读并(至少在某种程度上)理解了算法中的步骤。然而,由于我在 Ruby 方面缺乏经验,尤其是处理按位运算,Jamis Buck 在他的博客中提供的递归方法真的让我感到困惑。特别是第 40 和 41 行:
grid[cy][cx] |= direction
grid[ny][nx] |= OPPOSITE[direction]
我知道这里完成的 OR 操作是为了满足条件中所见的单元格“已经遍历”的要求:... && grid[ny][nx] == 0
不过,据我所知,就这些。为什么这些不能只是 bool 值呢?对 grid[ny][nx]
执行 OR 操作有什么意义?与最初存储的相反方向?对不起,如果这是我没有看到的微不足道的东西。总的来说,算法和 Ruby 还是比较新的。
最佳答案
把迷宫想象成一个房间网格,每个房间都有自己的 独立 墙壁。
Why couldn't these just be booleans instead?
作者指出
I generally implement the field as a grid of bitfields (where the bits in each cell describe which direction passages have been carved)
他实现了状态每个房间的 4 位,其中
0
是一堵墙,和1
是一个“ channel ”。如果你用 4 个 bool 值来实现它,你将花费更多的代码和内存。
What is the point of performing an OR operation on the grid[ny][nx] with the opposite direction originally stored?
用在两个房间之间开辟一条 channel 独立 您需要拆除的墙壁 两个墙壁。
例子:当你想制作北 channel 时,你必须拆除当前房间的北墙和相邻房间的南墙。
What is the meaning behind performing an OR operation on the "current" cell and the neighbor to its right?
(grid[y][x] | grid[y][x+1]) & S != 0
字面意思是“如果当前房间或正确的房间有南 channel ”。让我们翻译 this part伪代码:IF (current room has no Bottom wall) print " " ELSE print "_"
IF (current room has no Right wall)
IF (either(current room OR Right one) has no Bottom wall) print " " ELSE print "_"
ELSE
print "|"
END
空间更改为 .
,两个水平相邻的房间(带 channel )的底部看起来像___
或 ...
或 .._
或 _..
第 59 行控制此模式中第二个字符的逻辑。您可以修复种子(第 14 行),然后在第 59 行(
(grid[y][x] & grid[y][x+1]) & S != 0
)中更改按位 AND 的按位 OR 以查看显示的变化。
关于ruby - 理解递归回溯算法的 Ruby 实现,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/65614614/