6

我正在研究我的游戏引擎的一小部分，并想知道如何优化某些部分。

情况很简单，如下：

  • 我有一张Tiles 的地图（存储在一个二维数组中）（~260k 瓷砖，但假设更多）
  • 我有一个Items 列表，它们总是至少和最多一个 tile
  • ATile在逻辑上可以包含无限数量的Items
  • 在游戏执行过程中，许多Items 不断创建，它们从自己的开始Tile
  • 每个Item不断地改变它Tile的邻居之一（上，右，下，左）

到目前为止，每个Item都引用了它的实际Tile，我只保留了一个项目列表。每次Item移动到相邻的图块时，我都会更新item->tile = ..，我很好。这工作正常，但它是单向的。

在扩展引擎时，我意识到我必须多次查找拼贴中包含的所有项目，这实际上会降低性能（尤其是在某些情况下，我必须逐个查找一系列拼贴的所有项目） .

这意味着我想找到一个适合于找到特定项目的所有项目的数据结构Tile比O(n)更好，但我想避免在“从一个瓦片移动到另一个瓦片”阶段（现在只是分配一个指针，我想避免在那里做很多操作，因为它非常频繁）。

我正在考虑使用自定义数据结构来利用项目总是移动到相邻单元格的事实，但我目前正在黑暗中摸索！任何建议都会受到赞赏，即使是棘手或神秘的方法。不幸的是，我不能只是浪费内存，因此需要进行良好的权衡。

我正在用 STL 用 C++ 开发它，但没有 Boost。（是的，我确实知道multimap，它不满足我，但如果我没有找到更好的东西，我会尝试）

4

3 回答 3

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

这会将瓦片地图上的坐标映射到指示哪些项目在该瓦片上的项目指针集。您不需要为每个坐标输入一个条目，只需要那些实际上有项目的坐标。现在，我知道你是这么说的：

但我想避免在“从一块瓷砖移动到另一块瓷砖”阶段产生太多开销

这种方法将涉及在该阶段增加更多开销。但是您是否真的尝试过这样的事情并确定这是一个问题？

于 2012-04-16T14:49:44.417 回答
0

对我来说，我会将 a 包装std::vector成矩阵类型（IE 对 1d 数组施加 2d 访问），这使您可以快速随机访问任何图块（实现矩阵是微不足道的）。

采用

 vector_index=y_pos*y_size+x_pos;

索引大小的向量

 vector_size=y_size*x_size;

然后每个项目都可以有一个项目的 std::vector （如果一个 tile 的项目数量非常动态，可能是一个双端队列），这些都是随机访问包含的，开销非常小。

对于您的用例，我会远离间接容器。

PS：如果你想要你可以有我的矩阵模板。

于 2012-04-16T14:26:45.507 回答
0

如果您真的认为让每个 tile 存储它的项目会花费太多空间，那么请考虑使用四叉树来存储项目。这使您可以有效地获取磁贴上的所有项目，但将磁贴网格保留在适当的位置以进行项目移动。

于 2012-07-05T20:24:54.740 回答