ruby - 多算法迷宫构建器的特定数据结构

Question

我已经读过this问题，并对我的问题进行了研究，但我发现我还没有合适的答案。

我想在 ruby​​ 中构建一个通用数据结构，用它我可以实现任何我认为合适的(二维、矩形)迷宫生成算法。首先，我将实现 Randomized Prim's和 Depth-First Search ，稍后我会想要实现 Sidewinder和别的。目标是能够生成各种不同外观的迷宫。仅供引用，墙并不是一个“填充”的单元格 - 它是两个相邻单元格之间的分隔物，并且要么是实心的，要么不是实心的。

但我面临的问题是所有算法都需要了解不同的事情。例如，Prim 表示选择一个 Cell 并将其 Walls 添加到 wall_list 中。没关系，我可以从这个开始:

class Cell
  def get_surrounding_walls
    # some code
  end
end


class Wall
  @solid = true
  def remove
    @solid = false
  end
end

wall_list = []

但现在我开始对如何存储特定细节感到困惑。我应该有一个多维单元格数组吗？细胞会追踪自己的四壁吗？如果我这样做，那么当我切换墙时，我必须增加复杂性，因为我还需要获取相邻单元格的墙。如果我让一个单元格仅跟踪其右墙和下墙，那么我会增加获取上墙和左墙状态的复杂性。

另一方面，如果单元格和墙维护在单独的列表中，我应该为所有墙使用一个数组，还是为上/下墙使用一个数组，为左/右墙使用一个数组？在第一种情况下，选择随机墙并查询特定墙的状态更容易，但实际构建更困难 - 墙与网格不能很好地对齐。这使得细胞更难了解它周围的墙壁。

我是否应该追踪细胞？常识说它们需要是对象，因为后来的一些算法将要求单元格知道它们的设置。但是如果我想使用某种 Graph ，就像 Adjacency Matrix ，那么整个结构似乎只设置为轨道墙。此外，对于大型迷宫，矩阵会变得非常大。

这可能是分析瘫痪的情况，但事实仍然是我不知道从哪里开始。。

Answer 1

为了避免重复墙壁信息，因为单元格可以共享墙壁。让每个单元仅存储顶墙和右墙的状态。您需要处理最左列和底行的边缘情况，因为它们的墙壁状态不会被覆盖。您可以通过引入包含该信息的虚拟单元来做到这一点。

创建这样的哈希

wall[[10,5]] = [1,0]

因此第 10 行第 5 列的单元格有顶墙，没有右墙。

获取牢房的所有墙壁。您必须查询它的底部和左侧单元格

因此，要获取 [10,5] 的所有墙壁，您需要像这样查询哈希

wall[[11,5]][0]
wall[[10,4]][1]

所以单元格 [10,5] 的全套墙是

[ wall[[10,5]][0], wall[[10,5]][1] , wall[[11,5]][0] , wall[[10,4]][1] ]

上面的数组是每面墙从顶部开始顺时针旋转的状态。

因此，墙壁的信息被存储，细胞的墙壁被推断出来。

您还可以使用数组而不是散列来存储墙壁的位置