Gar*_*ees 15
该源代码可以在谷歌代码,这样你就可以自己读,找到了!由函数所产生的迷宫generate_maze中game.c,行78ff.
Netwalk通过运行Prim算法的随机版本来生成迷宫,以找到最小生成树.Prim的算法一次迭代地生成一个树,从源节点(或节点:在这种情况下,"服务器",深蓝色双高度框)开始.在运行算法的任何给定点,数据结构看起来像这样:
绿色的细胞是生长分支尖端的细胞:它们仍然至少有一个空的邻居可以生长.在每一步中,算法选择这些绿色单元中的一个,然后选择其中一个空的邻居(1),并在该邻居中添加一个分支.这个新的分支块邻近分支从其方向增长.当分支没有空的邻居(2)时,它将从绿色单元列表中删除.
最终绿色列表为空:网络的任何分支都没有任何空的邻居.这意味着电路板已满,每个单元通过单个路径连接到服务器.
[我在几个地方理想化了细节:(1)实际上Netwalk算法有点天真,只是选择一个随机方向,如果那个方向的邻居是非空的,它什么也不做,继续到下一次迭代.(2)没有及时检测到没有空邻居的分支:如果碰巧选择它们,它们只会从绿色列表中删除.该演示修复了这些轻微的不足之处.]