具有块而不是墙的深度优先搜索迷宫生成算法

Question

我正在尝试将深度优先搜索算法应用到我的游戏中.我一直在研究这个网页:http://www.mazeworks.com/mazegen/mazetut/index.htm,但却发现我无法使用块而不是Walls.我所说的块是一个覆盖整个单元格的正方形,而不仅仅是边缘.我认为用这种方式做起来会更容易,但现在我不太确定.有没有人这样做过？如果是这样,怎么样？(伪代码很好).或者,如果它更容易,我应该采用墙壁方法吗？

Answer 1

根据您实际希望实现的目标，我为您提供两种解决方案。它们基本上都是您引用的网站上提供的算法。

1.) 迷宫中的预定义位置有方块

• 2*k+1你在网格上运行算法
• 假设单元格的编号从左上角开始（0,0）。将所有具有 2 个奇数坐标 ( (2*p+1, 2*q+1); p,q < k) 的单元格标记为块。
• 您可以在剩余的单元格（“偶数单元格”）上运行来自源的修改后的算法。修改是：
  • 从随机选取的偶数单元格开始
  • “邻居单元格”是任何网格方向上的第二个但下一个单元格；即你“跳过”一块砖。
  • 您无需推倒牢房之间的墙壁，而是将块变成可进入的牢房。但是，选择和回溯不会考虑该单元格

2.）您需要的是块，而不是分隔单元格的墙壁。

在开始算法之前，将任意数量的单元格标记为块。按照源中所述进行操作，但切勿考虑任何块单元。如果您想保证迷宫中的完全无障碍，您必须采取特殊的预防措施。一个简单的方案是永远不会将单元格标记为具有超过 1 个块作为邻居的块。

希望这些想法适合您的需求，

最好的问候，卡斯滕