生成随机道路

Question

我试图在秋千应用程序上生成随机道路。但是，我无法创造这样的道路，使它们不会相互交叉。我的意思是一条路不应该跨越另一条路，除非它们有一个共同的交叉点。

我尝试生成随机点，并使用最小生成树连接它们，但它似乎不工作。

你有什么想法吗？

Answer 1

我会先尝试一下容易的事情：生成一堆随机道路并只保留那些与目前发现的不相交的道路。这有O(n^2)运行时，但很容易理解和实现。

伪代码：

points = (lots of random points) 
roads = empty list 
repeat n times: 
    r = road(pick_random(points), pick_random(points)) 
    if r does not intersect anything in roads list: 
    add r to roads 

这样做的好处超过最小生成树，它可以生成周期为你，这将使一个更有趣的公路网。