多算法迷宫构建器的具体数据结构

Question

我已阅读this问题，并对我的问题做了研究，但是我发现我还没有合适的答案。

我想建立一个通用的数据结构在红宝石与我可以实现任何（2D，矩形）我认为合适的迷宫生成算法。首先，我将执行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 = [] 

但是现在我开始遇到关于如何存储特定细节的混淆。我应该有一个多维数组的单元格？细胞跟踪他们自己的四面墙吗？如果我这样做了，那么当我切换墙时，我必须增加复杂性，因为我需要获取相邻单元格的墙。如果我得到一个单元格来跟踪它的右侧和下侧墙，那么我会增加获取UP和左侧墙的状态的复杂性。

另一方面，如果单元格和墙壁保持在单独的列表中，我是否应该为所有的墙壁设置一个阵列，还是为上/下墙壁和左/右墙壁设置一个阵列？在第一种情况下，选择一个随机墙更容易，并且查询特定墙的状态，但实际结构更难 - 墙与网格很不一致。而且它让单元难以了解围绕它的墙。

我应该跟踪细胞吗？常识说他们需要成为对象，因为后面的一些算法会要求细胞知道设置了哪些对象。但是如果我想使用某种Graph，比如Adjacency Matrix，那么整个结构似乎只设置为跟踪墙。而且，对于大型迷宫来说，矩阵变得非常大。

这可能是一个分析麻痹的情况，但事实仍然是，我不知道开始。

Answer 1

为了避免重复壁信息，因为细胞可以共享墙壁。每个单元格只存储顶部和右侧墙的状态。您将需要处理最左侧列和最后一行的边框，因为它们的墙壁状态不会被覆盖。您可以通过引入包含该信息的虚拟单元来完成此操作。

创建一个哈希这样行10列5

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

所以细胞具有顶壁和无权墙。

获取单元格的所有墙。你必须查询它的底部和左侧的电池

因此，要获得所有的墙壁[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] ] 

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

因此，墙的信息被存储，单元格的墙被推断出来。

你也可以使用一个阵列，而不是一个散列来存储壁

Answer 2

的位置为每个小区和每个壁一个对象。每个单元格存储其坐标和像边界单元缺少条目的散列，如{"left"=>left_wall, "up"=>up_wall, "right"=>right_wall}。墙壁参考他们的两个相邻的单元格并存储它们是否是实体。迷宫对象存储单元的二维阵列。

由于您使用Ruby进行编程，因此我假设速度不是最重要的。我试图在简单使用和简单实施之间取得平衡。

以下是一些支持的操作。

1. 获取单元格的上邻居。在散列中查找"up"以获得墙。将细胞与墙壁的邻居之一进行比较;返回不相等的邻居。
2. 获取与单元格相邻的单元格。迭代哈希值并执行上一步。
3. 将墙标记为固体/不是。简单。
4. 查询墙的状态。简单。
5. 获取随机单元格。简单。
6. 获取随机墙。我们没有墙的列表，所以我们必须有一点聪明。选择一个随机细胞和一个随机方向。如果那个单元在那个方向上有一堵墙，那就把它归还。否则，请再试一次。我们可以使用类似的技术获得随机的左/右墙。