Lifegame Mobile (CoffeeScript)



    


    



Boids – 群の行動

動物の群の行動をシミュレートする”Boids”という考え方をCoffeeScriptで組んでみたもの。個体がそれぞれ独立して一定のルールに従って行動する結果、群としての整然とした行動をとるようになる。

スマートフォン用はこちら







Boidsの考え方や開発過程はこちら

このアプリケーションのコード説明はこちら


Boids 2.3 – コード説明

概要

Boids 2.3では、分離(Separation)、結合(Cohesion)に加えて「整列(Alignment)」のルールを導入する。整列行動の考え方は、ここでは以下の通りとした。

  1. 前方視野内に個体が存在する場合、それらの個体の平均速度を求める
  2. 進行方向を、群の平均速度の方へ向けて少し変更する

なおこのバージョンで、個体生成時にランダムに与える速度の計算方法を変更した。

速度計算の変更

これまで、個体を生成したときに与える速さは、上限値V_MAXを定数としておいて、V_MAX~VMAX/2の範囲で一様乱数を発生させていた。

Boids 2.3では、速さの上限値vMAXに加えて下限値vMINCreatureクラスのクラス変数に持たせて、この間の一様乱数で速さを設定する。

これに伴って、以下を追加

  • HTMLの<script>要素に定数V_MINを追加
  • ControlerクラスにvMinのセッターを追加
  • セッターを通してV_MINの値をCreature._vMinにセット

整列のアルゴリズム

平均速度の算出

次図において、先方視野内に個体が存在する場合、それらの平均速度vmeanを計算する。

    $$ {\bf v}_{\rm mean} = \frac{1}{n} \sum^n_{i=1} {\bf v}_i $$

なお視野内の判定は、ベクトルの前後判定と個体との距離計算によっている。

boid2x_alignment_vmean

進路変更

先の図のように、自身の進行方向に対する平均速度の方向によって、以下の手順で進路を変更する。

  1. 平均速度ベクトルの向きが自身の進行方向より左右どちらに向いているかを判定
  2. 平均速度ベクトルが進行方向より右に向いているなら右へ、左に向いているなら左へ方向を少し変化させる。

これらの考え方はBoids 2.1の分離行動における回避動作と同じ。

コード内容

初期パラメータ定義

HTMLで定義する初期パラメータに、整列に関する以下の変数を追加する。

  • 整列判定の視野の深さ(BD23_ALIGNMENT_FIELD_DEPTH)
  • 整列行動における速度の変更角(BD23_ALIGNMENT_ANGLE)

なお、このバージョンで分離行動の視野の深さの変数名を変更している。

クラス変数

初期パラメータの保存のため、Creatureクラスのクラス変数を追加する。

パラメータのセッター

Controlerクラスに、Creatureクラス変数へのセッターを定義する。

パラメータのセット

HTMLで定義されたパラメータをControlerオブジェクトのセッターによってセットする。

Ceatureクラスの変更 – alignment()メソッドの追加

Creatureクラスのmove()メソッドがalignment()メソッドを呼び出すようにする。

alignment()メソッドを新たに定義する。

  • 速度の方向を変化させる回転行列のcos、sinに対応したローカル変数cssnを定義している
  • 平均速度の参照がvMeanプロパティに保存されるが、視野内に個体が存在しないときはnullとなる
  • 速度の回転方向は、右がマイナス方向、左がプラス方向となることに注意

全コード

以下に、分離、結合、整列の3ルールすべてを適用したBoids 2.3の全コードを示す。


↑ Boids 2.2のコード説明へ

↑ Boids 3.0のコード説明へ

Boids 2.2 – コード説明

概要

Boids 2.2では、分離(Separation)に加えて「結合(Cohesion)」のルールを導入する。結合行動の考え方は、ここでは以下の通りとした。

  1. 前方視角内に個体が存在する場合、それらの重心位置を求める
  2. 進行方向を、重心の方へ向けて少し変更する

結合のアルゴリズム

重心の算出

次図において、進行方向に直角な直線hより前方側の個体が存在する場合、それらの重心位置gを計算する。

    $$ {\bf g} = \frac{1}{n} \sum^n_{i=1} {\bf p}_i $$

なお、視野角の前方判定はベクトルの前後判定によって行っている。

boid2x_cohesion_gravity_center

進路変更

先の図のように、自身の進行方向に対する群の重心の位置によって、以下の手順で進路を変更する。

  1. 重心位置が自身の進行方向に対して左右どちら側にあるかを判定
  2. 重心位置がが進行方向より右側にあるなら右へ、左側にあるなら左へ方向を少し変化させる。

これらの考え方はBoids 2.1の分離行動における回避動作と同じ。

コード内容

初期パラメータ定義

HTMLで定義する初期パラメータに、結合に関する以下の変数を追加する。

  • 結合の進行方向の変化(BD22_COHESION_ANGLE)

クラス変数

初期パラメータの保存のため、Creatureクラスのクラス変数を追加する。

パラメータのセッター

Controlerクラスに、Creatureクラス変数へのセッターを定義する。

パラメータのセット

HTMLで定義されたパラメータをControlerオブジェクトのセッターによってセットする。

Ceatureクラスの変更 – cohesion()メソッドの追加

Creatureクラスのmove()メソッドがcohesion()メソッドを呼び出すようにする。

coheion()メソッドを新たに定義する。

  • 速度の方向を変化させる回転行列のcos、sinに対応したローカル変数cssnを定義している
  • 重心位置への参照がclusterCenterプロパティに保存されるが、視野内に個体が存在しないときはnullとなる
  • 速度の回転方向は、右がマイナス方向、左がプラス方向となることに注意


↑ Boids 2.1のコード説明へ

↓ Boids 2.3のコード説明へ

Boids 2.1 – コード説明

概要

Boids 2.1では、いよいよBoidsのルールの一つ「分離(Separation)」を導入する。分離行動の考え方は、ここでは以下の通りとした。

  1. 視野内に個体が存在するとき、最も距離が近い個体を選択する
  2. その直近個体と反対方向に、自身の進行方向を変化させる

分離のアルゴリズム

視野

個体は自身の進行方向の左右90度以内、180度の視野角を持ち、その視野角内で一定距離以内の個体に反応するものとする。

視野内外の判定の概念は下図の通りで、個体Pは視野内と判定され、個体Qは視野外として無視される。

boids2x_perspective

視野内外判定の手順は以下の通り。

  1. 前後判定の方法により、視野角内の個体があればそれを選定
  2. その個体について\overline{\rm SP}} \leqq lならば次へ進む
  3. その個体が最も近いなら入れ替え

回避動作

回避対象が自身の進路の右にいるなら左に、進路の左にいるなら右に、方向ベクトルの角度を変更する。進路変更の角度は予め設定しておく。

boids2x_separation_avoidance

回避動作の手順は以下の通り。

  1. 左右判定の方法により、回避対象が進行方向の左右どちらにあるかを判定
  2. 回避対象が進行方向の左にあるなら右へ、右にあるなら左へ方向を少し変化させる。

ここで方向ベクトルの変化量θは予め設定しておき、これに対応するcos、sinによる回転行列を適用して方向を変える。cos、sinの値は、できるだけ計算量が少なくなるようにする。

コード内容

初期パラメータ定義

HTMLで定義する初期パラメータに、分離に関する以下の変数を追加する。

  • 分離に関する視野の深さ(BD21_VIEW_FIELD_LENGTH)
  • 回避行動の進行方向の変化(BD21_SEPARATION_ANGLE)

クラス変数

初期パラメータの保存のため、Creatureクラスのクラス変数を追加する。

パラメータのセッター

Controlerクラスに、Creatureクラス変数へのセッターを定義する。

パラメータのセット

HTMLで定義されたパラメータをControlerオブジェクトのセッターによってセットする。

Ceatureクラスの変更 – separation()メソッドの追加

Creatureクラスのmove()メソッドがseparation()メソッドを呼び出すようにする。

separation()メソッドを新たに定義する。

  • 速度の方向を変化させる回転行列のcos、sinに対応したローカル変数cssnを定義している
  • 最も近い個体への参照がnearestCreatureプロパティに保存されるが、視野内に個体が存在しないときはnullとなる
  • 速度の回転方向は、右がマイナス方向、左がプラス方向となることに注意

 


↑ Boids 2.0のコード説明へ

↓ Boids 2.2のコード説明へ

 

Boids 2.0 – コード説明

概要

Boids 2.0は以後のBoids 2.xシリーズの土台となるもので、Boids 1.2に対して以下を変更している。

  • 位置と速度を持ったCreatureクラスのうち、位置と速度の保持、互いの位置関係の判定に関する性質を汎用のMovingAgentクラスとしてまとめ、taustation-geo2dパッケージに含めた
  • 初期パラメータをHTMLのスクリプトに置き、再コンパイルしなくてもパラメータを変更しやすくなるようにした。

MovingAgentクラスの導入

CreatureクラスはMovingAgentクラスを継承し、それらのメソッドを利用する。

 MovingAgentのプロパティを継承するため、位置と速度の指定が変更。たとえばCreatureクラスのインスタンスがcreatureだとすると、以下のようになる。

  • 位置のx座標は、creature:pos.x
  • 位置のy座標は、creature:pos.y
  • 速度のx成分は、creature:v.x
  • 速度のy成分は、creature:v.y

HTMLでの初期パラメータ設定

概要

各種パラメータの設定を、CoffeeScriptの再コンパイルやアップロードをしなくても、HTMLで設定・変更できるようにした。

  • 必要なパラメータをHTMLのスクリプトで定義
  •  以下のパラメータをセットするセッターを、全てControlerクラスのメソッドとして集約
    • 個体に関するパラメータはCreatureのクラス変数
    • アニメーションのインターバルはControlerクラスのプロパティ
  • スクリプト読み込み時に、Controlerオブジェクトのセッターにグローバル・パラメータ変数を渡してパラメータ設定

初期パラメータ定義

HTMLにパラメータをグローバル変数としてスクリプト記述。

注意点は、スクリプトはJavascriptにコンパイルされているので、直接読み込まれるグローバル変数もJavascriptの変数として書くこと。特に各定義の文末にセミコロン(;)を付けること。

クラス変数

上記のパラメータのうち、個体の運動に関わるものを、Creatureクラスのクラス変数として定義。

なお、アニメーションのフレーム・インターバル(interval_sec)は、Controlerクラスのクラス変数として定義している。

パラメータのセッター

上記のクラス変数にパラメータをセットするセッターを、Controlerクラスのメソッドとして集約。

パラメーターのセット

スクリプト実行時に、上記セッターを通してグローバル変数のパラメータを設定する。

Boids 2.0の全コード


↓ Boids 2.1のコード説明へ

CoffeeScript – Boids 2.x – ルールの実装

Boids 2.xの概要

Boids 2.xシリーズでは、Boids 1.xで準備した土台となるコードに、個体の行動ルール(分離、結合、整列)を一つずつ実装していく。

  1. Boids 2.0 Boids1.2のコードを以下のように変更。
    • Creatureクラスから汎用のMovingAgentクラスを分離して、これを継承
    • 初期パラメータの設定値をHTMLに置いて、変更しやすくした
  2. Boids 2.1 分離(Separation)のルールを適用し、互いの衝突を避けるようにする。
  3. Boids 2.2 結合(Cohesion)のルールを適用し、個体が群に集まろうとする傾向を持たせる。
  4. Boids 2.3 整列(Alignment)のルールを適用し、個体が皆と同じ方向に動こうとする傾向を持たせる。

Boids 2.0 – 基本コード

基本コードの挙動はBoids 1.2と同じで、各個体は壁との衝突を避けながら自由に動くが、他の個体は意識しない。

Boids 2.0のコード詳細



Boids 2.1 – 分離(Separation)

個体同士の衝突を避けるように進路を変更する行動ルールを適用する。他の個体が接近したときに、それぞれが進路を変更している様子がわかる。

Boids 2.1のコード詳細



Boids 2.2 – 結合(Cohesion)

各個体が、視野内の群の重心に向かって進路を変更するルールを適用する。全体として群を形成しようとする様子がわかる。

Boids 2.2のコード詳細



Boids 2.3 – 整列(Alignment)

各個体が、視野内の群の全体としての移動方向に自分の進路を合わせるよう変更するルールを適用する。群が全体として同じ方向に動こうとしている様子がわかる。

Boids 2.3のコード詳細




↑ Boids 1.x

 










CoffeeScript – geom2d.MovingAgentクラス

パッケージ

taustation_geom2d

クラス名

taustation_geom2d.MovingAgent

クラス仕様

概要

自分の位置を表すVectorオブジェクトと移動速度を表すVectorオブジェクトを要素に持ち、他のMovingAgentとの位置関係を判定するメソッドを準備している。

なお、Vectorクラスには、Vectorを位置ベクトルとしたときに、その点とMovingAgentとの位置関係を表すメソッドが用意されている。

クラス変数

なし

クラス・メソッド

なし

インスタンス・プロパティ

pos
自らの位置を保持するVectorオブジェクト
v
自らの移動速度を保持するVectorオブジェクト

コンストラクタ

constructor()
位置(0, 0)、速度(0, 0)のMovingAgentインスタンスを生成する。

インスタンス・メソッド

基本メソッド

setPosition(x, y)
MovingAgentの位置をx、yの座標値で指定する。
setVelocity(vx, vy)
MovingAgentの速度をvx、vyの成分で指定する。
getClone()
元のMovingAgentオブジェクトと同じ内容のクローンを生成して返す。

判定

isInFrontOf(other)
このMovingAgentオブジェクトが引数のMovingAgentオブジェクトの前方(左右180度より進行方向の側)にあるときtrue、後方にあるときfalseを返す。真横の時は前方と判定される。
isIntheRearOf(other)
isInFrontOf()と前後逆の判定結果を返す。
isOnTheRightOf(other)
このMovingAgentオブジェクトが引数のMovingAgentオブジェクトの右方にあるときtrue、左方にあるときfalseを返す。進行方向の延長線上にあるときは右方と判定される。
isOnTheLeftOf(movingAgent)
isOnTheRightOf()と左右逆の判定結果を返す。

コード

 

直線のパラメータ表示と操作

直線のパラメータ表示

たとえば2次元の直線のパラメータ表示は、以下のように一つのパラメータtに対してxとyが計算される方法。

    $$ \left\{ \begin{align*} x = a t + b \\ y = c t + d \end{align} \right. $$

直線の決定

通過点と方向が与えられた場合

直線が通過すべき点(px, py)と、直線の方向(vx, vy)が与えられた場合のパラメータ表示を決定する。

通過点でパラメータがt = 0とすればpxとpyが定まり、tが1単位増えた時のxとyの増分が直線の方向に対応することから、以下のように表される。

    $$ \left\{ \begin{align*} x = v_x t + p_x \\ y = v_y t + p_y \end{align} \right. $$

なおこれらを、パラメータtに対応した直線状の点の位置ベクトル{\bf x}、通過点の位置ベクトル{\bf p}、方向ベクトル{\bf v}で表示すると下記のようになる。

    \[{\bf x} = {\bf v} t + {\bf p}\]

2つの通過点が与えられた場合

2つの点p(px, py)とq(qx, qy)が与えられた場合の直線のパラメータ表示を決定する。

点pでt = 0、点qでt = 1とすれば、以下の式が得られる。

    $$ \left\{ \begin{align*} x = (q_x - p_x) t + p_x \\ y = (q_y - p_y) t + p_y \end{align} \right. $$

これをベクトル表示すれば以下の通り。

    \[{\bf x} = ( {\bf q} - {\bf p} ) t + {\bf p}\]

直線の式との関係

一般に直線の式は以下で与えられる。

    \[ax + by + c = 0\]

一方で媒介変数された直線の式からパラメーターを消去すると以下のようになる。

    \[\frac{x - p_x}{v_x} = \frac{y - p_y}{v_y}\]

これを変形すると、先の直線の式との対応関係がわかる。

    \[v_y x - v_x y -v_x p_x + v_y p_y = 0\]

交点の特定

以下の2つの直線の交点を求める。

    $$ \left\{ \begin{align*} {\bf x}_1 = {\bf v}_1 t_1 + {\bf p}_1 \\ {\bf x}_2 = {\bf v}_2 t_2 + {\bf p}_2 \end{align} $$

これを要素表示に展開する。

    $$ \left\{ \begin{align*} x_1 = v_{1x} t_1 + p_{1x} \\ y_1 = v_{1y} t_1 + p_{1y} \\ x_2 = v_{2x} t_2 + p_{2x} \\ y_2 = v_{2y} t_2 + p_{2y} \end{align} $$

ここでx1 = x2、y1 = y2と置いて、t1、t2を未知数とした以下の方程式を得る。

    $$ \left\{ \begin{align*} v_{1x} t_1 + p_{1x} = v_{2x} t_2 + p_{2x} \\ v_{1y} t_1 + p_{1y} = v_{2y} t_2 + p_{2y} \end{align} $$

この方程式を行列で表示すると以下の通り。

    \[\left[ \begin{array}{cc} v_{1x} & -v_{2x} \\ v_{1y} & -v_{2y} \end{array} \right] \left[ \begin{array}{c} t_1 \\ t_2 \end{array} \right] = \left[ \begin{array}{c} p_{2x} - p_{1x} \\ p_{2y} - p_{1y} \end{array} \right] = \left[ \begin{array}{c} \Delta p_x \\ \Delta p_y \end{array} \right]\]

これを解いて以下を得る。

    $$ \left\{ \begin{align*} t_1 = \frac{-v_{2y} \Delta p_x + v_{2x} \Delta p_y}{-v_{1x}v_{2y} + v_{1y} v_{2x}} \\ t_2 = \frac{-v_{1y} \Delta p_x + v_{1x} \Delta p_y}{-v_{1x}v_{2y} + v_{1y} v_{2x}} \end{align} \right. $$

これらの式は分母がゼロのときは解をもたないが、これは{\bf v}_1{\bf v}_2を90度回転させたベクトルが直角であること、すなわち2つの直線の方向が平行であることを示している。

さらに2つの直線がまったく一致するときは、分母・分子ともゼロとなり、解は不定となる。

ここで、交点の座標を確認する。

    $$ \begin{align*} x &= v_{1x} t_1 + p_{1x} = v_{2x} t_2 + p_{2x} \\ &= \frac{v_{1y} v_{2x} p_{1x} - v_{1x} v_{2y} p_{2x} + v_{1x} v_{2x}(p_{2y} - p_{1y})} {-v_{1x} v_{2y} + v_{1y} v_{2x}} \\ y &= v_{1y} t_1 + p_{1y} = v_{2y} t_2 + p_{2y} \\ &= \frac{v_{1y} v_{2y} (p_{2x} - p_{1x}) - v_{1x} v_{2y} p_{1y} + v_{1y} v_{2x} p_{2y}} {-v_{1x} v_{2y} + v_{1y} v_{2x}} \end{align} $$

当然この結果は、パラメータ表示の2直線からパラメータt1、t2を消去して陰関数表示をした以下の方程式の解と一致する。

    $$ \left\{ \begin{align*} v_{1y} x - v_{1x} y = v_{1y} p_{1x} - v_{1x} p_{1y} \\ v_{2y} x - v_{2x} y = v_{2y} p_{2x} - v_{2x} p_{2y} \end{align} \right. $$

 

交点の位置

パラメータ表示の場合、基準点においてt = 0とし、方向ベクトルの先、あるいはそれに相当する2つ目の点においてt = 1などとすれば、基準点から方向ベクトルの先のtは正の値、逆方向ではtが負の値になる。

これを利用して、二つの直線の交点が基準点より前方/後方どちらの側にあるか、あるいは半直線に交点が存在するか、といった判定が容易に可能となる。

math_geom_line1

 

ベクトルの内積

ベクトルの内積の表現には、要素表示を用いたものと幾何的なものの2つがある。

    $$ {\bf a} \cdot {\bf b} = a_x b_x + a_y b_y + a_z b_z = | {\bf a} | | {\bf b} | \cos \theta $$

2つの表現が等価であることを証明するのに、下図のように2つのベクトルで張られた三角形の\oberline{AB}の長さを考える。

math_vector_innerprod_1

まずベクトルの成分で計算した場合は、

    $$ \begin{align*} \overline{AB}^2 &= (a_x - b_x)^2 + (a_y - b_y)^2 + (a_z - b_z)^2 \\ &= a_x^2 + a_y^2 + a_z^2 + b_x^2 + b_y^2 + b_z^2 - 2 a_x b_x - 2 a_y b_y - 2 a_z b_z \end{align} $$

また余弦定理を用いて計算した場合は、a = | {\bf a} | , \: b = | {\bf b} |として以下のようになる。

    $$ \begin{align*} \overline{AB}^2 &= a^2 + b^2 - 2ab \cos \theta \\ &= a_x^2 + a_y^2 + a_z^2 + b_x^2 + b_y^2 + b_z^2 - 2ab \cos \theta \end{align} $$

上記2つが等しいことから、以下が得られる。

    $$ a_x b_x + a_y b_y + a_z b_z = ab \cos \theta $$

2次元の場合は、z成分を0とおいてx成分とy成分のみについて考えればよい。