针对这种情况的双向数据结构

Question

我正在研究我的游戏引擎的一部分，并思考如何优化其中的某些部分。

情况非常简单，如下所示：

- 我有一个Tile（存储在二维数组中）地图（~260k个tile，但假设更多）。 - 我有一个Item列表，它始终位于至少一个Tile和最多一个Tile中。 - 一个Tile可以包含无限数量的Item。 - 在游戏执行期间，许多Item会不断被创建，并从它们自己的Tile开始。 - 每个Item不断将其Tile更改为其邻居之一（向上、向右、向下、向左）。

到目前为止，每个Item都有对其实际Tile的引用，我只保留了一个物品列表。每当一个Item移动到相邻的Tile时，我只需更新item->tile = ...，这很好用。这很好用，但是它是单向的。

在扩展引擎时，我意识到我必须多次查找包含在Tile中的所有Item，而这实际上会降低性能（特别是在某些情况下，我必须逐个查找一系列Tile的所有项）。

这意味着我想找到一个适合更好地查找特定Tile中所有项目的数据结构，而不是O(n)，但我想避免在“从一个Tile移动到另一个Tile”阶段中产生过多的开销（现在只是分配指针，我想避免在那里进行许多操作，因为这是相当频繁的）。

我正在考虑使用自定义数据结构来利用项目始终移动到相邻单元格的事实，但目前我还没有头绪！任何建议都将不胜感激，即使是棘手或神秘的方法。不幸的是，我不能浪费内存，因此需要良好的权衡。 我正在使用C++和STL进行开发，但没有使用Boost。（是的，我知道multimap，但它并不令我满意，但如果找不到更好的东西，我会尝试的）。

- Jack

Answer 1

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

这将在瓦片地图上将坐标映射到Item指针的集合，指示哪些项目在该瓦片上。您不需要为每个坐标都添加条目，只需添加实际上有项目的坐标即可。现在，我知道你说过这句话：

但是我想避免在“从一个瓦片移动到另一个瓦片”的阶段中产生太多开销

而这种方法将在该阶段增加更多开销。但是您是否已经尝试过这样做并确定它是一个问题？

- Benjamin Lindley

Answer 2

如果你认为让每个瓦片存储它的物品会占用太多空间，那么考虑使用四叉树来存储物品。这样可以高效地获取瓦片上的所有物品，但同时保留了瓦片网格以便移动物品。

- cliclcly

Answer 3

对我来说，我会将一个std::vector封装成矩阵类型（即在一维数组上施加二维访问），这样可以快速随机访问任何一个瓦片（实现矩阵是微不足道的）。

使用：

 vector_index=y_pos*y_size+x_pos;

对大小为向量进行索引

 vector_size=y_size*x_size;

然后，每个项目都可以有一个std::vector的项目（如果瓷砖拥有的项目数量非常动态，可能是deque），这些都是随机访问包含非常少的开销。

我建议您在您的用例中避免使用间接容器。

附注：如果您想要，您可以使用我的矩阵模板。

- 111111

---

“Tile”地图已经是一个原始的二维指针，例如Tile map[WIDTH][HEIGHT]，因此我可以随机访问整个地图，但我不想为每个瓦片都有一个物品列表，因为这些物品是稀疏的，并且不占据地图本身的大区域。 - Jack

那听起来就像是糟糕的设计。首先，摆脱固定大小的数组，使用具有适当接口的向量；其次，通过给予Tile本地向量或其他方式，使其拥有自己的项目。 - 111111

这不是一个糟糕的设计，整个世界都需要地图。每个瓷砖存在的原因不是因为物品，而是因为许多其他事情。正如我所说，这只是引擎的一小部分 :) - Jack

是的，但如果一个项目必须拥有一个“Tile”，那么“Tile”肯定应该拥有该项目。如果您不使用它，空向量不会占用太多空间。 - 111111