把物体放进它覆盖的网格,可以缩小需要进一步检查的范围。但大物体覆盖多个格子时,同一对物体可能被反复提名,因此应把候选对合并,再做真正的几何相交检查。
本篇使用一组可以手算或逐行复查的虚构游戏记录。先读清操作顺序与边界,再看完整过程;它不是某一款现有游戏的隐藏公式,也不要求读者安装工具。
规则与输入
九个轴对齐矩形使用整数坐标,左下包含、右上排除。矩形写入所有覆盖到的固定大小方格;同格中任意两编号形成候选对,按较小编号在前去重。细查要求两轴重叠长度都严格大于零。
格子边长4,九个矩形[[9, -3, 13, 4], [7, 6, 11, 9], [0, 2, 3, 6], [6, 0, 11, 6], [-3, 2, -1, 9], [6, -2, 11, 5], [0, 1, 5, 5], [5, 7, 10, 8], [1, 5, 6, 6]]
逐步计算与结果
矩形0范围[9,-3,13,4),覆盖格子[[2, -1], [2, 0], [3, -1], [3, 0]]。右边和上边不包含,所以边界恰落在下一格起点时不会多占那一格。
矩形1范围[7,6,11,9),覆盖格子[[1, 1], [1, 2], [2, 1], [2, 2]]。右边和上边不包含,所以边界恰落在下一格起点时不会多占那一格。
矩形2范围[0,2,3,6),覆盖格子[[0, 0], [0, 1]]。右边和上边不包含,所以边界恰落在下一格起点时不会多占那一格。
矩形3范围[6,0,11,6),覆盖格子[[1, 0], [1, 1], [2, 0], [2, 1]]。右边和上边不包含,所以边界恰落在下一格起点时不会多占那一格。
矩形4范围[-3,2,-1,9),覆盖格子[[-1, 0], [-1, 1], [-1, 2]]。右边和上边不包含,所以边界恰落在下一格起点时不会多占那一格。
矩形5范围[6,-2,11,5),覆盖格子[[1, -1], [1, 0], [1, 1], [2, -1], [2, 0], [2, 1]]。右边和上边不包含,所以边界恰落在下一格起点时不会多占那一格。
矩形6范围[0,1,5,5),覆盖格子[[0, 0], [0, 1], [1, 0], [1, 1]]。右边和上边不包含,所以边界恰落在下一格起点时不会多占那一格。
矩形7范围[5,7,10,8),覆盖格子[[1, 1], [2, 1]]。右边和上边不包含,所以边界恰落在下一格起点时不会多占那一格。
矩形8范围[1,5,6,6),覆盖格子[[0, 1], [1, 1]]。右边和上边不包含,所以边界恰落在下一格起点时不会多占那一格。
去重后候选[[0, 3], [0, 5], [1, 3], [1, 5], [1, 6], [1, 7], [1, 8], [2, 6], [2, 8], [3, 5], [3, 6], [3, 7], [3, 8], [5, 6], [5, 7], [5, 8], [6, 7], [6, 8], [7, 8]];进一步检查两轴严格正重叠,真实相交为[[0, 3], [0, 5], [1, 7], [2, 6], [2, 8], [3, 5]]。其余候选只是共享格子,不是碰撞确认。
所有36种物体对里粗筛保留19对,精查通过6对。
怎样独立复核
独立枚举全部物体对,检查是否共享任一格,再判断实际矩形相交。所有真正相交对都应属于候选集合,但共享一个大格并不保证相交。边缘刚接触在本例被视为没有面积交叠。
网格粗筛不是最终碰撞结论。格子太大可能留下很多无关候选,太小则增加一个物体覆盖的格子数。本例没有旋转矩形、连续运动或碰撞响应,使用者要分清筛选阶段与精确检查阶段。
练习时可以只改变一个输入,再预测哪一步会最先改变。保留中间记录,检查空状态、相等数值和刚好落在边界的情况。最终结果碰巧相同,并不能证明两个过程等价;反过来,采用不同规则得出不同结果,也不应立即视作程序故障。