生成网络的算法，该网络用源、水平线、直角、T 形接头和节点填充 10x10 网格？

Question

只是为了好玩，我正在尝试创建一个非 Flash 版本的 http://www.jurjans.lv/stuff/net/FreeNet.htm .这些都是非常简单的东西，但我在精神上一直纠结于如何生成初始网络。

我可以用大量的 if/else 逻辑检查相邻的方 block ，逐个方 block 地完成它，但坦率地说，这似乎非常费力，我想知道是否有更聪明的方法。生成数学图或类似的东西，然后将其转换为网格？

我不是要别人为我编写所有代码 - 只是为我指明正确的方向!

Answer 1

完成的电路看起来是一棵生成树。

有一种简单的方法可以生成 random minimum spanning trees通过:

assigning random weights from some distribution to the edges of an undirected graph, and then constructing the minimum spanning tree of the graph.

总结一下:

1. 构建一个图，每个正方形的中心都有一个顶点

2. 在每个顶点与其上/下/左/右相邻顶点之间添加边

3. 为每条边分配随机权重(例如从 0 到 1 的均匀实数)

4. 构造 minimum spanning tree例如使用 Prim 或 Kruskal

5. 将图形转换为图 block

如果您想禁止某些形状(例如完全连接的顶点)，您可能需要额外的迭代来增加任何非法图 block 中使用的边的权重，然后重新生成生成树，直到您最终得到合法的图表。