Godot EngineでBoids Flockingシミュレーションを実装する | 人工生命

Boids FlockingシミュレーションをGodot Engineで実装します。


はじめに

以下のように、Boids Flocking (ボイドモデル / ボイド群衆アルゴリズム) をGodot Engineで実装してみました。

エサを追いかけるような、可愛げのあるboidsたちの動きがなかなかのお気に入りです。


今回は、これらの実装方法のメモを残します。


Boids Flockingとは

まずは、Boids Flockingアルゴリズムについておさらいします。

Boidsとは、鳥の群れの動きをシミュレートする人工生命プログラムです。
"Bird-oid"、「鳥っぽいもの」という意味で、Boidsと名づけられました。 クレイグ・レイノルズが開発し、論文は1987年に発表されています。

f:id:BioErrorLog:20200922104303p:plain
画像はクレイグ・レイノルズの論文より引用: Flocks, Herds, and Schools: A Distributed Behavioral Model, Craig W. Reynolds, 1987, Computer Graphics

このBoids Flockingアルゴリズムでは、以下の3つのシンプルな法則によって群れを形成します:

  • Separation: 分離
  • Alignment: 整列
  • Cohesion: 結合


Separation: 分離は、近隣のオブジェクトと近づきすぎないよう距離をとる力です。

f:id:BioErrorLog:20200922105607g:plain
Separation: 分離 | 画像はWikipediaより


Alignment: 整列は、近隣のオブジェクトと同じ方向に進もうとする力です。

f:id:BioErrorLog:20200922110610g:plain
Alignment: 整列 | 画像はWikipediaより


Cohesion: 結合は、近隣のオブジェクト集合の中心地に向かおうとする力です。

f:id:BioErrorLog:20200922113645g:plain
Cohesion: 結合 | 画像はWikipediaより


この3つの力の組み合わせで、オブジェクトの集合が鳥の群れのような挙動をとるようになります。 単純な法則から複雑な現象が沸き起こるところは、生き物の醍醐味ですね。


それでは、以下Godot EngineによるBoids Flockingシミュレーションの実装を見ていきます。


実装

最終的なソースコードは以下のGitHubに置いていますので、良ければまずはそちらをご覧ください。
以下の章では、各要素ごとの実装を取り上げて見ていきます。 github.com

Separation

まず、Separationの実装を見ていきます。 言語はGodot Engineの標準スクリプト言語のGDScriptです。

func process_seperation(neighbors):
    var vector = Vector2()
    var close_neighbors = []
    for boid in neighbors:
        if position.distance_to(boid.position) < perception_radius / 2:
            close_neighbors.push_back(boid)
    if close_neighbors.empty():
        return vector
    
    for boid in close_neighbors:
        var difference = position - boid.position
        vector += difference.normalized() / difference.length()
    
    vector /= close_neighbors.size()
    
    return steer(vector.normalized() * move_speed)

大きく二つの処理からなっています。
一つ目は近隣boidsの取得、
二つ目は近隣boidsからSeparateする力の算出です。

近隣boidsの取得は、以下のコードで行っています:

   var close_neighbors = []
    for boid in neighbors:
        if position.distance_to(boid.position) < perception_radius / 2:
            close_neighbors.push_back(boid)

もともとこの関数に渡されるneighbors自体、一定の範囲perception_radiusを基準に算出された近隣boidsを指しています。 しかし、Separation力の算出源をさらに近い位置にいるboidたちに絞るため、perception_radius / 2以内にいるboidsをclose_neighborsとして登録しています。

そしてこれらclose_neighborsから、以下のようにしてSeparationの力を算出しています:

   for boid in close_neighbors:
        var difference = position - boid.position
        vector += difference.normalized() / difference.length()
    
    vector /= close_neighbors.size()

こうして算出したSeparation力を、本体boidの移動ベクトルに加算するという流れです。


Alignment

続いて、Alignmentを見ます。

func process_alignments(neighbors):
    var vector = Vector2()
    if neighbors.empty():
        return vector
        
    for boid in neighbors:
        vector += boid.velocity
    vector /= neighbors.size()
    
    return steer(vector.normalized() * move_speed)

Alignment力の算出はシンプルです。 neighborsの現在の進行ベクトルの平均をもとにAlignment力を算出し、本体boidの移動ベクトルに返却します。


Cohesion

続いてCohesionです。

func process_cohesion(neighbors):
    var vector = Vector2()
    if neighbors.empty():
        return vector
    for boid in neighbors:
        vector += boid.position
    vector /= neighbors.size()
    
    return steer((vector - position).normalized() * move_speed)

こちらもシンプルで、neighborsの平均座標と本体boidの差分をもとにCohesion力を返却しています。


ここまでが、Boids FlockingモデルにおけるSeparation / Alignment / Cohesionの実装です。 次には補足として、エサを追いかける動作の実装を見ます。


エサを追いかける動作

エサを追いかける動作として、単純にあるポイントへの求心力を算出しています。

func process_centralization(centor: Vector2):
    if position.distance_to(centor) < centralization_force_radius:
        return Vector2()
        
    return steer((centor - position).normalized() * move_speed)   

この引数centorとしてエサの座標を渡すことで、エサへ向かう力を算出できます。 ただし、エサに近過ぎる場合は空Vectorを返却することで、エサにboidが収束してしまうのを防いでいます。


以上、ここまで見てきたそれぞれの力をフレームごとに計算し、以下のように合算して移動ベクトルをとることで、boidsの振る舞いが定義できます。

func _process(delta):
    var neighbors = get_neighbors(perception_radius)
    
    acceleration += process_alignments(neighbors) * alignment_force
    acceleration += process_cohesion(neighbors) * cohesion_force
    acceleration += process_seperation(neighbors) * seperation_force
    acceleration += process_centralization(prey_position) * centralization_force
        
    velocity += acceleration * delta
    velocity = velocity.clamped(move_speed)
    rotation = velocity.angle()
    
    translate(velocity * delta)


繰り返しになりますが、ソースコードはGitHubに置いていますので、良ければそちらもご覧ください。

今回の完成状態のムービーです(再掲):


おわりに

以上、Boids FlockingシミュレーションをGodot Engineで実装する際のメモを書きました。

処理効率等を考慮したプログラムではありませんので高度な利用はできませんが、彼らが動き出した時の感動はなかなかのものでした。

Boids Flockingは人工生命モデルの中でもシンプルかつ有名なものですが、今後はもっと複雑なモデルを動かせると楽しいだろうなとワクワクしています。


関連記事

人工生命に興味を持ったきっかけ、その動機を書いています: www.bioerrorlog.work


参考

Flocks, Herds, and Schools: A Distributed Behavioral Model, Craig W. Reynolds, 1987, Computer Graphics

GitHub - codatproduction/Boids-simulation: A flocking simulation with obstacle avoidance made in Godot!

Code That: Boids - YouTube

Boids - Wikipedia

GitHub - alifelab/alife_book_src: 「作って動かすALife - 実装を通した人工生命モデル理論入門」サンプルコード