网格粗筛碰撞时如何去掉重复候选对：3单位网格的矩形候选去重·练习04

把物体放进它覆盖的网格，可以缩小需要进一步检查的范围。但大物体覆盖多个格子时，同一对物体可能被反复提名，因此应把候选对合并，再做真正的几何相交检查。

本篇使用一组可以手算或逐行复查的虚构游戏记录。先读清操作顺序与边界，再看完整过程；它不是某一款现有游戏的隐藏公式，也不要求读者安装工具。

规则与输入

九个轴对齐矩形使用整数坐标，左下包含、右上排除。矩形写入所有覆盖到的固定大小方格；同格中任意两编号形成候选对，按较小编号在前去重。细查要求两轴重叠长度都严格大于零。

格子边长3，九个矩形[[8, -1, 10, 6], [-2, 4, -1, 10], [8, -1, 13, 3], [4, 3, 11, 6], [9, 0, 10, 6], [4, -2, 7, 1], [-3, 9, -1, 16], [7, 5, 11, 12], [-2, 8, 0, 12]]

逐步计算与结果

矩形0范围[8,-1,10,6)，覆盖格子[[2, -1], [2, 0], [2, 1], [3, -1], [3, 0], [3, 1]]。右边和上边不包含，所以边界恰落在下一格起点时不会多占那一格。

矩形1范围[-2,4,-1,10)，覆盖格子[[-1, 1], [-1, 2], [-1, 3]]。右边和上边不包含，所以边界恰落在下一格起点时不会多占那一格。

矩形2范围[8,-1,13,3)，覆盖格子[[2, -1], [2, 0], [3, -1], [3, 0], [4, -1], [4, 0]]。右边和上边不包含，所以边界恰落在下一格起点时不会多占那一格。

矩形3范围[4,3,11,6)，覆盖格子[[1, 1], [2, 1], [3, 1]]。右边和上边不包含，所以边界恰落在下一格起点时不会多占那一格。

矩形4范围[9,0,10,6)，覆盖格子[[3, 0], [3, 1]]。右边和上边不包含，所以边界恰落在下一格起点时不会多占那一格。

矩形5范围[4,-2,7,1)，覆盖格子[[1, -1], [1, 0], [2, -1], [2, 0]]。右边和上边不包含，所以边界恰落在下一格起点时不会多占那一格。

矩形6范围[-3,9,-1,16)，覆盖格子[[-1, 3], [-1, 4], [-1, 5]]。右边和上边不包含，所以边界恰落在下一格起点时不会多占那一格。

矩形7范围[7,5,11,12)，覆盖格子[[2, 1], [2, 2], [2, 3], [3, 1], [3, 2], [3, 3]]。右边和上边不包含，所以边界恰落在下一格起点时不会多占那一格。

矩形8范围[-2,8,0,12)，覆盖格子[[-1, 2], [-1, 3]]。右边和上边不包含，所以边界恰落在下一格起点时不会多占那一格。

去重后候选[[0, 2], [0, 3], [0, 4], [0, 5], [0, 7], [1, 6], [1, 8], [2, 4], [2, 5], [3, 4], [3, 7], [4, 7], [6, 8]]；进一步检查两轴严格正重叠，真实相交为[[0, 2], [0, 3], [0, 4], [0, 7], [1, 6], [1, 8], [2, 4], [3, 4], [3, 7], [4, 7], [6, 8]]。其余候选只是共享格子，不是碰撞确认。

所有36种物体对里粗筛保留13对，精查通过11对。

怎样独立复核

独立枚举全部物体对，检查是否共享任一格，再判断实际矩形相交。所有真正相交对都应属于候选集合，但共享一个大格并不保证相交。边缘刚接触在本例被视为没有面积交叠。

网格粗筛不是最终碰撞结论。格子太大可能留下很多无关候选，太小则增加一个物体覆盖的格子数。本例没有旋转矩形、连续运动或碰撞响应，使用者要分清筛选阶段与精确检查阶段。

练习时可以只改变一个输入，再预测哪一步会最先改变。保留中间记录，检查空状态、相等数值和刚好落在边界的情况。最终结果碰巧相同，并不能证明两个过程等价；反过来，采用不同规则得出不同结果，也不应立即视作程序故障。