如何有效地存儲航點

我有一個非常大的地圖的遊戲，我需要存儲很多航點（百萬，如果不是數十億），然後使用它們進行尋路使用A *算法。如何有效地存儲航點

我需要的：

起初我以爲使用一個簡單的向量，但這會盡快使用所有可用的內存。然後我以爲我應該使用mysql，這可能是一個好主意，因爲我可以查詢數據庫的一個航點區域。

最大的問題是，對於A *我需要儘可能快地訪問航點，所以也許我需要每個航點的唯一ID。

完成此操作的最佳方法是什麼？

2013-01-11 Roberto

任何關於wp極值的幅度要求的線索？ – WhozCraig

你打算用常規網格中的點填充地圖，然後下載網格並在其上執行A *？實際上爲網格中的每個節點創建一個對象，無論它是否爲空，都是一個天真的實現......但是壓縮一個大部分爲空的網格也不應該很難。 – Potatoswatter

我喜歡在MSQL數據庫中存儲航點的想法，以便您可以直接訪問它們。這是非常現成的想法。我不確定這是否是一個好主意，但我從來沒有想過，如果指針和引用是間接的，那麼數據庫就是要走的路。 –

我認爲你應該考慮通過自己管理你的記憶來讓它稍微低一點---明確地爲圖的每個節點調用new和delete;並通過內存地址引用您的節點。如果您擔心分配大量小塊內存，則可以考慮使用tcmalloc庫。

節點應包含鄰接列表。如果圖形是靜態的，我建議將鄰接點存儲在每個節點中的動態創建的數組中，該大小恰好與鄰居數量匹配。如果鄰居的數量可以隨時間變化，那麼std::vector可能是下一個最好的事情。

注意：我假設圖形是不規則的。對於常規圖形（例如Potatoswatter指出的網格），可以隱式地獲知節點的位置。

2013-01-11 08:31:53 CygnusX1

圖應該是規則的（一個網格） – Roberto

回答