生成随机道路

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

与最小生成树相比，它的优势在于它可以为您生成环路，从而形成更有趣的道路网络。