Following, springs & flocks

Flow-Field Following

フローフィールド追従

空間に置いた矢印に沿って粒子や群集を進める。

9 / 10

Interactive demo

Preparing the demo…

Flow-Field Following

Drag to orbit, Ctrl/⌘ + scroll to zoom. Use two fingers on touch screens.

This explanation is currently available in Japanese.

ひとことで

空間を格子に分け、各マスに「ここに来たらこの向きへ進め」という矢印(ベクトル)を書き込んでおき、エージェントは自分のいるマスの矢印を読んで進む方法です。矢印の場を 1 回作ってしまえば、何百・何千体いても全員がそれを参照するだけで済むため、大群の移動や、風・水流に流される表現に向いています。

ゲームでの使いどころ

  • RTS・タワーディフェンスの大群移動:数百のユニットが同じ目的地を目指すとき、1 体ずつ経路探索するかわりに、目的地からの流れ場を 1 回だけ作ります(Supreme Commander 2 で有名になった手法)。
  • 群集シミュレーション:スタジアムからの退場、避難誘導、街を行き交う群衆。
  • 風・水流・磁場:落ち葉や雪が風に流される、川に浮かぶ物が流される、パーティクルが力場に沿って動く。
  • AI の影響マップ:危険度や魅力度のマップの勾配を流れ場として使う。

しくみ

目的地への流れ場は 2 段階で作ります。

  1. 距離場(積分場):目的地のマスから幅優先探索(またはダイクストラ法)で広げ、各マスの「目的地までの歩数」を求める。壁のマスは通さない。
  2. 方向場:各マスについて、周囲 8 マスのうち最も歩数が小さいマスの方向を矢印として書き込む。

これで、どのマスからでも矢印をたどれば、壁を回り込む最短経路で目的地に着きます。経路探索は目的地ごとに 1 回で、エージェントの数に依存しません。

風などの場は、ノイズやシミュレーション結果から直接ベクトルを作ります。カールノイズを使えば、粒子が吸い込み点に溜まらない自然な流れになります。

エージェント側は、自分のマスの矢印(またはバイリニア補間した値)を希望速度としてシークするだけです。

実装のポイント

  • 斜め移動と角:斜めのマスへ向かう矢印は、両隣のマスが通れる場合だけ許可します。そうしないと壁の角をすり抜けようとして引っかかります。
  • 大きな地図は分割:マップ全体の流れ場は重いので、区画(セクター)ごとに作り、区画間は抽象グラフの経路探索でつなぐ階層化がよく使われます。
  • 局所回避と組み合わせる:流れ場だけではエージェント同士が重なります。分離や ORCA のような局所回避を足します。

つまずきやすい点

  • 格子の解像度:マスが粗いと細い通路を表現できず、細かいとメモリと計算が増えます。エージェントの大きさ程度が目安です。
  • 目的地が多い場合:目的地ごとに流れ場が必要なので、全員の行き先がばらばらな状況では向きません。その場合は個別の経路探索(A*)が適しています。
  • 動く障害物:障害物が動くたびに流れ場を作り直す必要があります。変化した周辺だけを更新する工夫が必要です。

デモで試すこと

  1. 「目的地への流れ」では、420 体のエージェントが矢印に従い、壁を回り込んで黄色い目的地へ集まります。
  2. 床をクリックして目的地を移すと、流れ場がその場で作り直され、全員の進路が一斉に変わります。
  3. 「ノイズの風」に切り替えると、同じ仕組みで風に流される粒子のような動きになります。

References

Spring-It-On ↗

A general reference for this subcategory.