FAILURE MAP
← Case archive

FA-86536 / Procedural level generation constraints / Open access

BSP dungeon partition: Odd widths lose a column · case 01

Odd-width partitions leave an unassigned column.

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

ROOT CAUSE

The second child reuses the first child width.

THE FAILURE

The second child reuses the first child width.

Unsuccessful approach: Reserving a wall column shrinks the right child.

Case contract

Recursively split the rectangle while depth remains. An axis can be split when that side is >= 2*min_size; if neither can, it is a leaf. Split vertically when w > h, or when w == h at even remaining depth; if the chosen axis cannot be split use the other. The first child gets floor(side/2). Returns leaves [x, y, w, h] in left/top-first 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(x, y, w, h, min_size, depth):
    out = []
    def split(x, y, w, h, d):
        can_v = w >= 2 * min_size
        can_h = h >= 2 * min_size
        if d == 0 or not (can_v or can_h):
            out.append([x, y, w, h])
            return
        vertical = w > h or (w == h and d % 2 == 0)
        if vertical and not can_v:
            vertical = False
        elif not vertical and not can_h:
            vertical = True
        if vertical:
            half = w // 2
            split(x, y, half, h, d - 1)
            split(x + half, y, half, h, d - 1)
        else:
            half = h // 2
            split(x, y, w, half, d - 1)
            split(x, y + half, w, h - half, d - 1)
    split(x, y, w, h, depth)
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('odd width #1', [1, 1, 9, 4, 2, 1], [[1, 1, 4, 4], [5, 1, 5, 4]]),
  ('exactly splittable #1', [0, 0, 8, 3, 4, 1], [[0, 0, 4, 3], [4, 0, 4, 3]]),
  ('regression second child width #1', [1, 4, 9, 1, 3, 4], [[1, 4, 4, 1], [5, 4, 5, 1]]),
  ('regression second child width #2',
   [2, 3, 26, 3, 4, 3],
   [[2, 3, 6, 3], [8, 3, 7, 3], [15, 3, 6, 3], [21, 3, 7, 3]]),
  ('square at even depth #1', [0, 0, 10, 10, 2, 2], [[0, 0, 5, 5], [0, 5, 5, 5], [5, 0, 5, 5], [5, 5, 5, 5]]),
  ('partial repair boundary #1', [2, 3, 16, 10, 5, 1], [[2, 3, 8, 10], [10, 3, 8, 10]]),
  ('control #1', [3, 0, 14, 28, 4, 1], [[3, 0, 14, 14], [3, 14, 14, 14]]),
  ('control #2', [5, 1, 1, 10, 4, 2], [[5, 1, 1, 5], [5, 6, 1, 5]])],
 [('odd width #1', [1, 1, 9, 4, 2, 1], [[1, 1, 4, 4], [5, 1, 5, 4]]),
  ('square at even depth #1', [0, 0, 10, 10, 2, 2], [[0, 0, 5, 5], [0, 5, 5, 5], [5, 0, 5, 5], [5, 5, 5, 5]]),
  ('regression second child width #1',
   [2, 3, 26, 3, 4, 3],
   [[2, 3, 6, 3], [8, 3, 7, 3], [15, 3, 6, 3], [21, 3, 7, 3]]),
  ('regression second child width #2', [3, 4, 21, 6, 6, 2], [[3, 4, 10, 6], [13, 4, 11, 6]]),
  ('partial repair boundary #1', [2, 3, 16, 10, 5, 1], [[2, 3, 8, 10], [10, 3, 8, 10]]),
  ('regression second child width #3', [1, 4, 9, 1, 3, 4], [[1, 4, 4, 1], [5, 4, 5, 1]]),
  ('control #1', [5, 1, 24, 20, 4, 0], [[5, 1, 24, 20]]),
  ('control #2', [5, 5, 1, 15, 5, 4], [[5, 5, 1, 7], [5, 12, 1, 8]])],
 [('odd width #1', [1, 1, 9, 4, 2, 1], [[1, 1, 4, 4], [5, 1, 5, 4]]),
  ('exactly splittable #1', [0, 0, 8, 3, 4, 1], [[0, 0, 4, 3], [4, 0, 4, 3]]),
  ('regression second child width #1',
   [4, 0, 10, 3, 2, 4],
   [[4, 0, 2, 3], [6, 0, 3, 3], [9, 0, 2, 3], [11, 0, 3, 3]]),
  ('regression second child width #2',
   [2, 3, 15, 3, 3, 3],
   [[2, 3, 3, 3], [5, 3, 4, 3], [9, 3, 4, 3], [13, 3, 4, 3]]),
  ('regression second child width #3', [1, 4, 9, 1, 3, 4], [[1, 4, 4, 1], [5, 4, 5, 1]]),
  ('partial repair boundary #1',
   [5, 5, 10, 8, 4, 2],
   [[5, 5, 5, 4], [5, 9, 5, 4], [10, 5, 5, 4], [10, 9, 5, 4]]),
  ('control #1', [5, 0, 15, 27, 5, 0], [[5, 0, 15, 27]]),
  ('control #2',
   [3, 2, 2, 18, 2, 3],
   [[3, 2, 2, 2],
    [3, 4, 2, 2],
    [3, 6, 2, 2],
    [3, 8, 2, 3],
    [3, 11, 2, 2],
    [3, 13, 2, 2],
    [3, 15, 2, 2],
    [3, 17, 2, 3]])],
 [('odd width #1', [1, 1, 9, 4, 2, 1], [[1, 1, 4, 4], [5, 1, 5, 4]]),
  ('exactly splittable #1', [0, 0, 8, 3, 4, 1], [[0, 0, 4, 3], [4, 0, 4, 3]]),
  ('regression second child width #1',
   [3, 5, 26, 4, 5, 4],
   [[3, 5, 6, 4], [9, 5, 7, 4], [16, 5, 6, 4], [22, 5, 7, 4]]),
  ('regression second child width #2', [0, 3, 21, 1, 3, 1], [[0, 3, 10, 1], [10, 3, 11, 1]]),
  ('regression second child width #3',
   [2, 3, 26, 3, 4, 3],
   [[2, 3, 6, 3], [8, 3, 7, 3], [15, 3, 6, 3], [21, 3, 7, 3]]),
  ('regression second child width #4', [3, 4, 21, 6, 6, 2], [[3, 4, 10, 6], [13, 4, 11, 6]]),
  ('control #1', [4, 2, 16, 17, 2, 1], [[4, 2, 16, 8], [4, 10, 16, 9]]),
  ('control #2', [2, 0, 23, 3, 6, 0], [[2, 0, 23, 3]])],
 [('odd width #1', [1, 1, 9, 4, 2, 1], [[1, 1, 4, 4], [5, 1, 5, 4]]),
  ('square at even depth #1', [0, 0, 10, 10, 2, 2], [[0, 0, 5, 5], [0, 5, 5, 5], [5, 0, 5, 5], [5, 5, 5, 5]]),
  ('regression second child width #1',
   [5, 5, 9, 8, 3, 4],
   [[5, 5, 4, 4], [5, 9, 4, 4], [9, 5, 5, 4], [9, 9, 5, 4]]),
  ('regression second child width #2',
   [3, 3, 29, 24, 5, 3],
   [[3, 3, 7, 12],
    [10, 3, 7, 12],
    [3, 15, 7, 12],
    [10, 15, 7, 12],
    [17, 3, 7, 12],
    [24, 3, 8, 12],
    [17, 15, 7, 12],
    [24, 15, 8, 12]]),
  ('regression second child width #3',
   [4, 0, 10, 3, 2, 4],
   [[4, 0, 2, 3], [6, 0, 3, 3], [9, 0, 2, 3], [11, 0, 3, 3]]),
  ('partial repair boundary #1',
   [2, 1, 16, 5, 4, 2],
   [[2, 1, 4, 5], [6, 1, 4, 5], [10, 1, 4, 5], [14, 1, 4, 5]]),
  ('control #1', [1, 0, 13, 21, 2, 0], [[1, 0, 13, 21]]),
  ('control #2', [5, 5, 2, 28, 5, 1], [[5, 5, 2, 14], [5, 19, 2, 14]])]]
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
odd width #1[[1, 1, 4, 4], [5, 1, 4, 4]][[1, 1, 4, 4], [5, 1, 5, 4]]Failed
exactly splittable #1[[0, 0, 4, 3], [4, 0, 4, 3]][[0, 0, 4, 3], [4, 0, 4, 3]]Passed
regression second child width #1[[1, 4, 4, 1], [5, 4, 4, 1]][[1, 4, 4, 1], [5, 4, 5, 1]]Failed
regression second child width #2[[2, 3, 6, 3], [8, 3, 6, 3], [15, 3, 6, 3], [21, 3, 6, 3]][[2, 3, 6, 3], [8, 3, 7, 3], [15, 3, 6, 3], [21, 3, 7, 3]]Failed
square at even depth #1[[0, 0, 5, 5], [0, 5, 5, 5], [5, 0, 5, 5], [5, 5, 5, 5]][[0, 0, 5, 5], [0, 5, 5, 5], [5, 0, 5, 5], [5, 5, 5, 5]]Passed
partial repair boundary #1[[2, 3, 8, 10], [10, 3, 8, 10]][[2, 3, 8, 10], [10, 3, 8, 10]]Passed
control #1[[3, 0, 14, 14], [3, 14, 14, 14]][[3, 0, 14, 14], [3, 14, 14, 14]]Passed
control #2[[5, 1, 1, 5], [5, 6, 1, 5]][[5, 1, 1, 5], [5, 6, 1, 5]]Passed

SHA-256 / 02e3cd82ffdf5a14493083cefcd2fb888a4d6a51201be1b9cc5a61fb8cb78bca

2 / The unsuccessful fix

Exit 1
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(x, y, w, h, min_size, depth):
    out = []
    def split(x, y, w, h, d):
        can_v = w >= 2 * min_size
        can_h = h >= 2 * min_size
        if d == 0 or not (can_v or can_h):
            out.append([x, y, w, h])
            return
        vertical = w > h or (w == h and d % 2 == 0)
        if vertical and not can_v:
            vertical = False
        elif not vertical and not can_h:
            vertical = True
        if vertical:
            half = w // 2
            split(x, y, half, h, d - 1)
            split(x + half + 1, y, w - half - 1, h, d - 1)
        else:
            half = h // 2
            split(x, y, w, half, d - 1)
            split(x, y + half, w, h - half, d - 1)
    split(x, y, w, h, depth)
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('odd width #1', [1, 1, 9, 4, 2, 1], [[1, 1, 4, 4], [5, 1, 5, 4]]),
  ('exactly splittable #1', [0, 0, 8, 3, 4, 1], [[0, 0, 4, 3], [4, 0, 4, 3]]),
  ('regression second child width #1', [1, 4, 9, 1, 3, 4], [[1, 4, 4, 1], [5, 4, 5, 1]]),
  ('regression second child width #2',
   [2, 3, 26, 3, 4, 3],
   [[2, 3, 6, 3], [8, 3, 7, 3], [15, 3, 6, 3], [21, 3, 7, 3]]),
  ('square at even depth #1', [0, 0, 10, 10, 2, 2], [[0, 0, 5, 5], [0, 5, 5, 5], [5, 0, 5, 5], [5, 5, 5, 5]]),
  ('partial repair boundary #1', [2, 3, 16, 10, 5, 1], [[2, 3, 8, 10], [10, 3, 8, 10]]),
  ('control #1', [3, 0, 14, 28, 4, 1], [[3, 0, 14, 14], [3, 14, 14, 14]]),
  ('control #2', [5, 1, 1, 10, 4, 2], [[5, 1, 1, 5], [5, 6, 1, 5]])],
 [('odd width #1', [1, 1, 9, 4, 2, 1], [[1, 1, 4, 4], [5, 1, 5, 4]]),
  ('square at even depth #1', [0, 0, 10, 10, 2, 2], [[0, 0, 5, 5], [0, 5, 5, 5], [5, 0, 5, 5], [5, 5, 5, 5]]),
  ('regression second child width #1',
   [2, 3, 26, 3, 4, 3],
   [[2, 3, 6, 3], [8, 3, 7, 3], [15, 3, 6, 3], [21, 3, 7, 3]]),
  ('regression second child width #2', [3, 4, 21, 6, 6, 2], [[3, 4, 10, 6], [13, 4, 11, 6]]),
  ('partial repair boundary #1', [2, 3, 16, 10, 5, 1], [[2, 3, 8, 10], [10, 3, 8, 10]]),
  ('regression second child width #3', [1, 4, 9, 1, 3, 4], [[1, 4, 4, 1], [5, 4, 5, 1]]),
  ('control #1', [5, 1, 24, 20, 4, 0], [[5, 1, 24, 20]]),
  ('control #2', [5, 5, 1, 15, 5, 4], [[5, 5, 1, 7], [5, 12, 1, 8]])],
 [('odd width #1', [1, 1, 9, 4, 2, 1], [[1, 1, 4, 4], [5, 1, 5, 4]]),
  ('exactly splittable #1', [0, 0, 8, 3, 4, 1], [[0, 0, 4, 3], [4, 0, 4, 3]]),
  ('regression second child width #1',
   [4, 0, 10, 3, 2, 4],
   [[4, 0, 2, 3], [6, 0, 3, 3], [9, 0, 2, 3], [11, 0, 3, 3]]),
  ('regression second child width #2',
   [2, 3, 15, 3, 3, 3],
   [[2, 3, 3, 3], [5, 3, 4, 3], [9, 3, 4, 3], [13, 3, 4, 3]]),
  ('regression second child width #3', [1, 4, 9, 1, 3, 4], [[1, 4, 4, 1], [5, 4, 5, 1]]),
  ('partial repair boundary #1',
   [5, 5, 10, 8, 4, 2],
   [[5, 5, 5, 4], [5, 9, 5, 4], [10, 5, 5, 4], [10, 9, 5, 4]]),
  ('control #1', [5, 0, 15, 27, 5, 0], [[5, 0, 15, 27]]),
  ('control #2',
   [3, 2, 2, 18, 2, 3],
   [[3, 2, 2, 2],
    [3, 4, 2, 2],
    [3, 6, 2, 2],
    [3, 8, 2, 3],
    [3, 11, 2, 2],
    [3, 13, 2, 2],
    [3, 15, 2, 2],
    [3, 17, 2, 3]])],
 [('odd width #1', [1, 1, 9, 4, 2, 1], [[1, 1, 4, 4], [5, 1, 5, 4]]),
  ('exactly splittable #1', [0, 0, 8, 3, 4, 1], [[0, 0, 4, 3], [4, 0, 4, 3]]),
  ('regression second child width #1',
   [3, 5, 26, 4, 5, 4],
   [[3, 5, 6, 4], [9, 5, 7, 4], [16, 5, 6, 4], [22, 5, 7, 4]]),
  ('regression second child width #2', [0, 3, 21, 1, 3, 1], [[0, 3, 10, 1], [10, 3, 11, 1]]),
  ('regression second child width #3',
   [2, 3, 26, 3, 4, 3],
   [[2, 3, 6, 3], [8, 3, 7, 3], [15, 3, 6, 3], [21, 3, 7, 3]]),
  ('regression second child width #4', [3, 4, 21, 6, 6, 2], [[3, 4, 10, 6], [13, 4, 11, 6]]),
  ('control #1', [4, 2, 16, 17, 2, 1], [[4, 2, 16, 8], [4, 10, 16, 9]]),
  ('control #2', [2, 0, 23, 3, 6, 0], [[2, 0, 23, 3]])],
 [('odd width #1', [1, 1, 9, 4, 2, 1], [[1, 1, 4, 4], [5, 1, 5, 4]]),
  ('square at even depth #1', [0, 0, 10, 10, 2, 2], [[0, 0, 5, 5], [0, 5, 5, 5], [5, 0, 5, 5], [5, 5, 5, 5]]),
  ('regression second child width #1',
   [5, 5, 9, 8, 3, 4],
   [[5, 5, 4, 4], [5, 9, 4, 4], [9, 5, 5, 4], [9, 9, 5, 4]]),
  ('regression second child width #2',
   [3, 3, 29, 24, 5, 3],
   [[3, 3, 7, 12],
    [10, 3, 7, 12],
    [3, 15, 7, 12],
    [10, 15, 7, 12],
    [17, 3, 7, 12],
    [24, 3, 8, 12],
    [17, 15, 7, 12],
    [24, 15, 8, 12]]),
  ('regression second child width #3',
   [4, 0, 10, 3, 2, 4],
   [[4, 0, 2, 3], [6, 0, 3, 3], [9, 0, 2, 3], [11, 0, 3, 3]]),
  ('partial repair boundary #1',
   [2, 1, 16, 5, 4, 2],
   [[2, 1, 4, 5], [6, 1, 4, 5], [10, 1, 4, 5], [14, 1, 4, 5]]),
  ('control #1', [1, 0, 13, 21, 2, 0], [[1, 0, 13, 21]]),
  ('control #2', [5, 5, 2, 28, 5, 1], [[5, 5, 2, 14], [5, 19, 2, 14]])]]
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
odd width #1[[1, 1, 4, 4], [6, 1, 4, 4]][[1, 1, 4, 4], [5, 1, 5, 4]]Failed
exactly splittable #1[[0, 0, 4, 3], [5, 0, 3, 3]][[0, 0, 4, 3], [4, 0, 4, 3]]Failed
regression second child width #1[[1, 4, 4, 1], [6, 4, 4, 1]][[1, 4, 4, 1], [5, 4, 5, 1]]Failed
regression second child width #2[[2, 3, 6, 3], [9, 3, 6, 3], [16, 3, 6, 3], [23, 3, 5, 3]][[2, 3, 6, 3], [8, 3, 7, 3], [15, 3, 6, 3], [21, 3, 7, 3]]Failed
square at even depth #1[[0, 0, 5, 5], [0, 5, 5, 5], [6, 0, 4, 5], [6, 5, 4, 5]][[0, 0, 5, 5], [0, 5, 5, 5], [5, 0, 5, 5], [5, 5, 5, 5]]Failed
partial repair boundary #1[[2, 3, 8, 10], [11, 3, 7, 10]][[2, 3, 8, 10], [10, 3, 8, 10]]Failed
control #1[[3, 0, 14, 14], [3, 14, 14, 14]][[3, 0, 14, 14], [3, 14, 14, 14]]Passed
control #2[[5, 1, 1, 5], [5, 6, 1, 5]][[5, 1, 1, 5], [5, 6, 1, 5]]Passed

SHA-256 / f276458ff4ad41f1f4282a52681721e446832b3e7a753d9df80ab6d1460575ae

HELD IN THE MEMBER ARCHIVE

The verified repair and its recorded checks are member-only.

This mechanism has 8 recorded checks per implementation. The open-access tier publishes the failure and the unsuccessful fix; the repaired source that passes every check, and the observations that prove it, are available to members.

Every case sharing this mechanism uses the same contract and the same repair, so this one record is held back for all of them.

Member access is invitation-based. Sign in with your invited account to inspect the repair.

Sign in to the archive ↗

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

Case digest / d87a630fe587efdc3c650a01666aad0d81efc5f0d7822127465042b4eb6f6968