迷路生成
再帰バックトラッカー、プリム法、クラスカル法、ウィルソン法など、グリッドを削って任意の2点間に経路がちょうど1本だけの「完全迷路」を作るアルゴリズム群。
「完全」な迷路とは、グリッド上の全域木のことだ。すべてのセルがつながり、ループはなく、どの2セル間にも経路が1本だけ存在する。再帰バックトラッカー(深さ優先探索)は長く曲がりくねった通路を作り、プリム法やクラスカル法は短く枝分かれの多い迷路になる。ウィルソン法(ループ除去ランダムウォーク)は偏りのない迷路を生む。手法ごとに通路の雰囲気がはっきり違う。
ループや部屋が欲しければ、後から意図的に壁を壊せばよい。Jamis Buckの解説記事によって、これらのアルゴリズムはゲーム開発者の間で広く知られるようになった。