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

Question

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

Answer 1

源代码可在 Google Code上找到，因此您可以自己阅读并找出答案！迷宫由第78ff 行generate_maze中的函数生成。game.c

---

更新：试试演示！

Netwalk 通过运行Prim 算法的随机版本来找到最小生成树来生成迷宫。Prim 的算法从一个源节点（或多个节点：在本例中为“服务器”，深蓝色双高框）开始，一次迭代地生成一个分支。在算法运行的任何给定点，数据结构看起来像这样：

绿色的细胞是生长树枝顶端的细胞：它们仍然至少有一个空的邻居可以生长。在每一步，该算法都会选择其中一个绿色单元格，然后选择其一个空邻居⁽¹⁾，并在该邻居中添加一个分支。这个新的分支阻止相邻的分支向它的方向生长。当一个分支没有更多的空邻居⁽²⁾时，它将从绿色单元格列表中删除。

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

[我在几个地方理想化了细节：（1）实际上Netwalk算法有点天真，只是选择一个随机方向，如果那个方向的邻居非空，它什么都不做并继续到下一次迭代。(2)没有及时发现没有空邻居的分支：只有在恰好被选中时才会从绿色列表中删除。该演示修复了这些小问题。]