由网友(一季浅舞)分享简介：什么是算法生成的迷宫游戏 Netwalk ？What is the algorithm for generating the maze in the game Netwalk?推荐答案在源code是在谷歌code可，这样你就可以自己读，找到了！迷宫由函数 generate_maze 在 game.c ，行78f...

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

What is the algorithm for generating the maze in the game Netwalk?

推荐答案

在源code是在谷歌code可，这样你就可以自己读，找到了！迷宫由函数 generate_maze 在 game.c ，行78ff。

The source code is available at Google Code, so you can read it for yourself and find out! The maze is generated by the function generate_maze in game.c, lines 78ff.

更新！试试演示

Netwalk通过运行一个随机版本 Prim算法的找到生成的迷宫< A HREF =htt​​p://en.wikipedia.org/wiki/Minimum_spanning_tree相对=nofollow>最小生成树。 Prim算法迭代地增长一次分支树的时间，从源节点开始（或节点：在这种情况下，服务器，深蓝色的双高度框）。在算法的运行任何给定的点，数据结构看起来是这样的：

Netwalk generates a maze by running a randomized version of Prim's algorithm to find a minimum spanning tree. Prim's algorithm iteratively grows a tree once branch at a time, starting from a source node (or nodes: in this case, the "server", the dark blue double-height box). At any given point in the running of the algorithm, the data structure looks something like this:

以绿色的细胞是细胞的生长枝的秘诀：他们仍然有至少一个空邻居到他们可能会增长。在每一步，算法挑选这些绿色细胞中的一个，然后再挑选其空的邻国之一（1），并增加了一个分支到该邻居。这种新的支传导阻滞从它的方向不断增长的相邻分支。当一个分支已经没有更多的空邻居（2），那么它是从绿色细胞的名单中删除。

The cells coloured in green are cells at the tips of the growing branches: they still have at least one empty neighbour into which they might grow. At each step, the algorithm picks one of these green cells, and then picks one of its empty neighbours(1), and adds a branch into that neighbour. This new branch block neighbouring branches from growing in its direction. When a branch has no more empty neighbours(2), then it is removed from the list of green cells.

最后，绿列表为空：无网络的分支机构有任何空的邻居。这意味着该板是满的，并且每一个小区由一个单一的路径连接到所述服务器

Eventually the green list is empty: none of the branches of the network have any empty neighbours. This means that the board is full, and every cell is connected to the server by a single path.

[我理想化了几个地方的细节：（1）其实Netwalk算法是有点幼稚，只是选择一个随机的方向，如果这个方向邻居非空，它无关，并继续下一次迭代。 （2）分行没有空的邻居没有及时发现：他们只是从绿色清单中删除，如果他们正好被选中。该演示解决这些小infelicities。]

[I've idealised the details in a couple of places: (1) in fact the Netwalk algorithm is a bit naïve, and just picks a random direction, and if the neighbour in that direction is non-empty, it does nothing and continues to the next iteration. (2) Branches with no empty neighbours are not detected in a timely manner: they are only removed from the green list if they happen to be selected. The demo fixes these minor infelicities.]