FA-86606 / Procedural level generation constraints / Open access
Treasure dead-end finder: Chasms count as exits · case 01
Cells beside a chasm are not recognized as dead ends.
ROOT CAUSE
Any non-wall neighbour counts as walkable, including chasms.
VERIFIED REPAIR
Restore `grid[rr][cc] in '.D'` at the walkable neighbour step.
Unsuccessful approach: Excluding doors hides dead ends that lead into a doorway.
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] != '#':
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 = [[('chasm edge #1', [['.~.', '...'], [1, 1], [1, 1]], [[0, 0], [0, 2]]),
('door as neighbour #1', [['#D#', '#.#', '###'], [0, 1], [0, 1]], [[1, 1]]),
('regression walkable neighbour #1',
[['#.#.#', '.#D~~', '..~..', '..D.~'], [1, 4], [2, 0]],
[[1, 0], [2, 4]]),
('regression walkable neighbour #2', [['...D#~', '~.###~', '~..D..'], [1, 3], [0, 2]], [[0, 0], [2, 5]]),
('regression walkable neighbour #3',
[['#~.#.', '#...D', 'D.#..', '#....', '##..~'], [3, 0], [3, 3]],
[[0, 2], [0, 4]]),
('regression walkable neighbour #4', [['~D.#D', '#.#~.'], [0, 1], [1, 2]], [[0, 2], [1, 1], [1, 4]]),
('isolated floor #1', [['#.#', '###'], [1, 0], [1, 0]], []),
('control #1', [['.##', '#..'], [1, 2], [0, 1]], [[1, 1]])],
[('chasm edge #1', [['.~.', '...'], [1, 1], [1, 1]], [[0, 0], [0, 2]]),
('door as neighbour #1', [['#D#', '#.#', '###'], [0, 1], [0, 1]], [[1, 1]]),
('regression walkable neighbour #1', [['...D#~', '~.###~', '~..D..'], [1, 3], [0, 2]], [[0, 0], [2, 5]]),
('regression walkable neighbour #2',
[['#~.#.', '#...D', 'D.#..', '#....', '##..~'], [3, 0], [3, 3]],
[[0, 2], [0, 4]]),
('regression walkable neighbour #3', [['~D.#D', '#.#~.'], [0, 1], [1, 2]], [[0, 2], [1, 1], [1, 4]]),
('regression walkable neighbour #4', [['...#~.', 'D.~~.D'], [1, 1], [1, 1]], [[0, 2], [0, 5], [1, 4]]),
('isolated floor #1', [['#.#', '###'], [1, 0], [1, 0]], []),
('control #1', [['.##', '#..'], [1, 2], [0, 1]], [[1, 1]])],
[('chasm edge #1', [['.~.', '...'], [1, 1], [1, 1]], [[0, 0], [0, 2]]),
('door as neighbour #1', [['#D#', '#.#', '###'], [0, 1], [0, 1]], [[1, 1]]),
('regression walkable neighbour #1', [['~D.#D', '#.#~.'], [0, 1], [1, 2]], [[0, 2], [1, 1], [1, 4]]),
('fault site walkable neighbour #1', [['.~~##.', '##~DD~'], [0, 1], [1, 0]], []),
('regression walkable neighbour #2', [['...#~.', 'D.~~.D'], [1, 1], [1, 1]], [[0, 2], [0, 5], [1, 4]]),
('regression walkable neighbour #3', [['~.##.', 'D..#~', '...##'], [0, 3], [0, 1]], []),
('isolated floor #1', [['#.#', '###'], [1, 0], [1, 0]], []),
('control #1', [['#.', '..', '##', '##', '##'], [0, 0], [1, 0]], [[0, 1]])],
[('chasm edge #1', [['.~.', '...'], [1, 1], [1, 1]], [[0, 0], [0, 2]]),
('door as neighbour #1', [['#D#', '#.#', '###'], [0, 1], [0, 1]], [[1, 1]]),
('regression walkable neighbour #1', [['...#~.', 'D.~~.D'], [1, 1], [1, 1]], [[0, 2], [0, 5], [1, 4]]),
('fault site walkable neighbour #1',
[['..#...', '~..##.', '##~##.'], [0, 0], [0, 5]],
[[0, 3], [1, 2], [2, 5]]),
('regression walkable neighbour #2', [['~.##.', 'D..#~', '...##'], [0, 3], [0, 1]], []),
('regression walkable neighbour #3', [['##.#.', '.~#D.', 'D#.~#'], [0, 3], [1, 4]], [[0, 4], [1, 0]]),
('isolated floor #1', [['#.#', '###'], [1, 0], [1, 0]], []),
('control #1', [['...', '..#'], [0, 1], [0, 0]], [[0, 2]])],
[('chasm edge #1', [['.~.', '...'], [1, 1], [1, 1]], [[0, 0], [0, 2]]),
('door as neighbour #1', [['#D#', '#.#', '###'], [0, 1], [0, 1]], [[1, 1]]),
('regression walkable neighbour #1', [['~.##.', 'D..#~', '...##'], [0, 3], [0, 1]], []),
('regression walkable neighbour #2', [['##.#.', '.~#D.', 'D#.~#'], [0, 3], [1, 4]], [[0, 4], [1, 0]]),
('regression walkable neighbour #3', [['D.', 'DD', '.~', '#.'], [3, 0], [3, 0]], [[2, 0]]),
('regression walkable neighbour #4',
[['.D~~.~', '~..#.D', '#~D.#.', '#..~.#', '.#...#'], [1, 5], [0, 5]],
[[0, 0], [0, 4], [2, 3], [2, 5], [3, 1], [3, 4]]),
('isolated floor #1', [['#.#', '###'], [1, 0], [1, 0]], []),
('control #1', [['..', '.#'], [1, 1], [1, 0]], [[0, 1]])]]
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 |
|---|---|---|---|
| chasm edge #1 | [] | [[0, 0], [0, 2]] | Failed |
| door as neighbour #1 | [[1, 1]] | [[1, 1]] | Passed |
| regression walkable neighbour #1 | [[0, 3], [1, 0]] | [[1, 0], [2, 4]] | Failed |
| regression walkable neighbour #2 | [] | [[0, 0], [2, 5]] | Failed |
| regression walkable neighbour #3 | [[0, 4]] | [[0, 2], [0, 4]] | Failed |
| regression walkable neighbour #4 | [[0, 2], [1, 1]] | [[0, 2], [1, 1], [1, 4]] | Failed |
| isolated floor #1 | [] | [] | Passed |
| control #1 | [[1, 1]] | [[1, 1]] | Passed |
SHA-256 / cad9c05d902cdf6a73f14de7bbc92fa69654092add686ee0a621424f8ef267d7
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] == '.':
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 = [[('chasm edge #1', [['.~.', '...'], [1, 1], [1, 1]], [[0, 0], [0, 2]]),
('door as neighbour #1', [['#D#', '#.#', '###'], [0, 1], [0, 1]], [[1, 1]]),
('regression walkable neighbour #1',
[['#.#.#', '.#D~~', '..~..', '..D.~'], [1, 4], [2, 0]],
[[1, 0], [2, 4]]),
('regression walkable neighbour #2', [['...D#~', '~.###~', '~..D..'], [1, 3], [0, 2]], [[0, 0], [2, 5]]),
('regression walkable neighbour #3',
[['#~.#.', '#...D', 'D.#..', '#....', '##..~'], [3, 0], [3, 3]],
[[0, 2], [0, 4]]),
('regression walkable neighbour #4', [['~D.#D', '#.#~.'], [0, 1], [1, 2]], [[0, 2], [1, 1], [1, 4]]),
('isolated floor #1', [['#.#', '###'], [1, 0], [1, 0]], []),
('control #1', [['.##', '#..'], [1, 2], [0, 1]], [[1, 1]])],
[('chasm edge #1', [['.~.', '...'], [1, 1], [1, 1]], [[0, 0], [0, 2]]),
('door as neighbour #1', [['#D#', '#.#', '###'], [0, 1], [0, 1]], [[1, 1]]),
('regression walkable neighbour #1', [['...D#~', '~.###~', '~..D..'], [1, 3], [0, 2]], [[0, 0], [2, 5]]),
('regression walkable neighbour #2',
[['#~.#.', '#...D', 'D.#..', '#....', '##..~'], [3, 0], [3, 3]],
[[0, 2], [0, 4]]),
('regression walkable neighbour #3', [['~D.#D', '#.#~.'], [0, 1], [1, 2]], [[0, 2], [1, 1], [1, 4]]),
('regression walkable neighbour #4', [['...#~.', 'D.~~.D'], [1, 1], [1, 1]], [[0, 2], [0, 5], [1, 4]]),
('isolated floor #1', [['#.#', '###'], [1, 0], [1, 0]], []),
('control #1', [['.##', '#..'], [1, 2], [0, 1]], [[1, 1]])],
[('chasm edge #1', [['.~.', '...'], [1, 1], [1, 1]], [[0, 0], [0, 2]]),
('door as neighbour #1', [['#D#', '#.#', '###'], [0, 1], [0, 1]], [[1, 1]]),
('regression walkable neighbour #1', [['~D.#D', '#.#~.'], [0, 1], [1, 2]], [[0, 2], [1, 1], [1, 4]]),
('fault site walkable neighbour #1', [['.~~##.', '##~DD~'], [0, 1], [1, 0]], []),
('regression walkable neighbour #2', [['...#~.', 'D.~~.D'], [1, 1], [1, 1]], [[0, 2], [0, 5], [1, 4]]),
('regression walkable neighbour #3', [['~.##.', 'D..#~', '...##'], [0, 3], [0, 1]], []),
('isolated floor #1', [['#.#', '###'], [1, 0], [1, 0]], []),
('control #1', [['#.', '..', '##', '##', '##'], [0, 0], [1, 0]], [[0, 1]])],
[('chasm edge #1', [['.~.', '...'], [1, 1], [1, 1]], [[0, 0], [0, 2]]),
('door as neighbour #1', [['#D#', '#.#', '###'], [0, 1], [0, 1]], [[1, 1]]),
('regression walkable neighbour #1', [['...#~.', 'D.~~.D'], [1, 1], [1, 1]], [[0, 2], [0, 5], [1, 4]]),
('fault site walkable neighbour #1',
[['..#...', '~..##.', '##~##.'], [0, 0], [0, 5]],
[[0, 3], [1, 2], [2, 5]]),
('regression walkable neighbour #2', [['~.##.', 'D..#~', '...##'], [0, 3], [0, 1]], []),
('regression walkable neighbour #3', [['##.#.', '.~#D.', 'D#.~#'], [0, 3], [1, 4]], [[0, 4], [1, 0]]),
('isolated floor #1', [['#.#', '###'], [1, 0], [1, 0]], []),
('control #1', [['...', '..#'], [0, 1], [0, 0]], [[0, 2]])],
[('chasm edge #1', [['.~.', '...'], [1, 1], [1, 1]], [[0, 0], [0, 2]]),
('door as neighbour #1', [['#D#', '#.#', '###'], [0, 1], [0, 1]], [[1, 1]]),
('regression walkable neighbour #1', [['~.##.', 'D..#~', '...##'], [0, 3], [0, 1]], []),
('regression walkable neighbour #2', [['##.#.', '.~#D.', 'D#.~#'], [0, 3], [1, 4]], [[0, 4], [1, 0]]),
('regression walkable neighbour #3', [['D.', 'DD', '.~', '#.'], [3, 0], [3, 0]], [[2, 0]]),
('regression walkable neighbour #4',
[['.D~~.~', '~..#.D', '#~D.#.', '#..~.#', '.#...#'], [1, 5], [0, 5]],
[[0, 0], [0, 4], [2, 3], [2, 5], [3, 1], [3, 4]]),
('isolated floor #1', [['#.#', '###'], [1, 0], [1, 0]], []),
('control #1', [['..', '.#'], [1, 1], [1, 0]], [[0, 1]])]]
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 |
|---|---|---|---|
| chasm edge #1 | [[0, 0], [0, 2]] | [[0, 0], [0, 2]] | Passed |
| door as neighbour #1 | [] | [[1, 1]] | Failed |
| regression walkable neighbour #1 | [[1, 0], [2, 4], [3, 3]] | [[1, 0], [2, 4]] | Failed |
| regression walkable neighbour #2 | [[0, 0], [2, 2], [2, 4], [2, 5]] | [[0, 0], [2, 5]] | Failed |
| regression walkable neighbour #3 | [[0, 2]] | [[0, 2], [0, 4]] | Failed |
| regression walkable neighbour #4 | [] | [[0, 2], [1, 1], [1, 4]] | Failed |
| isolated floor #1 | [] | [] | Passed |
| control #1 | [[1, 1]] | [[1, 1]] | Passed |
SHA-256 / 435a4d7539a780041a7613c6c58d34c1e40d5e69db419a80c2dd3308349088b5
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 = [[('chasm edge #1', [['.~.', '...'], [1, 1], [1, 1]], [[0, 0], [0, 2]]),
('door as neighbour #1', [['#D#', '#.#', '###'], [0, 1], [0, 1]], [[1, 1]]),
('regression walkable neighbour #1',
[['#.#.#', '.#D~~', '..~..', '..D.~'], [1, 4], [2, 0]],
[[1, 0], [2, 4]]),
('regression walkable neighbour #2', [['...D#~', '~.###~', '~..D..'], [1, 3], [0, 2]], [[0, 0], [2, 5]]),
('regression walkable neighbour #3',
[['#~.#.', '#...D', 'D.#..', '#....', '##..~'], [3, 0], [3, 3]],
[[0, 2], [0, 4]]),
('regression walkable neighbour #4', [['~D.#D', '#.#~.'], [0, 1], [1, 2]], [[0, 2], [1, 1], [1, 4]]),
('isolated floor #1', [['#.#', '###'], [1, 0], [1, 0]], []),
('control #1', [['.##', '#..'], [1, 2], [0, 1]], [[1, 1]])],
[('chasm edge #1', [['.~.', '...'], [1, 1], [1, 1]], [[0, 0], [0, 2]]),
('door as neighbour #1', [['#D#', '#.#', '###'], [0, 1], [0, 1]], [[1, 1]]),
('regression walkable neighbour #1', [['...D#~', '~.###~', '~..D..'], [1, 3], [0, 2]], [[0, 0], [2, 5]]),
('regression walkable neighbour #2',
[['#~.#.', '#...D', 'D.#..', '#....', '##..~'], [3, 0], [3, 3]],
[[0, 2], [0, 4]]),
('regression walkable neighbour #3', [['~D.#D', '#.#~.'], [0, 1], [1, 2]], [[0, 2], [1, 1], [1, 4]]),
('regression walkable neighbour #4', [['...#~.', 'D.~~.D'], [1, 1], [1, 1]], [[0, 2], [0, 5], [1, 4]]),
('isolated floor #1', [['#.#', '###'], [1, 0], [1, 0]], []),
('control #1', [['.##', '#..'], [1, 2], [0, 1]], [[1, 1]])],
[('chasm edge #1', [['.~.', '...'], [1, 1], [1, 1]], [[0, 0], [0, 2]]),
('door as neighbour #1', [['#D#', '#.#', '###'], [0, 1], [0, 1]], [[1, 1]]),
('regression walkable neighbour #1', [['~D.#D', '#.#~.'], [0, 1], [1, 2]], [[0, 2], [1, 1], [1, 4]]),
('fault site walkable neighbour #1', [['.~~##.', '##~DD~'], [0, 1], [1, 0]], []),
('regression walkable neighbour #2', [['...#~.', 'D.~~.D'], [1, 1], [1, 1]], [[0, 2], [0, 5], [1, 4]]),
('regression walkable neighbour #3', [['~.##.', 'D..#~', '...##'], [0, 3], [0, 1]], []),
('isolated floor #1', [['#.#', '###'], [1, 0], [1, 0]], []),
('control #1', [['#.', '..', '##', '##', '##'], [0, 0], [1, 0]], [[0, 1]])],
[('chasm edge #1', [['.~.', '...'], [1, 1], [1, 1]], [[0, 0], [0, 2]]),
('door as neighbour #1', [['#D#', '#.#', '###'], [0, 1], [0, 1]], [[1, 1]]),
('regression walkable neighbour #1', [['...#~.', 'D.~~.D'], [1, 1], [1, 1]], [[0, 2], [0, 5], [1, 4]]),
('fault site walkable neighbour #1',
[['..#...', '~..##.', '##~##.'], [0, 0], [0, 5]],
[[0, 3], [1, 2], [2, 5]]),
('regression walkable neighbour #2', [['~.##.', 'D..#~', '...##'], [0, 3], [0, 1]], []),
('regression walkable neighbour #3', [['##.#.', '.~#D.', 'D#.~#'], [0, 3], [1, 4]], [[0, 4], [1, 0]]),
('isolated floor #1', [['#.#', '###'], [1, 0], [1, 0]], []),
('control #1', [['...', '..#'], [0, 1], [0, 0]], [[0, 2]])],
[('chasm edge #1', [['.~.', '...'], [1, 1], [1, 1]], [[0, 0], [0, 2]]),
('door as neighbour #1', [['#D#', '#.#', '###'], [0, 1], [0, 1]], [[1, 1]]),
('regression walkable neighbour #1', [['~.##.', 'D..#~', '...##'], [0, 3], [0, 1]], []),
('regression walkable neighbour #2', [['##.#.', '.~#D.', 'D#.~#'], [0, 3], [1, 4]], [[0, 4], [1, 0]]),
('regression walkable neighbour #3', [['D.', 'DD', '.~', '#.'], [3, 0], [3, 0]], [[2, 0]]),
('regression walkable neighbour #4',
[['.D~~.~', '~..#.D', '#~D.#.', '#..~.#', '.#...#'], [1, 5], [0, 5]],
[[0, 0], [0, 4], [2, 3], [2, 5], [3, 1], [3, 4]]),
('isolated floor #1', [['#.#', '###'], [1, 0], [1, 0]], []),
('control #1', [['..', '.#'], [1, 1], [1, 0]], [[0, 1]])]]
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 |
|---|---|---|---|
| chasm edge #1 | [[0, 0], [0, 2]] | [[0, 0], [0, 2]] | Passed |
| door as neighbour #1 | [[1, 1]] | [[1, 1]] | Passed |
| regression walkable neighbour #1 | [[1, 0], [2, 4]] | [[1, 0], [2, 4]] | Passed |
| regression walkable neighbour #2 | [[0, 0], [2, 5]] | [[0, 0], [2, 5]] | Passed |
| regression walkable neighbour #3 | [[0, 2], [0, 4]] | [[0, 2], [0, 4]] | Passed |
| regression walkable neighbour #4 | [[0, 2], [1, 1], [1, 4]] | [[0, 2], [1, 1], [1, 4]] | Passed |
| isolated floor #1 | [] | [] | Passed |
| control #1 | [[1, 1]] | [[1, 1]] | Passed |
SHA-256 / e14f578440f560f9d0579a66029eacd2b7e63a2dbeaac39e065f1f6bfa4ca9dd
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.192614+00:00.
Case digest / 9ccada3e87e1818cf08a01ceb2d48d38a53803186885758143cae969bc9fc866