FAILURE MAP
← Case archive

FA-87611 / Collision detection broadphase / Open access

Traversal stops before a boundary reached exactly at max_t · case 01

A ray ending exactly on a cell border misses that cell.

Verified by executionVariant 1 · 8 checks per implementationDownload source bundle ↓JSON ↗

ROOT CAUSE

The stop test is t >= max_t.

VERIFIED REPAIR

Continue while the boundary t <= max_t.

Unsuccessful approach: Scaling max_t by the cell size mixes parameter and world units.

Case contract

solve(o, d, cs, max_t): Amanatides-Woo traversal of a uniform grid for a ray o+t*d (d not normalized). Start in cell floor(o/cs); step the axis with the smaller next boundary t (x on ties) while that t <= max_t, at most 64 cells. Return the visited cells [[ix,iy],...].

Why this case matters

Broadphase stages decide which object pairs ever reach narrowphase; a wrong boundary, ordering or bookkeeping rule silently drops real contacts or floods the solver with false candidates.

1 / The failure

Exit 1
"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(o, d, cs, max_t):
    ix, iy = math.floor(o[0] / cs), math.floor(o[1] / cs)
    sx = 1 if d[0] > 0 else (-1 if d[0] < 0 else 0)
    sy = 1 if d[1] > 0 else (-1 if d[1] < 0 else 0)
    inf = float('inf')
    if sx > 0:
        tmx = ((ix + 1) * cs - o[0]) / d[0]
    elif sx < 0:
        tmx = (ix * cs - o[0]) / d[0]
    else:
        tmx = inf
    if sy > 0:
        tmy = ((iy + 1) * cs - o[1]) / d[1]
    elif sy < 0:
        tmy = (iy * cs - o[1]) / d[1]
    else:
        tmy = inf
    tdx = cs / abs(d[0]) if sx else inf
    tdy = cs / abs(d[1]) if sy else inf
    cells = [[ix, iy]]
    while len(cells) < 64:
        if tmx <= tmy:
            t, ax = tmx, 0
        else:
            t, ax = tmy, 1
        if t >= max_t:
            break
        if ax == 0:
            ix += sx
            tmx += tdx
        else:
            iy += sy
            tmy += tdy
        cells.append([ix, iy])
    return cells
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[[[[1.5, -1.75], [0, 1], 2.0, 1.0], [[0, -1]]], [[[1.75, 1.5], [-4, -1], 0.5, 1.0], [[3, 3], [3, 2], [2, 2], [1, 2], [0, 2], [-1, 2], [-1, 1], [-2, 1], [-3, 1], [-4, 1], [-5, 1], [-5, 0]]], [[[1.0, -1.0], [2, 1], 0.5, 1.0], [[2, -2], [3, -2], [4, -2], [4, -1], [5, -1], [6, -1], [6, 0]]], [[[-0.25, -1.25], [-1, 2], 0.5, 0.5], [[-1, -3], [-1, -2], [-2, -2], [-2, -1]]], [[[1.25, 0.75], [0, 1], 0.5, 2.0], [[2, 1], [2, 2], [2, 3], [2, 4], [2, 5]]], [[[-2.0, -1.5], [-4, 4], 0.5, 0.5], [[-4, -3], [-5, -3], [-6, -3], [-6, -2], [-7, -2], [-7, -1], [-8, -1], [-8, 0], [-9, 0], [-9, 1]]], [[[0.0, -1.5], [-2, -1], 1.0, 0.5], [[0, -2], [-1, -2], [-2, -2], [-2, -3]]], [[[-1.25, -1.75], [2, 0], 1.0, 3.0], [[-2, -2], [-1, -2], [0, -2], [1, -2], [2, -2], [3, -2], [4, -2]]]], [[[[-2.0, 1.5], [2, -1], 0.5, 1.0], [[-4, 3], [-4, 2], [-3, 2], [-2, 2], [-2, 1], [-1, 1], [0, 1], [0, 0]]], [[[1.5, -0.75], [1, 4], 0.5, 0.5], [[3, -2], [3, -1], [3, 0], [3, 1], [3, 2], [4, 2]]], [[[0.75, -0.25], [-1, 4], 0.5, 2.0], [[1, -1], [1, 0], [1, 1], [0, 1], [0, 2], [0, 3], [0, 4], [0, 5], [-1, 5], [-1, 6], [-1, 7], [-1, 8], [-1, 9], [-2, 9], [-2, 10], [-2, 11], [-2, 12], [-2, 13], [-3, 13], [-3, 14], [-3, 15]]], [[[0.5, 1.25], [-4, 0], 2.0, 0.5], [[0, 0], [-1, 0]]], [[[-1.75, -2.0], [-1, -1], 2.0, 1.0], [[-1, -1], [-1, -2], [-2, -2]]], [[[1.25, 0.75], [0, 0], 1.0, 3.0], [[1, 0]]], [[[1.5, 1.75], [2, 4], 2.0, 1.0], [[0, 0], [0, 1], [1, 1], [1, 2]]], [[[-1.25, 2.0], [0, -2], 0.5, 1.0], [[-3, 4], [-3, 3], [-3, 2], [-3, 1], [-3, 0], [-3, -1]]]], [[[[-0.75, -1.0], [1, -2], 2.0, 1.0], [[-1, -1], [-1, -2], [0, -2]]], [[[-1.0, -1.0], [-4, 4], 0.5, 0.5], [[-2, -2], [-3, -2], [-4, -2], [-4, -1], [-5, -1], [-5, 0], [-6, 0], [-6, 1], [-7, 1], [-7, 2]]], [[[1.25, 0.5], [0, 1], 2.0, 1.0], [[0, 0]]], [[[1.75, 1.75], [4, -2], 2.0, 0.5], [[0, 0], [1, 0]]], [[[1.0, -2.0], [-1, 1], 2.0, 2.0], [[0, -1], [-1, -1], [-1, 0]]], [[[0.25, 0.25], [-1, 0], 1.0, 1.0], [[0, 0], [-1, 0]]], [[[-1.75, 1.0], [0, 0], 1.0, 1.0], [[-2, 1]]], [[[0.0, -0.25], [-1, -1], 0.5, 2.0], [[0, -1], [-1, -1], [-1, -2], [-2, -2], [-2, -3], [-3, -3], [-3, -4], [-4, -4], [-4, -5], [-5, -5]]]], [[[[0.25, 0.25], [-1, 4], 2.0, 0.5], [[0, 0], [-1, 0], [-1, 1]]], [[[2.0, -1.75], [4, -2], 2.0, 3.0], [[1, -1], [1, -2], [2, -2], [3, -2], [3, -3], [4, -3], [5, -3], [5, -4], [6, -4], [7, -4]]], [[[-1.0, 0.75], [2, 0], 0.5, 1.0], [[-2, 1], [-1, 1], [0, 1], [1, 1], [2, 1]]], [[[-0.5, -1.5], [-1, -1], 0.5, 2.0], [[-1, -3], [-2, -3], [-2, -4], [-3, -4], [-3, -5], [-4, -5], [-4, -6], [-5, -6], [-5, -7], [-6, -7], [-6, -8]]], [[[-1.25, 0.75], [-2, -2], 0.5, 0.5], [[-3, 1], [-4, 1], [-4, 0], [-5, 0], [-5, -1]]], [[[-0.5, -0.75], [-2, 0], 2.0, 3.0], [[-1, -1], [-2, -1], [-3, -1], [-4, -1]]], [[[1.25, 1.0], [-4, -1], 1.0, 1.0], [[1, 1], [1, 0], [0, 0], [-1, 0], [-2, 0], [-3, 0], [-3, -1]]], [[[1.75, -1.75], [1, -1], 1.0, 3.0], [[1, -2], [2, -2], [2, -3], [3, -3], [3, -4], [4, -4], [4, -5]]]], [[[[-1.75, 0.25], [4, 0], 2.0, 0.5], [[-1, 0], [0, 0]]], [[[0.5, 1.5], [0, 2], 1.0, 0.5], [[0, 1], [0, 2]]], [[[-0.75, 0.0], [0, -2], 0.5, 3.0], [[-2, 0], [-2, -1], [-2, -2], [-2, -3], [-2, -4], [-2, -5], [-2, -6], [-2, -7], [-2, -8], [-2, -9], [-2, -10], [-2, -11], [-2, -12], [-2, -13]]], [[[0.0, 2.0], [-1, -2], 2.0, 0.5], [[0, 1], [-1, 1], [-1, 0]]], [[[-0.75, -1.0], [1, 4], 2.0, 3.0], [[-1, -1], [-1, 0], [0, 0], [0, 1], [0, 2], [0, 3], [0, 4], [1, 4], [1, 5]]], [[[0.5, -1.0], [-4, 4], 1.0, 2.0], [[0, -1], [-1, -1], [-1, 0], [-2, 0], [-2, 1], [-3, 1], [-3, 2], [-4, 2], [-4, 3], [-5, 3], [-5, 4], [-6, 4], [-6, 5], [-7, 5], [-7, 6], [-8, 6], [-8, 7]]], [[[1.25, 0.0], [1, -2], 2.0, 2.0], [[0, 0], [0, -1], [1, -1], [1, -2], [1, -3]]], [[[1.0, -2.0], [-2, 0], 2.0, 2.0], [[0, -1], [-1, -1], [-2, -1]]]]]
for i, (args, expected) in enumerate(fixtures[N-1]):
    check("case %d" % i, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
Boundary fixtureActualExpectedOutcome
case 0[[0, -1]][[0, -1]]Passed
case 1[[3, 3], [3, 2], [2, 2], [1, 2], [0, 2], [-1, 2], [-1, 1], [-2, 1], [-3, 1], [-4, 1], [-5, 1]][[3, 3], [3, 2], [2, 2], [1, 2], [0, 2], [-1, 2], [-1, 1], [-2, 1], [-3, 1], [-4, 1], [-5, 1], [-5, 0]]Failed
case 2[[2, -2], [3, -2], [4, -2], [4, -1], [5, -1]][[2, -2], [3, -2], [4, -2], [4, -1], [5, -1], [6, -1], [6, 0]]Failed
case 3[[-1, -3], [-1, -2], [-2, -2], [-2, -1]][[-1, -3], [-1, -2], [-2, -2], [-2, -1]]Passed
case 4[[2, 1], [2, 2], [2, 3], [2, 4], [2, 5]][[2, 1], [2, 2], [2, 3], [2, 4], [2, 5]]Passed
case 5[[-4, -3], [-5, -3], [-6, -3], [-6, -2], [-7, -2], [-7, -1], [-8, -1], [-8, 0]][[-4, -3], [-5, -3], [-6, -3], [-6, -2], [-7, -2], [-7, -1], [-8, -1], [-8, 0], [-9, 0], [-9, 1]]Failed
case 6[[0, -2], [-1, -2]][[0, -2], [-1, -2], [-2, -2], [-2, -3]]Failed
case 7[[-2, -2], [-1, -2], [0, -2], [1, -2], [2, -2], [3, -2], [4, -2]][[-2, -2], [-1, -2], [0, -2], [1, -2], [2, -2], [3, -2], [4, -2]]Passed

SHA-256 / f721892e316098b14a37f980b21c2e84bc4bef6c05e5736b5a2e112031a5dd84

2 / The unsuccessful fix

Exit 1
"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(o, d, cs, max_t):
    ix, iy = math.floor(o[0] / cs), math.floor(o[1] / cs)
    sx = 1 if d[0] > 0 else (-1 if d[0] < 0 else 0)
    sy = 1 if d[1] > 0 else (-1 if d[1] < 0 else 0)
    inf = float('inf')
    if sx > 0:
        tmx = ((ix + 1) * cs - o[0]) / d[0]
    elif sx < 0:
        tmx = (ix * cs - o[0]) / d[0]
    else:
        tmx = inf
    if sy > 0:
        tmy = ((iy + 1) * cs - o[1]) / d[1]
    elif sy < 0:
        tmy = (iy * cs - o[1]) / d[1]
    else:
        tmy = inf
    tdx = cs / abs(d[0]) if sx else inf
    tdy = cs / abs(d[1]) if sy else inf
    cells = [[ix, iy]]
    while len(cells) < 64:
        if tmx <= tmy:
            t, ax = tmx, 0
        else:
            t, ax = tmy, 1
        if t > max_t * cs:
            break
        if ax == 0:
            ix += sx
            tmx += tdx
        else:
            iy += sy
            tmy += tdy
        cells.append([ix, iy])
    return cells
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[[[[1.5, -1.75], [0, 1], 2.0, 1.0], [[0, -1]]], [[[1.75, 1.5], [-4, -1], 0.5, 1.0], [[3, 3], [3, 2], [2, 2], [1, 2], [0, 2], [-1, 2], [-1, 1], [-2, 1], [-3, 1], [-4, 1], [-5, 1], [-5, 0]]], [[[1.0, -1.0], [2, 1], 0.5, 1.0], [[2, -2], [3, -2], [4, -2], [4, -1], [5, -1], [6, -1], [6, 0]]], [[[-0.25, -1.25], [-1, 2], 0.5, 0.5], [[-1, -3], [-1, -2], [-2, -2], [-2, -1]]], [[[1.25, 0.75], [0, 1], 0.5, 2.0], [[2, 1], [2, 2], [2, 3], [2, 4], [2, 5]]], [[[-2.0, -1.5], [-4, 4], 0.5, 0.5], [[-4, -3], [-5, -3], [-6, -3], [-6, -2], [-7, -2], [-7, -1], [-8, -1], [-8, 0], [-9, 0], [-9, 1]]], [[[0.0, -1.5], [-2, -1], 1.0, 0.5], [[0, -2], [-1, -2], [-2, -2], [-2, -3]]], [[[-1.25, -1.75], [2, 0], 1.0, 3.0], [[-2, -2], [-1, -2], [0, -2], [1, -2], [2, -2], [3, -2], [4, -2]]]], [[[[-2.0, 1.5], [2, -1], 0.5, 1.0], [[-4, 3], [-4, 2], [-3, 2], [-2, 2], [-2, 1], [-1, 1], [0, 1], [0, 0]]], [[[1.5, -0.75], [1, 4], 0.5, 0.5], [[3, -2], [3, -1], [3, 0], [3, 1], [3, 2], [4, 2]]], [[[0.75, -0.25], [-1, 4], 0.5, 2.0], [[1, -1], [1, 0], [1, 1], [0, 1], [0, 2], [0, 3], [0, 4], [0, 5], [-1, 5], [-1, 6], [-1, 7], [-1, 8], [-1, 9], [-2, 9], [-2, 10], [-2, 11], [-2, 12], [-2, 13], [-3, 13], [-3, 14], [-3, 15]]], [[[0.5, 1.25], [-4, 0], 2.0, 0.5], [[0, 0], [-1, 0]]], [[[-1.75, -2.0], [-1, -1], 2.0, 1.0], [[-1, -1], [-1, -2], [-2, -2]]], [[[1.25, 0.75], [0, 0], 1.0, 3.0], [[1, 0]]], [[[1.5, 1.75], [2, 4], 2.0, 1.0], [[0, 0], [0, 1], [1, 1], [1, 2]]], [[[-1.25, 2.0], [0, -2], 0.5, 1.0], [[-3, 4], [-3, 3], [-3, 2], [-3, 1], [-3, 0], [-3, -1]]]], [[[[-0.75, -1.0], [1, -2], 2.0, 1.0], [[-1, -1], [-1, -2], [0, -2]]], [[[-1.0, -1.0], [-4, 4], 0.5, 0.5], [[-2, -2], [-3, -2], [-4, -2], [-4, -1], [-5, -1], [-5, 0], [-6, 0], [-6, 1], [-7, 1], [-7, 2]]], [[[1.25, 0.5], [0, 1], 2.0, 1.0], [[0, 0]]], [[[1.75, 1.75], [4, -2], 2.0, 0.5], [[0, 0], [1, 0]]], [[[1.0, -2.0], [-1, 1], 2.0, 2.0], [[0, -1], [-1, -1], [-1, 0]]], [[[0.25, 0.25], [-1, 0], 1.0, 1.0], [[0, 0], [-1, 0]]], [[[-1.75, 1.0], [0, 0], 1.0, 1.0], [[-2, 1]]], [[[0.0, -0.25], [-1, -1], 0.5, 2.0], [[0, -1], [-1, -1], [-1, -2], [-2, -2], [-2, -3], [-3, -3], [-3, -4], [-4, -4], [-4, -5], [-5, -5]]]], [[[[0.25, 0.25], [-1, 4], 2.0, 0.5], [[0, 0], [-1, 0], [-1, 1]]], [[[2.0, -1.75], [4, -2], 2.0, 3.0], [[1, -1], [1, -2], [2, -2], [3, -2], [3, -3], [4, -3], [5, -3], [5, -4], [6, -4], [7, -4]]], [[[-1.0, 0.75], [2, 0], 0.5, 1.0], [[-2, 1], [-1, 1], [0, 1], [1, 1], [2, 1]]], [[[-0.5, -1.5], [-1, -1], 0.5, 2.0], [[-1, -3], [-2, -3], [-2, -4], [-3, -4], [-3, -5], [-4, -5], [-4, -6], [-5, -6], [-5, -7], [-6, -7], [-6, -8]]], [[[-1.25, 0.75], [-2, -2], 0.5, 0.5], [[-3, 1], [-4, 1], [-4, 0], [-5, 0], [-5, -1]]], [[[-0.5, -0.75], [-2, 0], 2.0, 3.0], [[-1, -1], [-2, -1], [-3, -1], [-4, -1]]], [[[1.25, 1.0], [-4, -1], 1.0, 1.0], [[1, 1], [1, 0], [0, 0], [-1, 0], [-2, 0], [-3, 0], [-3, -1]]], [[[1.75, -1.75], [1, -1], 1.0, 3.0], [[1, -2], [2, -2], [2, -3], [3, -3], [3, -4], [4, -4], [4, -5]]]], [[[[-1.75, 0.25], [4, 0], 2.0, 0.5], [[-1, 0], [0, 0]]], [[[0.5, 1.5], [0, 2], 1.0, 0.5], [[0, 1], [0, 2]]], [[[-0.75, 0.0], [0, -2], 0.5, 3.0], [[-2, 0], [-2, -1], [-2, -2], [-2, -3], [-2, -4], [-2, -5], [-2, -6], [-2, -7], [-2, -8], [-2, -9], [-2, -10], [-2, -11], [-2, -12], [-2, -13]]], [[[0.0, 2.0], [-1, -2], 2.0, 0.5], [[0, 1], [-1, 1], [-1, 0]]], [[[-0.75, -1.0], [1, 4], 2.0, 3.0], [[-1, -1], [-1, 0], [0, 0], [0, 1], [0, 2], [0, 3], [0, 4], [1, 4], [1, 5]]], [[[0.5, -1.0], [-4, 4], 1.0, 2.0], [[0, -1], [-1, -1], [-1, 0], [-2, 0], [-2, 1], [-3, 1], [-3, 2], [-4, 2], [-4, 3], [-5, 3], [-5, 4], [-6, 4], [-6, 5], [-7, 5], [-7, 6], [-8, 6], [-8, 7]]], [[[1.25, 0.0], [1, -2], 2.0, 2.0], [[0, 0], [0, -1], [1, -1], [1, -2], [1, -3]]], [[[1.0, -2.0], [-2, 0], 2.0, 2.0], [[0, -1], [-1, -1], [-2, -1]]]]]
for i, (args, expected) in enumerate(fixtures[N-1]):
    check("case %d" % i, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
Boundary fixtureActualExpectedOutcome
case 0[[0, -1], [0, 0]][[0, -1]]Failed
case 1[[3, 3], [3, 2], [2, 2], [1, 2], [0, 2], [-1, 2], [-1, 1]][[3, 3], [3, 2], [2, 2], [1, 2], [0, 2], [-1, 2], [-1, 1], [-2, 1], [-3, 1], [-4, 1], [-5, 1], [-5, 0]]Failed
case 2[[2, -2], [3, -2], [4, -2], [4, -1]][[2, -2], [3, -2], [4, -2], [4, -1], [5, -1], [6, -1], [6, 0]]Failed
case 3[[-1, -3], [-1, -2], [-2, -2]][[-1, -3], [-1, -2], [-2, -2], [-2, -1]]Failed
case 4[[2, 1], [2, 2], [2, 3]][[2, 1], [2, 2], [2, 3], [2, 4], [2, 5]]Failed
case 5[[-4, -3], [-5, -3], [-6, -3], [-6, -2], [-7, -2], [-7, -1]][[-4, -3], [-5, -3], [-6, -3], [-6, -2], [-7, -2], [-7, -1], [-8, -1], [-8, 0], [-9, 0], [-9, 1]]Failed
case 6[[0, -2], [-1, -2], [-2, -2], [-2, -3]][[0, -2], [-1, -2], [-2, -2], [-2, -3]]Passed
case 7[[-2, -2], [-1, -2], [0, -2], [1, -2], [2, -2], [3, -2], [4, -2]][[-2, -2], [-1, -2], [0, -2], [1, -2], [2, -2], [3, -2], [4, -2]]Passed

SHA-256 / d9868e590e70dc71fba6ec50371995abcfc7fb2b0f06269b4f8ad8b64074532d

3 / The verified repair

Exit 0
"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(o, d, cs, max_t):
    ix, iy = math.floor(o[0] / cs), math.floor(o[1] / cs)
    sx = 1 if d[0] > 0 else (-1 if d[0] < 0 else 0)
    sy = 1 if d[1] > 0 else (-1 if d[1] < 0 else 0)
    inf = float('inf')
    if sx > 0:
        tmx = ((ix + 1) * cs - o[0]) / d[0]
    elif sx < 0:
        tmx = (ix * cs - o[0]) / d[0]
    else:
        tmx = inf
    if sy > 0:
        tmy = ((iy + 1) * cs - o[1]) / d[1]
    elif sy < 0:
        tmy = (iy * cs - o[1]) / d[1]
    else:
        tmy = inf
    tdx = cs / abs(d[0]) if sx else inf
    tdy = cs / abs(d[1]) if sy else inf
    cells = [[ix, iy]]
    while len(cells) < 64:
        if tmx <= tmy:
            t, ax = tmx, 0
        else:
            t, ax = tmy, 1
        if t > max_t:
            break
        if ax == 0:
            ix += sx
            tmx += tdx
        else:
            iy += sy
            tmy += tdy
        cells.append([ix, iy])
    return cells
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[[[[1.5, -1.75], [0, 1], 2.0, 1.0], [[0, -1]]], [[[1.75, 1.5], [-4, -1], 0.5, 1.0], [[3, 3], [3, 2], [2, 2], [1, 2], [0, 2], [-1, 2], [-1, 1], [-2, 1], [-3, 1], [-4, 1], [-5, 1], [-5, 0]]], [[[1.0, -1.0], [2, 1], 0.5, 1.0], [[2, -2], [3, -2], [4, -2], [4, -1], [5, -1], [6, -1], [6, 0]]], [[[-0.25, -1.25], [-1, 2], 0.5, 0.5], [[-1, -3], [-1, -2], [-2, -2], [-2, -1]]], [[[1.25, 0.75], [0, 1], 0.5, 2.0], [[2, 1], [2, 2], [2, 3], [2, 4], [2, 5]]], [[[-2.0, -1.5], [-4, 4], 0.5, 0.5], [[-4, -3], [-5, -3], [-6, -3], [-6, -2], [-7, -2], [-7, -1], [-8, -1], [-8, 0], [-9, 0], [-9, 1]]], [[[0.0, -1.5], [-2, -1], 1.0, 0.5], [[0, -2], [-1, -2], [-2, -2], [-2, -3]]], [[[-1.25, -1.75], [2, 0], 1.0, 3.0], [[-2, -2], [-1, -2], [0, -2], [1, -2], [2, -2], [3, -2], [4, -2]]]], [[[[-2.0, 1.5], [2, -1], 0.5, 1.0], [[-4, 3], [-4, 2], [-3, 2], [-2, 2], [-2, 1], [-1, 1], [0, 1], [0, 0]]], [[[1.5, -0.75], [1, 4], 0.5, 0.5], [[3, -2], [3, -1], [3, 0], [3, 1], [3, 2], [4, 2]]], [[[0.75, -0.25], [-1, 4], 0.5, 2.0], [[1, -1], [1, 0], [1, 1], [0, 1], [0, 2], [0, 3], [0, 4], [0, 5], [-1, 5], [-1, 6], [-1, 7], [-1, 8], [-1, 9], [-2, 9], [-2, 10], [-2, 11], [-2, 12], [-2, 13], [-3, 13], [-3, 14], [-3, 15]]], [[[0.5, 1.25], [-4, 0], 2.0, 0.5], [[0, 0], [-1, 0]]], [[[-1.75, -2.0], [-1, -1], 2.0, 1.0], [[-1, -1], [-1, -2], [-2, -2]]], [[[1.25, 0.75], [0, 0], 1.0, 3.0], [[1, 0]]], [[[1.5, 1.75], [2, 4], 2.0, 1.0], [[0, 0], [0, 1], [1, 1], [1, 2]]], [[[-1.25, 2.0], [0, -2], 0.5, 1.0], [[-3, 4], [-3, 3], [-3, 2], [-3, 1], [-3, 0], [-3, -1]]]], [[[[-0.75, -1.0], [1, -2], 2.0, 1.0], [[-1, -1], [-1, -2], [0, -2]]], [[[-1.0, -1.0], [-4, 4], 0.5, 0.5], [[-2, -2], [-3, -2], [-4, -2], [-4, -1], [-5, -1], [-5, 0], [-6, 0], [-6, 1], [-7, 1], [-7, 2]]], [[[1.25, 0.5], [0, 1], 2.0, 1.0], [[0, 0]]], [[[1.75, 1.75], [4, -2], 2.0, 0.5], [[0, 0], [1, 0]]], [[[1.0, -2.0], [-1, 1], 2.0, 2.0], [[0, -1], [-1, -1], [-1, 0]]], [[[0.25, 0.25], [-1, 0], 1.0, 1.0], [[0, 0], [-1, 0]]], [[[-1.75, 1.0], [0, 0], 1.0, 1.0], [[-2, 1]]], [[[0.0, -0.25], [-1, -1], 0.5, 2.0], [[0, -1], [-1, -1], [-1, -2], [-2, -2], [-2, -3], [-3, -3], [-3, -4], [-4, -4], [-4, -5], [-5, -5]]]], [[[[0.25, 0.25], [-1, 4], 2.0, 0.5], [[0, 0], [-1, 0], [-1, 1]]], [[[2.0, -1.75], [4, -2], 2.0, 3.0], [[1, -1], [1, -2], [2, -2], [3, -2], [3, -3], [4, -3], [5, -3], [5, -4], [6, -4], [7, -4]]], [[[-1.0, 0.75], [2, 0], 0.5, 1.0], [[-2, 1], [-1, 1], [0, 1], [1, 1], [2, 1]]], [[[-0.5, -1.5], [-1, -1], 0.5, 2.0], [[-1, -3], [-2, -3], [-2, -4], [-3, -4], [-3, -5], [-4, -5], [-4, -6], [-5, -6], [-5, -7], [-6, -7], [-6, -8]]], [[[-1.25, 0.75], [-2, -2], 0.5, 0.5], [[-3, 1], [-4, 1], [-4, 0], [-5, 0], [-5, -1]]], [[[-0.5, -0.75], [-2, 0], 2.0, 3.0], [[-1, -1], [-2, -1], [-3, -1], [-4, -1]]], [[[1.25, 1.0], [-4, -1], 1.0, 1.0], [[1, 1], [1, 0], [0, 0], [-1, 0], [-2, 0], [-3, 0], [-3, -1]]], [[[1.75, -1.75], [1, -1], 1.0, 3.0], [[1, -2], [2, -2], [2, -3], [3, -3], [3, -4], [4, -4], [4, -5]]]], [[[[-1.75, 0.25], [4, 0], 2.0, 0.5], [[-1, 0], [0, 0]]], [[[0.5, 1.5], [0, 2], 1.0, 0.5], [[0, 1], [0, 2]]], [[[-0.75, 0.0], [0, -2], 0.5, 3.0], [[-2, 0], [-2, -1], [-2, -2], [-2, -3], [-2, -4], [-2, -5], [-2, -6], [-2, -7], [-2, -8], [-2, -9], [-2, -10], [-2, -11], [-2, -12], [-2, -13]]], [[[0.0, 2.0], [-1, -2], 2.0, 0.5], [[0, 1], [-1, 1], [-1, 0]]], [[[-0.75, -1.0], [1, 4], 2.0, 3.0], [[-1, -1], [-1, 0], [0, 0], [0, 1], [0, 2], [0, 3], [0, 4], [1, 4], [1, 5]]], [[[0.5, -1.0], [-4, 4], 1.0, 2.0], [[0, -1], [-1, -1], [-1, 0], [-2, 0], [-2, 1], [-3, 1], [-3, 2], [-4, 2], [-4, 3], [-5, 3], [-5, 4], [-6, 4], [-6, 5], [-7, 5], [-7, 6], [-8, 6], [-8, 7]]], [[[1.25, 0.0], [1, -2], 2.0, 2.0], [[0, 0], [0, -1], [1, -1], [1, -2], [1, -3]]], [[[1.0, -2.0], [-2, 0], 2.0, 2.0], [[0, -1], [-1, -1], [-2, -1]]]]]
for i, (args, expected) in enumerate(fixtures[N-1]):
    check("case %d" % i, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
Boundary fixtureActualExpectedOutcome
case 0[[0, -1]][[0, -1]]Passed
case 1[[3, 3], [3, 2], [2, 2], [1, 2], [0, 2], [-1, 2], [-1, 1], [-2, 1], [-3, 1], [-4, 1], [-5, 1], [-5, 0]][[3, 3], [3, 2], [2, 2], [1, 2], [0, 2], [-1, 2], [-1, 1], [-2, 1], [-3, 1], [-4, 1], [-5, 1], [-5, 0]]Passed
case 2[[2, -2], [3, -2], [4, -2], [4, -1], [5, -1], [6, -1], [6, 0]][[2, -2], [3, -2], [4, -2], [4, -1], [5, -1], [6, -1], [6, 0]]Passed
case 3[[-1, -3], [-1, -2], [-2, -2], [-2, -1]][[-1, -3], [-1, -2], [-2, -2], [-2, -1]]Passed
case 4[[2, 1], [2, 2], [2, 3], [2, 4], [2, 5]][[2, 1], [2, 2], [2, 3], [2, 4], [2, 5]]Passed
case 5[[-4, -3], [-5, -3], [-6, -3], [-6, -2], [-7, -2], [-7, -1], [-8, -1], [-8, 0], [-9, 0], [-9, 1]][[-4, -3], [-5, -3], [-6, -3], [-6, -2], [-7, -2], [-7, -1], [-8, -1], [-8, 0], [-9, 0], [-9, 1]]Passed
case 6[[0, -2], [-1, -2], [-2, -2], [-2, -3]][[0, -2], [-1, -2], [-2, -2], [-2, -3]]Passed
case 7[[-2, -2], [-1, -2], [0, -2], [1, -2], [2, -2], [3, -2], [4, -2]][[-2, -2], [-1, -2], [0, -2], [1, -2], [2, -2], [3, -2], [4, -2]]Passed

SHA-256 / 8a372fe60350516881b8b0fd90baba1daa80c09b0b2fe5eed3eb070161b6d948

Verification & scope

A deterministic bounded teaching model with stipulated toy conventions; not a production physics engine or spatial index. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.

Observations recorded using Python 3.12.14 at 2026-09-29T14:51:00.495051+00:00.

Case digest / 01ef24d0de736569fe45e2d763edf86c9b29cdc09ba0ca41581a5a7f4292d458