這種情況下的雙向數據結構

Question

我正在研究我的遊戲引擎的一小部分，並想知道如何優化某些部分。

的情況相當簡單，它是：

• 我有地圖Tile S（存儲在一個兩維數組）（〜26萬瓦，但承擔更多）
• 我有Item秒的列表，它始終是至少在大多數瓷磚
• 一個Tile在邏輯上包含的Item小號
• 無限量在遊戲執行許多Item s爲連續LY創建，他們從自身做起Tile
• 每Item連續地改變Tile到一個鄰居（上，右，下，左）

截至目前每Item有其實際Tile參考，我只是保留一個項目清單。 每次Item移動到相鄰的瓷磚時，我只需更新item->tile = ..，我很好。這工作正常，但它是單向的。

在擴展引擎的同時，我意識到我必須多次查找瓦片中包含的所有項目，並且這會有效地降低性能（特別是在某些情況下，我必須查找一系列瓦片的所有項目，逐個）。

這意味着我想找到適合自己的查找特定Tile的所有項目比爲O（n）更好的數據結構，但我想，以避免從一個平鋪「移動到多少開銷另一個「階段（現在只是分配一個指針，我想避免在那裏做很多操作，因爲它非常頻繁）。

我在考慮一個自定義數據結構，以利用項目總是移動到鄰居單元但我目前在黑暗中摸索的事實！任何建議，將不勝感激，即使棘手或神祕的方法。不幸的是，我不能浪費記憶，所以需要一個很好的折衷。

我正在用STL開發它，但沒有提升。 （是的，我知道關於multimap，它不滿足我，但我會嘗試，如果我沒有找到更好的東西）

Answer 1

struct Coordinate { int x, y; }; 
map<Coordinate, set<Item*>> tile_items; 

這將瓦片貼圖上的座標映射到指示哪些項目在該貼片上的項目指針集合。你不需要每個座標的條目，只有那些實際上有物品的條目。現在，我知道你說的這個：

，但我想避免的開銷在「從一個磚 移動到另一個」階段

而且這種方法將涉及在增加更多的開銷相。但是你有沒有嘗試過這樣的事情，並確定它是一個問題？

Answer 2

對我來說，我會包裝std::vector成矩陣類型（IE施加2d訪問在1d陣列上），這給你快速的隨機訪問你的任何瓷磚（實現矩陣是微不足道的）。

使用

vector_index=y_pos*y_size+x_pos; 

到索引大小

vector_size=y_size*x_size; 

的向量然後，每個項可以具有項目的一個std ::矢量（如果項的磚具有的量是非常動態的，也許一個deque）這些都是隨機訪問包含非常小的開銷。

我會遠離您的用例的間接容器。PS：如果你想你可以有我的矩陣模板。

Answer 3

如果你真的認爲每個瓷磚存儲它的物品會花費你太多的空間，考慮使用四叉樹來存儲物品。這使您可以高效地獲取瓷磚上的所有物品，但將物品移動的Tile網格保留原位。