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

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

Netwalk game screenshot

来源

2011-07-07 boring

我已经根据已发布的答案的质量重新打开了此文件。然而，社区可以自由地不同意我的决定。我的推理是，答案证明这个问题确实是以客观的方式以建设性的方式回答 - 虽然我同意这个措词是相当广泛的。 –

@Tim：谢谢。 –

@Gareth Rees :) –

的source code is available在谷歌代码，这样你就可以自己读，找到了！迷宫由函数generate_maze在game.c行78ff中生成。

Update: try the demo!

Netwalk运行的Prim's algorithm随机版本找到一个minimum spanning tree产生一个迷宫。 Prim的算法一次从一个源节点（或多个节点：在这种情况下，“服务器”，深蓝色的双高度框）开始一次一个分支地迭代地生长一棵树。在算法的运行任何给定的时刻，数据结构看起来是这样的：

enter image description here

在绿色的细胞在生长枝的顶端细胞：他们仍然有至少一个空他们可能成长的邻居。在每一步中，算法选取其中一个绿色单元，然后选取其中一个空的邻居^（1），并向该邻居添加一个分支。这个新的分支阻止邻近的分支向其方向发展。当一个分支不再有空的邻居^（2），那么它将从绿色单元格列表中移除。

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

enter image description here

[我理想化了几个位置的详细信息：（1）实际上Netwalk算法是有点幼稚，只是挑选一个随机的方向，而如果在该方向上的邻居非空，它什么都不做，继续下一次迭代。（2）没有空的邻居的分支没有及时检测到：如果他们恰好被选中，他们只能从绿色列表中删除。该演示修复了这些小缺陷。]

来源

2011-07-07 09:45:04

非常感谢您指出游戏和演示背后的想法。这很酷。 – boring

这是一个非常广泛的客观答案。感谢您的贡献。 –

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

回答

相关问题