2026-09-09 · design-roundup
Can You Guard "One Key, One Door"? — Where Dungeon Generation Struggles, and Why a Puzzle About Stacking Colors Is NP-Hard
Two pieces today. "Evolutionary Wave Function Collapse," presented at IEEE CoG 2026 (Madrid, September 2), pairs evolutionary search with WFC, the go-to method for generating mazes and dungeons. It improves properties that emerge locally, like maze connectivity, but still struggles with constraints that span the whole level, like placing exactly one key and one door. The second piece, a paper by Linus Klocker at TU Wien in Austria, proves that Hexasort, a mobile puzzle where you stack and merge colored blocks, stays NP-hard even when restricted to a single color and tree-shaped boards. One paper generates; the other proves difficulty mathematically. Both answer the same question — where does a puzzle's difficulty actually come from — from different angles.
