Poisson Disk Sampling

This explanation is currently available in Japanese.

ひとことで

点をランダムに置きながら、どの 2 点も決めた距離 $r$ より近づかないようにする置き方です。ただの乱数で木を植えると、2 本が重なったり、何もない大きな空き地ができたりします。ポアソンディスク分布では、点どうしがほどよく離れつつ、規則的な格子のようにも見えない、自然な並びになります。森の木、草むら、岩、敵の出現位置など、「ばらばらだけど偏らない」配置が欲しいときの定番です。

ゲームでの使いどころ

• 木・岩・草の配置：オープンワールドの植生を、重ならず、すき間も少なく並べる。密度マスクによる散布と組み合わせて、場所ごとに密度を変える。
• 敵やアイテムの出現位置：宝箱や敵が 1 か所に固まらないよう、最小距離を守って選ぶ。
• ボロノイの種点：ボロノイ破砕や地域の区分けの種点にすると、大きさのそろった自然な区画になる。
• 標本点の配置：ぼかしや影の柔らかさを求めるときの標本点。偏りが少ないので、少ない点でもむらが目立ちにくい（ブルーノイズの一種）。

しくみ

ブリッドソンの方法（Bridson 2007）が速くて簡単です。

1. 格子を用意：一辺 $r / \sqrt{2}$ の格子を作ります。この大きさだと、1 つのセルに入る点は多くても 1 つです。
2. 最初の点：領域の中にでたらめに 1 点置き、「アクティブな点」のリストに入れます。
3. 周りに候補を試す：アクティブな点を 1 つ選び、その点から距離 $r$〜$2r$ の輪の中に、候補を最大 $k$ 個（30 前後）ランダムに作ります。
4. 近すぎないか調べる：候補の周りの格子セル（5 × 5 くらい）だけを見て、距離 $r$ より近い点がなければ採用し、アクティブに加えます。
5. 成長を終える：$k$ 個試してもすべて近すぎたら、その点の周りはもう埋まったとみなし、アクティブから外します。
6. アクティブがなくなるまで 3〜5 をくり返します。

格子のおかげで、近さの判定は周りの数セルを見るだけで済み、点の数 $n$ に比例した時間 $O(n)$ で終わります。

実装のポイント

• 場所で距離を変える：ノイズやマスクで $r$ を場所ごとに変えると、密な森とまばらな林を 1 回で作れます。判定には、2 点の $r$ の大きい方を使います（格子は最小の $r$ に合わせます）。
• 試行回数 $k$：小さいと、まだすき間があるのに早く止まります。大きいとすき間が減りますが遅くなります。30 前後がよく使われます。
• 前もって作ってタイル状に並べる：広い地形では、端がつながるポアソンディスクのタイルを作っておき、くり返し並べる方法もあります（くり返しが目立たないようワンタイルと組み合わせることも）。

つまずきやすい点

• 格子の大きさの間違い：セルを $r$ にすると、1 セルに複数の点が入り、判定が漏れます。$r / \sqrt{2}$ にします。
• 境界の扱い：領域の外にはみ出した候補を捨てるのを忘れると、端に点が貼り付きます。
• 決定的な結果が欲しい：ネットワーク対戦や保存データの再現には、シード付きの乱数を使い、同じ順番で処理します。

デモで試すこと

1. 黄色いアクティブな点の周りに候補が試され、赤い候補（近すぎて捨てたもの）と、採用された木が増えていきます。アクティブな点が外へ外へと広がっていく様子を見てください。
2. 「近寄れない範囲」を表示すると、青い円どうしが重ならず、すき間なく並ぶことがわかります。
3. 「でたらめ」に切り替えると、木が重なったり、大きな空き地ができたりします。
4. 「場所で距離を変える」では、ノイズに合わせて密な森とまばらな林ができます。「試行回数 k」を 1〜3 にすると、すき間が残ったまま止まることも確かめてください。