FAILURE MAP
← Case archive

FA-86611 / Procedural level generation constraints / Open access

Treasure dead-end finder: Isolated cells count as dead ends · case 01

Treasure is placed in sealed pockets the player cannot reach.

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

ROOT CAUSE

Zero-degree cells pass the dead-end test.

VERIFIED REPAIR

Restore `if n == 1:` at the dead-end degree step.

Unsuccessful approach: Excluding only the start still admits sealed pockets.

Case contract

Cells: '#' wall, '~' chasm (not walkable), '.' floor, 'D' door (walkable). A dead end is a '.' cell, other than start and exit ([row, col] lists), with exactly one walkable in-bounds 4-neighbour. Returns dead ends in row-major order.

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(grid, start, exit):
    h = len(grid)
    w = len(grid[0])
    ends = []
    for r in range(h):
        for c in range(w):
            if grid[r][c] != '.' or [r, c] in (start, exit):
                continue
            n = 0
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                rr, cc = r + dr, c + dc
                if 0 <= rr < h and 0 <= cc < w and grid[rr][cc] in '.D':
                    n += 1
            if n <= 1:
                ends.append([r, c])
    return ends
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('isolated floor #1', [['#.#', '###'], [1, 0], [1, 0]], []),
  ('regression dead-end degree #1', [['#.#.#', '.#D~~', '..~..', '..D.~'], [1, 4], [2, 0]], [[1, 0], [2, 4]]),
  ('regression dead-end degree #2', [['.~~##.', '##~DD~'], [0, 1], [1, 0]], []),
  ('regression dead-end degree #3', [['~.##.', 'D..#~', '...##'], [0, 3], [0, 1]], []),
  ('regression dead-end degree #4', [['##.#.', '.~#D.', 'D#.~#'], [0, 3], [1, 4]], [[0, 4], [1, 0]]),
  ('door as neighbour #1', [['#D#', '#.#', '###'], [0, 1], [0, 1]], [[1, 1]]),
  ('chasm edge #1', [['.~.', '...'], [1, 1], [1, 1]], [[0, 0], [0, 2]]),
  ('control #1', [['...D#~', '~.###~', '~..D..'], [1, 3], [0, 2]], [[0, 0], [2, 5]])],
 [('isolated floor #1', [['#.#', '###'], [1, 0], [1, 0]], []),
  ('regression dead-end degree #1', [['.~~##.', '##~DD~'], [0, 1], [1, 0]], []),
  ('regression dead-end degree #2', [['~.##.', 'D..#~', '...##'], [0, 3], [0, 1]], []),
  ('regression dead-end degree #3', [['##.#.', '.~#D.', 'D#.~#'], [0, 3], [1, 4]], [[0, 4], [1, 0]]),
  ('regression dead-end degree #4', [['D.', 'DD', '.~', '#.'], [3, 0], [3, 0]], [[2, 0]]),
  ('door as neighbour #1', [['#D#', '#.#', '###'], [0, 1], [0, 1]], [[1, 1]]),
  ('chasm edge #1', [['.~.', '...'], [1, 1], [1, 1]], [[0, 0], [0, 2]]),
  ('control #1', [['...D#~', '~.###~', '~..D..'], [1, 3], [0, 2]], [[0, 0], [2, 5]])],
 [('isolated floor #1', [['#.#', '###'], [1, 0], [1, 0]], []),
  ('regression dead-end degree #1', [['##.#.', '.~#D.', 'D#.~#'], [0, 3], [1, 4]], [[0, 4], [1, 0]]),
  ('regression dead-end degree #2', [['D.', 'DD', '.~', '#.'], [3, 0], [3, 0]], [[2, 0]]),
  ('regression dead-end degree #3',
   [['.D~~.~', '~..#.D', '#~D.#.', '#..~.#', '.#...#'], [1, 5], [0, 5]],
   [[0, 0], [0, 4], [2, 3], [2, 5], [3, 1], [3, 4]]),
  ('regression dead-end degree #4', [['.##', '#..'], [1, 2], [0, 1]], [[1, 1]]),
  ('door as neighbour #1', [['#D#', '#.#', '###'], [0, 1], [0, 1]], [[1, 1]]),
  ('chasm edge #1', [['.~.', '...'], [1, 1], [1, 1]], [[0, 0], [0, 2]]),
  ('control #1', [['...D#~', '~.###~', '~..D..'], [1, 3], [0, 2]], [[0, 0], [2, 5]])],
 [('isolated floor #1', [['#.#', '###'], [1, 0], [1, 0]], []),
  ('regression dead-end degree #1',
   [['.D~~.~', '~..#.D', '#~D.#.', '#..~.#', '.#...#'], [1, 5], [0, 5]],
   [[0, 0], [0, 4], [2, 3], [2, 5], [3, 1], [3, 4]]),
  ('regression dead-end degree #2', [['.##', '#..'], [1, 2], [0, 1]], [[1, 1]]),
  ('regression dead-end degree #3',
   [['.###..', '~#~~..', '....~.', '~D~...', '.#~D~.', '~D...#'], [3, 0], [1, 0]],
   [[2, 0], [4, 5], [5, 4]]),
  ('regression dead-end degree #4',
   [['#D...D', '#D#...', '##.##.', '#.##.#', '#D##.~', 'D.#...'], [2, 5], [5, 3]],
   [[3, 1], [3, 4], [5, 5]]),
  ('door as neighbour #1', [['#D#', '#.#', '###'], [0, 1], [0, 1]], [[1, 1]]),
  ('chasm edge #1', [['.~.', '...'], [1, 1], [1, 1]], [[0, 0], [0, 2]]),
  ('control #1', [['#~.#.', '#...D', 'D.#..', '#....', '##..~'], [3, 0], [3, 3]], [[0, 2], [0, 4]])],
 [('isolated floor #1', [['#.#', '###'], [1, 0], [1, 0]], []),
  ('regression dead-end degree #1',
   [['.###..', '~#~~..', '....~.', '~D~...', '.#~D~.', '~D...#'], [3, 0], [1, 0]],
   [[2, 0], [4, 5], [5, 4]]),
  ('regression dead-end degree #2',
   [['#D...D', '#D#...', '##.##.', '#.##.#', '#D##.~', 'D.#...'], [2, 5], [5, 3]],
   [[3, 1], [3, 4], [5, 5]]),
  ('regression dead-end degree #3', [['#~.~.', '..#~.', '#.D.~', '~#~..'], [1, 4], [1, 0]], [[0, 4], [3, 4]]),
  ('regression dead-end degree #4',
   [['..#.D.', '~~D###', '...##.', '...DD~', 'D~.DD#', 'D..~D~'], [0, 4], [0, 0]],
   [[0, 1], [0, 3], [0, 5]]),
  ('door as neighbour #1', [['#D#', '#.#', '###'], [0, 1], [0, 1]], [[1, 1]]),
  ('chasm edge #1', [['.~.', '...'], [1, 1], [1, 1]], [[0, 0], [0, 2]]),
  ('control #1', [['~D.#D', '#.#~.'], [0, 1], [1, 2]], [[0, 2], [1, 1], [1, 4]])]]
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
isolated floor #1[[0, 1]][]Failed
regression dead-end degree #1[[0, 1], [0, 3], [1, 0], [2, 4]][[1, 0], [2, 4]]Failed
regression dead-end degree #2[[0, 0], [0, 5]][]Failed
regression dead-end degree #3[[0, 4]][]Failed
regression dead-end degree #4[[0, 2], [0, 4], [1, 0], [2, 2]][[0, 4], [1, 0]]Failed
door as neighbour #1[[1, 1]][[1, 1]]Passed
chasm edge #1[[0, 0], [0, 2]][[0, 0], [0, 2]]Passed
control #1[[0, 0], [2, 5]][[0, 0], [2, 5]]Passed

SHA-256 / 448a13ecf7f4f48d87d7a12d96b7dce902d3df789273d1675b6d6432c50a77fc

2 / The unsuccessful fix

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

N = 1
observations = []
def solve(grid, start, exit):
    h = len(grid)
    w = len(grid[0])
    ends = []
    for r in range(h):
        for c in range(w):
            if grid[r][c] != '.' or [r, c] in (start, exit):
                continue
            n = 0
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                rr, cc = r + dr, c + dc
                if 0 <= rr < h and 0 <= cc < w and grid[rr][cc] in '.D':
                    n += 1
            if n == 1 or n == 0 and [r, c] != start:
                ends.append([r, c])
    return ends
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('isolated floor #1', [['#.#', '###'], [1, 0], [1, 0]], []),
  ('regression dead-end degree #1', [['#.#.#', '.#D~~', '..~..', '..D.~'], [1, 4], [2, 0]], [[1, 0], [2, 4]]),
  ('regression dead-end degree #2', [['.~~##.', '##~DD~'], [0, 1], [1, 0]], []),
  ('regression dead-end degree #3', [['~.##.', 'D..#~', '...##'], [0, 3], [0, 1]], []),
  ('regression dead-end degree #4', [['##.#.', '.~#D.', 'D#.~#'], [0, 3], [1, 4]], [[0, 4], [1, 0]]),
  ('door as neighbour #1', [['#D#', '#.#', '###'], [0, 1], [0, 1]], [[1, 1]]),
  ('chasm edge #1', [['.~.', '...'], [1, 1], [1, 1]], [[0, 0], [0, 2]]),
  ('control #1', [['...D#~', '~.###~', '~..D..'], [1, 3], [0, 2]], [[0, 0], [2, 5]])],
 [('isolated floor #1', [['#.#', '###'], [1, 0], [1, 0]], []),
  ('regression dead-end degree #1', [['.~~##.', '##~DD~'], [0, 1], [1, 0]], []),
  ('regression dead-end degree #2', [['~.##.', 'D..#~', '...##'], [0, 3], [0, 1]], []),
  ('regression dead-end degree #3', [['##.#.', '.~#D.', 'D#.~#'], [0, 3], [1, 4]], [[0, 4], [1, 0]]),
  ('regression dead-end degree #4', [['D.', 'DD', '.~', '#.'], [3, 0], [3, 0]], [[2, 0]]),
  ('door as neighbour #1', [['#D#', '#.#', '###'], [0, 1], [0, 1]], [[1, 1]]),
  ('chasm edge #1', [['.~.', '...'], [1, 1], [1, 1]], [[0, 0], [0, 2]]),
  ('control #1', [['...D#~', '~.###~', '~..D..'], [1, 3], [0, 2]], [[0, 0], [2, 5]])],
 [('isolated floor #1', [['#.#', '###'], [1, 0], [1, 0]], []),
  ('regression dead-end degree #1', [['##.#.', '.~#D.', 'D#.~#'], [0, 3], [1, 4]], [[0, 4], [1, 0]]),
  ('regression dead-end degree #2', [['D.', 'DD', '.~', '#.'], [3, 0], [3, 0]], [[2, 0]]),
  ('regression dead-end degree #3',
   [['.D~~.~', '~..#.D', '#~D.#.', '#..~.#', '.#...#'], [1, 5], [0, 5]],
   [[0, 0], [0, 4], [2, 3], [2, 5], [3, 1], [3, 4]]),
  ('regression dead-end degree #4', [['.##', '#..'], [1, 2], [0, 1]], [[1, 1]]),
  ('door as neighbour #1', [['#D#', '#.#', '###'], [0, 1], [0, 1]], [[1, 1]]),
  ('chasm edge #1', [['.~.', '...'], [1, 1], [1, 1]], [[0, 0], [0, 2]]),
  ('control #1', [['...D#~', '~.###~', '~..D..'], [1, 3], [0, 2]], [[0, 0], [2, 5]])],
 [('isolated floor #1', [['#.#', '###'], [1, 0], [1, 0]], []),
  ('regression dead-end degree #1',
   [['.D~~.~', '~..#.D', '#~D.#.', '#..~.#', '.#...#'], [1, 5], [0, 5]],
   [[0, 0], [0, 4], [2, 3], [2, 5], [3, 1], [3, 4]]),
  ('regression dead-end degree #2', [['.##', '#..'], [1, 2], [0, 1]], [[1, 1]]),
  ('regression dead-end degree #3',
   [['.###..', '~#~~..', '....~.', '~D~...', '.#~D~.', '~D...#'], [3, 0], [1, 0]],
   [[2, 0], [4, 5], [5, 4]]),
  ('regression dead-end degree #4',
   [['#D...D', '#D#...', '##.##.', '#.##.#', '#D##.~', 'D.#...'], [2, 5], [5, 3]],
   [[3, 1], [3, 4], [5, 5]]),
  ('door as neighbour #1', [['#D#', '#.#', '###'], [0, 1], [0, 1]], [[1, 1]]),
  ('chasm edge #1', [['.~.', '...'], [1, 1], [1, 1]], [[0, 0], [0, 2]]),
  ('control #1', [['#~.#.', '#...D', 'D.#..', '#....', '##..~'], [3, 0], [3, 3]], [[0, 2], [0, 4]])],
 [('isolated floor #1', [['#.#', '###'], [1, 0], [1, 0]], []),
  ('regression dead-end degree #1',
   [['.###..', '~#~~..', '....~.', '~D~...', '.#~D~.', '~D...#'], [3, 0], [1, 0]],
   [[2, 0], [4, 5], [5, 4]]),
  ('regression dead-end degree #2',
   [['#D...D', '#D#...', '##.##.', '#.##.#', '#D##.~', 'D.#...'], [2, 5], [5, 3]],
   [[3, 1], [3, 4], [5, 5]]),
  ('regression dead-end degree #3', [['#~.~.', '..#~.', '#.D.~', '~#~..'], [1, 4], [1, 0]], [[0, 4], [3, 4]]),
  ('regression dead-end degree #4',
   [['..#.D.', '~~D###', '...##.', '...DD~', 'D~.DD#', 'D..~D~'], [0, 4], [0, 0]],
   [[0, 1], [0, 3], [0, 5]]),
  ('door as neighbour #1', [['#D#', '#.#', '###'], [0, 1], [0, 1]], [[1, 1]]),
  ('chasm edge #1', [['.~.', '...'], [1, 1], [1, 1]], [[0, 0], [0, 2]]),
  ('control #1', [['~D.#D', '#.#~.'], [0, 1], [1, 2]], [[0, 2], [1, 1], [1, 4]])]]
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
isolated floor #1[[0, 1]][]Failed
regression dead-end degree #1[[0, 1], [0, 3], [1, 0], [2, 4]][[1, 0], [2, 4]]Failed
regression dead-end degree #2[[0, 0], [0, 5]][]Failed
regression dead-end degree #3[[0, 4]][]Failed
regression dead-end degree #4[[0, 2], [0, 4], [1, 0], [2, 2]][[0, 4], [1, 0]]Failed
door as neighbour #1[[1, 1]][[1, 1]]Passed
chasm edge #1[[0, 0], [0, 2]][[0, 0], [0, 2]]Passed
control #1[[0, 0], [2, 5]][[0, 0], [2, 5]]Passed

SHA-256 / 35ad3f746bdcda5cf90dab5c9a96a6859ddbf24606877a911261f01121726e43

3 / The verified repair

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

N = 1
observations = []
def solve(grid, start, exit):
    h = len(grid)
    w = len(grid[0])
    ends = []
    for r in range(h):
        for c in range(w):
            if grid[r][c] != '.' or [r, c] in (start, exit):
                continue
            n = 0
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                rr, cc = r + dr, c + dc
                if 0 <= rr < h and 0 <= cc < w and grid[rr][cc] in '.D':
                    n += 1
            if n == 1:
                ends.append([r, c])
    return ends
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('isolated floor #1', [['#.#', '###'], [1, 0], [1, 0]], []),
  ('regression dead-end degree #1', [['#.#.#', '.#D~~', '..~..', '..D.~'], [1, 4], [2, 0]], [[1, 0], [2, 4]]),
  ('regression dead-end degree #2', [['.~~##.', '##~DD~'], [0, 1], [1, 0]], []),
  ('regression dead-end degree #3', [['~.##.', 'D..#~', '...##'], [0, 3], [0, 1]], []),
  ('regression dead-end degree #4', [['##.#.', '.~#D.', 'D#.~#'], [0, 3], [1, 4]], [[0, 4], [1, 0]]),
  ('door as neighbour #1', [['#D#', '#.#', '###'], [0, 1], [0, 1]], [[1, 1]]),
  ('chasm edge #1', [['.~.', '...'], [1, 1], [1, 1]], [[0, 0], [0, 2]]),
  ('control #1', [['...D#~', '~.###~', '~..D..'], [1, 3], [0, 2]], [[0, 0], [2, 5]])],
 [('isolated floor #1', [['#.#', '###'], [1, 0], [1, 0]], []),
  ('regression dead-end degree #1', [['.~~##.', '##~DD~'], [0, 1], [1, 0]], []),
  ('regression dead-end degree #2', [['~.##.', 'D..#~', '...##'], [0, 3], [0, 1]], []),
  ('regression dead-end degree #3', [['##.#.', '.~#D.', 'D#.~#'], [0, 3], [1, 4]], [[0, 4], [1, 0]]),
  ('regression dead-end degree #4', [['D.', 'DD', '.~', '#.'], [3, 0], [3, 0]], [[2, 0]]),
  ('door as neighbour #1', [['#D#', '#.#', '###'], [0, 1], [0, 1]], [[1, 1]]),
  ('chasm edge #1', [['.~.', '...'], [1, 1], [1, 1]], [[0, 0], [0, 2]]),
  ('control #1', [['...D#~', '~.###~', '~..D..'], [1, 3], [0, 2]], [[0, 0], [2, 5]])],
 [('isolated floor #1', [['#.#', '###'], [1, 0], [1, 0]], []),
  ('regression dead-end degree #1', [['##.#.', '.~#D.', 'D#.~#'], [0, 3], [1, 4]], [[0, 4], [1, 0]]),
  ('regression dead-end degree #2', [['D.', 'DD', '.~', '#.'], [3, 0], [3, 0]], [[2, 0]]),
  ('regression dead-end degree #3',
   [['.D~~.~', '~..#.D', '#~D.#.', '#..~.#', '.#...#'], [1, 5], [0, 5]],
   [[0, 0], [0, 4], [2, 3], [2, 5], [3, 1], [3, 4]]),
  ('regression dead-end degree #4', [['.##', '#..'], [1, 2], [0, 1]], [[1, 1]]),
  ('door as neighbour #1', [['#D#', '#.#', '###'], [0, 1], [0, 1]], [[1, 1]]),
  ('chasm edge #1', [['.~.', '...'], [1, 1], [1, 1]], [[0, 0], [0, 2]]),
  ('control #1', [['...D#~', '~.###~', '~..D..'], [1, 3], [0, 2]], [[0, 0], [2, 5]])],
 [('isolated floor #1', [['#.#', '###'], [1, 0], [1, 0]], []),
  ('regression dead-end degree #1',
   [['.D~~.~', '~..#.D', '#~D.#.', '#..~.#', '.#...#'], [1, 5], [0, 5]],
   [[0, 0], [0, 4], [2, 3], [2, 5], [3, 1], [3, 4]]),
  ('regression dead-end degree #2', [['.##', '#..'], [1, 2], [0, 1]], [[1, 1]]),
  ('regression dead-end degree #3',
   [['.###..', '~#~~..', '....~.', '~D~...', '.#~D~.', '~D...#'], [3, 0], [1, 0]],
   [[2, 0], [4, 5], [5, 4]]),
  ('regression dead-end degree #4',
   [['#D...D', '#D#...', '##.##.', '#.##.#', '#D##.~', 'D.#...'], [2, 5], [5, 3]],
   [[3, 1], [3, 4], [5, 5]]),
  ('door as neighbour #1', [['#D#', '#.#', '###'], [0, 1], [0, 1]], [[1, 1]]),
  ('chasm edge #1', [['.~.', '...'], [1, 1], [1, 1]], [[0, 0], [0, 2]]),
  ('control #1', [['#~.#.', '#...D', 'D.#..', '#....', '##..~'], [3, 0], [3, 3]], [[0, 2], [0, 4]])],
 [('isolated floor #1', [['#.#', '###'], [1, 0], [1, 0]], []),
  ('regression dead-end degree #1',
   [['.###..', '~#~~..', '....~.', '~D~...', '.#~D~.', '~D...#'], [3, 0], [1, 0]],
   [[2, 0], [4, 5], [5, 4]]),
  ('regression dead-end degree #2',
   [['#D...D', '#D#...', '##.##.', '#.##.#', '#D##.~', 'D.#...'], [2, 5], [5, 3]],
   [[3, 1], [3, 4], [5, 5]]),
  ('regression dead-end degree #3', [['#~.~.', '..#~.', '#.D.~', '~#~..'], [1, 4], [1, 0]], [[0, 4], [3, 4]]),
  ('regression dead-end degree #4',
   [['..#.D.', '~~D###', '...##.', '...DD~', 'D~.DD#', 'D..~D~'], [0, 4], [0, 0]],
   [[0, 1], [0, 3], [0, 5]]),
  ('door as neighbour #1', [['#D#', '#.#', '###'], [0, 1], [0, 1]], [[1, 1]]),
  ('chasm edge #1', [['.~.', '...'], [1, 1], [1, 1]], [[0, 0], [0, 2]]),
  ('control #1', [['~D.#D', '#.#~.'], [0, 1], [1, 2]], [[0, 2], [1, 1], [1, 4]])]]
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
isolated floor #1[][]Passed
regression dead-end degree #1[[1, 0], [2, 4]][[1, 0], [2, 4]]Passed
regression dead-end degree #2[][]Passed
regression dead-end degree #3[][]Passed
regression dead-end degree #4[[0, 4], [1, 0]][[0, 4], [1, 0]]Passed
door as neighbour #1[[1, 1]][[1, 1]]Passed
chasm edge #1[[0, 0], [0, 2]][[0, 0], [0, 2]]Passed
control #1[[0, 0], [2, 5]][[0, 0], [2, 5]]Passed

SHA-256 / 7fe35dcfc4b059084ae550bf589bf281ff654898c972ec161a535071c49a7bed

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

Case digest / f1f124bdbb26c6d33d7d8e4136eed5266c2396278b883b49f755e1c48a59d578