Boidsの実装について調査となんか作りたい
boidsでなんか作りたいなぁと思い始めてきて、ちょっと調べていたんでめも
サンプルコード付きでわかりやすい記事
他の記事
Boids、一定範囲内で以下の計算をするということが分かった
- 分離
- 結合
- 整列
アルゴリズムとしてはそこまで複雑ではないんだなぁ
いまやりたいこととして、Unity VFX GraphでBoidsシミュレーションをしたいなぁ
現状は近傍探索の機能が無いので、ComputeShaderを組み合わせる必要があると思う
ComputeShaderで計算した結果をテクスチャ成りGraphicsBufferに書き込み、それをPropertyBinder経由でVFX Graphに渡すというイメージ
いい感じにこれを作って、書典16で単著の本を出したいな~
クリエイティブコーディングの教科書の人が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);
},
};
へこみさんのBoidsの解説記事
ここでは壁の跳ね返りをちゃんと実装している
まずはいったん最速でCPUべーすのBoidsシミュレーションをやってみる
なるべくComputeShaderに移行しやすい形にしたいので、Boidsのデータを配列で一貫して扱い、
ロジックは個別の処理に切り分けていきたい
VFXGraph使いたいので早めにURP設定しておくか
unity 2023.2で環境構築した
edoさんのComputeShader解説記事
今疑問に思ったのが、毎フレーム処理する時にdeltaTime的な時間スケーリングはしなくてよいのかという点
たしかクリエイティブコーディングの教科書のサンプルにはそんな感じのものはなかった気がする
なんでなくて動くんだ?
徐々に近づいていく処理というのがホントに微笑変化だからか?
そういえばクリエイティブコーディングの教科書のコードでは
アップデートの時に元の配列を壊してしまわないか(つまり並列処理しているのに途中でpositionを変えてしまってはいけない)気になったんだけど、
いったんすべてのaccだけを更新して、そのあと一斉にそのaccからv,pを算出するようなコードになっていた
なるほどなぁ
これは真似しよう
C#実装でSpan<T>使ってみるか?
純粋関数を作るうえでReadOnlySpan<T>が使えるのが良さそうに思った
あんまりPublic関数にしないような感じだし、なにせよフィールドにできないので
内部で配列処理の時に使うだけでも使ってみようかしらね
クリエイティブコーディングの教科書のコードだと
fleeだけfor分の中にあるんだな
VFX GraphではVFXTipe属性で独自定義した構造体をGraphicsBufferからサンプリングできるようになるらしい
これは使えそう
いったん、CPUベースの整列処理だけ実行できるようにしてみた
どんどん値が小さくなってしまうのは、これはそういうもんっぽいな
ためしにクリエイティブコーディングの教科書のサンプルで、separationとcohesionをスキップしてみたら同じような現象が起きた
分離や結合も実装して、いい感じに動いた!
一旦この、MonoBehaviourで作ってプレハブをインスタンス化して作った最小限のものをベンチマークにしつつ、最終的にはCompuetShaderで計算してVFX Graphで表示するところまでをやっていく
次はCPUベースの処理をGraphicsBufferに落としてみて、それをVFX Graphで表示してみる
それができたらGraphicsBuffer→VFX Graphの動作検証ができるので
そこから最後にGraphicsBuffer生成をComputeShaderに置き換えればよい
書典16のスケジューリングも始めないとだな・・・
こんな感じでBoidsDataという構造体を作り、BoidsCoreのロジックをこれ用に置き換えていた
Sample Graphics BufferノードでBoidsDataをサンプリングできそうな感じになってる!
VFXGraph Property Binderの作り方docs
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);
}
いい感じにVFXGraphに接続できた!
ちょっと物理シミュレーションを意識した見た目に
ComputeShaderの勉強をする
この記事に、thread数の決定についての言及がある
気になるので読みたい
ひとまず入門などの解説をしているサイトをひたすら読み漁るか
キャッチ-でわかりやすそうなサイト
シンプルな実装の例@Qiita
IndieVisualLabさんの神資料……すでにBoidsのCompuetShader実装がある……
ライフゲームの実装
Unity公式docsの説明
おっしてここで紹介されていたUnity Japanのデモプロジェクト
そしてUnityステーションの配信 この配信でBoidsのデモをやっていたのか!
ComputeBufferではなくGraphicsBufferを使おうねという記事
これずっと頭の中にあって、GraphicsBufferを使うようにしていたんだけど
変わった点って頂点シェーダとして使えるようになったとか、命名が変更になったとか
そんな感じなんだな
機能的には上記だけど、ComputeShaderは廃止予定なので移行したほうが良さそう
昨日としてはそこまで変わらないという理解を得た
まぁVFXGraphでも使えるのはGraphicsBuffferだしな、こっちを使っていく
めーぷるさんのCompuetShaderの記事
わかりやすそう
なんとなくGPUインスタンシングについて勉強していた
VFX Graphの中身ってどうなってるんだろ
Compute Shaderの実行結果を非同期に取得できるかなって思ったんだけど、これはレンダーテクスチャのデータ取得に使われるっぽい
お、CompueteShaderと和解できた
これは指定したVector3ですべてのGraphicsBuffer要素を埋めるというComputeShader
要素数100個でやってみた
10,000個でもできた
dispathに指定する数って制限なかったっけなって思ったけどどうなんだろう
1,000,000でやったらこんなメッセージが
スレッドグループの数は65535が上限らしい
スレッドグループということは、スレッドを増やせばよい?
さきほどはスレッドが4でスレッドグループが250,000だったため65535を超えてしまっていた
これをスレッド数64にしたらスレッドグループは15,625になるわね
これで解決したっぽい
これでComputeShader実装を進めるにあたり不安点はないかなと思いつつ、
計算結果を並列で入力したバッファに書き込んで大丈夫なのかという不安がある
Unity-jpの実装では入力バッファに並列して書き込んでいるっぽいんだけど、
これって大丈夫なのかな
いったん入力と処理結果を同じバッファに書き込むことにして、
問題がありそうであればバッファを分けよう
今回の実装、if文による分岐が頻出だけど、パフォーマンスは大丈夫なんかな
BoidsのCompueteShaderで、境界処理だけを実装したものを作成した
これでいったん全体を実行しても問題はないはず
また、BoidsBinderに関してもBoidsCore.csではなくComputeShaderに差し替えたバージョンを作成中(WIP)
初期化とUpdateの関数のコードを埋めれば実行できそう
ここからの実装て順としては、
- BoidsBinderの実装を一通り完成させる
- 実行してみて、境界処理だけは知っている状態を動作確認する
この時にBoidsCountを増やしてみてパフォーマンスを確認できればSuperCool - 整列・分離・結合の処理をそれぞれ実装して動作確認
ここからの予定はまだわからないので、いったん上記を実装してから決める
個人的には、ComputeShaderにGraphicsBufferをUpdateのたびにSetしなくていいのかな、とか
GraphicsBufferを初期化する時に使ったNativeArrayは初期化の時点でDisposeしてるけど大丈夫なのかなとか
なんかそこらへんのデータの更新・破棄のタイミングでうまく動作するか不安
境界処理のみをCompuetShaderで実装してみたけど、なぜか動いているものと動いていないものがある……。
上記は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;
1万エンティティで100fps越え!いいぞ!
まだ境界処理しか実装していないので、これから計算量が2乗になるから心配
alignだけ実装してみた これだけでもある程度Boidsっぽい
最終的にboidsの挙動をすべて実装し、動いた!
16,384(=1024*16)エンティティが動いていても60fps!すばらしい!
現状をUnityRecorderで録画
リポジトリも公開して、クローズ!