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

Question

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

Answer 1

source code is available在 Google Code 上，您可以自己阅读并找出答案!迷宫是由函数 generate_maze 生成的在 game.c 中，第 78ff 行。

---

Update: try the demo!

Netwalk 通过运行 Prim's algorithm 的随机版本生成迷宫找到一个minimum spanning tree . Prim 的算法从一个源节点(或多个节点:在本例中为“服务器”，深蓝色双高框)开始，每次迭代地生长一棵树。在算法运行的任何给定点，数据结构如下所示:

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

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

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