什麼是在遊戲Netwalk中生成迷宮的算法？

在遊戲中生成迷宮的算法是什麼Netwalk？什麼是在遊戲Netwalk中生成迷宮的算法？

Netwalk game screenshot

來源

2011-07-07 boring

我已經根據已發佈的答案的質量重新打開了此文件。然而，社區可以自由地不同意我的決定。我的推理是，答案證明這個問題確實是以客觀的方式以建設性的方式回答 - 雖然我同意這個措詞是相當廣泛的。 –

@Tim：謝謝。 –

@Gareth Rees :) –

的source code is available在谷歌代碼，這樣你就可以自己讀，找到了！迷宮由函數generate_maze在game.c行78ff中生成。

Update: try the demo!

Netwalk運行的Prim's algorithm隨機版本找到一個minimum spanning tree產生一個迷宮。 Prim的算法一次從一個源節點（或多個節點：在這種情況下，「服務器」，深藍色的雙高度框）開始一次一個分支地迭代地生長一棵樹。在算法的運行任何給定的時刻，數據結構看起來是這樣的：

enter image description here

在綠色的細胞在生長枝的頂端細胞：他們仍然有至少一個空他們可能成長的鄰居。在每一步中，算法選取其中一個綠色單元，然後選取其中一個空的鄰居^（1），並向該鄰居添加一個分支。這個新的分支阻止鄰近的分支向其方向發展。當一個分支不再有空的鄰居^（2），那麼它將從綠色單元格列表中移除。

最終綠色列表爲空：網絡的分支都沒有任何空的鄰居。這意味着電路板已滿，並且每個單元都通過單個路徑連接到服務器。

enter image description here

[我理想化了幾個位置的詳細信息：（1）實際上Netwalk算法是有點幼稚，只是挑選一個隨機的方向，而如果在該方向上的鄰居非空，它什麼都不做，繼續下一次迭代。（2）沒有空的鄰居的分支沒有及時檢測到：如果他們恰好被選中，他們只能從綠色列表中刪除。該演示修復了這些小缺陷。]

來源

2011-07-07 09:45:04

非常感謝您指出遊戲和演示背後的想法。這很酷。 – boring

這是一個非常廣泛的客觀答案。感謝您的貢獻。 –

什麼是在遊戲Netwalk中生成迷宮的算法？

回答

相關問題