FAILURE MAP
← Case archive

FA-86651 / Procedural level generation constraints / Open access

Boss room selection: Ties choose the highest room id · case 01

Equal-distance candidates pick the wrong boss room.

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

ROOT CAUSE

Ties prefer larger room ids.

THE FAILURE

Ties prefer larger room ids.

Unsuccessful approach: Letting later entries win makes the result depend on BFS order.

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] = 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 tie break #1', [6, [[0, 1], [1, 2], [1, 3], [1, 4], [2, 0], [1, 4]], 2], [3, 2]),
  ('regression tie break #2', [8, [[0, 1], [1, 2], [1, 4], [5, 2], [3, 6], [7, 3], [3, 7]], 2], [0, 2]),
  ('regression tie break #3', [7, [[0, 1], [3, 0], [4, 1], [5, 4], [6, 5], [4, 0]], 4], [3, 2]),
  ('regression tie break #4', [4, [[0, 1], [2, 0], [1, 3], [2, 3], [0, 3]], 0], [1, 1]),
  ('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 tie break #1', [8, [[0, 1], [1, 2], [1, 4], [5, 2], [3, 6], [7, 3], [3, 7]], 2], [0, 2]),
  ('regression tie break #2', [7, [[0, 1], [3, 0], [4, 1], [5, 4], [6, 5], [4, 0]], 4], [3, 2]),
  ('regression tie break #3', [4, [[0, 1], [2, 0], [1, 3], [2, 3], [0, 3]], 0], [1, 1]),
  ('regression tie break #4', [3, [[2, 0], [0, 1]], 0], [1, 1]),
  ('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 tie break #1', [4, [[0, 1], [2, 0], [1, 3], [2, 3], [0, 3]], 0], [1, 1]),
  ('regression tie break #2', [3, [[2, 0], [0, 1]], 0], [1, 1]),
  ('regression tie break #3', [6, [[0, 1], [0, 3], [5, 0]], 0], [1, 1]),
  ('regression tie break #4', [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', [1, [], 0], None)],
 [('two leaves tie #1', [3, [[0, 2], [0, 1]], 0], [1, 1]),
  ('regression tie break #1', [6, [[0, 1], [0, 3], [5, 0]], 0], [1, 1]),
  ('regression tie break #2', [8, [[0, 1], [2, 0], [0, 4], [3, 5], [7, 6], [4, 3], [4, 6]], 7], [1, 4]),
  ('regression tie break #3', [6, [[2, 1], [3, 1], [1, 5]], 3], [2, 2]),
  ('regression tie break #4', [4, [[1, 0], [2, 0], [3, 0]], 0], [1, 1]),
  ('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]),
  ('regression tie break #1', [6, [[2, 1], [3, 1], [1, 5]], 3], [2, 2]),
  ('regression tie break #2', [4, [[1, 0], [2, 0], [3, 0]], 0], [1, 1]),
  ('regression tie break #3', [3, [[2, 0], [1, 2], [1, 2]], 2], [0, 1]),
  ('regression tie break #4', [6, [[0, 1], [0, 2], [2, 3], [0, 4], [5, 4]], 0], [3, 2]),
  ('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, 1][1, 1]Failed
regression tie break #1[4, 2][3, 2]Failed
regression tie break #2[4, 2][0, 2]Failed
regression tie break #3[6, 2][3, 2]Failed
regression tie break #4[3, 1][1, 1]Failed
door listed backwards #1[1, 1][1, 1]Passed
isolated start #1NoneNonePassed
control #1NoneNonePassed

SHA-256 / cec56a581efa91093bd40a3f6254116c0671bc7fab8426f27cb8f0b68018a94a

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[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]:
            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 tie break #1', [6, [[0, 1], [1, 2], [1, 3], [1, 4], [2, 0], [1, 4]], 2], [3, 2]),
  ('regression tie break #2', [8, [[0, 1], [1, 2], [1, 4], [5, 2], [3, 6], [7, 3], [3, 7]], 2], [0, 2]),
  ('regression tie break #3', [7, [[0, 1], [3, 0], [4, 1], [5, 4], [6, 5], [4, 0]], 4], [3, 2]),
  ('regression tie break #4', [4, [[0, 1], [2, 0], [1, 3], [2, 3], [0, 3]], 0], [1, 1]),
  ('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 tie break #1', [8, [[0, 1], [1, 2], [1, 4], [5, 2], [3, 6], [7, 3], [3, 7]], 2], [0, 2]),
  ('regression tie break #2', [7, [[0, 1], [3, 0], [4, 1], [5, 4], [6, 5], [4, 0]], 4], [3, 2]),
  ('regression tie break #3', [4, [[0, 1], [2, 0], [1, 3], [2, 3], [0, 3]], 0], [1, 1]),
  ('regression tie break #4', [3, [[2, 0], [0, 1]], 0], [1, 1]),
  ('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 tie break #1', [4, [[0, 1], [2, 0], [1, 3], [2, 3], [0, 3]], 0], [1, 1]),
  ('regression tie break #2', [3, [[2, 0], [0, 1]], 0], [1, 1]),
  ('regression tie break #3', [6, [[0, 1], [0, 3], [5, 0]], 0], [1, 1]),
  ('regression tie break #4', [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', [1, [], 0], None)],
 [('two leaves tie #1', [3, [[0, 2], [0, 1]], 0], [1, 1]),
  ('regression tie break #1', [6, [[0, 1], [0, 3], [5, 0]], 0], [1, 1]),
  ('regression tie break #2', [8, [[0, 1], [2, 0], [0, 4], [3, 5], [7, 6], [4, 3], [4, 6]], 7], [1, 4]),
  ('regression tie break #3', [6, [[2, 1], [3, 1], [1, 5]], 3], [2, 2]),
  ('regression tie break #4', [4, [[1, 0], [2, 0], [3, 0]], 0], [1, 1]),
  ('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]),
  ('regression tie break #1', [6, [[2, 1], [3, 1], [1, 5]], 3], [2, 2]),
  ('regression tie break #2', [4, [[1, 0], [2, 0], [3, 0]], 0], [1, 1]),
  ('regression tie break #3', [3, [[2, 0], [1, 2], [1, 2]], 2], [0, 1]),
  ('regression tie break #4', [6, [[0, 1], [0, 2], [2, 3], [0, 4], [5, 4]], 0], [3, 2]),
  ('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, 1][1, 1]Failed
regression tie break #1[4, 2][3, 2]Failed
regression tie break #2[4, 2][0, 2]Failed
regression tie break #3[6, 2][3, 2]Failed
regression tie break #4[3, 1][1, 1]Failed
door listed backwards #1[1, 1][1, 1]Passed
isolated start #1NoneNonePassed
control #1NoneNonePassed

SHA-256 / 48c7f664f3d6dbe0880a848ddda2203432bfe45ad1972eab01c57dec17d849f1

HELD IN THE MEMBER ARCHIVE

The verified repair and its recorded checks are member-only.

This mechanism has 8 recorded checks per implementation. The open-access tier publishes the failure and the unsuccessful fix; the repaired source that passes every check, and the observations that prove it, are available to members.

Every case sharing this mechanism uses the same contract and the same repair, so this one record is held back for all of them.

Member access is invitation-based. Sign in with your invited account to inspect the repair.

Sign in to the archive ↗

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

Case digest / 8684838e548783882302597079f0425802124e6ffe504c8012129628832504e4