这种情况下的双向数据结构

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网格保留原位。