Jac*_*ack 6 c++ data-structures
我正在研究我的游戏引擎的一小部分,并想知道如何优化一些部分.
情况非常简单,如下:
Tiles 的地图(存储在一个二维数组中)(约260k瓦片,但假设更多)Items 列表,它总是至少和最多是一个瓷砖Tile逻辑上可以包含无限量的ItemsItem,不断创建许多s并且它们从它们自己开始TileItem不断地改变它Tile的邻居之一(向上,向右,向下,向左)到目前为止,每个人Item都有对它的实际参考Tile,我只保留一个项目列表.每次Item移动到相邻的瓷砖我都会更新item->tile = ..,我很好.这很好但是它是单向的.
在扩展引擎的同时,我意识到我必须多次找到瓷砖中包含的所有物品,这实际上会降低性能(特别是在某些情况下,我必须逐个找到一系列瓷砖的所有物品) .
这意味着我想找到一个适合查找Tile比O(n)更好的特定项目的数据结构,但我想避免在"从一个瓷砖移动到另一个瓷砖"阶段(现在它只是指定一个指针,我想避免在那里做很多操作,因为它很频繁).
我正在考虑一个自定义数据结构,以利用物品总是移动到相邻单元格但我正在黑暗中摸索的事实!任何建议都会受到赞赏,甚至是棘手的或神秘的方法.不幸的是,我不能浪费内存,因此需要进行良好的权衡.
我正在使用STL在C++中开发它但没有Boost.(是的,我知道multimap,它不能让我满意,但如果我找不到更好的东西,我会试试)
struct Coordinate { int x, y; };
map<Coordinate, set<Item*>> tile_items;
这会将图块地图上的坐标映射到项目指针集，指示哪些项目位于该图块上。您不需要为每个坐标输入一个条目，只需要为那些实际有项目的坐标输入条目。现在，我知道你说过这样的话：
但我想避免“从一个图块移动到另一个图块”阶段的过多开销
这种方法会在该阶段增加更多的开销。但你是否真的尝试过类似的事情并确定这是一个问题？