所以，我在考慮製作一個簡單的隨機世界生成器。這個發生器會創建一個起始「單元」，它有一到四個隨機出口（在基本方向上，像迷宮）。在決定完成這些退出之後，我會在每個出口處生成一個新的隨機「單元格」，並在玩家接近世界尚未生成的部分時重複。這個概念將允許一個「無限」的世界各種隨機生成的世界。然而，我不確定如何在內部最好地表達這一點。隨機世界的數據結構
我使用C++（這並不重要，我可以實現任何必要的數據結構）。起初，我想過使用一種有向圖，其中每個節點都將邊定向到周圍的每個單元，但如果用戶在世界中找到一個點，回溯到這個點，那麼這可能不會奏效從另一個方向點。世界可能會做一些奇怪的事情，比如在一個地方生成兩個單元格。
對於這種情況，哪種數據結構可能最有效？還是我在隨機的世代中做一些真正愚蠢的事情？
任何幫助將不勝感激。 謝謝， Chris
A map< pair<int,int>, cell>可能會工作得很好;該對將代表x，y座標。如果在這些座標的地圖中沒有單元格，請創建一個新的單元格。如果你想使它真正無限，你可以用你必須提供的任意長度的整數類來替換整數（例如bigint）
難道你沒有存儲的散列（或STL集）嗎？包含佔用單元格的所有網格座標的集合？
然後，當您在創建一個新的單元格時，可以快速檢查候選單元格位置是否已被佔用。 （如果你有有限的空間，你可以使用一個二維數組 - 我想我在一篇Byte雜誌的文章中看到了〜1980年 - 但是如果我理解正確，你想要一個可以無限延伸的世界）
如果世界的細胞排列成一個網格，你可以很容易地給他們笛卡爾座標。如果您保留現有單元格的大列表，那麼在確定從給定單元格退出之前，可以檢查該列表以查看它的任何鄰居是否已經存在。如果他們這樣做，並且你不想擁有單向門（有向圖？），那麼你就必須考慮他們的退出。如果您不介意在遊戲中安裝滑槽，您仍然可以隨意選擇退出，只要確保已連接到現有單元即可。
優化說明：檢查散列表以查看它是否包含特定鍵是O（1）。
唯一的問題是，一旦世界變大，查找時間會開始變糟，對嗎？ – 2010-10-22 17:03:16
如果他使用散列表，則不需要。 – nmichaels 2010-10-22 17:05:27
關於單向門的好處以及對有向圖的需求。 – 2010-10-22 17:51:29
我建議你閱讀關於圖。這正是隨機圖生成的應用。不是'cell'和'exit'，而是描述'node'和'edge'。
再加上，你可以做最短路徑分析，循環檢測和各種其他有用的圖論應用。
This將幫助您瞭解有關節點和邊：
和here是這些概念完成的應用程序。我以OOP的方式實現了這一點 - 每個節點都知道它是其他節點的邊緣。一個流行的選擇是使用adjacency list來實現這一點。我認爲鄰接表概念基本上是user470379用他的答案描述的。但是，他的地圖解決方案允許使用無限圖，而傳統的鄰接列表則沒有。我喜歡圖論，這是它的完美應用。
祝你好運！
布賴恩J. Stianr-
我真的很想使用圖表，也許我會的，我不得不四處看看。我只是覺得HashMap可能更有效率。 – 2010-10-22 17:18:20
這隻取決於你想要做什麼，以及你想如何解決問題。如果你正在談論一個人類玩家會與之互動的東西，我認爲把這個想法看作一個圖形的清晰度將超過你通過使用HashMap獲得的任何效率收益。你真的關心你的程序是否需要一秒來生成一個容易推理的隨機圖，而生成一個難以調試或應用任何現有算法的HashMap的1/10秒？ – 2010-10-22 17:23:09
我不能相信我沒有想到這一點，它的這樣一個簡單的解決方案和快速。 – 2010-10-22 17:02:52
正如@Nathon提到的一個新單元格一樣，一定要檢查相鄰單元格是否存在，並根據需要創建/防止進入這些相鄰單元格的門。 – jholl 2010-10-22 17:09:51