哪种STL容器最适合实现C++游戏中的2D碰撞检测？

核心结论 #

优先使用std::unordered_map作为碰撞查询的专用容器，配合存储全量生物的std::vector搭配使用，可将碰撞查询复杂度从O(n)降到平均O(1)，彻底解决当前的性能问题。 #

现有方案的性能瓶颈 #

你当前使用std::vector存储所有生物，每次碰撞检测需要遍历全量生物做坐标匹配，400个生物每轮行动最多会产生16万次匹配计算，再加上额外的逻辑开销才会出现20~30秒的异常耗时，线性遍历的结构天生不适合高频坐标查询场景。 #

std::unordered_map适配方案 #

实现逻辑 #

• 存储结构：std::unordered_map的键用坐标值，值存储对应位置生物的指针/索引，同时保留原有的std::vector存储全量生物实例，专门用于全局状态更新（如每轮批量修改生物强度、结算死亡、处理繁殖逻辑），两个容器同步维护即可。
• 坐标键的简化实现：不需要额外自定义坐标结构体的哈希函数，可直接把32位的x、y坐标拼接成64位整数作为键，示例代码逻辑：
  uint64_t coord_key = (static_cast<uint64_t>(x) << 32) | static_cast<uint32_t>(y);

业务适配性 #

• 碰撞查询：调用unordered_map::find(coord_key)即可在平均O(1)时间内得到目标坐标的生物信息，无需遍历全量数据。
• 生物移动：生物位置变化时，先删除哈希表中旧坐标的键值对，再插入新坐标的键值对即可，两次操作都是平均O(1)复杂度。
• 生物死亡：先删除哈希表中对应坐标的键值对，再从std::vector中移除生物实例即可，也可采用标记删除的方式进一步降低删除开销。
• 生物繁殖：新生物实例插入std::vector的同时，把对应坐标和索引写入哈希表即可。
• 强度修改：直接修改std::vector中存储的生物实例属性即可，不需要改动哈希表结构。

备选方案：固定尺寸地图用std::array #

如果你的游戏地图是固定大小的小尺寸网格（比如1000*1000以内），可以直接声明二维std::array存储对应坐标的生物指针，查询和修改效率是纯O(1)，比哈希表更快，缺点是超大地图会造成内存浪费。 #

额外优化建议 #

可以先批量计算所有生物的目标移动坐标，统一完成碰撞校验之后再批量更新所有生物的位置，减少容器的频繁修改操作，进一步提升运行效率。

内容的提问来源于stack exchange，提问作者Michał Turek