Closed78

Boidsの実装について調査となんか作りたい

にー兄さんにー兄さん

boidsでなんか作りたいなぁと思い始めてきて、ちょっと調べていたんでめも

にー兄さんにー兄さん

Boids、一定範囲内で以下の計算をするということが分かった

  • 分離
  • 結合
  • 整列

アルゴリズムとしてはそこまで複雑ではないんだなぁ

にー兄さんにー兄さん

いまやりたいこととして、Unity VFX GraphでBoidsシミュレーションをしたいなぁ
現状は近傍探索の機能が無いので、ComputeShaderを組み合わせる必要があると思う

にー兄さんにー兄さん

ComputeShaderで計算した結果をテクスチャ成りGraphicsBufferに書き込み、それをPropertyBinder経由でVFX Graphに渡すというイメージ

にー兄さんにー兄さん

クリエイティブコーディングの教科書の人がCodepenを公開してくださっていたのでコードが見れてよいな

jsコード全文
let vehicles;

function setup() {
  createCanvas(windowWidth, windowHeight);

  vehicles = [];
  for (let i = 0; i < 50; i++) {
    const position = createVector(random(width), random(height));
    const velocity = p5.Vector.random2D();
    velocity.setMag(random(2, 4));
    const maxSpeed = 4;
    const maxForce = 2;
    vehicles.push(Vehicle.create(position, velocity, maxSpeed, maxForce));
  }
}

function draw() {
  clear();

  vehicles.forEach((v) => {
    Vehicle.flock(v, vehicles);
    Vehicle.update(v);
    Vehicle.draw(v, "#aaa");
  });
}

const Vehicle = {
  create: function (position, velocity, maxSpeed, maxForce) {
    return { position, velocity, acceleration: createVector(), maxSpeed, maxForce };
  },

  update: function (v) {
    v.acceleration.limit(v.maxForce);
    v.velocity.add(v.acceleration);
    v.velocity.limit(v.maxSpeed);
    v.position.add(v.velocity);
    v.acceleration.set(0);

    Vehicle.adjustEdge(v);
  },

  adjustEdge: function (v) {
    if (v.position.x < 0) {
      v.position.x = 0;
      v.velocity.x *= -1;
    } else if (v.position.x >= width) {
      v.position.x = width - 1;
      v.velocity.x *= -1;
    }

    if (v.position.y < 0) {
      v.position.y = 0;
      v.velocity.y *= -1;
    } else if (v.position.y >= height) {
      v.position.y = height - 1;
      v.velocity.y *= -1;
    }
  },

  draw: function (v, strokeColor) {
    push();
    noFill();
    strokeWeight(2);
    stroke(strokeColor);
    translate(v.position);
    rotate(v.velocity.heading());
    beginShape();
    const r = 8;
    vertex(r * 2, 0);
    vertex(-r, r);
    vertex(-r, -r);
    endShape(CLOSE);
    pop();
  },

  seek: function (v, target) {
    const tv = p5.Vector.sub(target, v.position);
    tv.limit(v.maxSpeed);
    const force = p5.Vector.sub(tv, v.velocity);
    v.acceleration.add(force);
  },

  flee: function (v, target) {
    const tv = p5.Vector.sub(target, v.position);
    tv.limit(v.maxSpeed);
    const force = p5.Vector.sub(tv, v.velocity);
    v.acceleration.sub(force);
  },

  inSight(v, other) {
    const d = dist(v.position.x, v.position.y, other.position.x, other.position.y);
    return d < 100;
  },

  align(v, vehicles) {
    const avgVel = createVector();
    let n = 0;
    for (const other of vehicles) {
      if (v === other || !Vehicle.inSight(v, other)) continue;
      avgVel.add(other.velocity);
      n++;
    }
    if (n > 0) {
      avgVel.div(n);
      avgVel.limit(v.maxSpeed);
      v.acceleration.add(p5.Vector.sub(avgVel, v.velocity));
    }
  },

  separation(v, boids) {
    for (const other of boids) {
      if (v === other || !Vehicle.inSight(v, other)) continue;
      const d = dist(v.position.x, v.position.y, other.position.x, other.position.y);
      if (d < 50) {
        Vehicle.flee(v, other.position);
      }
    }
  },

  cohesion(v, boids) {
    let avgPos = createVector();
    let n = 0;
    for (const other of boids) {
      if (v === other || !Vehicle.inSight(v, other)) continue;
      avgPos.add(other.position);
      n++;
    }
    if (n > 0) {
      avgPos.div(n);
      Vehicle.seek(v, avgPos);
    }
  },

  flock(v, boids) {
    Vehicle.align(v, boids);
    Vehicle.cohesion(v, boids);
    Vehicle.separation(v, boids);
  },
};
にー兄さんにー兄さん

気になってたこととして、Bunding(境界)の処理ってどうしてるんだろうって思ったら
境界にたどり着いたらその方向のpositionを境界外に行かないようにして、velocityを反転させていた

  adjustEdge: function (v) {
    if (v.position.x < 0) {
      v.position.x = 0;
      v.velocity.x *= -1;
    } else if (v.position.x >= width) {
      v.position.x = width - 1;
      v.velocity.x *= -1;
    }

    if (v.position.y < 0) {
      v.position.y = 0;
      v.velocity.y *= -1;
    } else if (v.position.y >= height) {
      v.position.y = height - 1;
      v.velocity.y *= -1;
    }
  },
にー兄さんにー兄さん

vehicleはposition、velocity、accを持つ

  create: function (position, velocity, maxSpeed, maxForce) {
    return {
      position,
      velocity,
      acceleration: createVector(),
      maxSpeed,
      maxForce,
    };
にー兄さんにー兄さん

createVector関数はたぶんp5.jsのやつかな
accは生成時はゼロベクトルが入っているっぽい

にー兄さんにー兄さん

コードリーディングができたので、メソッドにコメントを付けた

コメント付きjsコード全文
コメントを付けた
let vehicles;

function setup() {
  createCanvas(windowWidth, windowHeight);

  vehicles = [];
  for (let i = 0; i < 50; i++) {
    const position = createVector(random(width), random(height));
    const velocity = p5.Vector.random2D();
    velocity.setMag(random(2, 4));
    const maxSpeed = 4;
    const maxForce = 2;
    vehicles.push(Vehicle.create(position, velocity, maxSpeed, maxForce));
  }
}

function draw() {
  clear();

  vehicles.forEach((v) => {
    Vehicle.flock(v, vehicles);
    Vehicle.update(v);
    Vehicle.draw(v, "#aaa");
  });
}

const Vehicle = {
  create: function (position, velocity, maxSpeed, maxForce) {
    return {
      position,
      velocity,
      acceleration: createVector(),
      maxSpeed,
      maxForce,
    };
  },

  /**
   * Update関数。
   * 加速度を速度に、速度を位置に加算している。
   * また速度制限や境界処理などを行っている。
   * ここの中でpos,velocity,accなどが最終決定されそう。
   * @param {Vehilcle} v
   */
  update: function (v) {
    v.acceleration.limit(v.maxForce);
    v.velocity.add(v.acceleration);
    v.velocity.limit(v.maxSpeed);
    v.position.add(v.velocity);
    v.acceleration.set(0);

    Vehicle.adjustEdge(v);
  },

  /**
   * 境界にたどり着いたときに、
   * その境界よりも大きくならないようにPositionを調整し
   * velocityを反転させている
   * @param {Vehicle} v
   */
  adjustEdge: function (v) {
    if (v.position.x < 0) {
      v.position.x = 0;
      v.velocity.x *= -1;
    } else if (v.position.x >= width) {
      v.position.x = width - 1;
      v.velocity.x *= -1;
    }

    if (v.position.y < 0) {
      v.position.y = 0;
      v.velocity.y *= -1;
    } else if (v.position.y >= height) {
      v.position.y = height - 1;
      v.velocity.y *= -1;
    }
  },

  /**
   * 一個一個のVehicleを描画するための関数
   * @param {Vehicle} v Vehicleオブジェクト
   * @param {string} strokeColor 色
   */
  draw: function (v, strokeColor) {
    push();
    noFill();
    strokeWeight(2);
    stroke(strokeColor);
    translate(v.position);
    rotate(v.velocity.heading());
    beginShape();
    const r = 8;
    vertex(r * 2, 0);
    vertex(-r, r);
    vertex(-r, -r);
    endShape(CLOSE);
    pop();
  },

  /**
   * targetの方向にVehicleを近づける処理。
   * 自身からtargetに向かうベクトルと
   * 自身の速度ベクトルの差を
   * 自身の加速度に加えることで近づくような処理をしている
   * @param {Vehicle} v 
   * @param {Vector2D} target 
   */
  seek: function (v, target) {
    const tv = p5.Vector.sub(target, v.position);
    tv.limit(v.maxSpeed);
    const force = p5.Vector.sub(tv, v.velocity);
    v.acceleration.add(force);
  },

  /**
   * 特定のVehicleを避ける処理。
   * (自身からtargetへのベクトル)から
   * 自身のVelocityの差を取り
   * さらにそれをaccから差し引くという処理。
   * これによって相手のVehicleを避けるような加速度が加わる
   * @param {Vehicle} v 
   * @param {Vector2D} target 
   */
  flee: function (v, target) {
    const tv = p5.Vector.sub(target, v.position);
    tv.limit(v.maxSpeed);
    const force = p5.Vector.sub(tv, v.velocity);
    v.acceleration.sub(force);
  },

  /**
   * 範囲内にあるかの判定。
   * 関数内では距離が100未満であれば範囲内と判定する。
   * @param {Vehicle} v 
   * @param {Vehicle} other 
   * @returns 
   */
  inSight(v, other) {
    const d = dist(
      v.position.x,
      v.position.y,
      other.position.x,
      other.position.y
    );
    return d < 100;
  },

  /**
   * 整列。
   * 範囲内の自分以外のvehicleに対して
   * velocityの平均を算出し
   * 自信のvelocityとの差分をaccに加算する
   * @param {Vehicle} v 
   * @param {Vehicle[]} vehicles 
   */
  align(v, vehicles) {
    const avgVel = createVector();
    let n = 0;
    for (const other of vehicles) {
      if (v === other || !Vehicle.inSight(v, other)) continue;
      avgVel.add(other.velocity);
      n++;
    }
    if (n > 0) {
      avgVel.div(n);
      avgVel.limit(v.maxSpeed);
      v.acceleration.add(p5.Vector.sub(avgVel, v.velocity));
    }
  },

  /**
   * 分離。
   * 範囲内の自分以外のvehicleに対して
   * 距離が近かった場合に避けるように動作する
   * @param {Vehicle} v 
   * @param {Vehicle[]} boids 
   */
  separation(v, boids) {
    for (const other of boids) {
      if (v === other || !Vehicle.inSight(v, other)) continue;
      const d = dist(
        v.position.x,
        v.position.y,
        other.position.x,
        other.position.y
      );
      if (d < 50) {
        Vehicle.flee(v, other.position);
      }
    }
  },

  /**
   * 結合。
   * 範囲内の自分以外のpositionの平均ベクトルへseekする
   * @param {Vehicle} v 
   * @param {Vehicle[]} boids 
   */
  cohesion(v, boids) {
    let avgPos = createVector();
    let n = 0;
    for (const other of boids) {
      if (v === other || !Vehicle.inSight(v, other)) continue;
      avgPos.add(other.position);
      n++;
    }
    if (n > 0) {
      avgPos.div(n);
      Vehicle.seek(v, avgPos);
    }
  },

  /**
   * Boids処理の3要素である
   * - 整列
   * - 結合
   * - 分離
   * を順番に実行するだけの関数
   * @param {Vehicle} v 
   * @param {Vehicle[]} boids 
   */
  flock(v, boids) {
    Vehicle.align(v, boids);
    Vehicle.cohesion(v, boids);
    Vehicle.separation(v, boids);
  },
};
にー兄さんにー兄さん

まずはいったん最速でCPUべーすのBoidsシミュレーションをやってみる
なるべくComputeShaderに移行しやすい形にしたいので、Boidsのデータを配列で一貫して扱い、
ロジックは個別の処理に切り分けていきたい

にー兄さんにー兄さん

今疑問に思ったのが、毎フレーム処理する時にdeltaTime的な時間スケーリングはしなくてよいのかという点

にー兄さんにー兄さん

たしかクリエイティブコーディングの教科書のサンプルにはそんな感じのものはなかった気がする
なんでなくて動くんだ?
徐々に近づいていく処理というのがホントに微笑変化だからか?

にー兄さんにー兄さん

そういえばクリエイティブコーディングの教科書のコードでは
アップデートの時に元の配列を壊してしまわないか(つまり並列処理しているのに途中でpositionを変えてしまってはいけない)気になったんだけど、
いったんすべてのaccだけを更新して、そのあと一斉にそのaccからv,pを算出するようなコードになっていた
なるほどなぁ

にー兄さんにー兄さん

クリエイティブコーディングの教科書のコードだと
fleeだけfor分の中にあるんだな

にー兄さんにー兄さん

いったん、CPUベースの整列処理だけ実行できるようにしてみた

https://youtu.be/QUoIzGPV4_4

にー兄さんにー兄さん

どんどん値が小さくなってしまうのは、これはそういうもんっぽいな
ためしにクリエイティブコーディングの教科書のサンプルで、separationとcohesionをスキップしてみたら同じような現象が起きた

にー兄さんにー兄さん

一旦この、MonoBehaviourで作ってプレハブをインスタンス化して作った最小限のものをベンチマークにしつつ、最終的にはCompuetShaderで計算してVFX Graphで表示するところまでをやっていく

にー兄さんにー兄さん

次はCPUベースの処理をGraphicsBufferに落としてみて、それをVFX Graphで表示してみる
それができたらGraphicsBuffer→VFX Graphの動作検証ができるので
そこから最後にGraphicsBuffer生成をComputeShaderに置き換えればよい

にー兄さんにー兄さん

こんな感じでBoidsDataという構造体を作り、BoidsCoreのロジックをこれ用に置き換えていた

にー兄さんにー兄さん

Sample Graphics BufferノードでBoidsDataをサンプリングできそうな感じになってる!

にー兄さんにー兄さん

Property Binderを作成してVFXGraphにBoidsのデータを渡す

public override void UpdateBinding(VisualEffect component)
{
    component.SetInt(boidsCountProperty, boidsCount);

    _boidsCore.Update(Time.deltaTime * timeScale, new UpdateParams
    {
        InsightRange = insightRange,
        MaxVelocity = maxVelocity,
        MaxAcceleration = maxAcceleration,
        BoundarySize = boundarySize,
        FleeThreshold = fleeThreshold,
        AlignWeight = alignWeight,
        SeparationWeight = separationWeight,
        CohesionWeight = cohesionWeight
    });

    if (_boidsGraphicsBuffer == null)
    {
        return;
    }

    _boidsGraphicsBuffer.SetData(_boidsCore.Boids);
    component.SetGraphicsBuffer(boidsBufferProperty, _boidsGraphicsBuffer);
}

にー兄さんにー兄さん

ComputeBufferではなくGraphicsBufferを使おうねという記事
https://zenn.dev/fuqunaga/articles/6f572cd4d526fc107dcd

これずっと頭の中にあって、GraphicsBufferを使うようにしていたんだけど
変わった点って頂点シェーダとして使えるようになったとか、命名が変更になったとか
そんな感じなんだな

機能的には上記だけど、ComputeShaderは廃止予定なので移行したほうが良さそう
昨日としてはそこまで変わらないという理解を得た

にー兄さんにー兄さん

お、CompueteShaderと和解できた

にー兄さんにー兄さん

これは指定したVector3ですべてのGraphicsBuffer要素を埋めるというComputeShader
要素数100個でやってみた

にー兄さんにー兄さん

10,000個でもできた
dispathに指定する数って制限なかったっけなって思ったけどどうなんだろう

にー兄さんにー兄さん

1,000,000でやったらこんなメッセージが
スレッドグループの数は65535が上限らしい

にー兄さんにー兄さん

さきほどはスレッドが4でスレッドグループが250,000だったため65535を超えてしまっていた
これをスレッド数64にしたらスレッドグループは15,625になるわね

にー兄さんにー兄さん

これでComputeShader実装を進めるにあたり不安点はないかなと思いつつ、
計算結果を並列で入力したバッファに書き込んで大丈夫なのかという不安がある

Unity-jpの実装では入力バッファに並列して書き込んでいるっぽいんだけど、
これって大丈夫なのかな

https://github.com/unity3d-jp/BoidComputeShader/blob/main/Assets/Boid/Boid/Boid.compute

にー兄さんにー兄さん

いったん入力と処理結果を同じバッファに書き込むことにして、
問題がありそうであればバッファを分けよう

にー兄さんにー兄さん

今回の実装、if文による分岐が頻出だけど、パフォーマンスは大丈夫なんかな

にー兄さんにー兄さん

BoidsのCompueteShaderで、境界処理だけを実装したものを作成した
これでいったん全体を実行しても問題はないはず

また、BoidsBinderに関してもBoidsCore.csではなくComputeShaderに差し替えたバージョンを作成中(WIP)
初期化とUpdateの関数のコードを埋めれば実行できそう

にー兄さんにー兄さん

ここからの実装て順としては、

  1. BoidsBinderの実装を一通り完成させる
  2. 実行してみて、境界処理だけは知っている状態を動作確認する
    この時にBoidsCountを増やしてみてパフォーマンスを確認できればSuperCool
  3. 整列・分離・結合の処理をそれぞれ実装して動作確認

ここからの予定はまだわからないので、いったん上記を実装してから決める

にー兄さんにー兄さん

個人的には、ComputeShaderにGraphicsBufferをUpdateのたびにSetしなくていいのかな、とか
GraphicsBufferを初期化する時に使ったNativeArrayは初期化の時点でDisposeしてるけど大丈夫なのかなとか
なんかそこらへんのデータの更新・破棄のタイミングでうまく動作するか不安

にー兄さんにー兄さん

上記はboids countがnumthreadsで割り切れていなかったのが原因ぽい(64スレッドに対してboids countを1000指定していた)

にー兄さんにー兄さん

バリデーションを追加した

if (_csMainKernel == null)
{
    return false;
}

boidsComputeShader.GetKernelThreadGroupSizes(_csMainKernel.Value, out var x, out _, out _);
var isBoidsCountCanDivideWithNumThreads = boidsCount % x == 0;
このスクラップは2024/05/05にクローズされました