Boidsシミュレーション

こんにちは、エンジニアの成田です。

以前のアリのフェロモントレイルに続き、今回も人工知能のシミュレーションを行ってみます。今回は人工生命のアルゴリズムとしてはメジャーであるBoidsを取り上げます。

1.Boids

Boidsとは1987年のSIGGRAPHでCraig Reynolds氏が発表した人工生命プログラムで、鳥や魚、陸上動物の群れのような動きを行うオブジェクト(boid)の集合体です。このアルゴリズムの面白いところは各オブジェクトに簡単なルールをいくつか適用するだけで全体が複雑な動きを見せるところです。その意味では前回のアリのフェロモントレイルと同じくBoidsも群知能と言えます。

Reynoldsが群れをシミュレーションするために定義したルールは

1. 衝突の回避…近隣の仲間との衝突を避ける
2. 速度の適合…近隣の仲間の速度に合わせようとする
3. 群れ中心化…近隣の仲間の近くに居ようとする

これだけです。各ルールの詳細は後で述べますが、各boidについてこれらのルールからboidが次に向かうべきベクトルを計算するだけというシンプルなアルゴリズムです。それにもかかわらず、各boidはリアルな動きを見せるため、昔からゲームや映画に本アルゴリズムがよく用いられてきました。

2.実装

それではBoidsを実装してみます。特に理由はありませんが今回はUnityを使ってみました。

ではまずBoidの見た目を作成したいのですが、自分はモデリングできません。ですので苦し紛れにこんなのを作ってみました。

ピノキオの鼻みたいになってる方向が進行方向になります。
これをプレハブとして複製して使います。

このBoidにまずは基本の動きをさせましょう。スクリプトを追加します。
次のようなソースです。

using UnityEngine;
using System.Collections.Generic;

public class BoidScript : MonoBehaviour, IObject {
    private Vector3 position;  // 位置  
    public Vector3 Position
    {
        get
        {
            return position;
        }
        set
        {
            position = transform.position = value;
        }
    }
    private Vector3 velocity;  // 速度  
    public Vector3 Velocity
    {
        get
        {
            return velocity;
        }
        set
        {
            velocity = value;
            transform.forward = velocity.normalized;
        }
    }
    private Vector3 acceleration = Vector3.zero;  // 加速度  

    void Awake () {
        position = transform.position;
        Velocity = transform.forward * 2.0f;  // 初速  
    }

    // Use this for initialization  
    void Start () {

    }

    // Update is called once per frame  
    void Update () {
        // dtと前回の加速度から位置差分・速度を計算  
        float dt = Time.deltaTime;
        Vector3 dPos = Velocity * dt + 0.5f * acceleration * dt * dt;  // d = v0*t + 1/2*a*t^2  
        Velocity = Velocity + acceleration * dt;    // v = v0 + a*t  
        // 速度はBoidMinV以上BoidMaxV以下でなければならない  
        float clamped = Mathf.Clamp (Velocity.magnitude, Main.BoidMinV, Main.BoidMaxV);
        Velocity = Velocity / Velocity.magnitude * clamped;
        Position = Position + dPos;

        // 加速度更新  
        acceleration = Vector3.zero;
    }
}

PositionとVelocityのプロパティは、これらを変更した時にGameObjectの位置と角度も一緒に調整するようになっています。
Update()内は高校物理のあれですね。等加速度運動の公式というやつです。次に速度がClampしてありますが、Main.BoidMinVとMain.BoidMaxVはboidの最低速度・最高速度の定数です。物が空気や水の中を進むとき、抵抗のため一定の速度以上は出せません。これを模しているわけです。

加速度は今はゼロにしているため、等速運動を行うはずです。

次にシーン上のどこかにシミュレーション全体を管理するスクリプトを置きましょう。

using UnityEngine;
using System.Collections.Generic;

public interface IObject
{
    Vector3 Position { get; set; }
}

public class VirtualBoid : IObject {
    private Vector3 position;
    public Vector3 Position
    {
        get
        {
            return position;
        }
        set
        {
            position = value;
        }
    }

    public VirtualBoid(Vector3 pos) {
        Position = pos;
    }
}

public class Main : MonoBehaviour {
    // ステージ領域  
    public const float MinX = -10.0f;
    public const float MaxX = 10.0f;
    public const float MinY = 0.0f;
    public const float MaxY = 20.0f;
    public const float MinZ = -10.0f;
    public const float MaxZ = 10.0f;

    public GameObject Boid;  // boidプレハブ  

    // 壁となるPlane  
    private Plane Up = new Plane(new Vector3(0,-1,0), new Vector3(0,MaxY,0));
    private Plane Down = new Plane(new Vector3(0,1,0), new Vector3(0,MinY,0));
    private Plane Left = new Plane(new Vector3(1,0,0), new Vector3(MinX,0,0));
    private Plane Right = new Plane(new Vector3(-1,0,0), new Vector3(MaxX,0,0));
    private Plane Forward = new Plane(new Vector3(0,0,-1), new Vector3(0,0,MaxZ));
    private Plane Back = new Plane(new Vector3(0,0,1), new Vector3(0,0,MinZ));

    public const int BoidCount = 100;  // boidの数  
    private List<BoidScript> boids = new List<BoidScript>();

    public const float BoidMaxV = 5.0f;  // boidが出せる最高速度  
    public const float BoidMinV = 2.0f;  // boidが出せる最低速度  
    public const float BoidFOV = 5.0f;  // boidの視界  

    // シングルトンアクセス  
    private static Main instance;
    public static Main Instance
    {
        get {
            if (instance == null) {
                instance = GameObject.FindObjectOfType<Main>();
                DontDestroyOnLoad(instance.gameObject);
            }
            return instance;
        }
    }

    void Awake () {

    }

    // Use this for initialization  
    void Start () {
        for (int i = 0; i < BoidCount; i++)
        {
            GameObject boid = (GameObject) Instantiate (Boid,
                new Vector3 (Random.Range(MinX, MaxX), Random.Range(MinY, MaxY), Random.Range(MinZ, MaxZ)),
                Random.rotation);
            boids.Add (boid.GetComponent<BoidScript> ());
        }
    }

    // Update is called once per frame  
    void Update () {

    }

今はIObjectとVirtualBoidについては気にしないでください。Mainの各定数に関しても特に説明は必要ないと思いますが、Planeに関しては後々シミュレーション領域の壁にするために用意してあります。
Start ()内でプレハブから各boidをBoidCount個複製してランダムな位置にランダムな角度で配置し、シミュレーションを開始します。

これを実行すると、各boidが同じ速度のままシミュレーション領域から飛び出していけば準備は完了です。

ではBoidsのルールを実装していきましょう。

a.衝突の回避…近隣の仲間との衝突を避ける

boidは近隣の仲間との距離が近づきすぎてぶつかりそうになると逆方向へ逃げて衝突を回避しようとします。
まず「近隣の仲間」を取得するメソッドをMainクラスに作成しましょう。

   public List<BoidScript> GetOtherBoidsInFOV (BoidScript obj) {
        List<BoidScript> retBoids = new List<BoidScript> ();
        foreach(BoidScript boid in boids) {
            if (boid == obj)
                continue;
            Vector3 diff = boid.Position - obj.Position;
            if (diff.magnitude <= BoidFOV)
                retBoids.Add (boid);
        }
        return retBoids;
    }

引数に該当のboidを渡すと、そのboidから距離がBoidFOV以下となるboidのリストを返すメソッドです。
これを利用してルールを実装します。

近隣の各boidについて、正規化した逆ベクトルを作り距離の2乗で割ったベクトルを作成します。
これによって遠いうちはゆっくり、近くなりすぎてしまうと急旋回して回避するようになります。
さらにこれらを近隣のboid全体で平均します。

   private Vector3 Rule1 () {
        List<BoidScript> objects = new List<BoidScript> ();
        objects.AddRange (Main.Instance.GetOtherBoidsInFOV (this));

        if (objects.Count == 0)
            return Vector3.zero;

        Vector3 vec = Vector3.zero;
        foreach (BoidScript obj in objects) {
            Vector3 diff = obj.Position - Position;
            vec += -1 * diff.normalized * 10.0f / (diff.magnitude * diff.magnitude);
        }
        return vec / objects.Count;
    }

これで衝突回避のルールができました。
さらにboidにシミュレーション領域に収まっていてもらうために、6隅の領域壁を仮想的なboidとすることで壁との衝突も同じ処理で回避することができます。
Mainクラスに次のようなメソッドを作成します。

   public List<IObject> GetVirtualBoidsOnWall (BoidScript obj) {
        List<IObject> boids = new List<IObject> ();
        float d;
        d = Up.GetDistanceToPoint (obj.transform.position);
        if (d <= BoidFOV) {
            boids.Add (new VirtualBoid(obj.Position - d * Up.normal));
        }
        d = Down.GetDistanceToPoint (obj.transform.position);
        if (d <= BoidFOV) {
            boids.Add (new VirtualBoid(obj.Position - d * Down.normal));
        }
        d = Left.GetDistanceToPoint (obj.transform.position);
        if (d <= BoidFOV) {
            boids.Add (new VirtualBoid(obj.Position - d * Left.normal));
        }
        d = Right.GetDistanceToPoint (obj.transform.position);
        if (d <= BoidFOV) {
            boids.Add (new VirtualBoid(obj.Position - d * Right.normal));
        }
        d = Forward.GetDistanceToPoint (obj.transform.position);
        if (d <= BoidFOV) {
            boids.Add (new VirtualBoid(obj.Position - d * Forward.normal));
        }
        d = Back.GetDistanceToPoint (obj.transform.position);
        if (d <= BoidFOV) {
            boids.Add (new VirtualBoid(obj.Position - d * Back.normal));
        }
        return boids;
    }

このメソッドではboidの位置から各壁平面に対して垂線を落として、その足に当たる位置に仮想的なboidがあるものとします。本物のboidと同じく、boidの視界内にある場合だけリストで返します。

本物のboidと仮想boidをリストに混ぜて同じように扱うことができます。

   private Vector3 Rule1 () {
        List<IObject> objects = new List<IObject> ();
        objects.AddRange (Main.Instance.GetVirtualBoidsOnWall (this));
        objects.AddRange (Main.Instance.GetOtherBoidsInFOV (this).ConvertAll<IObject>(c => c as IObject));

        if (objects.Count == 0)
            return Vector3.zero;

        Vector3 vec = Vector3.zero;
        foreach (IObject obj in objects) {
            Vector3 diff = obj.Position - Position;
            vec += -1 * diff.normalized * 10.0f / (diff.magnitude * diff.magnitude);
        }
        return vec / objects.Count;
    }

これで衝突回避のアルゴリズムが完成しました。

b.速度の適合…近隣の仲間の速度に合わせようとする

これは簡単です。boidの視界内のboidの速度ベクトルを平均して、そのベクトルと自分の速度ベクトルとの差分を取るだけです。

   private Vector3 Rule2 () {
        List<BoidScript> boids = new List<BoidScript> ();
        boids.AddRange (Main.Instance.GetOtherBoidsInFOV (this));

        if (boids.Count == 0)
            return Vector3.zero;

        Vector3 vec = Vector3.zero;
        foreach (BoidScript boid in boids) {
            vec += boid.Velocity;
        }
        Vector3 ave = vec / boids.Count;
        return ave - Velocity;
    }

c.群れ中心化…近隣の仲間の近くに居ようとする

群れ中心化とは、近くの仲間たちの真ん中へ移動しようとすることです。
これも簡単です。boidの視界内のboidの位置の重心を取り、その位置と自分の位置との差分を取るだけです。

   private Vector3 Rule3 () {
        List<BoidScript> boids = new List<BoidScript> ();
        boids.AddRange (Main.Instance.GetOtherBoidsInFOV (this));

        if (boids.Count == 0)
            return Vector3.zero;

        Vector3 pos = Vector3.zero;
        foreach (BoidScript boid in boids) {
            pos += boid.Position;
        }
        Vector3 ave = pos / boids.Count;
        return ave - Position;
    }

最後にこれらの各ルールで作ったベクトルを合成します。

   public const float Rule1Factor = 5.0f;  // ルール#1の重み  
    public const float Rule2Factor = 2.0f;  // ルール#2の重み  
    public const float Rule3Factor = 1.0f;  // ルール#3の重み  

    // Update is called once per frame  
    void Update () {
        // dtと前回の加速度から位置差分・速度を計算  
        float dt = Time.deltaTime;
        Vector3 dPos = Velocity * dt + 0.5f * acceleration * dt * dt;  // d = v0*t + 1/2*a*t^2  
        Velocity = Velocity + acceleration * dt;    // v = v0 + a*t  
        // 速度はBoidMinV以上BoidMaxV以下でなければならない  
        float clamped = Mathf.Clamp (Velocity.magnitude, Main.BoidMinV, Main.BoidMaxV);
        Velocity = Velocity / Velocity.magnitude * clamped;
        Position = Position + dPos;

        // 加速度更新  
        acceleration = (Rule1Factor * Rule1 () + Rule2Factor * Rule2 () + Rule3Factor * Rule3 ()) / (Rule1Factor + Rule2Factor + Rule3Factor);
    }

Reynoldsは各ルールには優先度があると言っていますので、各ルールで作成したベクトルは加算平均を取るより重み付けをした加重平均をした方が良いでしょう。
この重み付けなどのパラメータ調整は正直実行しながら調整していく泥臭い部分になってしまいます……

プロジェクトファイルはこちらになります。
engblog.zip

実行してみましょう。

最初はバラバラに動いていたboidが次第に群れを成して泳ぐ姿を見ることができると思います。上手くいかなかったらパラメータを調整してみる必要があるかもしれません。

いかがでしたでしょうか。視覚的に動く人工知能は見てるだけでも面白いですよね。