FA-86371 / Procedural level generation constraints / Open access
Level reachability flood fill: Water blocks swimmers · case 01
Levels requiring swimming are rejected even when the player can swim.
ROOT CAUSE
Water is treated as impassable regardless of the swim ability.
VERIFIED REPAIR
Restore `(t == '~' and not swim)` at the water passability step.
Unsuccessful approach: Inverting the flag lets non-swimmers cross and blocks swimmers.
Case contract
grid rows of '#' wall, '.' floor, 'D' door (passable), '~' water (passable only when swim) and 'E' exit. From start [row, col], 4-neighbour flood fill. Returns {reachable: number of reached cells including start, exit: whether an E cell was reached}.
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, swim):
h = len(grid)
w = len(grid[0])
sr, sc = start
seen = {(sr, sc)}
stack = [(sr, sc)]
found = False
while stack:
r, c = stack.pop()
if grid[r][c] == 'E':
found = True
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < h and 0 <= nc < w and (nr, nc) not in seen:
t = grid[nr][nc]
if t == '#' or t == '~':
continue
seen.add((nr, nc))
stack.append((nr, nc))
return {'reachable': len(seen), 'exit': found}
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression water passability #1',
[['~.D#.', 'D....', '#.D#E'], [1, 4], True],
{'reachable': 12, 'exit': True}),
('regression water passability #2',
[['E', '.', '.', '.', '~'], [2, 0], True],
{'reachable': 5, 'exit': True}),
('partial repair boundary #1',
[['D.~E.', '#~~.#', 'DD...'], [2, 3], False],
{'reachable': 8, 'exit': True}),
('partial repair boundary #2',
[['.##.', '.D#D', 'D...', '.D~.', '.#DE', '.~#.', '.~DD'], [3, 0], False],
{'reachable': 20, 'exit': True}),
('diagonal gap only #1', [['.#', '#E'], [0, 0], False], {'reachable': 1, 'exit': False}),
('door corridor #1', [['.DE'], [0, 0], False], {'reachable': 3, 'exit': True}),
('walled-in start #1', [['#.#', '#E#'], [0, 1], True], {'reachable': 2, 'exit': True}),
('control #1', [['E', '.'], [1, 0], False], {'reachable': 2, 'exit': True})],
[('regression water passability #1',
[['#D~..', '.#D.~', '.#...', '....D', 'DD#..', '.D.~#', '~~E.D'], [0, 3], True],
{'reachable': 30, 'exit': True}),
('regression water passability #2',
[['.', '.', '~', 'E', '.', '~'], [4, 0], True],
{'reachable': 6, 'exit': True}),
('regression water passability #3',
[['E', '.', '.', '.', '~'], [2, 0], True],
{'reachable': 5, 'exit': True}),
('partial repair boundary #1',
[['.##.', '.D#D', 'D...', '.D~.', '.#DE', '.~#.', '.~DD'], [3, 0], False],
{'reachable': 20, 'exit': True}),
('walled-in start #1', [['#.#', '#E#'], [0, 1], True], {'reachable': 2, 'exit': True}),
('diagonal gap only #1', [['.#', '#E'], [0, 0], False], {'reachable': 1, 'exit': False}),
('control #1', [['E', '.'], [1, 0], False], {'reachable': 2, 'exit': True}),
('control #2', [['.E..', '.D..'], [0, 1], True], {'reachable': 8, 'exit': True})],
[('regression water passability #1', [['#E', '~.'], [0, 1], True], {'reachable': 3, 'exit': True}),
('regression water passability #2',
[['##.E#.D', '.#...#D', '.D.D~~.', '...DDD.', '~.#..#.', '..#....'], [2, 2], True],
{'reachable': 34, 'exit': True}),
('partial repair boundary #1',
[['..', '.E', 'DD', '.#', '..', '.~', '..'], [6, 0], False],
{'reachable': 12, 'exit': True}),
('partial repair boundary #2', [['~D.E..~', '.......'], [1, 5], False], {'reachable': 12, 'exit': True}),
('door corridor #1', [['.DE'], [0, 0], False], {'reachable': 3, 'exit': True}),
('walled-in start #1', [['#.#', '#E#'], [0, 1], True], {'reachable': 2, 'exit': True}),
('control #1', [['.E..', '.D..'], [0, 1], True], {'reachable': 8, 'exit': True}),
('control #2', [['E.D.', '...D'], [1, 0], True], {'reachable': 8, 'exit': True})],
[('regression water passability #1',
[['..E.#.#', '#.~..#.', 'D.#..#.'], [0, 3], True],
{'reachable': 12, 'exit': True}),
('regression water passability #2',
[['..#...', '~.D#D.', 'DD#E~~', '.D..##'], [0, 3], True],
{'reachable': 19, 'exit': True}),
('regression water passability #3',
[['#D~..', '.#D.~', '.#...', '....D', 'DD#..', '.D.~#', '~~E.D'], [0, 3], True],
{'reachable': 30, 'exit': True}),
('regression water passability #4',
[['.', '.', '~', 'E', '.', '~'], [4, 0], True],
{'reachable': 6, 'exit': True}),
('diagonal gap only #1', [['.#', '#E'], [0, 0], False], {'reachable': 1, 'exit': False}),
('door corridor #1', [['.DE'], [0, 0], False], {'reachable': 3, 'exit': True}),
('control #1', [['~.#D##E'], [0, 6], False], {'reachable': 1, 'exit': True}),
('control #2', [['E.D..'], [0, 3], False], {'reachable': 5, 'exit': True})],
[('regression water passability #1',
[['D#', '.~', '#~', '.D', '~E'], [1, 0], True],
{'reachable': 8, 'exit': True}),
('regression water passability #2',
[['.', '.', '~', '~', '#', 'E'], [1, 0], True],
{'reachable': 4, 'exit': False}),
('partial repair boundary #1',
[['DD~.', '.#.#', '~.E.', '#.~~', 'D.~.'], [4, 3], False],
{'reachable': 1, 'exit': False}),
('partial repair boundary #2', [['.', 'E', 'D', '~', '~'], [1, 0], False], {'reachable': 3, 'exit': True}),
('walled-in start #1', [['#.#', '#E#'], [0, 1], True], {'reachable': 2, 'exit': True}),
('diagonal gap only #1', [['.#', '#E'], [0, 0], False], {'reachable': 1, 'exit': False}),
('control #1', [['.E', '.D', 'D.'], [0, 0], True], {'reachable': 6, 'exit': True}),
('control #2', [['E..'], [0, 1], False], {'reachable': 3, 'exit': True})]]
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 water passability #1 | {'exit': True, 'reachable': 11} | {'exit': True, 'reachable': 12} | Failed |
| regression water passability #2 | {'exit': True, 'reachable': 4} | {'exit': True, 'reachable': 5} | Failed |
| partial repair boundary #1 | {'exit': True, 'reachable': 8} | {'exit': True, 'reachable': 8} | Passed |
| partial repair boundary #2 | {'exit': True, 'reachable': 20} | {'exit': True, 'reachable': 20} | Passed |
| diagonal gap only #1 | {'exit': False, 'reachable': 1} | {'exit': False, 'reachable': 1} | Passed |
| door corridor #1 | {'exit': True, 'reachable': 3} | {'exit': True, 'reachable': 3} | Passed |
| walled-in start #1 | {'exit': True, 'reachable': 2} | {'exit': True, 'reachable': 2} | Passed |
| control #1 | {'exit': True, 'reachable': 2} | {'exit': True, 'reachable': 2} | Passed |
SHA-256 / 054cc09bb62f227b89b208c098eecc7e80847f8cf7dd7a7cc3b87b667ad65a49
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(grid, start, swim):
h = len(grid)
w = len(grid[0])
sr, sc = start
seen = {(sr, sc)}
stack = [(sr, sc)]
found = False
while stack:
r, c = stack.pop()
if grid[r][c] == 'E':
found = True
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < h and 0 <= nc < w and (nr, nc) not in seen:
t = grid[nr][nc]
if t == '#' or (t == '~' and swim):
continue
seen.add((nr, nc))
stack.append((nr, nc))
return {'reachable': len(seen), 'exit': found}
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression water passability #1',
[['~.D#.', 'D....', '#.D#E'], [1, 4], True],
{'reachable': 12, 'exit': True}),
('regression water passability #2',
[['E', '.', '.', '.', '~'], [2, 0], True],
{'reachable': 5, 'exit': True}),
('partial repair boundary #1',
[['D.~E.', '#~~.#', 'DD...'], [2, 3], False],
{'reachable': 8, 'exit': True}),
('partial repair boundary #2',
[['.##.', '.D#D', 'D...', '.D~.', '.#DE', '.~#.', '.~DD'], [3, 0], False],
{'reachable': 20, 'exit': True}),
('diagonal gap only #1', [['.#', '#E'], [0, 0], False], {'reachable': 1, 'exit': False}),
('door corridor #1', [['.DE'], [0, 0], False], {'reachable': 3, 'exit': True}),
('walled-in start #1', [['#.#', '#E#'], [0, 1], True], {'reachable': 2, 'exit': True}),
('control #1', [['E', '.'], [1, 0], False], {'reachable': 2, 'exit': True})],
[('regression water passability #1',
[['#D~..', '.#D.~', '.#...', '....D', 'DD#..', '.D.~#', '~~E.D'], [0, 3], True],
{'reachable': 30, 'exit': True}),
('regression water passability #2',
[['.', '.', '~', 'E', '.', '~'], [4, 0], True],
{'reachable': 6, 'exit': True}),
('regression water passability #3',
[['E', '.', '.', '.', '~'], [2, 0], True],
{'reachable': 5, 'exit': True}),
('partial repair boundary #1',
[['.##.', '.D#D', 'D...', '.D~.', '.#DE', '.~#.', '.~DD'], [3, 0], False],
{'reachable': 20, 'exit': True}),
('walled-in start #1', [['#.#', '#E#'], [0, 1], True], {'reachable': 2, 'exit': True}),
('diagonal gap only #1', [['.#', '#E'], [0, 0], False], {'reachable': 1, 'exit': False}),
('control #1', [['E', '.'], [1, 0], False], {'reachable': 2, 'exit': True}),
('control #2', [['.E..', '.D..'], [0, 1], True], {'reachable': 8, 'exit': True})],
[('regression water passability #1', [['#E', '~.'], [0, 1], True], {'reachable': 3, 'exit': True}),
('regression water passability #2',
[['##.E#.D', '.#...#D', '.D.D~~.', '...DDD.', '~.#..#.', '..#....'], [2, 2], True],
{'reachable': 34, 'exit': True}),
('partial repair boundary #1',
[['..', '.E', 'DD', '.#', '..', '.~', '..'], [6, 0], False],
{'reachable': 12, 'exit': True}),
('partial repair boundary #2', [['~D.E..~', '.......'], [1, 5], False], {'reachable': 12, 'exit': True}),
('door corridor #1', [['.DE'], [0, 0], False], {'reachable': 3, 'exit': True}),
('walled-in start #1', [['#.#', '#E#'], [0, 1], True], {'reachable': 2, 'exit': True}),
('control #1', [['.E..', '.D..'], [0, 1], True], {'reachable': 8, 'exit': True}),
('control #2', [['E.D.', '...D'], [1, 0], True], {'reachable': 8, 'exit': True})],
[('regression water passability #1',
[['..E.#.#', '#.~..#.', 'D.#..#.'], [0, 3], True],
{'reachable': 12, 'exit': True}),
('regression water passability #2',
[['..#...', '~.D#D.', 'DD#E~~', '.D..##'], [0, 3], True],
{'reachable': 19, 'exit': True}),
('regression water passability #3',
[['#D~..', '.#D.~', '.#...', '....D', 'DD#..', '.D.~#', '~~E.D'], [0, 3], True],
{'reachable': 30, 'exit': True}),
('regression water passability #4',
[['.', '.', '~', 'E', '.', '~'], [4, 0], True],
{'reachable': 6, 'exit': True}),
('diagonal gap only #1', [['.#', '#E'], [0, 0], False], {'reachable': 1, 'exit': False}),
('door corridor #1', [['.DE'], [0, 0], False], {'reachable': 3, 'exit': True}),
('control #1', [['~.#D##E'], [0, 6], False], {'reachable': 1, 'exit': True}),
('control #2', [['E.D..'], [0, 3], False], {'reachable': 5, 'exit': True})],
[('regression water passability #1',
[['D#', '.~', '#~', '.D', '~E'], [1, 0], True],
{'reachable': 8, 'exit': True}),
('regression water passability #2',
[['.', '.', '~', '~', '#', 'E'], [1, 0], True],
{'reachable': 4, 'exit': False}),
('partial repair boundary #1',
[['DD~.', '.#.#', '~.E.', '#.~~', 'D.~.'], [4, 3], False],
{'reachable': 1, 'exit': False}),
('partial repair boundary #2', [['.', 'E', 'D', '~', '~'], [1, 0], False], {'reachable': 3, 'exit': True}),
('walled-in start #1', [['#.#', '#E#'], [0, 1], True], {'reachable': 2, 'exit': True}),
('diagonal gap only #1', [['.#', '#E'], [0, 0], False], {'reachable': 1, 'exit': False}),
('control #1', [['.E', '.D', 'D.'], [0, 0], True], {'reachable': 6, 'exit': True}),
('control #2', [['E..'], [0, 1], False], {'reachable': 3, 'exit': True})]]
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 water passability #1 | {'exit': True, 'reachable': 11} | {'exit': True, 'reachable': 12} | Failed |
| regression water passability #2 | {'exit': True, 'reachable': 4} | {'exit': True, 'reachable': 5} | Failed |
| partial repair boundary #1 | {'exit': True, 'reachable': 13} | {'exit': True, 'reachable': 8} | Failed |
| partial repair boundary #2 | {'exit': True, 'reachable': 23} | {'exit': True, 'reachable': 20} | Failed |
| diagonal gap only #1 | {'exit': False, 'reachable': 1} | {'exit': False, 'reachable': 1} | Passed |
| door corridor #1 | {'exit': True, 'reachable': 3} | {'exit': True, 'reachable': 3} | Passed |
| walled-in start #1 | {'exit': True, 'reachable': 2} | {'exit': True, 'reachable': 2} | Passed |
| control #1 | {'exit': True, 'reachable': 2} | {'exit': True, 'reachable': 2} | Passed |
SHA-256 / e27902eadd0944aa71cce16dbc8469ed361d46263c5c4a36b8e1169dfb8e0bf5
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(grid, start, swim):
h = len(grid)
w = len(grid[0])
sr, sc = start
seen = {(sr, sc)}
stack = [(sr, sc)]
found = False
while stack:
r, c = stack.pop()
if grid[r][c] == 'E':
found = True
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < h and 0 <= nc < w and (nr, nc) not in seen:
t = grid[nr][nc]
if t == '#' or (t == '~' and not swim):
continue
seen.add((nr, nc))
stack.append((nr, nc))
return {'reachable': len(seen), 'exit': found}
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression water passability #1',
[['~.D#.', 'D....', '#.D#E'], [1, 4], True],
{'reachable': 12, 'exit': True}),
('regression water passability #2',
[['E', '.', '.', '.', '~'], [2, 0], True],
{'reachable': 5, 'exit': True}),
('partial repair boundary #1',
[['D.~E.', '#~~.#', 'DD...'], [2, 3], False],
{'reachable': 8, 'exit': True}),
('partial repair boundary #2',
[['.##.', '.D#D', 'D...', '.D~.', '.#DE', '.~#.', '.~DD'], [3, 0], False],
{'reachable': 20, 'exit': True}),
('diagonal gap only #1', [['.#', '#E'], [0, 0], False], {'reachable': 1, 'exit': False}),
('door corridor #1', [['.DE'], [0, 0], False], {'reachable': 3, 'exit': True}),
('walled-in start #1', [['#.#', '#E#'], [0, 1], True], {'reachable': 2, 'exit': True}),
('control #1', [['E', '.'], [1, 0], False], {'reachable': 2, 'exit': True})],
[('regression water passability #1',
[['#D~..', '.#D.~', '.#...', '....D', 'DD#..', '.D.~#', '~~E.D'], [0, 3], True],
{'reachable': 30, 'exit': True}),
('regression water passability #2',
[['.', '.', '~', 'E', '.', '~'], [4, 0], True],
{'reachable': 6, 'exit': True}),
('regression water passability #3',
[['E', '.', '.', '.', '~'], [2, 0], True],
{'reachable': 5, 'exit': True}),
('partial repair boundary #1',
[['.##.', '.D#D', 'D...', '.D~.', '.#DE', '.~#.', '.~DD'], [3, 0], False],
{'reachable': 20, 'exit': True}),
('walled-in start #1', [['#.#', '#E#'], [0, 1], True], {'reachable': 2, 'exit': True}),
('diagonal gap only #1', [['.#', '#E'], [0, 0], False], {'reachable': 1, 'exit': False}),
('control #1', [['E', '.'], [1, 0], False], {'reachable': 2, 'exit': True}),
('control #2', [['.E..', '.D..'], [0, 1], True], {'reachable': 8, 'exit': True})],
[('regression water passability #1', [['#E', '~.'], [0, 1], True], {'reachable': 3, 'exit': True}),
('regression water passability #2',
[['##.E#.D', '.#...#D', '.D.D~~.', '...DDD.', '~.#..#.', '..#....'], [2, 2], True],
{'reachable': 34, 'exit': True}),
('partial repair boundary #1',
[['..', '.E', 'DD', '.#', '..', '.~', '..'], [6, 0], False],
{'reachable': 12, 'exit': True}),
('partial repair boundary #2', [['~D.E..~', '.......'], [1, 5], False], {'reachable': 12, 'exit': True}),
('door corridor #1', [['.DE'], [0, 0], False], {'reachable': 3, 'exit': True}),
('walled-in start #1', [['#.#', '#E#'], [0, 1], True], {'reachable': 2, 'exit': True}),
('control #1', [['.E..', '.D..'], [0, 1], True], {'reachable': 8, 'exit': True}),
('control #2', [['E.D.', '...D'], [1, 0], True], {'reachable': 8, 'exit': True})],
[('regression water passability #1',
[['..E.#.#', '#.~..#.', 'D.#..#.'], [0, 3], True],
{'reachable': 12, 'exit': True}),
('regression water passability #2',
[['..#...', '~.D#D.', 'DD#E~~', '.D..##'], [0, 3], True],
{'reachable': 19, 'exit': True}),
('regression water passability #3',
[['#D~..', '.#D.~', '.#...', '....D', 'DD#..', '.D.~#', '~~E.D'], [0, 3], True],
{'reachable': 30, 'exit': True}),
('regression water passability #4',
[['.', '.', '~', 'E', '.', '~'], [4, 0], True],
{'reachable': 6, 'exit': True}),
('diagonal gap only #1', [['.#', '#E'], [0, 0], False], {'reachable': 1, 'exit': False}),
('door corridor #1', [['.DE'], [0, 0], False], {'reachable': 3, 'exit': True}),
('control #1', [['~.#D##E'], [0, 6], False], {'reachable': 1, 'exit': True}),
('control #2', [['E.D..'], [0, 3], False], {'reachable': 5, 'exit': True})],
[('regression water passability #1',
[['D#', '.~', '#~', '.D', '~E'], [1, 0], True],
{'reachable': 8, 'exit': True}),
('regression water passability #2',
[['.', '.', '~', '~', '#', 'E'], [1, 0], True],
{'reachable': 4, 'exit': False}),
('partial repair boundary #1',
[['DD~.', '.#.#', '~.E.', '#.~~', 'D.~.'], [4, 3], False],
{'reachable': 1, 'exit': False}),
('partial repair boundary #2', [['.', 'E', 'D', '~', '~'], [1, 0], False], {'reachable': 3, 'exit': True}),
('walled-in start #1', [['#.#', '#E#'], [0, 1], True], {'reachable': 2, 'exit': True}),
('diagonal gap only #1', [['.#', '#E'], [0, 0], False], {'reachable': 1, 'exit': False}),
('control #1', [['.E', '.D', 'D.'], [0, 0], True], {'reachable': 6, 'exit': True}),
('control #2', [['E..'], [0, 1], False], {'reachable': 3, 'exit': True})]]
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 water passability #1 | {'exit': True, 'reachable': 12} | {'exit': True, 'reachable': 12} | Passed |
| regression water passability #2 | {'exit': True, 'reachable': 5} | {'exit': True, 'reachable': 5} | Passed |
| partial repair boundary #1 | {'exit': True, 'reachable': 8} | {'exit': True, 'reachable': 8} | Passed |
| partial repair boundary #2 | {'exit': True, 'reachable': 20} | {'exit': True, 'reachable': 20} | Passed |
| diagonal gap only #1 | {'exit': False, 'reachable': 1} | {'exit': False, 'reachable': 1} | Passed |
| door corridor #1 | {'exit': True, 'reachable': 3} | {'exit': True, 'reachable': 3} | Passed |
| walled-in start #1 | {'exit': True, 'reachable': 2} | {'exit': True, 'reachable': 2} | Passed |
| control #1 | {'exit': True, 'reachable': 2} | {'exit': True, 'reachable': 2} | Passed |
SHA-256 / 234fe90d77ca4f68d0c0127011467080452ac1f416137f02019511475a58d69d
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:48.908023+00:00.
Case digest / 7e9ef1e95ba9b7f218d761518f2bbb6ccd5a6d03142a152fa2b02106f07bc961