生成Netwalk游戏中迷宫的算法是什么？

Question

6

游戏Netwalk中生成迷宫的算法是什么？

Netwalk game screenshot

- user235273

1

鉴于已发布的答案质量，我重新打开了这个问题。然而，社区可以自由地不同意我的决定。我的理由是，答案证明了这个问题确实可以客观地、建设性地回答，尽管我同意措辞相当宽泛。 - Tim Post

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Gareth Rees · Accepted Answer

源代码可在Google Code上获取，因此您可以自行阅读并发现！迷宫是通过函数generate_maze在game.c的第78行及以下生成的。

Netwalk运行随机版本的普林姆算法来寻找最小生成树从而生成迷宫。普林姆算法迭代地一次添加一个分支来增加这棵树的大小，从一个源节点（或多个节点：在本例中，是“服务器”，即深蓝色双高度框）开始。在算法运行的任何给定时刻，数据结构看起来像这样：

enter image description here

绿色着色的单元格是生长分支的末端单元格：它们仍然具有至少一个空邻居，可以向其中一个邻居生长。在每个步骤中，算法选择这些绿色单元格之一，然后选择其一个空邻居^（1），并向该邻居添加分支。这个新的分支会阻止相邻分支向其方向生长。当分支没有更多的空邻居时^（2），则将其从绿色单元格列表中删除。

最终，绿色列表为空：网络的任何分支都没有任何空邻居。这意味着该板已满，并且每个单元格都通过单个路径连接到服务器。

enter image description here

我在一些地方进行了理想化：（1）实际上Netwalk算法有点天真，只是随机选择一个方向，如果该方向的邻居不为空，则什么也不做并继续进行下一次迭代。（2）没有空邻居的分支不能及时检测出来：它们只有在被选择时才从绿色列表中删除。演示修复了这些轻微的缺陷。