FA-86601 / Procedural level generation constraints / Open access
Treasure dead-end finder: Doors and chasms become treasure spots · case 01
Treasure spawns on doors or over chasms.
ROOT CAUSE
Only walls are excluded as candidates.
VERIFIED REPAIR
Restore `grid[r][c] != '.'` at the candidate tile step.
Unsuccessful approach: Still admits doors as treasure cells.
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 = [[('regression candidate tile #1', [['...D#~', '~.###~', '~..D..'], [1, 3], [0, 2]], [[0, 0], [2, 5]]),
('regression candidate tile #2',
[['#~.#.', '#...D', 'D.#..', '#....', '##..~'], [3, 0], [3, 3]],
[[0, 2], [0, 4]]),
('regression candidate tile #3', [['~D.#D', '#.#~.'], [0, 1], [1, 2]], [[0, 2], [1, 1], [1, 4]]),
('regression candidate tile #4', [['.~~##.', '##~DD~'], [0, 1], [1, 0]], []),
('door as neighbour #1', [['#D#', '#.#', '###'], [0, 1], [0, 1]], [[1, 1]]),
('chasm edge #1', [['.~.', '...'], [1, 1], [1, 1]], [[0, 0], [0, 2]]),
('isolated floor #1', [['#.#', '###'], [1, 0], [1, 0]], []),
('control #1', [['#.#.#', '.#D~~', '..~..', '..D.~'], [1, 4], [2, 0]], [[1, 0], [2, 4]])],
[('regression candidate tile #1', [['~D.#D', '#.#~.'], [0, 1], [1, 2]], [[0, 2], [1, 1], [1, 4]]),
('regression candidate tile #2', [['.~~##.', '##~DD~'], [0, 1], [1, 0]], []),
('regression candidate tile #3', [['##.#.', '.~#D.', 'D#.~#'], [0, 3], [1, 4]], [[0, 4], [1, 0]]),
('regression candidate tile #4',
[['.###..', '~#~~..', '....~.', '~D~...', '.#~D~.', '~D...#'], [3, 0], [1, 0]],
[[2, 0], [4, 5], [5, 4]]),
('isolated floor #1', [['#.#', '###'], [1, 0], [1, 0]], []),
('door as neighbour #1', [['#D#', '#.#', '###'], [0, 1], [0, 1]], [[1, 1]]),
('control #1', [['#.#.#', '.#D~~', '..~..', '..D.~'], [1, 4], [2, 0]], [[1, 0], [2, 4]]),
('control #2', [['D.', 'DD', '.~', '#.'], [3, 0], [3, 0]], [[2, 0]])],
[('fault site candidate tile #1', [['...#~.', 'D.~~.D'], [1, 1], [1, 1]], [[0, 2], [0, 5], [1, 4]]),
('fault site candidate tile #2',
[['..#...', '~..##.', '##~##.'], [0, 0], [0, 5]],
[[0, 3], [1, 2], [2, 5]]),
('regression candidate tile #1', [['##.#.', '.~#D.', 'D#.~#'], [0, 3], [1, 4]], [[0, 4], [1, 0]]),
('regression candidate tile #2',
[['.###..', '~#~~..', '....~.', '~D~...', '.#~D~.', '~D...#'], [3, 0], [1, 0]],
[[2, 0], [4, 5], [5, 4]]),
('chasm edge #1', [['.~.', '...'], [1, 1], [1, 1]], [[0, 0], [0, 2]]),
('isolated floor #1', [['#.#', '###'], [1, 0], [1, 0]], []),
('control #1', [['D.', 'DD', '.~', '#.'], [3, 0], [3, 0]], [[2, 0]]),
('control #2', [['.##', '#..'], [1, 2], [0, 1]], [[1, 1]])],
[('fault site candidate tile #1', [['~.##.', 'D..#~', '...##'], [0, 3], [0, 1]], []),
('regression candidate tile #1', [['##.#.', '.~#D.', 'D#.~#'], [0, 3], [1, 4]], [[0, 4], [1, 0]]),
('regression candidate tile #2',
[['..###', '..~#.', '#...D', '..##D', '.#.#D'], [4, 2], [0, 4]],
[[1, 4], [4, 0]]),
('regression candidate tile #3',
[['.~.#', '...#', '.#.D', '#~D~', '#~..'], [0, 1], [1, 2]],
[[0, 0], [0, 2], [2, 0], [4, 3]]),
('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], [2, 0]], [[0, 0], [1, 1]]),
('control #2', [['DD', '~.', '#.', 'D~'], [3, 0], [0, 0]], [[2, 1]])],
[('fault site candidate tile #1',
[['.D~~.~', '~..#.D', '#~D.#.', '#..~.#', '.#...#'], [1, 5], [0, 5]],
[[0, 0], [0, 4], [2, 3], [2, 5], [3, 1], [3, 4]]),
('fault site candidate tile #2', [['~#~', '..#'], [1, 2], [0, 2]], [[1, 0], [1, 1]]),
('regression candidate tile #1',
[['#D...D', '#D#...', '##.##.', '#.##.#', '#D##.~', 'D.#...'], [2, 5], [5, 3]],
[[3, 1], [3, 4], [5, 5]]),
('regression candidate tile #2', [['.D#.D', 'D...#', '~.~.D', '.D#.#'], [1, 2], [3, 4]], [[3, 0], [3, 3]]),
('isolated floor #1', [['#.#', '###'], [1, 0], [1, 0]], []),
('door as neighbour #1', [['#D#', '#.#', '###'], [0, 1], [0, 1]], [[1, 1]]),
('control #1', [['DDD.', '...#'], [1, 2], [0, 1]], [[0, 3]]),
('control #2', [['.#...~', '.#.D~D', '....##'], [1, 0], [0, 0]], [[0, 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 fixture | Actual | Expected | Outcome |
|---|---|---|---|
| regression candidate tile #1 | [[0, 0], [0, 3], [1, 5], [2, 0], [2, 5]] | [[0, 0], [2, 5]] | Failed |
| regression candidate tile #2 | [[0, 2], [0, 4], [2, 0]] | [[0, 2], [0, 4]] | Failed |
| regression candidate tile #3 | [[0, 0], [0, 2], [0, 4], [1, 1], [1, 3], [1, 4]] | [[0, 2], [1, 1], [1, 4]] | Failed |
| regression candidate tile #4 | [[1, 2], [1, 3], [1, 4]] | [] | Failed |
| door as neighbour #1 | [[1, 1]] | [[1, 1]] | Passed |
| chasm edge #1 | [[0, 0], [0, 2]] | [[0, 0], [0, 2]] | Passed |
| isolated floor #1 | [] | [] | Passed |
| control #1 | [[1, 0], [2, 4]] | [[1, 0], [2, 4]] | Passed |
SHA-256 / ab3dc389a49a5b4a07394131f712f0ee4bd7295b3decbe8a06e0eac92dfab48d
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] not in '.D' 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 = [[('regression candidate tile #1', [['...D#~', '~.###~', '~..D..'], [1, 3], [0, 2]], [[0, 0], [2, 5]]),
('regression candidate tile #2',
[['#~.#.', '#...D', 'D.#..', '#....', '##..~'], [3, 0], [3, 3]],
[[0, 2], [0, 4]]),
('regression candidate tile #3', [['~D.#D', '#.#~.'], [0, 1], [1, 2]], [[0, 2], [1, 1], [1, 4]]),
('regression candidate tile #4', [['.~~##.', '##~DD~'], [0, 1], [1, 0]], []),
('door as neighbour #1', [['#D#', '#.#', '###'], [0, 1], [0, 1]], [[1, 1]]),
('chasm edge #1', [['.~.', '...'], [1, 1], [1, 1]], [[0, 0], [0, 2]]),
('isolated floor #1', [['#.#', '###'], [1, 0], [1, 0]], []),
('control #1', [['#.#.#', '.#D~~', '..~..', '..D.~'], [1, 4], [2, 0]], [[1, 0], [2, 4]])],
[('regression candidate tile #1', [['~D.#D', '#.#~.'], [0, 1], [1, 2]], [[0, 2], [1, 1], [1, 4]]),
('regression candidate tile #2', [['.~~##.', '##~DD~'], [0, 1], [1, 0]], []),
('regression candidate tile #3', [['##.#.', '.~#D.', 'D#.~#'], [0, 3], [1, 4]], [[0, 4], [1, 0]]),
('regression candidate tile #4',
[['.###..', '~#~~..', '....~.', '~D~...', '.#~D~.', '~D...#'], [3, 0], [1, 0]],
[[2, 0], [4, 5], [5, 4]]),
('isolated floor #1', [['#.#', '###'], [1, 0], [1, 0]], []),
('door as neighbour #1', [['#D#', '#.#', '###'], [0, 1], [0, 1]], [[1, 1]]),
('control #1', [['#.#.#', '.#D~~', '..~..', '..D.~'], [1, 4], [2, 0]], [[1, 0], [2, 4]]),
('control #2', [['D.', 'DD', '.~', '#.'], [3, 0], [3, 0]], [[2, 0]])],
[('fault site candidate tile #1', [['...#~.', 'D.~~.D'], [1, 1], [1, 1]], [[0, 2], [0, 5], [1, 4]]),
('fault site candidate tile #2',
[['..#...', '~..##.', '##~##.'], [0, 0], [0, 5]],
[[0, 3], [1, 2], [2, 5]]),
('regression candidate tile #1', [['##.#.', '.~#D.', 'D#.~#'], [0, 3], [1, 4]], [[0, 4], [1, 0]]),
('regression candidate tile #2',
[['.###..', '~#~~..', '....~.', '~D~...', '.#~D~.', '~D...#'], [3, 0], [1, 0]],
[[2, 0], [4, 5], [5, 4]]),
('chasm edge #1', [['.~.', '...'], [1, 1], [1, 1]], [[0, 0], [0, 2]]),
('isolated floor #1', [['#.#', '###'], [1, 0], [1, 0]], []),
('control #1', [['D.', 'DD', '.~', '#.'], [3, 0], [3, 0]], [[2, 0]]),
('control #2', [['.##', '#..'], [1, 2], [0, 1]], [[1, 1]])],
[('fault site candidate tile #1', [['~.##.', 'D..#~', '...##'], [0, 3], [0, 1]], []),
('regression candidate tile #1', [['##.#.', '.~#D.', 'D#.~#'], [0, 3], [1, 4]], [[0, 4], [1, 0]]),
('regression candidate tile #2',
[['..###', '..~#.', '#...D', '..##D', '.#.#D'], [4, 2], [0, 4]],
[[1, 4], [4, 0]]),
('regression candidate tile #3',
[['.~.#', '...#', '.#.D', '#~D~', '#~..'], [0, 1], [1, 2]],
[[0, 0], [0, 2], [2, 0], [4, 3]]),
('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], [2, 0]], [[0, 0], [1, 1]]),
('control #2', [['DD', '~.', '#.', 'D~'], [3, 0], [0, 0]], [[2, 1]])],
[('fault site candidate tile #1',
[['.D~~.~', '~..#.D', '#~D.#.', '#..~.#', '.#...#'], [1, 5], [0, 5]],
[[0, 0], [0, 4], [2, 3], [2, 5], [3, 1], [3, 4]]),
('fault site candidate tile #2', [['~#~', '..#'], [1, 2], [0, 2]], [[1, 0], [1, 1]]),
('regression candidate tile #1',
[['#D...D', '#D#...', '##.##.', '#.##.#', '#D##.~', 'D.#...'], [2, 5], [5, 3]],
[[3, 1], [3, 4], [5, 5]]),
('regression candidate tile #2', [['.D#.D', 'D...#', '~.~.D', '.D#.#'], [1, 2], [3, 4]], [[3, 0], [3, 3]]),
('isolated floor #1', [['#.#', '###'], [1, 0], [1, 0]], []),
('door as neighbour #1', [['#D#', '#.#', '###'], [0, 1], [0, 1]], [[1, 1]]),
('control #1', [['DDD.', '...#'], [1, 2], [0, 1]], [[0, 3]]),
('control #2', [['.#...~', '.#.D~D', '....##'], [1, 0], [0, 0]], [[0, 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 fixture | Actual | Expected | Outcome |
|---|---|---|---|
| regression candidate tile #1 | [[0, 0], [0, 3], [2, 5]] | [[0, 0], [2, 5]] | Failed |
| regression candidate tile #2 | [[0, 2], [0, 4], [2, 0]] | [[0, 2], [0, 4]] | Failed |
| regression candidate tile #3 | [[0, 2], [0, 4], [1, 1], [1, 4]] | [[0, 2], [1, 1], [1, 4]] | Failed |
| regression candidate tile #4 | [[1, 3], [1, 4]] | [] | Failed |
| door as neighbour #1 | [[1, 1]] | [[1, 1]] | Passed |
| chasm edge #1 | [[0, 0], [0, 2]] | [[0, 0], [0, 2]] | Passed |
| isolated floor #1 | [] | [] | Passed |
| control #1 | [[1, 0], [2, 4]] | [[1, 0], [2, 4]] | Passed |
SHA-256 / c8bef56f614eade5e2c51799ab0214f748245a1152a2c1b53251e5284f2ba00e
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 = [[('regression candidate tile #1', [['...D#~', '~.###~', '~..D..'], [1, 3], [0, 2]], [[0, 0], [2, 5]]),
('regression candidate tile #2',
[['#~.#.', '#...D', 'D.#..', '#....', '##..~'], [3, 0], [3, 3]],
[[0, 2], [0, 4]]),
('regression candidate tile #3', [['~D.#D', '#.#~.'], [0, 1], [1, 2]], [[0, 2], [1, 1], [1, 4]]),
('regression candidate tile #4', [['.~~##.', '##~DD~'], [0, 1], [1, 0]], []),
('door as neighbour #1', [['#D#', '#.#', '###'], [0, 1], [0, 1]], [[1, 1]]),
('chasm edge #1', [['.~.', '...'], [1, 1], [1, 1]], [[0, 0], [0, 2]]),
('isolated floor #1', [['#.#', '###'], [1, 0], [1, 0]], []),
('control #1', [['#.#.#', '.#D~~', '..~..', '..D.~'], [1, 4], [2, 0]], [[1, 0], [2, 4]])],
[('regression candidate tile #1', [['~D.#D', '#.#~.'], [0, 1], [1, 2]], [[0, 2], [1, 1], [1, 4]]),
('regression candidate tile #2', [['.~~##.', '##~DD~'], [0, 1], [1, 0]], []),
('regression candidate tile #3', [['##.#.', '.~#D.', 'D#.~#'], [0, 3], [1, 4]], [[0, 4], [1, 0]]),
('regression candidate tile #4',
[['.###..', '~#~~..', '....~.', '~D~...', '.#~D~.', '~D...#'], [3, 0], [1, 0]],
[[2, 0], [4, 5], [5, 4]]),
('isolated floor #1', [['#.#', '###'], [1, 0], [1, 0]], []),
('door as neighbour #1', [['#D#', '#.#', '###'], [0, 1], [0, 1]], [[1, 1]]),
('control #1', [['#.#.#', '.#D~~', '..~..', '..D.~'], [1, 4], [2, 0]], [[1, 0], [2, 4]]),
('control #2', [['D.', 'DD', '.~', '#.'], [3, 0], [3, 0]], [[2, 0]])],
[('fault site candidate tile #1', [['...#~.', 'D.~~.D'], [1, 1], [1, 1]], [[0, 2], [0, 5], [1, 4]]),
('fault site candidate tile #2',
[['..#...', '~..##.', '##~##.'], [0, 0], [0, 5]],
[[0, 3], [1, 2], [2, 5]]),
('regression candidate tile #1', [['##.#.', '.~#D.', 'D#.~#'], [0, 3], [1, 4]], [[0, 4], [1, 0]]),
('regression candidate tile #2',
[['.###..', '~#~~..', '....~.', '~D~...', '.#~D~.', '~D...#'], [3, 0], [1, 0]],
[[2, 0], [4, 5], [5, 4]]),
('chasm edge #1', [['.~.', '...'], [1, 1], [1, 1]], [[0, 0], [0, 2]]),
('isolated floor #1', [['#.#', '###'], [1, 0], [1, 0]], []),
('control #1', [['D.', 'DD', '.~', '#.'], [3, 0], [3, 0]], [[2, 0]]),
('control #2', [['.##', '#..'], [1, 2], [0, 1]], [[1, 1]])],
[('fault site candidate tile #1', [['~.##.', 'D..#~', '...##'], [0, 3], [0, 1]], []),
('regression candidate tile #1', [['##.#.', '.~#D.', 'D#.~#'], [0, 3], [1, 4]], [[0, 4], [1, 0]]),
('regression candidate tile #2',
[['..###', '..~#.', '#...D', '..##D', '.#.#D'], [4, 2], [0, 4]],
[[1, 4], [4, 0]]),
('regression candidate tile #3',
[['.~.#', '...#', '.#.D', '#~D~', '#~..'], [0, 1], [1, 2]],
[[0, 0], [0, 2], [2, 0], [4, 3]]),
('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], [2, 0]], [[0, 0], [1, 1]]),
('control #2', [['DD', '~.', '#.', 'D~'], [3, 0], [0, 0]], [[2, 1]])],
[('fault site candidate tile #1',
[['.D~~.~', '~..#.D', '#~D.#.', '#..~.#', '.#...#'], [1, 5], [0, 5]],
[[0, 0], [0, 4], [2, 3], [2, 5], [3, 1], [3, 4]]),
('fault site candidate tile #2', [['~#~', '..#'], [1, 2], [0, 2]], [[1, 0], [1, 1]]),
('regression candidate tile #1',
[['#D...D', '#D#...', '##.##.', '#.##.#', '#D##.~', 'D.#...'], [2, 5], [5, 3]],
[[3, 1], [3, 4], [5, 5]]),
('regression candidate tile #2', [['.D#.D', 'D...#', '~.~.D', '.D#.#'], [1, 2], [3, 4]], [[3, 0], [3, 3]]),
('isolated floor #1', [['#.#', '###'], [1, 0], [1, 0]], []),
('door as neighbour #1', [['#D#', '#.#', '###'], [0, 1], [0, 1]], [[1, 1]]),
('control #1', [['DDD.', '...#'], [1, 2], [0, 1]], [[0, 3]]),
('control #2', [['.#...~', '.#.D~D', '....##'], [1, 0], [0, 0]], [[0, 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 fixture | Actual | Expected | Outcome |
|---|---|---|---|
| regression candidate tile #1 | [[0, 0], [2, 5]] | [[0, 0], [2, 5]] | Passed |
| regression candidate tile #2 | [[0, 2], [0, 4]] | [[0, 2], [0, 4]] | Passed |
| regression candidate tile #3 | [[0, 2], [1, 1], [1, 4]] | [[0, 2], [1, 1], [1, 4]] | Passed |
| regression candidate tile #4 | [] | [] | Passed |
| door as neighbour #1 | [[1, 1]] | [[1, 1]] | Passed |
| chasm edge #1 | [[0, 0], [0, 2]] | [[0, 0], [0, 2]] | Passed |
| isolated floor #1 | [] | [] | Passed |
| control #1 | [[1, 0], [2, 4]] | [[1, 0], [2, 4]] | Passed |
SHA-256 / 478172aeafdaf93f17182129a6d8bacb07e1ac32c276799e9f88a0dd71955de5
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.126716+00:00.
Case digest / 2fe569e77b0b146e81e9b6645c6ca3332cdf95d5e76732a182fe1a9eccc376b9