FAILURE MAP
← Case archive

FA-86646 / Procedural level generation constraints / Open access

Boss room selection: Distance equals discovery order · case 01

The last discovered room becomes the boss even if close to start.

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

ROOT CAUSE

Distance is the discovery counter instead of parent distance plus one.

VERIFIED REPAIR

Restore `dist[v] = dist[u] + 1` at the distance update step.

Unsuccessful approach: Measuring from start directly makes every room distance one.

Case contract

Rooms 0..n-1 joined by two-way doors [a, b]. The boss room is the reachable room (other than start) with the largest BFS door distance from start, ties to the lowest room id. Returns [room, distance] or None when no other room is reachable.

Why this case matters

Procedural generators silently emit unplayable or unfair levels when a single constraint check uses the wrong boundary, axis, neighborhood or update order; the defect is visible in exact generated geometry.

1 / The failure

Exit 1
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(n, doors, start):
    adj = {i: [] for i in range(n)}
    for a, b in doors:
        adj[a].append(b)
        adj[b].append(a)
    dist = {start: 0}
    queue = [start]
    for u in queue:
        for v in sorted(adj[u]):
            if v not in dist:
                dist[v] = len(dist)
                queue.append(v)
    best = None
    for room, d in dist.items():
        if room == start:
            continue
        if best is None or d > best[1] or (d == best[1] and room < best[0]):
            best = [room, d]
    return best
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('two leaves tie #1', [3, [[0, 2], [0, 1]], 0], [1, 1]),
  ('regression distance update #1', [6, [[0, 1], [1, 2], [1, 3], [1, 4], [2, 0], [1, 4]], 2], [3, 2]),
  ('regression distance update #2', [7, [[0, 1], [0, 2], [1, 3], [4, 0], [3, 5], [6, 2]], 1], [6, 3]),
  ('regression distance update #3', [8, [[0, 1], [1, 2], [1, 4], [5, 2], [3, 6], [7, 3], [3, 7]], 2], [0, 2]),
  ('regression distance update #4', [6, [[1, 0], [0, 2], [3, 0], [4, 2], [3, 5]], 4], [5, 4]),
  ('door listed backwards #1', [2, [[1, 0]], 0], [1, 1]),
  ('isolated start #1', [3, [[1, 2]], 0], None),
  ('control #1', [1, [], 0], None)],
 [('two leaves tie #1', [3, [[0, 2], [0, 1]], 0], [1, 1]),
  ('regression distance update #1', [7, [[0, 1], [0, 2], [1, 3], [4, 0], [3, 5], [6, 2]], 1], [6, 3]),
  ('regression distance update #2', [8, [[0, 1], [1, 2], [1, 4], [5, 2], [3, 6], [7, 3], [3, 7]], 2], [0, 2]),
  ('regression distance update #3', [6, [[1, 0], [0, 2], [3, 0], [4, 2], [3, 5]], 4], [5, 4]),
  ('regression distance update #4',
   [8, [[0, 1], [2, 0], [1, 3], [0, 4], [5, 0], [3, 6], [1, 7], [0, 5], [0, 1]], 5],
   [6, 4]),
  ('door listed backwards #1', [2, [[1, 0]], 0], [1, 1]),
  ('isolated start #1', [3, [[1, 2]], 0], None),
  ('control #1', [1, [], 0], None)],
 [('two leaves tie #1', [3, [[0, 2], [0, 1]], 0], [1, 1]),
  ('regression distance update #1', [6, [[1, 0], [0, 2], [3, 0], [4, 2], [3, 5]], 4], [5, 4]),
  ('regression distance update #2',
   [8, [[0, 1], [2, 0], [1, 3], [0, 4], [5, 0], [3, 6], [1, 7], [0, 5], [0, 1]], 5],
   [6, 4]),
  ('regression distance update #3', [7, [[0, 1], [3, 0], [4, 1], [5, 4], [6, 5], [4, 0]], 4], [3, 2]),
  ('partial repair boundary #1', [3, [[0, 1], [2, 1], [0, 1]], 2], [0, 2]),
  ('door listed backwards #1', [2, [[1, 0]], 0], [1, 1]),
  ('isolated start #1', [3, [[1, 2]], 0], None),
  ('control #1', [1, [], 0], None)],
 [('two leaves tie #1', [3, [[0, 2], [0, 1]], 0], [1, 1]),
  ('regression distance update #1', [7, [[0, 1], [3, 0], [4, 1], [5, 4], [6, 5], [4, 0]], 4], [3, 2]),
  ('fault site distance update #1', [4, [[0, 1], [2, 0], [1, 3], [2, 3], [0, 3]], 0], [1, 1]),
  ('partial repair boundary #1', [3, [[0, 1], [2, 1], [0, 1]], 2], [0, 2]),
  ('regression distance update #2', [4, [[0, 1], [0, 2], [0, 3], [1, 3], [2, 0]], 3], [2, 2]),
  ('door listed backwards #1', [2, [[1, 0]], 0], [1, 1]),
  ('isolated start #1', [3, [[1, 2]], 0], None),
  ('control #1', [8, [[1, 0], [1, 3], [3, 4], [4, 5], [0, 6], [7, 4], [3, 7]], 2], None)],
 [('two leaves tie #1', [3, [[0, 2], [0, 1]], 0], [1, 1]),
  ('fault site distance update #1', [3, [[2, 0], [0, 1]], 0], [1, 1]),
  ('regression distance update #1', [4, [[0, 1], [0, 2], [0, 3], [1, 3], [2, 0]], 3], [2, 2]),
  ('partial repair boundary #1', [3, [[1, 0], [2, 1]], 0], [2, 2]),
  ('regression distance update #2', [8, [[0, 1], [2, 0], [0, 4], [3, 5], [7, 6], [4, 3], [4, 6]], 7], [1, 4]),
  ('door listed backwards #1', [2, [[1, 0]], 0], [1, 1]),
  ('isolated start #1', [3, [[1, 2]], 0], None),
  ('control #1', [5, [[0, 1], [0, 2], [3, 0], [0, 3]], 4], None)]]
for label, args, expected in cases[N-1]:
    check(label, 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
two leaves tie #1[2, 2][1, 1]Failed
regression distance update #1[4, 4][3, 2]Failed
regression distance update #2[6, 6][6, 3]Failed
regression distance update #3[4, 4][0, 2]Failed
regression distance update #4[5, 5][5, 4]Failed
door listed backwards #1[1, 1][1, 1]Passed
isolated start #1NoneNonePassed
control #1NoneNonePassed

SHA-256 / c8e96707f11a03e57d6940f882b6c10b419c8d28c0573f90243a721c67eab0c5

2 / The unsuccessful fix

Exit 1
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(n, doors, start):
    adj = {i: [] for i in range(n)}
    for a, b in doors:
        adj[a].append(b)
        adj[b].append(a)
    dist = {start: 0}
    queue = [start]
    for u in queue:
        for v in sorted(adj[u]):
            if v not in dist:
                dist[v] = dist[start] + 1
                queue.append(v)
    best = None
    for room, d in dist.items():
        if room == start:
            continue
        if best is None or d > best[1] or (d == best[1] and room < best[0]):
            best = [room, d]
    return best
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('two leaves tie #1', [3, [[0, 2], [0, 1]], 0], [1, 1]),
  ('regression distance update #1', [6, [[0, 1], [1, 2], [1, 3], [1, 4], [2, 0], [1, 4]], 2], [3, 2]),
  ('regression distance update #2', [7, [[0, 1], [0, 2], [1, 3], [4, 0], [3, 5], [6, 2]], 1], [6, 3]),
  ('regression distance update #3', [8, [[0, 1], [1, 2], [1, 4], [5, 2], [3, 6], [7, 3], [3, 7]], 2], [0, 2]),
  ('regression distance update #4', [6, [[1, 0], [0, 2], [3, 0], [4, 2], [3, 5]], 4], [5, 4]),
  ('door listed backwards #1', [2, [[1, 0]], 0], [1, 1]),
  ('isolated start #1', [3, [[1, 2]], 0], None),
  ('control #1', [1, [], 0], None)],
 [('two leaves tie #1', [3, [[0, 2], [0, 1]], 0], [1, 1]),
  ('regression distance update #1', [7, [[0, 1], [0, 2], [1, 3], [4, 0], [3, 5], [6, 2]], 1], [6, 3]),
  ('regression distance update #2', [8, [[0, 1], [1, 2], [1, 4], [5, 2], [3, 6], [7, 3], [3, 7]], 2], [0, 2]),
  ('regression distance update #3', [6, [[1, 0], [0, 2], [3, 0], [4, 2], [3, 5]], 4], [5, 4]),
  ('regression distance update #4',
   [8, [[0, 1], [2, 0], [1, 3], [0, 4], [5, 0], [3, 6], [1, 7], [0, 5], [0, 1]], 5],
   [6, 4]),
  ('door listed backwards #1', [2, [[1, 0]], 0], [1, 1]),
  ('isolated start #1', [3, [[1, 2]], 0], None),
  ('control #1', [1, [], 0], None)],
 [('two leaves tie #1', [3, [[0, 2], [0, 1]], 0], [1, 1]),
  ('regression distance update #1', [6, [[1, 0], [0, 2], [3, 0], [4, 2], [3, 5]], 4], [5, 4]),
  ('regression distance update #2',
   [8, [[0, 1], [2, 0], [1, 3], [0, 4], [5, 0], [3, 6], [1, 7], [0, 5], [0, 1]], 5],
   [6, 4]),
  ('regression distance update #3', [7, [[0, 1], [3, 0], [4, 1], [5, 4], [6, 5], [4, 0]], 4], [3, 2]),
  ('partial repair boundary #1', [3, [[0, 1], [2, 1], [0, 1]], 2], [0, 2]),
  ('door listed backwards #1', [2, [[1, 0]], 0], [1, 1]),
  ('isolated start #1', [3, [[1, 2]], 0], None),
  ('control #1', [1, [], 0], None)],
 [('two leaves tie #1', [3, [[0, 2], [0, 1]], 0], [1, 1]),
  ('regression distance update #1', [7, [[0, 1], [3, 0], [4, 1], [5, 4], [6, 5], [4, 0]], 4], [3, 2]),
  ('fault site distance update #1', [4, [[0, 1], [2, 0], [1, 3], [2, 3], [0, 3]], 0], [1, 1]),
  ('partial repair boundary #1', [3, [[0, 1], [2, 1], [0, 1]], 2], [0, 2]),
  ('regression distance update #2', [4, [[0, 1], [0, 2], [0, 3], [1, 3], [2, 0]], 3], [2, 2]),
  ('door listed backwards #1', [2, [[1, 0]], 0], [1, 1]),
  ('isolated start #1', [3, [[1, 2]], 0], None),
  ('control #1', [8, [[1, 0], [1, 3], [3, 4], [4, 5], [0, 6], [7, 4], [3, 7]], 2], None)],
 [('two leaves tie #1', [3, [[0, 2], [0, 1]], 0], [1, 1]),
  ('fault site distance update #1', [3, [[2, 0], [0, 1]], 0], [1, 1]),
  ('regression distance update #1', [4, [[0, 1], [0, 2], [0, 3], [1, 3], [2, 0]], 3], [2, 2]),
  ('partial repair boundary #1', [3, [[1, 0], [2, 1]], 0], [2, 2]),
  ('regression distance update #2', [8, [[0, 1], [2, 0], [0, 4], [3, 5], [7, 6], [4, 3], [4, 6]], 7], [1, 4]),
  ('door listed backwards #1', [2, [[1, 0]], 0], [1, 1]),
  ('isolated start #1', [3, [[1, 2]], 0], None),
  ('control #1', [5, [[0, 1], [0, 2], [3, 0], [0, 3]], 4], None)]]
for label, args, expected in cases[N-1]:
    check(label, 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
two leaves tie #1[1, 1][1, 1]Passed
regression distance update #1[0, 1][3, 2]Failed
regression distance update #2[0, 1][6, 3]Failed
regression distance update #3[0, 1][0, 2]Failed
regression distance update #4[0, 1][5, 4]Failed
door listed backwards #1[1, 1][1, 1]Passed
isolated start #1NoneNonePassed
control #1NoneNonePassed

SHA-256 / 90087e1e90c7288ff6106ab4deacd804ca8a007e233dcc827cc0d1223496ed4d

3 / The verified repair

Exit 0
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(n, doors, start):
    adj = {i: [] for i in range(n)}
    for a, b in doors:
        adj[a].append(b)
        adj[b].append(a)
    dist = {start: 0}
    queue = [start]
    for u in queue:
        for v in sorted(adj[u]):
            if v not in dist:
                dist[v] = dist[u] + 1
                queue.append(v)
    best = None
    for room, d in dist.items():
        if room == start:
            continue
        if best is None or d > best[1] or (d == best[1] and room < best[0]):
            best = [room, d]
    return best
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('two leaves tie #1', [3, [[0, 2], [0, 1]], 0], [1, 1]),
  ('regression distance update #1', [6, [[0, 1], [1, 2], [1, 3], [1, 4], [2, 0], [1, 4]], 2], [3, 2]),
  ('regression distance update #2', [7, [[0, 1], [0, 2], [1, 3], [4, 0], [3, 5], [6, 2]], 1], [6, 3]),
  ('regression distance update #3', [8, [[0, 1], [1, 2], [1, 4], [5, 2], [3, 6], [7, 3], [3, 7]], 2], [0, 2]),
  ('regression distance update #4', [6, [[1, 0], [0, 2], [3, 0], [4, 2], [3, 5]], 4], [5, 4]),
  ('door listed backwards #1', [2, [[1, 0]], 0], [1, 1]),
  ('isolated start #1', [3, [[1, 2]], 0], None),
  ('control #1', [1, [], 0], None)],
 [('two leaves tie #1', [3, [[0, 2], [0, 1]], 0], [1, 1]),
  ('regression distance update #1', [7, [[0, 1], [0, 2], [1, 3], [4, 0], [3, 5], [6, 2]], 1], [6, 3]),
  ('regression distance update #2', [8, [[0, 1], [1, 2], [1, 4], [5, 2], [3, 6], [7, 3], [3, 7]], 2], [0, 2]),
  ('regression distance update #3', [6, [[1, 0], [0, 2], [3, 0], [4, 2], [3, 5]], 4], [5, 4]),
  ('regression distance update #4',
   [8, [[0, 1], [2, 0], [1, 3], [0, 4], [5, 0], [3, 6], [1, 7], [0, 5], [0, 1]], 5],
   [6, 4]),
  ('door listed backwards #1', [2, [[1, 0]], 0], [1, 1]),
  ('isolated start #1', [3, [[1, 2]], 0], None),
  ('control #1', [1, [], 0], None)],
 [('two leaves tie #1', [3, [[0, 2], [0, 1]], 0], [1, 1]),
  ('regression distance update #1', [6, [[1, 0], [0, 2], [3, 0], [4, 2], [3, 5]], 4], [5, 4]),
  ('regression distance update #2',
   [8, [[0, 1], [2, 0], [1, 3], [0, 4], [5, 0], [3, 6], [1, 7], [0, 5], [0, 1]], 5],
   [6, 4]),
  ('regression distance update #3', [7, [[0, 1], [3, 0], [4, 1], [5, 4], [6, 5], [4, 0]], 4], [3, 2]),
  ('partial repair boundary #1', [3, [[0, 1], [2, 1], [0, 1]], 2], [0, 2]),
  ('door listed backwards #1', [2, [[1, 0]], 0], [1, 1]),
  ('isolated start #1', [3, [[1, 2]], 0], None),
  ('control #1', [1, [], 0], None)],
 [('two leaves tie #1', [3, [[0, 2], [0, 1]], 0], [1, 1]),
  ('regression distance update #1', [7, [[0, 1], [3, 0], [4, 1], [5, 4], [6, 5], [4, 0]], 4], [3, 2]),
  ('fault site distance update #1', [4, [[0, 1], [2, 0], [1, 3], [2, 3], [0, 3]], 0], [1, 1]),
  ('partial repair boundary #1', [3, [[0, 1], [2, 1], [0, 1]], 2], [0, 2]),
  ('regression distance update #2', [4, [[0, 1], [0, 2], [0, 3], [1, 3], [2, 0]], 3], [2, 2]),
  ('door listed backwards #1', [2, [[1, 0]], 0], [1, 1]),
  ('isolated start #1', [3, [[1, 2]], 0], None),
  ('control #1', [8, [[1, 0], [1, 3], [3, 4], [4, 5], [0, 6], [7, 4], [3, 7]], 2], None)],
 [('two leaves tie #1', [3, [[0, 2], [0, 1]], 0], [1, 1]),
  ('fault site distance update #1', [3, [[2, 0], [0, 1]], 0], [1, 1]),
  ('regression distance update #1', [4, [[0, 1], [0, 2], [0, 3], [1, 3], [2, 0]], 3], [2, 2]),
  ('partial repair boundary #1', [3, [[1, 0], [2, 1]], 0], [2, 2]),
  ('regression distance update #2', [8, [[0, 1], [2, 0], [0, 4], [3, 5], [7, 6], [4, 3], [4, 6]], 7], [1, 4]),
  ('door listed backwards #1', [2, [[1, 0]], 0], [1, 1]),
  ('isolated start #1', [3, [[1, 2]], 0], None),
  ('control #1', [5, [[0, 1], [0, 2], [3, 0], [0, 3]], 4], None)]]
for label, args, expected in cases[N-1]:
    check(label, 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
two leaves tie #1[1, 1][1, 1]Passed
regression distance update #1[3, 2][3, 2]Passed
regression distance update #2[6, 3][6, 3]Passed
regression distance update #3[0, 2][0, 2]Passed
regression distance update #4[5, 4][5, 4]Passed
door listed backwards #1[1, 1][1, 1]Passed
isolated start #1NoneNonePassed
control #1NoneNonePassed

SHA-256 / d6989bca6f3990532d55f9d018f7a6ce25e1e82070c9c434b7f38a45e3866821

Verification & scope

Deterministic toy contract stipulated for this model; integer or exact arithmetic only, not a reproduction of any specific game engine. 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:50:51.498731+00:00.

Case digest / 01ecafc549dc2548ee29086dd922ccdeef95ba18ebe80b381c45aa85317570e6