創建一個隨機的2D凹面多邊形景觀JavaScript

Question

我正在寫一個簡單的月球登陸器克隆JavaScript（http://www.isogenicengine.com/demos/1.1.0/lander/），而不是一個基本的景觀，只是有高點和低點，我想要一個算法來產生隨機洞穴狀空間。給定一個與[0,0,192,1200]一起工作的矩形區域，算法應該能夠生成如下圖所示的內容。理想情況下，洞穴區域的任何「入口」都應該有一定的寬度，以便着陸器可以「進入」它。

我認爲，這也許是不可能的，而且我可以改爲只畫了一堆像上面的圖像的像素數據轉換成粗多邊形的數據，但它是這樣冷卻器有隨機產生的水平！

對於超級核心獎勵積分，指定多少洞穴狀結構的能力會更加棒。

該算法的輸出將是一個點數組，每個點都是一個包含x和y屬性{x：val，y：val}的對象，當您在當前點和下一個點之間依次繪製線條時，組成多邊形。

如果有人有一個類似的JavaScript實現，也會有很大的幫助！

Answer 1

從學習什麼氣泡圖開始就像在建築中使用一樣。這是一個空間的拓撲圖，氣泡是空間和線條來表示通道。我沒有找到任何一個偉大的網頁快速推薦，但做一個圖像搜索產生大量的例子。

氣泡圖可以被認爲是一個以氣泡爲頂點的圖。在你的例子中，將包括頂邊在內的「天空」模型化爲一個頂點。洞是另一個頂點，入口是邊。從這個角度來看，很容易產生儘可能多的像洞穴一樣的複雜性。下一個技巧就是把它變成幾何圖形。本質上，你想從圖的骨架中推出並在玩家可以導航的地方製作空洞。同時，您要確保這些空隙不會擠出太多，變薄或消除牆壁。所以你還需要模擬實體區域，這是用dual graph完成的。雙重圖形在原來的「底下」，在邊緣交叉點意味着衝突的解決方式，有利於空洞而不是固體。

總結：（1）用你想要的特徵做一個拓撲圖。 （2）爲圖形創建幾何圖形，爲每個頂點和每條邊的路徑分配一個位置。 （3）構建一個雙圖，並分配其幾何。 （4）通過向外擴展與每張圖相關聯的空間，解決衝突而不是堵塞。

您可能想要說服自己，最終幾何圖形的邊界列表可以通過圖形的半邊遍歷來生成，就像用一隻手在牆上走迷宮一樣。

Answer 2

如果您有興趣，可以使用行進方塊將標量值（可能從Perlin或Simplex Noise獲取）的2D場轉換爲一組邊線。當然，最終結果會取決於你如何得到二維場標量值（你如何操作Perlin或Simplex Noise）。

This是我能找到的最好的網站，詳細介紹了細節。（它並沒有像Marching Cubes，它的3D雙胞胎一樣有很好的記錄）

實際上，Wiki頁面非常好。