FAILURE MAP
← Case archive

FA-86376 / Procedural level generation constraints / Open access

Level reachability flood fill: Start cell is not counted · case 01

An enclosed start reports zero reachable cells.

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

ROOT CAUSE

The visited set starts empty, so the start is counted only if a neighbour leads back.

VERIFIED REPAIR

Restore `seen = {(sr, sc)}` at the start seeding step.

Unsuccessful approach: Seeding with swapped coordinates marks the wrong cell as visited.

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 = set()
    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}),
  ('walled-in start #1', [['#.#', '#E#'], [0, 1], True], {'reachable': 2, 'exit': True}),
  ('fault site start seeding #1', [['~.#D##E'], [0, 6], False], {'reachable': 1, 'exit': True}),
  ('fault site start seeding #2',
   [['DD~.', '.#.#', '~.E.', '#.~~', 'D.~.'], [4, 3], False],
   {'reachable': 1, 'exit': False}),
  ('partial repair boundary #1', [['E', '.'], [1, 0], False], {'reachable': 2, 'exit': True}),
  ('partial repair boundary #2',
   [['~.D#.', 'D....', '#.D#E'], [1, 4], True],
   {'reachable': 12, 'exit': True}),
  ('door corridor #1', [['.DE'], [0, 0], False], {'reachable': 3, 'exit': True}),
  ('control #1', [['.E..', '.D..'], [0, 1], True], {'reachable': 8, 'exit': True})],
 [('diagonal gap only #1', [['.#', '#E'], [0, 0], False], {'reachable': 1, 'exit': False}),
  ('walled-in start #1', [['#.#', '#E#'], [0, 1], True], {'reachable': 2, 'exit': True}),
  ('fault site start seeding #1',
   [['DD~.', '.#.#', '~.E.', '#.~~', 'D.~.'], [4, 3], False],
   {'reachable': 1, 'exit': False}),
  ('fault site start seeding #2', [['E'], [0, 0], False], {'reachable': 1, '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}),
  ('control #1', [['.E..', '.D..'], [0, 1], True], {'reachable': 8, 'exit': True})],
 [('diagonal gap only #1', [['.#', '#E'], [0, 0], False], {'reachable': 1, 'exit': False}),
  ('walled-in start #1', [['#.#', '#E#'], [0, 1], True], {'reachable': 2, 'exit': True}),
  ('fault site start seeding #1', [['E', '#', '~', '.'], [0, 0], True], {'reachable': 1, 'exit': True}),
  ('fault site start seeding #2', [['E'], [0, 0], True], {'reachable': 1, 'exit': True}),
  ('partial repair boundary #1', [['E', '.', '.', '.', '~'], [2, 0], True], {'reachable': 5, '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}),
  ('control #1', [['E.D.', '...D'], [1, 0], True], {'reachable': 8, 'exit': True})],
 [('diagonal gap only #1', [['.#', '#E'], [0, 0], False], {'reachable': 1, 'exit': False}),
  ('walled-in start #1', [['#.#', '#E#'], [0, 1], True], {'reachable': 2, 'exit': True}),
  ('fault site start seeding #1',
   [['#D~.##', '.D.~E#', '.~...~', '....#.', '#.....'], [0, 3], False],
   {'reachable': 1, 'exit': False}),
  ('fault site start seeding #2', [['E', '#'], [0, 0], False], {'reachable': 1, 'exit': True}),
  ('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}),
  ('control #1',
   [['.##.', '.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}),
  ('walled-in start #1', [['#.#', '#E#'], [0, 1], True], {'reachable': 2, 'exit': True}),
  ('fault site start seeding #1',
   [['.~~~D', 'E....', '.~.#D', '~.~#~', '~~D~D', '.#~#.'], [5, 0], False],
   {'reachable': 1, 'exit': False}),
  ('fault site start seeding #2',
   [['D', '#', 'E', '#', '.', '.', '.'], [2, 0], True],
   {'reachable': 1, 'exit': True}),
  ('partial repair boundary #1',
   [['.', '.', '~', 'E', '.', '~'], [4, 0], True],
   {'reachable': 6, 'exit': True}),
  ('partial repair boundary #2', [['E.D..'], [0, 3], False], {'reachable': 5, 'exit': True}),
  ('door corridor #1', [['.DE'], [0, 0], False], {'reachable': 3, 'exit': True}),
  ('control #1', [['.E', '.D', 'D.'], [0, 0], True], {'reachable': 6, '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
diagonal gap only #1{'exit': False, 'reachable': 0}{'exit': False, 'reachable': 1}Failed
walled-in start #1{'exit': True, 'reachable': 2}{'exit': True, 'reachable': 2}Passed
fault site start seeding #1{'exit': True, 'reachable': 0}{'exit': True, 'reachable': 1}Failed
fault site start seeding #2{'exit': False, 'reachable': 0}{'exit': False, 'reachable': 1}Failed
partial repair boundary #1{'exit': True, 'reachable': 2}{'exit': True, 'reachable': 2}Passed
partial repair boundary #2{'exit': True, 'reachable': 12}{'exit': True, 'reachable': 12}Passed
door corridor #1{'exit': True, 'reachable': 3}{'exit': True, 'reachable': 3}Passed
control #1{'exit': True, 'reachable': 8}{'exit': True, 'reachable': 8}Passed

SHA-256 / e58109cc58a9b7a5b18f0a3891d14b04c1969689de2ab49cbcb76cae60b4c303

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 = {(sc, sr)}
    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}),
  ('walled-in start #1', [['#.#', '#E#'], [0, 1], True], {'reachable': 2, 'exit': True}),
  ('fault site start seeding #1', [['~.#D##E'], [0, 6], False], {'reachable': 1, 'exit': True}),
  ('fault site start seeding #2',
   [['DD~.', '.#.#', '~.E.', '#.~~', 'D.~.'], [4, 3], False],
   {'reachable': 1, 'exit': False}),
  ('partial repair boundary #1', [['E', '.'], [1, 0], False], {'reachable': 2, 'exit': True}),
  ('partial repair boundary #2',
   [['~.D#.', 'D....', '#.D#E'], [1, 4], True],
   {'reachable': 12, 'exit': True}),
  ('door corridor #1', [['.DE'], [0, 0], False], {'reachable': 3, 'exit': True}),
  ('control #1', [['.E..', '.D..'], [0, 1], True], {'reachable': 8, 'exit': True})],
 [('diagonal gap only #1', [['.#', '#E'], [0, 0], False], {'reachable': 1, 'exit': False}),
  ('walled-in start #1', [['#.#', '#E#'], [0, 1], True], {'reachable': 2, 'exit': True}),
  ('fault site start seeding #1',
   [['DD~.', '.#.#', '~.E.', '#.~~', 'D.~.'], [4, 3], False],
   {'reachable': 1, 'exit': False}),
  ('fault site start seeding #2', [['E'], [0, 0], False], {'reachable': 1, '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}),
  ('control #1', [['.E..', '.D..'], [0, 1], True], {'reachable': 8, 'exit': True})],
 [('diagonal gap only #1', [['.#', '#E'], [0, 0], False], {'reachable': 1, 'exit': False}),
  ('walled-in start #1', [['#.#', '#E#'], [0, 1], True], {'reachable': 2, 'exit': True}),
  ('fault site start seeding #1', [['E', '#', '~', '.'], [0, 0], True], {'reachable': 1, 'exit': True}),
  ('fault site start seeding #2', [['E'], [0, 0], True], {'reachable': 1, 'exit': True}),
  ('partial repair boundary #1', [['E', '.', '.', '.', '~'], [2, 0], True], {'reachable': 5, '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}),
  ('control #1', [['E.D.', '...D'], [1, 0], True], {'reachable': 8, 'exit': True})],
 [('diagonal gap only #1', [['.#', '#E'], [0, 0], False], {'reachable': 1, 'exit': False}),
  ('walled-in start #1', [['#.#', '#E#'], [0, 1], True], {'reachable': 2, 'exit': True}),
  ('fault site start seeding #1',
   [['#D~.##', '.D.~E#', '.~...~', '....#.', '#.....'], [0, 3], False],
   {'reachable': 1, 'exit': False}),
  ('fault site start seeding #2', [['E', '#'], [0, 0], False], {'reachable': 1, 'exit': True}),
  ('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}),
  ('control #1',
   [['.##.', '.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}),
  ('walled-in start #1', [['#.#', '#E#'], [0, 1], True], {'reachable': 2, 'exit': True}),
  ('fault site start seeding #1',
   [['.~~~D', 'E....', '.~.#D', '~.~#~', '~~D~D', '.#~#.'], [5, 0], False],
   {'reachable': 1, 'exit': False}),
  ('fault site start seeding #2',
   [['D', '#', 'E', '#', '.', '.', '.'], [2, 0], True],
   {'reachable': 1, 'exit': True}),
  ('partial repair boundary #1',
   [['.', '.', '~', 'E', '.', '~'], [4, 0], True],
   {'reachable': 6, 'exit': True}),
  ('partial repair boundary #2', [['E.D..'], [0, 3], False], {'reachable': 5, 'exit': True}),
  ('door corridor #1', [['.DE'], [0, 0], False], {'reachable': 3, 'exit': True}),
  ('control #1', [['.E', '.D', 'D.'], [0, 0], True], {'reachable': 6, '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
diagonal gap only #1{'exit': False, 'reachable': 1}{'exit': False, 'reachable': 1}Passed
walled-in start #1{'exit': True, 'reachable': 3}{'exit': True, 'reachable': 2}Failed
fault site start seeding #1{'exit': True, 'reachable': 1}{'exit': True, 'reachable': 1}Passed
fault site start seeding #2{'exit': False, 'reachable': 1}{'exit': False, 'reachable': 1}Passed
partial repair boundary #1{'exit': True, 'reachable': 3}{'exit': True, 'reachable': 2}Failed
partial repair boundary #2{'exit': True, 'reachable': 13}{'exit': True, 'reachable': 12}Failed
door corridor #1{'exit': True, 'reachable': 3}{'exit': True, 'reachable': 3}Passed
control #1{'exit': True, 'reachable': 8}{'exit': True, 'reachable': 8}Passed

SHA-256 / 201f5d35fb9960e1d5a2ca5fc10da98d4270e970f35c2e594801089f27499adb

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}),
  ('walled-in start #1', [['#.#', '#E#'], [0, 1], True], {'reachable': 2, 'exit': True}),
  ('fault site start seeding #1', [['~.#D##E'], [0, 6], False], {'reachable': 1, 'exit': True}),
  ('fault site start seeding #2',
   [['DD~.', '.#.#', '~.E.', '#.~~', 'D.~.'], [4, 3], False],
   {'reachable': 1, 'exit': False}),
  ('partial repair boundary #1', [['E', '.'], [1, 0], False], {'reachable': 2, 'exit': True}),
  ('partial repair boundary #2',
   [['~.D#.', 'D....', '#.D#E'], [1, 4], True],
   {'reachable': 12, 'exit': True}),
  ('door corridor #1', [['.DE'], [0, 0], False], {'reachable': 3, 'exit': True}),
  ('control #1', [['.E..', '.D..'], [0, 1], True], {'reachable': 8, 'exit': True})],
 [('diagonal gap only #1', [['.#', '#E'], [0, 0], False], {'reachable': 1, 'exit': False}),
  ('walled-in start #1', [['#.#', '#E#'], [0, 1], True], {'reachable': 2, 'exit': True}),
  ('fault site start seeding #1',
   [['DD~.', '.#.#', '~.E.', '#.~~', 'D.~.'], [4, 3], False],
   {'reachable': 1, 'exit': False}),
  ('fault site start seeding #2', [['E'], [0, 0], False], {'reachable': 1, '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}),
  ('control #1', [['.E..', '.D..'], [0, 1], True], {'reachable': 8, 'exit': True})],
 [('diagonal gap only #1', [['.#', '#E'], [0, 0], False], {'reachable': 1, 'exit': False}),
  ('walled-in start #1', [['#.#', '#E#'], [0, 1], True], {'reachable': 2, 'exit': True}),
  ('fault site start seeding #1', [['E', '#', '~', '.'], [0, 0], True], {'reachable': 1, 'exit': True}),
  ('fault site start seeding #2', [['E'], [0, 0], True], {'reachable': 1, 'exit': True}),
  ('partial repair boundary #1', [['E', '.', '.', '.', '~'], [2, 0], True], {'reachable': 5, '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}),
  ('control #1', [['E.D.', '...D'], [1, 0], True], {'reachable': 8, 'exit': True})],
 [('diagonal gap only #1', [['.#', '#E'], [0, 0], False], {'reachable': 1, 'exit': False}),
  ('walled-in start #1', [['#.#', '#E#'], [0, 1], True], {'reachable': 2, 'exit': True}),
  ('fault site start seeding #1',
   [['#D~.##', '.D.~E#', '.~...~', '....#.', '#.....'], [0, 3], False],
   {'reachable': 1, 'exit': False}),
  ('fault site start seeding #2', [['E', '#'], [0, 0], False], {'reachable': 1, 'exit': True}),
  ('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}),
  ('control #1',
   [['.##.', '.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}),
  ('walled-in start #1', [['#.#', '#E#'], [0, 1], True], {'reachable': 2, 'exit': True}),
  ('fault site start seeding #1',
   [['.~~~D', 'E....', '.~.#D', '~.~#~', '~~D~D', '.#~#.'], [5, 0], False],
   {'reachable': 1, 'exit': False}),
  ('fault site start seeding #2',
   [['D', '#', 'E', '#', '.', '.', '.'], [2, 0], True],
   {'reachable': 1, 'exit': True}),
  ('partial repair boundary #1',
   [['.', '.', '~', 'E', '.', '~'], [4, 0], True],
   {'reachable': 6, 'exit': True}),
  ('partial repair boundary #2', [['E.D..'], [0, 3], False], {'reachable': 5, 'exit': True}),
  ('door corridor #1', [['.DE'], [0, 0], False], {'reachable': 3, 'exit': True}),
  ('control #1', [['.E', '.D', 'D.'], [0, 0], True], {'reachable': 6, '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
diagonal gap only #1{'exit': False, 'reachable': 1}{'exit': False, 'reachable': 1}Passed
walled-in start #1{'exit': True, 'reachable': 2}{'exit': True, 'reachable': 2}Passed
fault site start seeding #1{'exit': True, 'reachable': 1}{'exit': True, 'reachable': 1}Passed
fault site start seeding #2{'exit': False, 'reachable': 1}{'exit': False, 'reachable': 1}Passed
partial repair boundary #1{'exit': True, 'reachable': 2}{'exit': True, 'reachable': 2}Passed
partial repair boundary #2{'exit': True, 'reachable': 12}{'exit': True, 'reachable': 12}Passed
door corridor #1{'exit': True, 'reachable': 3}{'exit': True, 'reachable': 3}Passed
control #1{'exit': True, 'reachable': 8}{'exit': True, 'reachable': 8}Passed

SHA-256 / aaebadf30408095963dcffffd23c261d17f4a8a58e80549b776d4f1d86c2ed92

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.927143+00:00.

Case digest / f53305a1ec871175759d5e3d42b2358a233d111ad4c934176ab2a8f9b7a41abe