如何在隨機生成的六角形地圖中查找島嶼？

我正在爲Codigniter和JQuery中的遊戲編程風險。我想出了一種方法來創建隨機生成的地圖，方法是對瓦片進行完整佈局然後刪除隨機地圖。但是，這有時會產生我稱之爲島嶼的情況。如何在隨機生成的六角形地圖中查找島嶼？

存在風險，您只能攻擊一個空間。所以如果一個玩家碰巧擁有一個他們自己的小島，他們永遠不會失去活力。

我試圖找到一種方法，我可以在遊戲開始查看它是否有島嶼之前檢查地圖。

我已經想出了一個函數來找出每個空間有多少個相鄰的空間，但我不知道如何實現它以找到島嶼。

每個失蹤點也被確定爲「水」。

我不能使用圖片代碼： http://imgur.com/xwWzC.gif

來源

2009-08-17 J3nnings

有一個標準名稱爲這個問題，但我的頭頂部以下可能的工作：

隨機
顏色選擇任何瓷磚它
顏色鄰國
顏色的鄰居的鄰居
將其鄰居的鄰居的鄰居等顏色

完成後（即當所有的鄰居都被着色時），遍歷所有瓷磚的列表以查看是否有任何靜止/留下未着色（如果是的話，他們是一個島）。

來源

2009-08-17 00:07:45 ChrisW

這肯定會奏效，非常感謝。 – J3nnings 2009-08-17 00:12:15

[笑話：http：//xkcd.com/221/展示瞭如何隨機選擇一個瓷磚] – ChrisW 2009-08-17 00:21:49

這將起作用，但描述並不能完全解釋問題，特別是，「如果是這樣，他們是一個島」。這可能是最初選擇的瓷磚是島的一部分，無色瓷磚是「大陸」的一部分。如果你在找到一個島嶼時重新生成整個地圖，這是可以的，但如果你打算只重建受影響的地區，這可能是一個問題。 – Imagist 2009-08-17 00:41:54

你怎麼做隨機生成？可能最好的方法是在這個時候解決它。當你生成地圖時，如果你注意到你剛創建的地圖是不可能的，你可以通過添加適當的元素來解決它。

儘管我們需要知道你是如何做這一代的。

來源

2009-08-17 00:05:07

+1。每次選擇一個要刪除的圖塊時，檢查是否有從每個相鄰圖塊到相鄰圖塊的路徑。 – 2009-08-17 12:05:00

我遇到了與OP類似的問題，並且我同意你修復代碼更好。 – Dolphin 2009-08-20 20:19:42

在您的數據集上運行模糊的內核。

治療六角形格子作爲圖像（它是，排序的）

值（X，Y）=所有瓦片的平均解決此（X，Y）

這將略微侵蝕海灘，並消除島嶼。

作爲練習，學生可以在結果數據集上運行邊緣檢測內核來填充沙灘圖塊。

來源

2009-08-17 00:29:46

這是你的基本的深度優先遍歷開始隨機瓷磚，僞編碼在蟒蛇般的語言：

visited = set() 
queue = Queue() 
r = random tile 
queue.add(r) 
while not queue.empty(): 
    current = queue.pop() 
    visited.add(current) 
    for neighbor in current.neighbors(): 
     if neighbor not in visited: 
      queue.add(neighbor) 
if visited == set(all tiles): 
    print "No islands" 
else: 
    print "Island starting at ", r

來源

2009-08-17 04:01:26 hughdbrown

這有望提供另一種解決方案。我使用的術語是「斷開的組件」，而不是「孤島」，因爲它只關係到所有瓷磚是否可以從所有其他瓷磚中獲得（如果存在不連貫的組件，那麼如果他的屬地都在一個組件中，則玩家無法通過征服獲勝）。

迭代所有'土地'瓦片（容易做到）併爲每個瓦片在圖形中生成一個節點。
對於每個頂點，將其與一個無向邊連接到表示其鄰居貼圖的頂點（最多6個）。
選取任何頂點並從中運行深度優先搜索（或麪包優先）。
如果DFS找到的頂點集合等於所有頂點的集合，則不存在斷開的組件，否則存在斷開的組件（島）。

這應該（我認爲）在時間O（n）運行，其中n是地塊的數量。

來源

2009-08-17 19:01:26 tw39124

最差情況下的時間可能會在O（n log6 n）時間內運行。 – jmucchiello 2009-08-17 19:15:21

如何在隨機生成的六角形地圖中查找島嶼？

回答

相關問題