空间哈希通过网格划分将碰撞检测复杂度从O(n²)降至近似O(n)，核心是合理设置网格尺寸（如64像素）并用线性键编码坐标（如gy×1000+gx）实现高效映射与查询。
空间哈希的核心思想是：把连续的二维（或三维）空间划分成规则网格，每个网格用一个整数坐标（如 (gx, gy)）标识，再把物体按其中心或包围盒映射到对应网格中；碰撞检测时只检查同一网格或邻近网格内的物体对，大幅减少 O(n²) 检查量。
1. 确定网格大小（Cell Size）
网格尺寸是关键参数——太小会导致大量空桶和哈希冲突；太大则退化为全局检测。一般设为略大于游戏中「最常见碰撞体的平均尺寸」，例如角色宽高约 32×32 像素，可取 cellSize = 64。
- 固定尺寸更简单：`const float CELL_SIZE = 64.0f;`
- 避免浮点误差：用 `floor` 或整数截断，而非 `(int)` 强转
- 若物体尺寸差异极大（如子弹 vs 地形），可考虑多层哈希或混合方案（但简单场景不推荐）
2. 哈希键的设计与存储
不用真正调用 std::hash，而是将网格坐标 (gx, gy) 编码为唯一整数键（如 Z-order 或线性索引），再用 std::unordered_map 存储该格子内的物体指针。
推荐线性键（简单、无碰撞、易调试）：
立即学习“C++免费学习笔记（深入）”；
int getHashKey(int gx, int gy) {
return gy * 1000 + gx; // 假设地图宽度 < 1000，避免冲突
}或者用 std::pair 直接作 key（需提供 hash 特化，稍麻烦但语义清晰）：
struct GridHash {
size_t operator()(const std::pair& p) const {
return (static_cast(p.first) << 20) ^ p.second;
}
};
std::unordered_map, std::vector, GridHash> grid; 3. 插入与更新物体
每个物体需维护其当前占据的网格范围（通常由 AABB 决定）。插入时计算其覆盖的所有网格，把指针加入对应桶中。
- 对物体 AABB 的左下、右上角分别做网格坐标转换：
gx = static_cast(floor(pos.x / CELL_SIZE)); - 遍历从
(min_gx, min_gy)到(max_gx, max_gy)的所有网格，调用grid[make_pair(gx,gy)].push_back(obj); - 移动物体时，先清空旧位置（需记录上一帧的网格范围），再重新插入新位置 —— 不建议每帧全清空重建
4. 碰撞查询（Broad Phase）
对每个物体 A，只检查它所在及周围 8 个网格（3×3 区域）中的其他物体 B，再用精确碰撞（如 AABB 或 Circle 检测）过滤。
- 先算出 A 当前覆盖的网格范围
[gx_min, gx_max] × [gy_min, gy_max] - 循环这 9 个网格（注意边界检查，防止访问不存在的 key）
- 对每个桶内物体，跳过自身（
if (b != a)），并避免重复配对（如仅当b > a按地址比较） - 返回的是候选对列表，后续交给 narrow phase 处理
基本上就这些。空间哈希不是黑魔法，它依赖“物体分布相对均匀”和“网格尺寸合理”。上线前务必用实际场景数据 profile 网格命中率和桶平均长度，调整 CELL_SIZE 是最有效的优化手段。
