nature of code：今日の練習「群れ(2)」、大量のオブジェクトを動かすときに考えたこと(5)

nature of code

See the Pen 群れ(2) by kanaparty (@kanaparty) on CodePen.

boid関連の練習問題、これで最後！
大量ものを動かすときにどうするか悩んだシリーズはこれで最後にしたい・・・！

前回書いたboid群れ
これはせいぜい３０個のビークルを生成するところでカクカクし始めたが
今回は３００個でまぁまぁきれいに動いている気がする

前回との差は、
自分の周りのビークルとの距離を測るとき、
前回は自分以外全てのビークルについて距離を測って計算していたところ、
今回は画面をグリッド上に割って、ビークルが自分自身が存在しているビークルと同じグリッド上にあるビークルだけ距離を測るように変えたこと。

どのグリッドにいるか管理する以下の記述を増やし

//グリッド上のビークルを操作する
class GridList  {
  constructor(){
    this.gridVol = 10;
    this.rowSpan = windowWidth / this.gridVol;
    this.colSpan = windowHeight / this.gridVol;
    this.gridlist = [];
    this.init();
  }
  //グリッドの初期化(グリッドの縦横を決める)
  init(){
    for (var i = 0; i < this.gridVol; i++) {
      this.gridlist[i] = [];
      for (var j = 0; j < this.gridVol; j++) {
        this.gridlist[i][j] = [];
      }
    }
  }
  //どのグリッドに納めるか計算していれる
  push(vehicle){
    var grid = this.calGrid(vehicle.vlocation);
    this.gridlist[grid[0]][grid[1]].push(vehicle);
  }
  //リストを空にする
  clear(){
    for (var i = 0; i < this.gridVol; i++) {
      for (var j = 0; j < this.gridVol; j++) {
        this.gridlist[i][j] = [];
      }
    }
  }
  //該当のグリッドの配列を返す
  retunArrayLinst(location){
    var grid = this.calGrid(location);
    return this.gridlist[grid[0]][grid[1]];
  }
  //どのグリッドに該当するか
  calGrid(location){
    var row = null;
    if(location.x < 0){
      row = 0;
    }
    else if(location.x > windowWidth){
      row = this.gridVol - 1;
    }
    else{
      row = Math.floor(location.x / this.rowSpan);
    }

    var col = null;
    if(location.y < 0){
      col = 0;
    }
    else if(location.y > this.gridVol){
      col = this.gridVol - 1;
    }
    else{
      col = Math.floor(location.y / this.colSpan);
    }

    return [row, col];
  }

}

アニメーションループの中で、全てのビークルがどのグリッドに属しているのかの情報をまとめて、

  var targetVehicle = vehicles.first;
  while (targetVehicle) {
    gridList.push(targetVehicle);
    targetVehicle = targetVehicle.next;
  }

近隣のビークルと距離を測るときに

    var neighborhood = gridList.retunArrayLinst(this.vlocation);

として、自分のいるグリッドにあるビークルのリストを計算対象にすることで だいぶ計算量が減りました。

覚えたこと

  • このやり方をバイナリラティス空間細分割というそう。
  • すべてを実行するのに何回の計算サイクルが必要かどうかを表すのには ビッグ・オー記法(Big-O notation) ビックオー記法とよばれる方法で計算する。

いままで連結リストのことを考えたり、newしないことを考えたりしたけど
だいたいのことはそのまま読み進めればnature of codeの６-14にいろいろ書いてあった。
いつも先回りして読者の疑問を受け止めてくれる構成になっていて、ほんとこの本いい本。
物理演算の章がこれですべて終了、次回からはセルオートマトンに入ります！楽しみ〜