ひとことで
四角い領域を縦か横に 2 つに分けることをくり返して、小さな区画に分ける方法です。分け方を二分木として覚えておくので、「どの区画とどの区画が兄弟か」がわかります。ダンジョン生成では、各区画に部屋を 1 つ置き、兄弟の区画どうしを通路でつなぐだけで、重ならない部屋が必ずすべてつながったマップができます。
ゲームでの使いどころ
- ダンジョン・建物の間取り：ローグライクの部屋と通路の配置。区画の大きさの下限で部屋の大きさを、分ける深さで部屋の数を調整できる。
- 都市の区画：街を大通りで分け、さらに小道で分けて、建物の敷地を作る。
- 描画と当たり判定：もともとは 3D の空間を平面で分けて、描く順番や見える範囲を高速に求めるための手法（『DOOM』『Quake』の BSP ツリー）。
- テクスチャアトラスの詰め込み：大きな画像を分けながら、小さな画像を隙間なく並べる。
しくみ
- 分ける：今の区画の長い方の辺を、真ん中あたり（ランダムに少しずらす）で 2 つに分けます。分けた 2 つを子として木に登録します。
- 止める：区画の短い方の辺が「最小の大きさ × 2」より小さい、または深さが上限に達したら、それ以上分けずに葉にします。
- 部屋を置く：各葉の区画の中に、少し余白を取って部屋を置きます。区画どうしが重ならないので、部屋も決して重なりません。
- 通路でつなぐ：木の深い所から順に、各節の左の子孫の部屋と右の子孫の部屋を 1 本の通路でつなぎます。根までたどれば、全部の部屋が 1 つにつながります。
長い方の辺を分けるのは、細長い区画（廊下のような部屋）を避けるためです。分ける位置を真ん中に寄せるほど、部屋の大きさがそろいます。
実装のポイント
- 分ける位置の範囲：最小の大きさより小さい区画ができないよう、切る位置を に制限します。
- 部屋の大きさのばらつき：区画いっぱいに部屋を作ると、格子のように規則的に見えます。区画の 60〜90% の範囲でランダムにすると自然です。
- 通路の形：部屋の中心どうしを L 字に結ぶのが簡単です。ほかの部屋を横切ってもよい作りなら、そのまま通路にできます。
- 輪を作る：木に沿ってつなぐだけだと、行き止まりの多い一本道になります。近い部屋どうしをいくつか追加でつなぐと、回り道のある遊びやすいマップになります（ドロネー分割で候補を作る方法もあります）。
つまずきやすい点
- 格子っぽさ：分割は必ず縦横の直線なので、部屋が格子状に並んで見えやすくなります。部屋の大きさや位置のばらつきを大きくします。
- 通路が部屋を突き抜ける：L 字の通路がほかの部屋を横切ると、意図しない出入口ができます。気になる場合は、通路を経路探索で壁を避けて引きます。
- 深さと最小の大きさの組み合わせ：深さを大きくしても、最小の大きさで止まるので、部屋の数には上限があります。
デモで試すこと
- 色つきの線が、分けた位置です（色は深さ）。範囲が 2 つ、4 つ、8 つ…と分かれていく様子と、右下の分割の木の対応を確かめてください。
- 分け終わると、木の葉（それ以上分けなかった区画）に部屋が置かれ、深い所から順に兄弟どうしが通路でつながります。
- 「区画の最小の大きさ」を小さくすると部屋が増え、大きくすると大部屋が少なくなります。
- 「分ける位置のばらつき」を 0 にすると、部屋の大きさがそろった規則的な配置になります。