空间哈希宽阶段：只登记中心格会漏掉大对象
一段长十米的障碍包围盒，右端已经包含一个小道具的包围盒，空间查询却没有把两者交给后续检测。障碍和道具的位置都正确，AABB 求交函数也能返回重叠；问题发生得更早：宽阶段只把对象登记到中心所在的格子，两个对象根本没有进入同一组候选。
这个错误会随着物体尺寸变化出现。地图里的角色大多接近一格宽时，中心登记配合邻格搜索可能一直正常；换成长墙、桥面或较大的触发区域后，原来的邻域范围就失去了完整性依据。本文用一个独立 C# 快照探针，把“找全候选”与“减少候选”分别验证，不把 AABB 重叠等同于实际形状碰撞。
图中浅色网格表示覆盖登记的概念，精确坐标与登记数量以下方数据图为准。
大盒的右端不在中心格附近
固定格长为 2 米，障碍 A 为 [0,10] × [0,2]，道具 B 为 [9,9.5] × [0.5,1.5]。中心分别落在格 (2,0) 与 (4,0)。只枚举同格对象会漏掉它们；即使搜索中心格周围一圈，横向差两个格的候选仍不会相遇。扩大到两圈能救回这个输入，却不能为任意尺寸对象提供保证。
这里采用另一种登记合同：每个 AABB 沿两轴从 floor(min / h) 枚举到 floor(max / h)，两端都包含。A 登记到六列、两行，共 12 个格；B 登记到一个格，总登记数为 13。两者在 (4,0) 相遇，候选对才有机会进入精确的 AABB 检查。
为什么必须包含最大端点所在格？当前接触语义使用闭区间。两个盒子在 x=2 相接时，右侧盒子的最小点属于格 1，左侧盒子的最大点也必须登记到格 1。把最大格号改为 ceil(max/h)-1，会把这个接触从候选集合里删掉。闭区间的零面积盒同样有效；产品若要忽略点或边接触，应在重叠判定中明确改变语义。
完整性的依据不依赖物体大小：两个闭 AABB 重叠，就存在一个共有点；用相同格长对这个点取格号，该格号必然同时位于两个盒子的逐轴枚举区间内。共同格因此至少产生一次候选。这份保证针对提交进来的有限浮点边界，不会补救上游已经算小的包围盒，也不替代数值误差的保守扩张。
同一对可以相遇八次，但只能交付一次
覆盖登记会产生重复。两个完全相同的 [0,6] × [0,2] 盒子共有八个格，逐格枚举会访问同一对八次。若把每次访问直接当作伤害或触发事件，下游就会承受重复副作用。探针先按快照数组序号组成规范键，再用集合去重，最后才做闭区间重叠检查。
下面是 SpatialHash.cs 的完整核心实现。Build → Range → Cell 决定登记范围，候选去重后调用 Overlap。数组必须在构建期间保持不变；序号只代表当前快照中的对象，不是跨帧实体身份。
public readonly record struct Box(double MinX, double MinY, double MaxX, double MaxY);
public sealed record BroadResult(HashSet<(int A, int B)> Candidates,
HashSet<(int A, int B)> Overlaps, int Memberships, long PairVisits);
public static class SpatialHash
{
public static bool Overlap(Box a, Box b) =>
a.MinX <= b.MaxX && b.MinX <= a.MaxX &&
a.MinY <= b.MaxY && b.MinY <= a.MaxY;
private static int Cell(double value, double size)
{
double index = Math.Floor(value / size);
if (!double.IsFinite(index) || index < -1000000 || index > 1000000)
throw new ArgumentOutOfRangeException(nameof(value));
return (int)index;
}
private static (int X0, int Y0, int X1, int Y1) Range(Box b, double size)
{
if (!double.IsFinite(b.MinX) || !double.IsFinite(b.MinY) ||
!double.IsFinite(b.MaxX) || !double.IsFinite(b.MaxY) ||
b.MinX > b.MaxX || b.MinY > b.MaxY)
throw new ArgumentException("包围盒无效");
int x0 = Cell(b.MinX, size), x1 = Cell(b.MaxX, size);
int y0 = Cell(b.MinY, size), y1 = Cell(b.MaxY, size);
if ((long)(x1 - x0 + 1) * (y1 - y0 + 1) > 4096)
throw new ArgumentException("单对象覆盖格数超过预算");
return (x0, y0, x1, y1);
}
public static BroadResult Build(IReadOnlyList<Box> boxes, double cellSize)
{
if (!double.IsFinite(cellSize) || cellSize <= 0)
throw new ArgumentOutOfRangeException(nameof(cellSize));
var cells = new Dictionary<(int X, int Y), List<int>>();
int memberships = 0;
for (int i = 0; i < boxes.Count; i++)
{
var r = Range(boxes[i], cellSize);
for (int y = r.Y0; y <= r.Y1; y++)
for (int x = r.X0; x <= r.X1; x++)
{
if (++memberships > 1000000)
throw new ArgumentException("快照总登记数超过预算");
if (!cells.TryGetValue((x, y), out var ids))
cells[(x, y)] = ids = new List<int>();
ids.Add(i);
}
}
var candidates = new HashSet<(int A, int B)>();
long visits = 0;
foreach (var ids in cells.Values)
for (int a = 0; a < ids.Count; a++)
for (int b = a + 1; b < ids.Count; b++)
{
visits++;
// 按数组序号递增登记，每个候选键天然满足 A < B。
candidates.Add((ids[a], ids[b]));
}
var overlaps = candidates.Where(p => Overlap(boxes[p.A], boxes[p.B])).ToHashSet();
return new(candidates, overlaps, memberships, visits);
}
}
按数组顺序登记，使每个桶的序号递增，因此候选键天然满足 A < B。若以后改为并行填桶，必须显式取较小与较大序号，不能继续依赖插入顺序。集合的遍历顺序也不是确定性协议；需要稳定处理顺序的逻辑应先排序，再交给后续系统。
Program.Boundaries 保留了上述八次访问的去重回归，以及负坐标、边接触、角接触和同格不重叠样本。负坐标必须使用向下取整：-0.5 与 0.1 在格长 2 时分属格 -1 和格 0。单纯截断会让它们挤进同一个桶；在这个样本中虽不会漏对，却会扩大候选，破坏预期的空间分区。
格长改变工作量，不应改变接触集合
验证集合由 x,y ∈ {-2,-1.5,…,2} 和 width,height ∈ {0,1,2} 的笛卡尔积构成，共 729 个盒子。Program.Oracle 独立使用 max(min) <= min(max) 求区间交集，检查全部 265,356 个无序对象对；它不调用被测 Overlap。对每种格长，测试同时检查参照集合是候选集合的子集，以及最终 AABB 接触集合与参照完全相等。
本次运行使用 .NET 9 Release。LAB_DIR 指向保存这两个源码文件与项目文件的研究目录，命令为：
dotnet build "$LAB_DIR/SpatialHashLab.csproj" -c Release
dotnet run --project "$LAB_DIR/SpatialHashLab.csproj" -c Release --no-build
构建与运行退出码均为 0，构建零警告、零错误。下列字段整理自当次真实输出；耗时是整个验证程序的墙钟时间，不是宽阶段性能基准。
passed=29 failed=0 skipped=0 elapsedMs=437.7409
centerA=(2, 0) centerB=(4, 0) centerCandidates=0
memberships=13 candidates=1 overlaps=1 pairVisits=1
exhaustiveBoxes=729 oraclePairChecks=265356 oracleOverlaps=53100
四种格长的最终接触数都是 53,100，但内部工作不同。格长从 3 减到 0.5，唯一候选从 150,336 减到 53,100，登记数却从 1,369 增到 6,561；重复访问总数也没有单调下降。仅凭“候选更少”不能宣布运行更快，需要按实际对象尺寸、密度和更新方式测量整条调用链。
若总登记数为 M，桶内数量为 n_c，去重前枚举次数就是各桶 n_c(n_c-1)/2 的总和。哈希表操作在通常的均摊分析下让登记接近 O(M)，却没有消除同桶拥挤时的平方项。代码的每对象 4,096 格、快照一百万次登记，以及格号范围限制只是显式拒绝边界；测试验证预算恰好允许与超出时抛错，没有声称它们约束了候选集合的最大内存或单帧耗时。
对象尺寸差距很大时，我更倾向先记录登记数、桶占用与重复访问量，再决定是否把超大对象送入单独的结构。拆分后必须补上大对象与普通对象之间的交叉查询，不能把超过预算的对象悄悄跳过。当前函数在拒绝输入时不返回半份结果，也没有实现这条替代路径。
长墙右端的道具现在进入了候选，但下一步仍是具体形状检测。这份静态快照不覆盖高速物体在两帧之间穿过障碍的情况；扫掠包围盒与连续碰撞需要另行建立时间范围。可以先固定到引擎接口里的要求是：完整覆盖决定候选不能漏，去重决定一对只交付一次，格长则在这两项成立之后调节工作量。