Boid Model による ALife の実装 with Javascript

計算機状で生命体を模したモデルを作り、その挙動を研究するという分野があり、一般に人工生命 (Alife) と呼ばれています。その中でも「群れ」をモデル化したものに boid model と呼ばれるものがあります。

今回は Boid Model の簡単な説明とそれを Javascipt + vue.js を使ってブラウザ上でインタラクティブにあそべるところまでを実装していきます。

完成図

agitated-goldberg-260b08.netlify.com f:id:dette:20181020175739g:plain

Boid Model とは

Boid Model とは Craig Reynolds によって開発された群れを模した Alfie のモデルのことを指します。Boid とは「bird-oid object」の省略系で、このモデルが鳥を模したものであることが名前からもわかります。

Boid は以下の3つの基準にしたがって行動します。

1. 分離

f:id:dette:20181020164507p:plain

自分の周りに沢山鳥がいると飛びづらいですよね。なので boid は自分の近くの boid から離れようとします。これが分離の動きです。

2. 平均化

f:id:dette:20181020164540p:plain

boid は周りの動きに敏感です。自分の近くにいる集団の速度と自分の速度を一致させようとします。これが平均化の動きです。

3. 結束

f:id:dette:20181020164600p:plain

boid は周りの boid から完全に離れることは望んでいません。ですので boid はまわりの boid の重心座標へ移動しようとします。これが結束の動きです。

基礎的な boid は以上の3つのルールにしたがって行動します。

一見単純な用に見えますが、これらの重み付けを変えたり、 boid が見える周りの範囲の大きさを変えたりすることで、多種多様な動きをするようになります。

実装

今回は boid モデルを javascript で実装します。

まず boid を扱う際には物理モデルを作成する必要があります。ここでいう物理モデルは座標 $x$ 速度 $v$ 加速度 $\alpha$ を物体は持っていて以下の式によって変化する、ということを指します。

$$ \dot{x}(t) = v(t) \\ \dot{v}(t) = \alpha(t) $$

実際にコンピューター上ではこれを離散化する必要があるため、ある短い時間 $\Delta t$ を用いて以下のように近似してやります。

$$ x(t+1) = x(t) + \Delta t v(t) \\ v(t+1) = v(t) + \Delta t \alpha(t) $$

必要な数式はこれだけです。（たぶん）

下準備

では実装に入ります。まず大量に座標を扱うことになるので、座標系クラス Coodinate を作ります。とりあえずは二次元で考えるので変数は x, y の２つにしておきます。ここでは省略しましたが座標同士の足し算、引き算、掛け算、ノルム計算などを実装しました。

class Coodinate {
  constructor(x, y) {
    this.x = x
    this.y = y
  }

  /**
   * 座標に数値を掛け算した座標を返します
   *
   * @static
   * @param {Coodinate} a
   * @param {Number} x
   * @memberof Coodinate
   */
  static mult(a, x) {
    const retval = new Coodinate(a.x * x, a.y * x)
    return retval
  }
  // などなど
}

次に物理法則にしたがって動く物体の基本となるクラス AbstractObject を作ります。このオブジェクトは場所、速度、加速度、速度の最大値、自分の位置の履歴を管理します。

class AbstractObject {
  /**
   *Creates an instance of AbstractObject.
   * @param {Coodinate} initPosition
   * @param {Numbe} maxVerocity オブジェクトの最大速度
   * @memberof AbstractObject
   */
  constructor(initPosition, maxVerocity = 5) {
    this.position = initPosition
    this.verocity = new Coodinate(Math.random(), Math.random())
    this.acceleration = new Coodinate(0, 0)
    this.maxVerocity = maxVerocity
    this.history = []
    this.ratio = null
  }

  /**
   * 加速度を元に座標と速度を更新するメソッドです
   *
   * @param {Coodinate} newAcceleration
   * @memberof AbstractObject
   */
  update(newAcceleration) {
    this.acceleration = newAcceleration
    this.verocity.plus(this.acceleration)
    const vNorm = Coodinate.distance(this.verocity, new Coodinate(0, 0))
    this.ratio = vNorm

    if (this.maxVerocity < vNorm) {
      const ratio = this.maxVerocity / vNorm
      this.verocity = this.verocity.multBy(ratio)
    }
    this.position.plus(this.verocity)

    this.history.push(Coodinate.copy(this.position))
  }
}

物体の位置が更新されるときは加速度を元に速度、速度を元に位置、というふうに計算していくので、加速度を渡して位置情報を update する関数を用意しています。

次に実際に動く boid object を作ります。今回は Fish と名づけました(今になって bird のほうが適切だったと気づきましたがまあ魚も群れを作るので）

/**
 * 魚の boid model
 *
 * @class Fish
 * @extends {AbstractObject}
 */
class Fish extends AbstractObject {
  static maxAccelerationNorm = 0.1
  static meanForceRatio = 0.7
  static dislikeForceRatio = 5.0
  static counter = 0

  /**
   * 魚のインスタンスを作成します
   * @param {Coodinate} initPosition
   * @param {number} [sakuteki=100] 魚が見える範囲です。この範囲内の魚に対して boid の3原則を適用します
   * @param {number} [dislikeDistance=20] この範囲内の魚からは遠ざかる動きをします.
   * @memberof Fish
   */
  constructor(initPosition, sakuteki = 100, dislikeDistance = 20) {
    super(initPosition)
    this.sakuteki = sakuteki
    this.dislikeDistance = dislikeDistance
    Fish.counter += 1
    this.id = Fish.counter
  }
  /**
   * 次のフレームでの自分の加速度(意志)を決定します
   *
   * @param {[Fish]} nearlyFishes
   * @memberof Fish
   */
  nextAcceleration(nearlyFishes) {
    // 近くに魚が居ない時加速しません
    if (nearlyFishes.length === 0) return new Coodinate(0, 0)

    const vList = nearlyFishes.map(f => f.verocity)
    const vMean = Coodinate.mean(vList)
    const pMean = Coodinate.mean(nearlyFishes.map(f => f.position))

    // 速度の平均値にどれぐらい合わせるかを計算 (法則2)
    const vDirection = Coodinate.minus(vMean, this.verocity)
      .norm()
      .multBy(Fish.meanForceRatio)

    // 中心に移動するちからのベクトルを計算 (法則3)
    const pDirection = Coodinate.minus(pMean, this.position).norm()

    let direction = pDirection.plus(vDirection)

    // 近すぎるおさかな
    const tooNearFishPositions = filterByDistance(
      nearlyFishes,
      this.position,
      this.dislikeDistance
    )

    if (tooNearFishPositions.length > 0) {
      const tooNearMeanPos = Coodinate.mean(
        tooNearFishPositions.map(f => f.position)
      )
      // 近すぎる魚からどのぐらい離れるかのベクトルを計算(法則1)
      const tooNearDirection = Coodinate.minus(tooNearMeanPos, this.position)
        .norm()
        .multBy(Fish.dislikeForceRatio)
      direction.minus(tooNearDirection)
    }

    return Coodinate.normalize(direction).multBy(Fish.maxAccelerationNorm)
  }
}

constructor に sakuteki と dislikeDistance のパラメータが加わりました。

sakuteki
- 自分の周りのこの範囲の魚を見ることができます。先の boid 3法則はこの範囲内の魚に対して適用されます。
dislikeDistance
- boid の第一法則である分離に関するパラメータです。この範囲内にいる魚からは逃げようとする動きを取ります。(コメント中の近すぎるお魚がそれに相当します。)

距離で絞り込んでくる必要がでたので関数を一つ用意しました。 viewFrom からみて maxDistance 内にいる魚を返す関数です。

function filterByDistance(fishes, viewFrom, maxDistance) {
  return fishes.filter(fish => {
    const d = Coodinate.distance(fish.position, viewFrom)
    return d < maxDistance
  })
}

最後に魚を泳がせるフィールドを用意します。

/**
 * 魚を泳がせるフィールドクラス
 *
 * @class Field
 */
export class Field {
  /**
   *Creates an instance of Field.
   * @param {number} [width=1000] フィールドの横幅
   * @param {number} [height=500] フィールドの縦幅
   * @param {number} [sakutekiRange=200] 新しく作る魚がどれぐらいの範囲を見れるか
   * @param {number} [dislikeDistance=20] 新しく作る魚はこの範囲以下の魚から離れようとします。
   * @memberof Field
   */
  constructor(
    width = 1000,
    height = 500,
    sakutekiRange = 200,
    dislikeDistance = 20
  ) {
    this.width = width
    this.height = height
    this.fishes = []
    this.newFishes = []
    this.sakutekiRange = sakutekiRange
    this.dislikeDistance = dislikeDistance
    this.isUpdating = false
  }

  /**
   *ランダムな位置に魚を追加します
   *
   * @memberof Field
   */
  addFish() {
    const x = (this.width * (0.5 + Math.random())) / 2
    const y = (this.height * (0.5 + Math.random())) / 2
    const pos = new Coodinate(x, y)
    const newFish = new Fish(pos, this.sakutekiRange, this.dislikeDistance)
    this.newFishes.push(newFish)

    if (this.isUpdating) return
    this.fishes = this.fishes.concat(this.newFishes)
    this.newFishes = []
  }

  /**
   * フィールドの時間を一つ進めます
   *
   * @memberof Field
   */
  next() {
    this.fishes = this.fishes.concat(this.newFishes.slice())
    this.newFishes = []

    // 初めに魚全員の行動(加速度)を決定する
    const accelerations = this.fishes.map(fish => {
      const fishesCanView = filterByDistance(
        this.fishes.filter(f => f !== fish),
        fish.position,
        fish.sakuteki
      )
      return fish.nextAcceleration(fishesCanView)
    })

    // 決めた行動（加速度）にしたがって更新
    this.fishes.forEach((fish, idx) => {
      const acc = accelerations[idx]

      // フィールドから外に出ようとする魚に対しては強制的に元に戻るような加速度をつける
      if (fish.position.x > this.width) {
        acc.plus(new Coodinate(-1, 0))
      }
      if (fish.position.x < 0) {
        acc.plus(new Coodinate(1, 0))
      }

      if (fish.position.y > this.height) {
        acc.plus(new Coodinate(0, -1))
      }
      if (fish.position.y < 0) {
        acc.plus(new Coodinate(0, 1))
      }

      fish.update(accelerations[idx])
    })
  }
}

動き自体は Fish が担っているので Field では特定の Fish インスタンスがどの範囲が見えているのか（見えている魚の集合はなんなのか）の計算が主になっています。

あとはこれを vue.js 上でレンダリングすると完成です。要は

FIeld のインスタンス field を作成
window.setInterval で定期的に field.next() を呼び出す

を繰り返せば OK です。

実装: https://github.com/nyk510/boid-model/blob/master/components/boid/BoidCanvas.vue *1

Deploy

今回は netlify を使って nuxt を静的ファイルとしてデプロイしました。

agitated-goldberg-260b08.netlify.com

パラメータ変えて遊んでみると、いろいろな周期と規則が見えてきて面白いです。

今回は本当にさわりだけでしたが、面白い！と思った人は Alife とか boid で検索して本とか論文とか読んで僕に教えてくれると嬉しいです;)

*1:vueファイルの解説も書きたかったですが、あまりにも長いので断念

nykergoto’s blog

機械学習とpythonをメインに