FAILURE MAP
← Case archive

FA-87596 / Collision detection broadphase / Open access

Rays travelling in -x measure the first boundary on the far side of the cell · case 01

Leftward rays step cells at the wrong times and skip cells.

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

ROOT CAUSE

For sx<0 the first x boundary uses (ix+1)*cs.

VERIFIED REPAIR

Moving in -x the next boundary is ix*cs.

Unsuccessful approach: Using (ix-1)*cs skips a whole cell before the first step.

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 + 1) * 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 = [[[[[-0.25, -1.25], [-1, 2], 0.5, 0.5], [[-1, -3], [-1, -2], [-2, -2], [-2, -1]]], [[[-0.75, -0.75], [-1, -2], 2.0, 0.5], [[-1, -1]]], [[[1.75, -1.0], [2, 2], 2.0, 1.0], [[0, -1], [1, -1], [1, 0]]], [[[-1.5, 0.25], [-1, 4], 0.5, 1.0], [[-3, 0], [-4, 0], [-4, 1], [-4, 2], [-4, 3], [-4, 4], [-5, 4], [-5, 5], [-5, 6], [-5, 7], [-5, 8], [-6, 8]]], [[[0.0, -1.5], [-2, -1], 1.0, 0.5], [[0, -2], [-1, -2], [-2, -2], [-2, -3]]], [[[-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], [4, -2], 1.0, 3.0], [[0, -2], [1, -2], [1, -3], [2, -3], [3, -3], [3, -4], [4, -4], [5, -4], [5, -5], [6, -5], [7, -5], [7, -6], [8, -6], [9, -6], [9, -7], [10, -7], [11, -7], [11, -8], [12, -8]]], [[[-1.25, -1.75], [2, 0], 1.0, 3.0], [[-2, -2], [-1, -2], [0, -2], [1, -2], [2, -2], [3, -2], [4, -2]]]], [[[[1.5, 1.75], [2, 4], 2.0, 1.0], [[0, 0], [0, 1], [1, 1], [1, 2]]], [[[-1.5, 0.5], [-4, 2], 1.0, 1.0], [[-2, 0], [-3, 0], [-3, 1], [-4, 1], [-5, 1], [-5, 2], [-6, 2]]], [[[1.75, -1.0], [-4, -1], 0.5, 3.0], [[3, -2], [3, -3], [2, -3], [1, -3], [0, -3], [-1, -3], [-1, -4], [-2, -4], [-3, -4], [-4, -4], [-5, -4], [-5, -5], [-6, -5], [-7, -5], [-8, -5], [-9, -5], [-9, -6], [-10, -6], [-11, -6], [-12, -6], [-13, -6], [-13, -7], [-14, -7], [-15, -7], [-16, -7], [-17, -7], [-17, -8], [-18, -8], [-19, -8], [-20, -8], [-21, -8], [-21, -9]]], [[[1.75, 1.0], [1, 4], 2.0, 3.0], [[0, 0], [1, 0], [1, 1], [1, 2], [1, 3], [1, 4], [2, 4], [2, 5], [2, 6]]], [[[1.0, 0.0], [-4, 2], 2.0, 1.0], [[0, 0], [-1, 0], [-2, 0], [-2, 1]]], [[[1.0, 0.5], [-2, -2], 0.5, 2.0], [[2, 1], [1, 1], [1, 0], [0, 0], [0, -1], [-1, -1], [-1, -2], [-2, -2], [-2, -3], [-3, -3], [-3, -4], [-4, -4], [-4, -5], [-5, -5], [-5, -6], [-6, -6], [-6, -7], [-7, -7], [-7, -8]]], [[[-1.75, 0.25], [0, 0], 0.5, 0.5], [[-4, 0]]], [[[-0.25, -0.75], [-4, -2], 2.0, 3.0], [[-1, -1], [-2, -1], [-2, -2], [-3, -2], [-4, -2], [-4, -3], [-5, -3], [-6, -3], [-6, -4], [-7, -4]]]], [[[[-0.5, 1.0], [-2, -2], 2.0, 1.0], [[-1, 0], [-1, -1], [-2, -1]]], [[[-2.0, 1.0], [2, 2], 1.0, 0.5], [[-2, 1], [-1, 1], [-1, 2]]], [[[-0.5, 0.0], [2, 0], 0.5, 2.0], [[-1, 0], [0, 0], [1, 0], [2, 0], [3, 0], [4, 0], [5, 0], [6, 0], [7, 0]]], [[[1.5, 2.0], [-2, 2], 1.0, 0.5], [[1, 2], [0, 2], [0, 3]]], [[[-0.25, -1.0], [-4, 4], 2.0, 0.5], [[-1, -1], [-1, 0], [-2, 0]]], [[[0.0, 1.0], [1, -2], 2.0, 2.0], [[0, 0], [0, -1], [0, -2], [1, -2]]], [[[-0.25, -1.75], [-2, -1], 1.0, 2.0], [[-1, -2], [-1, -3], [-2, -3], [-3, -3], [-3, -4], [-4, -4], [-5, -4]]], [[[0.25, -1.75], [-2, -2], 2.0, 0.5], [[0, -1], [-1, -1], [-1, -2]]]], [[[[1.0, -1.75], [-1, 1], 1.0, 0.5], [[1, -2], [0, -2]]], [[[1.25, 0.0], [-4, 1], 1.0, 2.0], [[1, 0], [0, 0], [-1, 0], [-2, 0], [-3, 0], [-3, 1], [-4, 1], [-5, 1], [-6, 1], [-7, 1], [-7, 2]]], [[[-2.0, -0.75], [-2, 4], 0.5, 3.0], [[-4, -2], [-5, -2], [-5, -1], [-5, 0], [-6, 0], [-6, 1], [-6, 2], [-7, 2], [-7, 3], [-7, 4], [-8, 4], [-8, 5], [-8, 6], [-9, 6], [-9, 7], [-9, 8], [-10, 8], [-10, 9], [-10, 10], [-11, 10], [-11, 11], [-11, 12], [-12, 12], [-12, 13], [-12, 14], [-13, 14], [-13, 15], [-13, 16], [-14, 16], [-14, 17], [-14, 18], [-15, 18], [-15, 19], [-15, 20], [-16, 20], [-16, 21], [-16, 22], [-17, 22]]], [[[1.25, -2.0], [1, 4], 2.0, 2.0], [[0, -1], [0, 0], [1, 0], [1, 1], [1, 2], [1, 3]]], [[[-0.75, 0.5], [1, 0], 0.5, 2.0], [[-2, 1], [-1, 1], [0, 1], [1, 1], [2, 1]]], [[[-1.75, 0.25], [-1, 4], 1.0, 2.0], [[-2, 0], [-2, 1], [-3, 1], [-3, 2], [-3, 3], [-3, 4], [-3, 5], [-4, 5], [-4, 6], [-4, 7], [-4, 8]]], [[[-0.5, -0.75], [-2, 0], 2.0, 3.0], [[-1, -1], [-2, -1], [-3, -1], [-4, -1]]], [[[1.5, 0.25], [4, 4], 0.5, 3.0], [[3, 0], [3, 1], [4, 1], [4, 2], [5, 2], [5, 3], [6, 3], [6, 4], [7, 4], [7, 5], [8, 5], [8, 6], [9, 6], [9, 7], [10, 7], [10, 8], [11, 8], [11, 9], [12, 9], [12, 10], [13, 10], [13, 11], [14, 11], [14, 12], [15, 12], [15, 13], [16, 13], [16, 14], [17, 14], [17, 15], [18, 15], [18, 16], [19, 16], [19, 17], [20, 17], [20, 18], [21, 18], [21, 19], [22, 19], [22, 20], [23, 20], [23, 21], [24, 21], [24, 22], [25, 22], [25, 23], [26, 23], [26, 24], [27, 24]]]], [[[[-2.0, 1.0], [4, 1], 1.0, 0.5], [[-2, 1], [-1, 1], [0, 1]]], [[[-1.75, 0.25], [4, 0], 2.0, 0.5], [[-1, 0], [0, 0]]], [[[1.0, -2.0], [-2, 0], 2.0, 2.0], [[0, -1], [-1, -1], [-2, -1]]], [[[-0.5, -0.75], [4, 0], 1.0, 0.5], [[-1, -1], [0, -1], [1, -1]]], [[[1.25, 1.75], [-1, -2], 0.5, 2.0], [[2, 3], [2, 2], [1, 2], [1, 1], [1, 0], [0, 0], [0, -1], [0, -2], [-1, -2], [-1, -3], [-1, -4], [-2, -4], [-2, -5]]], [[[-2.0, 2.0], [-2, 2], 1.0, 1.0], [[-2, 2], [-3, 2], [-4, 2], [-4, 3], [-5, 3], [-5, 4]]], [[[2.0, 0.0], [-2, -2], 0.5, 1.0], [[4, 0], [3, 0], [3, -1], [2, -1], [2, -2], [1, -2], [1, -3], [0, -3], [0, -4], [-1, -4], [-1, -5]]], [[[-2.0, -1.75], [-1, 1], 0.5, 3.0], [[-4, -4], [-5, -4], [-5, -3], [-6, -3], [-6, -2], [-7, -2], [-7, -1], [-8, -1], [-8, 0], [-9, 0], [-9, 1], [-10, 1], [-10, 2], [-11, 2]]]]]
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[[-1, -3], [-2, -3], [-2, -2], [-3, -2], [-3, -1]][[-1, -3], [-1, -2], [-2, -2], [-2, -1]]Failed
case 1[[-1, -1], [-2, -1]][[-1, -1]]Failed
case 2[[0, -1], [1, -1], [1, 0]][[0, -1], [1, -1], [1, 0]]Passed
case 3[[-3, 0], [-4, 0], [-5, 0], [-5, 1], [-5, 2], [-5, 3], [-5, 4], [-6, 4], [-6, 5], [-6, 6], [-6, 7], [-6, 8], [-7, 8]][[-3, 0], [-4, 0], [-4, 1], [-4, 2], [-4, 3], [-4, 4], [-5, 4], [-5, 5], [-5, 6], [-5, 7], [-5, 8], [-6, 8]]Failed
case 4[[0, -2], [-1, -2], [-2, -2], [-3, -2], [-3, -3]][[0, -2], [-1, -2], [-2, -2], [-2, -3]]Failed
case 5[[-4, -3], [-5, -3], [-6, -3], [-7, -3], [-7, -2], [-8, -2], [-8, -1], [-9, -1], [-9, 0], [-10, 0], [-10, 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], [1, -3], [2, -3], [3, -3], [3, -4], [4, -4], [5, -4], [5, -5], [6, -5], [7, -5], [7, -6], [8, -6], [9, -6], [9, -7], [10, -7], [11, -7], [11, -8], [12, -8]][[0, -2], [1, -2], [1, -3], [2, -3], [3, -3], [3, -4], [4, -4], [5, -4], [5, -5], [6, -5], [7, -5], [7, -6], [8, -6], [9, -6], [9, -7], [10, -7], [11, -7], [11, -8], [12, -8]]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 / 6934cff7044f0265c139b489e2625d12308ca33f78de4df8fa23dc63016bc322

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 - 1) * 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 = [[[[[-0.25, -1.25], [-1, 2], 0.5, 0.5], [[-1, -3], [-1, -2], [-2, -2], [-2, -1]]], [[[-0.75, -0.75], [-1, -2], 2.0, 0.5], [[-1, -1]]], [[[1.75, -1.0], [2, 2], 2.0, 1.0], [[0, -1], [1, -1], [1, 0]]], [[[-1.5, 0.25], [-1, 4], 0.5, 1.0], [[-3, 0], [-4, 0], [-4, 1], [-4, 2], [-4, 3], [-4, 4], [-5, 4], [-5, 5], [-5, 6], [-5, 7], [-5, 8], [-6, 8]]], [[[0.0, -1.5], [-2, -1], 1.0, 0.5], [[0, -2], [-1, -2], [-2, -2], [-2, -3]]], [[[-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], [4, -2], 1.0, 3.0], [[0, -2], [1, -2], [1, -3], [2, -3], [3, -3], [3, -4], [4, -4], [5, -4], [5, -5], [6, -5], [7, -5], [7, -6], [8, -6], [9, -6], [9, -7], [10, -7], [11, -7], [11, -8], [12, -8]]], [[[-1.25, -1.75], [2, 0], 1.0, 3.0], [[-2, -2], [-1, -2], [0, -2], [1, -2], [2, -2], [3, -2], [4, -2]]]], [[[[1.5, 1.75], [2, 4], 2.0, 1.0], [[0, 0], [0, 1], [1, 1], [1, 2]]], [[[-1.5, 0.5], [-4, 2], 1.0, 1.0], [[-2, 0], [-3, 0], [-3, 1], [-4, 1], [-5, 1], [-5, 2], [-6, 2]]], [[[1.75, -1.0], [-4, -1], 0.5, 3.0], [[3, -2], [3, -3], [2, -3], [1, -3], [0, -3], [-1, -3], [-1, -4], [-2, -4], [-3, -4], [-4, -4], [-5, -4], [-5, -5], [-6, -5], [-7, -5], [-8, -5], [-9, -5], [-9, -6], [-10, -6], [-11, -6], [-12, -6], [-13, -6], [-13, -7], [-14, -7], [-15, -7], [-16, -7], [-17, -7], [-17, -8], [-18, -8], [-19, -8], [-20, -8], [-21, -8], [-21, -9]]], [[[1.75, 1.0], [1, 4], 2.0, 3.0], [[0, 0], [1, 0], [1, 1], [1, 2], [1, 3], [1, 4], [2, 4], [2, 5], [2, 6]]], [[[1.0, 0.0], [-4, 2], 2.0, 1.0], [[0, 0], [-1, 0], [-2, 0], [-2, 1]]], [[[1.0, 0.5], [-2, -2], 0.5, 2.0], [[2, 1], [1, 1], [1, 0], [0, 0], [0, -1], [-1, -1], [-1, -2], [-2, -2], [-2, -3], [-3, -3], [-3, -4], [-4, -4], [-4, -5], [-5, -5], [-5, -6], [-6, -6], [-6, -7], [-7, -7], [-7, -8]]], [[[-1.75, 0.25], [0, 0], 0.5, 0.5], [[-4, 0]]], [[[-0.25, -0.75], [-4, -2], 2.0, 3.0], [[-1, -1], [-2, -1], [-2, -2], [-3, -2], [-4, -2], [-4, -3], [-5, -3], [-6, -3], [-6, -4], [-7, -4]]]], [[[[-0.5, 1.0], [-2, -2], 2.0, 1.0], [[-1, 0], [-1, -1], [-2, -1]]], [[[-2.0, 1.0], [2, 2], 1.0, 0.5], [[-2, 1], [-1, 1], [-1, 2]]], [[[-0.5, 0.0], [2, 0], 0.5, 2.0], [[-1, 0], [0, 0], [1, 0], [2, 0], [3, 0], [4, 0], [5, 0], [6, 0], [7, 0]]], [[[1.5, 2.0], [-2, 2], 1.0, 0.5], [[1, 2], [0, 2], [0, 3]]], [[[-0.25, -1.0], [-4, 4], 2.0, 0.5], [[-1, -1], [-1, 0], [-2, 0]]], [[[0.0, 1.0], [1, -2], 2.0, 2.0], [[0, 0], [0, -1], [0, -2], [1, -2]]], [[[-0.25, -1.75], [-2, -1], 1.0, 2.0], [[-1, -2], [-1, -3], [-2, -3], [-3, -3], [-3, -4], [-4, -4], [-5, -4]]], [[[0.25, -1.75], [-2, -2], 2.0, 0.5], [[0, -1], [-1, -1], [-1, -2]]]], [[[[1.0, -1.75], [-1, 1], 1.0, 0.5], [[1, -2], [0, -2]]], [[[1.25, 0.0], [-4, 1], 1.0, 2.0], [[1, 0], [0, 0], [-1, 0], [-2, 0], [-3, 0], [-3, 1], [-4, 1], [-5, 1], [-6, 1], [-7, 1], [-7, 2]]], [[[-2.0, -0.75], [-2, 4], 0.5, 3.0], [[-4, -2], [-5, -2], [-5, -1], [-5, 0], [-6, 0], [-6, 1], [-6, 2], [-7, 2], [-7, 3], [-7, 4], [-8, 4], [-8, 5], [-8, 6], [-9, 6], [-9, 7], [-9, 8], [-10, 8], [-10, 9], [-10, 10], [-11, 10], [-11, 11], [-11, 12], [-12, 12], [-12, 13], [-12, 14], [-13, 14], [-13, 15], [-13, 16], [-14, 16], [-14, 17], [-14, 18], [-15, 18], [-15, 19], [-15, 20], [-16, 20], [-16, 21], [-16, 22], [-17, 22]]], [[[1.25, -2.0], [1, 4], 2.0, 2.0], [[0, -1], [0, 0], [1, 0], [1, 1], [1, 2], [1, 3]]], [[[-0.75, 0.5], [1, 0], 0.5, 2.0], [[-2, 1], [-1, 1], [0, 1], [1, 1], [2, 1]]], [[[-1.75, 0.25], [-1, 4], 1.0, 2.0], [[-2, 0], [-2, 1], [-3, 1], [-3, 2], [-3, 3], [-3, 4], [-3, 5], [-4, 5], [-4, 6], [-4, 7], [-4, 8]]], [[[-0.5, -0.75], [-2, 0], 2.0, 3.0], [[-1, -1], [-2, -1], [-3, -1], [-4, -1]]], [[[1.5, 0.25], [4, 4], 0.5, 3.0], [[3, 0], [3, 1], [4, 1], [4, 2], [5, 2], [5, 3], [6, 3], [6, 4], [7, 4], [7, 5], [8, 5], [8, 6], [9, 6], [9, 7], [10, 7], [10, 8], [11, 8], [11, 9], [12, 9], [12, 10], [13, 10], [13, 11], [14, 11], [14, 12], [15, 12], [15, 13], [16, 13], [16, 14], [17, 14], [17, 15], [18, 15], [18, 16], [19, 16], [19, 17], [20, 17], [20, 18], [21, 18], [21, 19], [22, 19], [22, 20], [23, 20], [23, 21], [24, 21], [24, 22], [25, 22], [25, 23], [26, 23], [26, 24], [27, 24]]]], [[[[-2.0, 1.0], [4, 1], 1.0, 0.5], [[-2, 1], [-1, 1], [0, 1]]], [[[-1.75, 0.25], [4, 0], 2.0, 0.5], [[-1, 0], [0, 0]]], [[[1.0, -2.0], [-2, 0], 2.0, 2.0], [[0, -1], [-1, -1], [-2, -1]]], [[[-0.5, -0.75], [4, 0], 1.0, 0.5], [[-1, -1], [0, -1], [1, -1]]], [[[1.25, 1.75], [-1, -2], 0.5, 2.0], [[2, 3], [2, 2], [1, 2], [1, 1], [1, 0], [0, 0], [0, -1], [0, -2], [-1, -2], [-1, -3], [-1, -4], [-2, -4], [-2, -5]]], [[[-2.0, 2.0], [-2, 2], 1.0, 1.0], [[-2, 2], [-3, 2], [-4, 2], [-4, 3], [-5, 3], [-5, 4]]], [[[2.0, 0.0], [-2, -2], 0.5, 1.0], [[4, 0], [3, 0], [3, -1], [2, -1], [2, -2], [1, -2], [1, -3], [0, -3], [0, -4], [-1, -4], [-1, -5]]], [[[-2.0, -1.75], [-1, 1], 0.5, 3.0], [[-4, -4], [-5, -4], [-5, -3], [-6, -3], [-6, -2], [-7, -2], [-7, -1], [-8, -1], [-8, 0], [-9, 0], [-9, 1], [-10, 1], [-10, 2], [-11, 2]]]]]
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[[-1, -3], [-1, -2], [-1, -1]][[-1, -3], [-1, -2], [-2, -2], [-2, -1]]Failed
case 1[[-1, -1]][[-1, -1]]Passed
case 2[[0, -1], [1, -1], [1, 0]][[0, -1], [1, -1], [1, 0]]Passed
case 3[[-3, 0], [-3, 1], [-3, 2], [-3, 3], [-3, 4], [-4, 4], [-4, 5], [-4, 6], [-4, 7], [-4, 8], [-5, 8]][[-3, 0], [-4, 0], [-4, 1], [-4, 2], [-4, 3], [-4, 4], [-5, 4], [-5, 5], [-5, 6], [-5, 7], [-5, 8], [-6, 8]]Failed
case 4[[0, -2], [-1, -2], [-1, -3]][[0, -2], [-1, -2], [-2, -2], [-2, -3]]Failed
case 5[[-4, -3], [-5, -3], [-5, -2], [-6, -2], [-6, -1], [-7, -1], [-7, 0], [-8, 0], [-8, 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], [1, -3], [2, -3], [3, -3], [3, -4], [4, -4], [5, -4], [5, -5], [6, -5], [7, -5], [7, -6], [8, -6], [9, -6], [9, -7], [10, -7], [11, -7], [11, -8], [12, -8]][[0, -2], [1, -2], [1, -3], [2, -3], [3, -3], [3, -4], [4, -4], [5, -4], [5, -5], [6, -5], [7, -5], [7, -6], [8, -6], [9, -6], [9, -7], [10, -7], [11, -7], [11, -8], [12, -8]]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 / 170d9299ac187e5faf4cc7ffa89a8119d77873d98e84335389dd425448044c54

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 = [[[[[-0.25, -1.25], [-1, 2], 0.5, 0.5], [[-1, -3], [-1, -2], [-2, -2], [-2, -1]]], [[[-0.75, -0.75], [-1, -2], 2.0, 0.5], [[-1, -1]]], [[[1.75, -1.0], [2, 2], 2.0, 1.0], [[0, -1], [1, -1], [1, 0]]], [[[-1.5, 0.25], [-1, 4], 0.5, 1.0], [[-3, 0], [-4, 0], [-4, 1], [-4, 2], [-4, 3], [-4, 4], [-5, 4], [-5, 5], [-5, 6], [-5, 7], [-5, 8], [-6, 8]]], [[[0.0, -1.5], [-2, -1], 1.0, 0.5], [[0, -2], [-1, -2], [-2, -2], [-2, -3]]], [[[-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], [4, -2], 1.0, 3.0], [[0, -2], [1, -2], [1, -3], [2, -3], [3, -3], [3, -4], [4, -4], [5, -4], [5, -5], [6, -5], [7, -5], [7, -6], [8, -6], [9, -6], [9, -7], [10, -7], [11, -7], [11, -8], [12, -8]]], [[[-1.25, -1.75], [2, 0], 1.0, 3.0], [[-2, -2], [-1, -2], [0, -2], [1, -2], [2, -2], [3, -2], [4, -2]]]], [[[[1.5, 1.75], [2, 4], 2.0, 1.0], [[0, 0], [0, 1], [1, 1], [1, 2]]], [[[-1.5, 0.5], [-4, 2], 1.0, 1.0], [[-2, 0], [-3, 0], [-3, 1], [-4, 1], [-5, 1], [-5, 2], [-6, 2]]], [[[1.75, -1.0], [-4, -1], 0.5, 3.0], [[3, -2], [3, -3], [2, -3], [1, -3], [0, -3], [-1, -3], [-1, -4], [-2, -4], [-3, -4], [-4, -4], [-5, -4], [-5, -5], [-6, -5], [-7, -5], [-8, -5], [-9, -5], [-9, -6], [-10, -6], [-11, -6], [-12, -6], [-13, -6], [-13, -7], [-14, -7], [-15, -7], [-16, -7], [-17, -7], [-17, -8], [-18, -8], [-19, -8], [-20, -8], [-21, -8], [-21, -9]]], [[[1.75, 1.0], [1, 4], 2.0, 3.0], [[0, 0], [1, 0], [1, 1], [1, 2], [1, 3], [1, 4], [2, 4], [2, 5], [2, 6]]], [[[1.0, 0.0], [-4, 2], 2.0, 1.0], [[0, 0], [-1, 0], [-2, 0], [-2, 1]]], [[[1.0, 0.5], [-2, -2], 0.5, 2.0], [[2, 1], [1, 1], [1, 0], [0, 0], [0, -1], [-1, -1], [-1, -2], [-2, -2], [-2, -3], [-3, -3], [-3, -4], [-4, -4], [-4, -5], [-5, -5], [-5, -6], [-6, -6], [-6, -7], [-7, -7], [-7, -8]]], [[[-1.75, 0.25], [0, 0], 0.5, 0.5], [[-4, 0]]], [[[-0.25, -0.75], [-4, -2], 2.0, 3.0], [[-1, -1], [-2, -1], [-2, -2], [-3, -2], [-4, -2], [-4, -3], [-5, -3], [-6, -3], [-6, -4], [-7, -4]]]], [[[[-0.5, 1.0], [-2, -2], 2.0, 1.0], [[-1, 0], [-1, -1], [-2, -1]]], [[[-2.0, 1.0], [2, 2], 1.0, 0.5], [[-2, 1], [-1, 1], [-1, 2]]], [[[-0.5, 0.0], [2, 0], 0.5, 2.0], [[-1, 0], [0, 0], [1, 0], [2, 0], [3, 0], [4, 0], [5, 0], [6, 0], [7, 0]]], [[[1.5, 2.0], [-2, 2], 1.0, 0.5], [[1, 2], [0, 2], [0, 3]]], [[[-0.25, -1.0], [-4, 4], 2.0, 0.5], [[-1, -1], [-1, 0], [-2, 0]]], [[[0.0, 1.0], [1, -2], 2.0, 2.0], [[0, 0], [0, -1], [0, -2], [1, -2]]], [[[-0.25, -1.75], [-2, -1], 1.0, 2.0], [[-1, -2], [-1, -3], [-2, -3], [-3, -3], [-3, -4], [-4, -4], [-5, -4]]], [[[0.25, -1.75], [-2, -2], 2.0, 0.5], [[0, -1], [-1, -1], [-1, -2]]]], [[[[1.0, -1.75], [-1, 1], 1.0, 0.5], [[1, -2], [0, -2]]], [[[1.25, 0.0], [-4, 1], 1.0, 2.0], [[1, 0], [0, 0], [-1, 0], [-2, 0], [-3, 0], [-3, 1], [-4, 1], [-5, 1], [-6, 1], [-7, 1], [-7, 2]]], [[[-2.0, -0.75], [-2, 4], 0.5, 3.0], [[-4, -2], [-5, -2], [-5, -1], [-5, 0], [-6, 0], [-6, 1], [-6, 2], [-7, 2], [-7, 3], [-7, 4], [-8, 4], [-8, 5], [-8, 6], [-9, 6], [-9, 7], [-9, 8], [-10, 8], [-10, 9], [-10, 10], [-11, 10], [-11, 11], [-11, 12], [-12, 12], [-12, 13], [-12, 14], [-13, 14], [-13, 15], [-13, 16], [-14, 16], [-14, 17], [-14, 18], [-15, 18], [-15, 19], [-15, 20], [-16, 20], [-16, 21], [-16, 22], [-17, 22]]], [[[1.25, -2.0], [1, 4], 2.0, 2.0], [[0, -1], [0, 0], [1, 0], [1, 1], [1, 2], [1, 3]]], [[[-0.75, 0.5], [1, 0], 0.5, 2.0], [[-2, 1], [-1, 1], [0, 1], [1, 1], [2, 1]]], [[[-1.75, 0.25], [-1, 4], 1.0, 2.0], [[-2, 0], [-2, 1], [-3, 1], [-3, 2], [-3, 3], [-3, 4], [-3, 5], [-4, 5], [-4, 6], [-4, 7], [-4, 8]]], [[[-0.5, -0.75], [-2, 0], 2.0, 3.0], [[-1, -1], [-2, -1], [-3, -1], [-4, -1]]], [[[1.5, 0.25], [4, 4], 0.5, 3.0], [[3, 0], [3, 1], [4, 1], [4, 2], [5, 2], [5, 3], [6, 3], [6, 4], [7, 4], [7, 5], [8, 5], [8, 6], [9, 6], [9, 7], [10, 7], [10, 8], [11, 8], [11, 9], [12, 9], [12, 10], [13, 10], [13, 11], [14, 11], [14, 12], [15, 12], [15, 13], [16, 13], [16, 14], [17, 14], [17, 15], [18, 15], [18, 16], [19, 16], [19, 17], [20, 17], [20, 18], [21, 18], [21, 19], [22, 19], [22, 20], [23, 20], [23, 21], [24, 21], [24, 22], [25, 22], [25, 23], [26, 23], [26, 24], [27, 24]]]], [[[[-2.0, 1.0], [4, 1], 1.0, 0.5], [[-2, 1], [-1, 1], [0, 1]]], [[[-1.75, 0.25], [4, 0], 2.0, 0.5], [[-1, 0], [0, 0]]], [[[1.0, -2.0], [-2, 0], 2.0, 2.0], [[0, -1], [-1, -1], [-2, -1]]], [[[-0.5, -0.75], [4, 0], 1.0, 0.5], [[-1, -1], [0, -1], [1, -1]]], [[[1.25, 1.75], [-1, -2], 0.5, 2.0], [[2, 3], [2, 2], [1, 2], [1, 1], [1, 0], [0, 0], [0, -1], [0, -2], [-1, -2], [-1, -3], [-1, -4], [-2, -4], [-2, -5]]], [[[-2.0, 2.0], [-2, 2], 1.0, 1.0], [[-2, 2], [-3, 2], [-4, 2], [-4, 3], [-5, 3], [-5, 4]]], [[[2.0, 0.0], [-2, -2], 0.5, 1.0], [[4, 0], [3, 0], [3, -1], [2, -1], [2, -2], [1, -2], [1, -3], [0, -3], [0, -4], [-1, -4], [-1, -5]]], [[[-2.0, -1.75], [-1, 1], 0.5, 3.0], [[-4, -4], [-5, -4], [-5, -3], [-6, -3], [-6, -2], [-7, -2], [-7, -1], [-8, -1], [-8, 0], [-9, 0], [-9, 1], [-10, 1], [-10, 2], [-11, 2]]]]]
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[[-1, -3], [-1, -2], [-2, -2], [-2, -1]][[-1, -3], [-1, -2], [-2, -2], [-2, -1]]Passed
case 1[[-1, -1]][[-1, -1]]Passed
case 2[[0, -1], [1, -1], [1, 0]][[0, -1], [1, -1], [1, 0]]Passed
case 3[[-3, 0], [-4, 0], [-4, 1], [-4, 2], [-4, 3], [-4, 4], [-5, 4], [-5, 5], [-5, 6], [-5, 7], [-5, 8], [-6, 8]][[-3, 0], [-4, 0], [-4, 1], [-4, 2], [-4, 3], [-4, 4], [-5, 4], [-5, 5], [-5, 6], [-5, 7], [-5, 8], [-6, 8]]Passed
case 4[[0, -2], [-1, -2], [-2, -2], [-2, -3]][[0, -2], [-1, -2], [-2, -2], [-2, -3]]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], [1, -3], [2, -3], [3, -3], [3, -4], [4, -4], [5, -4], [5, -5], [6, -5], [7, -5], [7, -6], [8, -6], [9, -6], [9, -7], [10, -7], [11, -7], [11, -8], [12, -8]][[0, -2], [1, -2], [1, -3], [2, -3], [3, -3], [3, -4], [4, -4], [5, -4], [5, -5], [6, -5], [7, -5], [7, -6], [8, -6], [9, -6], [9, -7], [10, -7], [11, -7], [11, -8], [12, -8]]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 / 3125ac0dd00d2f5bc06de125de19e921e9abf121a5642bcda10d22c1dea9e205

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.331694+00:00.

Case digest / 2bbbccc25d04b9bfe1a3f333cd18a2f563b134c0f1578bf7f0206467a79dabf5