FA-86366 / Procedural level generation constraints / Open access
Level reachability flood fill: Flood fill squeezes through diagonal gaps · case 01
Levels are validated as solvable although the exit is only diagonally adjacent.
ROOT CAUSE
The fill uses the 8-neighbourhood although movement is 4-directional.
VERIFIED REPAIR
Restore `((1, 0), (-1, 0), (0, 1), (0, -1))` at the neighbourhood step.
Unsuccessful approach: Keeping only forward directions misses areas up or left of the start.
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), (1, 1), (-1, -1), (1, -1), (-1, 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 = [[('diagonal gap only #1', [['.#', '#E'], [0, 0], False], {'reachable': 1, 'exit': False}),
('regression neighbourhood #1',
[['..E.#.#', '#.~..#.', 'D.#..#.'], [0, 3], True],
{'reachable': 12, 'exit': True}),
('regression neighbourhood #2',
[['#.#..', '~~...', 'DDDE~', '.D.D.', '.....', '....#'], [4, 1], False],
{'reachable': 23, 'exit': True}),
('partial repair boundary #1', [['E', '.'], [1, 0], False], {'reachable': 2, 'exit': True}),
('partial repair boundary #2', [['.E..', '.D..'], [0, 1], True], {'reachable': 8, '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', [['~.#D##E'], [0, 6], False], {'reachable': 1, 'exit': True})],
[('diagonal gap only #1', [['.#', '#E'], [0, 0], False], {'reachable': 1, 'exit': False}),
('regression neighbourhood #1',
[['#.#..', '~~...', 'DDDE~', '.D.D.', '.....', '....#'], [4, 1], False],
{'reachable': 23, 'exit': True}),
('fault site neighbourhood #1',
[['.....D', '......', '.D~#.#', '...E#~'], [0, 0], True],
{'reachable': 20, 'exit': True}),
('partial repair boundary #1',
[['~.D#.', 'D....', '#.D#E'], [1, 4], True],
{'reachable': 12, 'exit': True}),
('partial repair boundary #2',
[['D.~E.', '#~~.#', 'DD...'], [2, 3], False],
{'reachable': 8, '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', [['~.#D##E'], [0, 6], False], {'reachable': 1, 'exit': True})],
[('diagonal gap only #1', [['.#', '#E'], [0, 0], False], {'reachable': 1, 'exit': False}),
('fault site neighbourhood #1',
[['#D~.##', '.D.~E#', '.~...~', '....#.', '#.....'], [0, 3], False],
{'reachable': 1, 'exit': False}),
('fault site neighbourhood #2', [['~#DD~.', '..~E.D'], [1, 0], False], {'reachable': 2, 'exit': False}),
('partial repair boundary #1', [['E', '.', '.', '.', '~'], [2, 0], True], {'reachable': 5, 'exit': True}),
('partial repair boundary #2', [['E.D.', '...D'], [1, 0], True], {'reachable': 8, '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', [['~.#D##E'], [0, 6], False], {'reachable': 1, 'exit': True})],
[('diagonal gap only #1', [['.#', '#E'], [0, 0], False], {'reachable': 1, 'exit': False}),
('regression neighbourhood #1',
[['~D', '.E', '~.', '.#', '..', '.D'], [1, 1], False],
{'reachable': 4, 'exit': True}),
('regression neighbourhood #2',
[['D#.#~', '.#~~.', 'D..E#', '.....', '.D.D.', '..~.D', '.~.D.'], [6, 2], False],
{'reachable': 24, 'exit': True}),
('partial repair boundary #1',
[['.##.', '.D#D', 'D...', '.D~.', '.#DE', '.~#.', '.~DD'], [3, 0], False],
{'reachable': 20, 'exit': True}),
('partial repair boundary #2',
[['..', '.E', 'DD', '.#', '..', '.~', '..'], [6, 0], 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', 'D.'], [0, 0], True], {'reachable': 6, 'exit': True})],
[('diagonal gap only #1', [['.#', '#E'], [0, 0], False], {'reachable': 1, 'exit': False}),
('regression neighbourhood #1',
[['.#~D', '#~~.', '~.E.', 'D.##', '~...'], [3, 1], True],
{'reachable': 15, 'exit': True}),
('regression neighbourhood #2',
[['...', 'E~D', '#.#', '~..', '#..', '~..'], [5, 2], False],
{'reachable': 7, 'exit': False}),
('partial repair boundary #1', [['~D.E..~', '.......'], [1, 5], False], {'reachable': 12, 'exit': True}),
('partial repair boundary #2',
[['#D~..', '.#D.~', '.#...', '....D', 'DD#..', '.D.~#', '~~E.D'], [0, 3], True],
{'reachable': 30, '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', [['DD~.', '.#.#', '~.E.', '#.~~', 'D.~.'], [4, 3], False], {'reachable': 1, 'exit': False})]]
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 |
|---|---|---|---|
| diagonal gap only #1 | {'exit': True, 'reachable': 2} | {'exit': False, 'reachable': 1} | Failed |
| regression neighbourhood #1 | {'exit': True, 'reachable': 15} | {'exit': True, 'reachable': 12} | Failed |
| regression neighbourhood #2 | {'exit': True, 'reachable': 24} | {'exit': True, 'reachable': 23} | Failed |
| partial repair boundary #1 | {'exit': True, 'reachable': 2} | {'exit': True, 'reachable': 2} | Passed |
| partial repair boundary #2 | {'exit': True, 'reachable': 8} | {'exit': True, 'reachable': 8} | 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': 1} | {'exit': True, 'reachable': 1} | Passed |
SHA-256 / a49e31898ea10f6f02fa4fbcecf829d31126e1a1e46f2c8ccc42dc00c772085d
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), (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 = [[('diagonal gap only #1', [['.#', '#E'], [0, 0], False], {'reachable': 1, 'exit': False}),
('regression neighbourhood #1',
[['..E.#.#', '#.~..#.', 'D.#..#.'], [0, 3], True],
{'reachable': 12, 'exit': True}),
('regression neighbourhood #2',
[['#.#..', '~~...', 'DDDE~', '.D.D.', '.....', '....#'], [4, 1], False],
{'reachable': 23, 'exit': True}),
('partial repair boundary #1', [['E', '.'], [1, 0], False], {'reachable': 2, 'exit': True}),
('partial repair boundary #2', [['.E..', '.D..'], [0, 1], True], {'reachable': 8, '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', [['~.#D##E'], [0, 6], False], {'reachable': 1, 'exit': True})],
[('diagonal gap only #1', [['.#', '#E'], [0, 0], False], {'reachable': 1, 'exit': False}),
('regression neighbourhood #1',
[['#.#..', '~~...', 'DDDE~', '.D.D.', '.....', '....#'], [4, 1], False],
{'reachable': 23, 'exit': True}),
('fault site neighbourhood #1',
[['.....D', '......', '.D~#.#', '...E#~'], [0, 0], True],
{'reachable': 20, 'exit': True}),
('partial repair boundary #1',
[['~.D#.', 'D....', '#.D#E'], [1, 4], True],
{'reachable': 12, 'exit': True}),
('partial repair boundary #2',
[['D.~E.', '#~~.#', 'DD...'], [2, 3], False],
{'reachable': 8, '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', [['~.#D##E'], [0, 6], False], {'reachable': 1, 'exit': True})],
[('diagonal gap only #1', [['.#', '#E'], [0, 0], False], {'reachable': 1, 'exit': False}),
('fault site neighbourhood #1',
[['#D~.##', '.D.~E#', '.~...~', '....#.', '#.....'], [0, 3], False],
{'reachable': 1, 'exit': False}),
('fault site neighbourhood #2', [['~#DD~.', '..~E.D'], [1, 0], False], {'reachable': 2, 'exit': False}),
('partial repair boundary #1', [['E', '.', '.', '.', '~'], [2, 0], True], {'reachable': 5, 'exit': True}),
('partial repair boundary #2', [['E.D.', '...D'], [1, 0], True], {'reachable': 8, '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', [['~.#D##E'], [0, 6], False], {'reachable': 1, 'exit': True})],
[('diagonal gap only #1', [['.#', '#E'], [0, 0], False], {'reachable': 1, 'exit': False}),
('regression neighbourhood #1',
[['~D', '.E', '~.', '.#', '..', '.D'], [1, 1], False],
{'reachable': 4, 'exit': True}),
('regression neighbourhood #2',
[['D#.#~', '.#~~.', 'D..E#', '.....', '.D.D.', '..~.D', '.~.D.'], [6, 2], False],
{'reachable': 24, 'exit': True}),
('partial repair boundary #1',
[['.##.', '.D#D', 'D...', '.D~.', '.#DE', '.~#.', '.~DD'], [3, 0], False],
{'reachable': 20, 'exit': True}),
('partial repair boundary #2',
[['..', '.E', 'DD', '.#', '..', '.~', '..'], [6, 0], 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', 'D.'], [0, 0], True], {'reachable': 6, 'exit': True})],
[('diagonal gap only #1', [['.#', '#E'], [0, 0], False], {'reachable': 1, 'exit': False}),
('regression neighbourhood #1',
[['.#~D', '#~~.', '~.E.', 'D.##', '~...'], [3, 1], True],
{'reachable': 15, 'exit': True}),
('regression neighbourhood #2',
[['...', 'E~D', '#.#', '~..', '#..', '~..'], [5, 2], False],
{'reachable': 7, 'exit': False}),
('partial repair boundary #1', [['~D.E..~', '.......'], [1, 5], False], {'reachable': 12, 'exit': True}),
('partial repair boundary #2',
[['#D~..', '.#D.~', '.#...', '....D', 'DD#..', '.D.~#', '~~E.D'], [0, 3], True],
{'reachable': 30, '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', [['DD~.', '.#.#', '~.E.', '#.~~', 'D.~.'], [4, 3], False], {'reachable': 1, 'exit': False})]]
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 |
|---|---|---|---|
| diagonal gap only #1 | {'exit': False, 'reachable': 1} | {'exit': False, 'reachable': 1} | Passed |
| regression neighbourhood #1 | {'exit': False, 'reachable': 5} | {'exit': True, 'reachable': 12} | Failed |
| regression neighbourhood #2 | {'exit': False, 'reachable': 7} | {'exit': True, 'reachable': 23} | Failed |
| partial repair boundary #1 | {'exit': False, 'reachable': 1} | {'exit': True, 'reachable': 2} | Failed |
| partial repair boundary #2 | {'exit': True, 'reachable': 6} | {'exit': True, 'reachable': 8} | Failed |
| 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': 1} | {'exit': True, 'reachable': 1} | Passed |
SHA-256 / d06b4d2b2088dcebe0222fd00d995ffd4f1468217c32150e29b924f8a5036e56
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 = [[('diagonal gap only #1', [['.#', '#E'], [0, 0], False], {'reachable': 1, 'exit': False}),
('regression neighbourhood #1',
[['..E.#.#', '#.~..#.', 'D.#..#.'], [0, 3], True],
{'reachable': 12, 'exit': True}),
('regression neighbourhood #2',
[['#.#..', '~~...', 'DDDE~', '.D.D.', '.....', '....#'], [4, 1], False],
{'reachable': 23, 'exit': True}),
('partial repair boundary #1', [['E', '.'], [1, 0], False], {'reachable': 2, 'exit': True}),
('partial repair boundary #2', [['.E..', '.D..'], [0, 1], True], {'reachable': 8, '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', [['~.#D##E'], [0, 6], False], {'reachable': 1, 'exit': True})],
[('diagonal gap only #1', [['.#', '#E'], [0, 0], False], {'reachable': 1, 'exit': False}),
('regression neighbourhood #1',
[['#.#..', '~~...', 'DDDE~', '.D.D.', '.....', '....#'], [4, 1], False],
{'reachable': 23, 'exit': True}),
('fault site neighbourhood #1',
[['.....D', '......', '.D~#.#', '...E#~'], [0, 0], True],
{'reachable': 20, 'exit': True}),
('partial repair boundary #1',
[['~.D#.', 'D....', '#.D#E'], [1, 4], True],
{'reachable': 12, 'exit': True}),
('partial repair boundary #2',
[['D.~E.', '#~~.#', 'DD...'], [2, 3], False],
{'reachable': 8, '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', [['~.#D##E'], [0, 6], False], {'reachable': 1, 'exit': True})],
[('diagonal gap only #1', [['.#', '#E'], [0, 0], False], {'reachable': 1, 'exit': False}),
('fault site neighbourhood #1',
[['#D~.##', '.D.~E#', '.~...~', '....#.', '#.....'], [0, 3], False],
{'reachable': 1, 'exit': False}),
('fault site neighbourhood #2', [['~#DD~.', '..~E.D'], [1, 0], False], {'reachable': 2, 'exit': False}),
('partial repair boundary #1', [['E', '.', '.', '.', '~'], [2, 0], True], {'reachable': 5, 'exit': True}),
('partial repair boundary #2', [['E.D.', '...D'], [1, 0], True], {'reachable': 8, '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', [['~.#D##E'], [0, 6], False], {'reachable': 1, 'exit': True})],
[('diagonal gap only #1', [['.#', '#E'], [0, 0], False], {'reachable': 1, 'exit': False}),
('regression neighbourhood #1',
[['~D', '.E', '~.', '.#', '..', '.D'], [1, 1], False],
{'reachable': 4, 'exit': True}),
('regression neighbourhood #2',
[['D#.#~', '.#~~.', 'D..E#', '.....', '.D.D.', '..~.D', '.~.D.'], [6, 2], False],
{'reachable': 24, 'exit': True}),
('partial repair boundary #1',
[['.##.', '.D#D', 'D...', '.D~.', '.#DE', '.~#.', '.~DD'], [3, 0], False],
{'reachable': 20, 'exit': True}),
('partial repair boundary #2',
[['..', '.E', 'DD', '.#', '..', '.~', '..'], [6, 0], 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', 'D.'], [0, 0], True], {'reachable': 6, 'exit': True})],
[('diagonal gap only #1', [['.#', '#E'], [0, 0], False], {'reachable': 1, 'exit': False}),
('regression neighbourhood #1',
[['.#~D', '#~~.', '~.E.', 'D.##', '~...'], [3, 1], True],
{'reachable': 15, 'exit': True}),
('regression neighbourhood #2',
[['...', 'E~D', '#.#', '~..', '#..', '~..'], [5, 2], False],
{'reachable': 7, 'exit': False}),
('partial repair boundary #1', [['~D.E..~', '.......'], [1, 5], False], {'reachable': 12, 'exit': True}),
('partial repair boundary #2',
[['#D~..', '.#D.~', '.#...', '....D', 'DD#..', '.D.~#', '~~E.D'], [0, 3], True],
{'reachable': 30, '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', [['DD~.', '.#.#', '~.E.', '#.~~', 'D.~.'], [4, 3], False], {'reachable': 1, 'exit': False})]]
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 |
|---|---|---|---|
| diagonal gap only #1 | {'exit': False, 'reachable': 1} | {'exit': False, 'reachable': 1} | Passed |
| regression neighbourhood #1 | {'exit': True, 'reachable': 12} | {'exit': True, 'reachable': 12} | Passed |
| regression neighbourhood #2 | {'exit': True, 'reachable': 23} | {'exit': True, 'reachable': 23} | Passed |
| partial repair boundary #1 | {'exit': True, 'reachable': 2} | {'exit': True, 'reachable': 2} | Passed |
| partial repair boundary #2 | {'exit': True, 'reachable': 8} | {'exit': True, 'reachable': 8} | 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': 1} | {'exit': True, 'reachable': 1} | Passed |
SHA-256 / 561fa3097088b48846ffc4f4f93eaca67a3faf710c34d08f5a682eb652320898
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.881032+00:00.
Case digest / fa0a625233d45b712f38358a355dc52167ec035a6722915cfcb00969461df5e5