ruby - 理解递归回溯算法的 Ruby 实现

Question

我试图了解生成迷宫的递归回溯算法的特定 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 还是比较新的。

Answer 1

把迷宫想象成一个房间网格，每个房间都有自己的 独立 墙壁。

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 以查看显示的变化。