在網格上隨機生成有向圖

我想隨機生成一個有向圖，目的是製作一個類似於來自寵物小精靈的冰滑動拼圖的益智遊戲。在網格上隨機生成有向圖

實際上，這就是我希望能夠隨機生成：http://bulbanews.bulbagarden.net/wiki/Crunching_the_numbers:_Graph_theory

我需要能夠限制圖的大小在x和y維度。在鏈接示例中，它將被限制爲8x4網格。

我運行的問題不是隨機生成圖形，而是隨機生成一個圖表，我可以在2d空間中正確繪製圖表，因爲我需要某個節點（如岩石）在節點的另一側，當你停止滑動時，讓它在視覺上有意義。與此有關的問題是，有時岩石會在兩個其他節點之間的路徑中結束，或者可能在另一個節點本身上，導致整個圖形斷開。

在與我認識的幾個人討論這個問題後，我們得出了一些可能導致解決方案的結論。在構建時將網格中的障礙物作爲圖的一部分。從一個完全填充的網格開始，只需繪製一條隨機路徑並刪除將使該路徑起作用的塊，但問題則是找出要刪除的路徑，以免意外引入更短的路徑。我們也認爲動態編程算法可能是有益的，儘管我們都不擅長從無關創建動態編程算法。任何關於這個問題被官方稱爲什麼的想法或參考（如果它是一個官方的圖形問題）將是最有幫助的。

來源

2012-01-16 Talon876

不錯的問題，但可能更適合Programmers SE網站。我的直覺不是嘗試生成圖形，而是先從隨機放置障礙開始，然後從中推導出圖形。 – voidengine 2012-01-17 14:42:58

我也嘗試過，並且最終不得不重新運行它以獲得一個好的。從開始到結束解決步驟的數量定義良好。而這需要一段時間，因爲它本質上是強制解決方案。我會再次在Programmers SE中再次問，謝謝。 – Talon876 2012-01-18 00:57:32

我不會把它看成一個圖形問題，因爲正如你所說的表示是不完整的。要生成一個謎題，我會直接在網格上工作，並向後工作;首先修復目的地，然後以某種方式放置岩石從一個或多個地點到達，並反覆添加石塊以達到其他地點，限制條件是您永遠不會添加破壞到目的地的所有路徑的石頭。

來源

2012-02-25 11:51:18 mitchus

您可能希望生成planar graph，這意味着圖形的邊緣在二維空間中不會相互重疊。平面圖的另一個定義是，每個平面圖都沒有K_3,3類型的完整子圖（具有六個節點的完整雙分圖）或K_5（具有五個節點的完整圖）。

在快速生成平面圖上有一個paper。

來源

2012-06-29 14:03:22 thestoneage

在網格上隨機生成有向圖

回答

相關問題