生成隨機道路

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 

這樣做的好處超過最小生成樹，它可以生成周期爲你，這將使一個更有趣的公路網。