FAILURE MAP
← Case archive

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.

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

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 fixtureActualExpectedOutcome
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 fixtureActualExpectedOutcome
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 fixtureActualExpectedOutcome
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