第36回　たくさんのオブジェクトを連結リストで扱う

前回の第35回「たくさんのパーティクルに弾けるようなアニメーションをさせる」ことで表現は仕上がった。今回は本連載の最終回として、たくさんのオブジェクトの扱いについてひとつ知識を深めたい。今回のお題にかぎらず、多くのオブジェクトは配列に入れるのがお約束だ。ただ、そうした処理を自らクラスでつくろうとするとき、「⁠連結リスト」という仕組みがある。それを紹介しよう。

連結リストの使い道

「連結リスト」はオブジェクトを順番にまとめる仕組みだ。配列と同じように、オブジェクトをいくつもエレメントとして加えてから、それらすべてを取り出して扱える。配列と異なるのは、エレメントがインデックスをもたないことだ。そのため、連結リストではエレメントをいきなり指定することはできず、頭から順に取り出しながら目指すオブジェクトを探さなければならない。

では、連結リストはどのような場合に使えて、エレメントをどういうコードで扱うのか。第30回「Box2Dでたくさんのボールを床に落とし続ける」で示したシミュレーションが雰囲気を教えてくれる。第30回コード1「ランダムな位置と大きさのボールをひたすらつくって床に自由落下させる」は、3次元空間の物体（剛体）のオブジェクトを以下のようなコードで取り出して、シミュレーションした。

シミュレーションを進める関数（update()）は、b2World.GetBodyList()メソッドで物理空間に加えられた初めの剛体（body）を取り出す。そのシミュレーションが済んだら、b2Body.GetNext()メソッドでつぎの剛体が得られる。whileループで、取り出す剛体がなくなるまで物理演算を繰り返した（Box2Dの処理については第29回「Box2Dで落としたボールを床に弾ませる」の「すべての剛体を物理シミュレーションする」参照⁠）⁠。

function update(delta) {

  var body = world.GetBodyList();
  while (body) {

    body = body.GetNext();
  }
}

今回のお題にも、すべてのパーティクルをアニメーションさせる以下のような関数（updateAnimation()）がある（第35回「たくさんのパーティクルに弾けるようなアニメーションをさせる」の「すべてのパーティクルを弾けるように動かす」参照⁠）⁠。ここでは配列（particles）を使って、オブジェクトはforループで取り出した。もちろん、この処理にまったく問題はない。

function updateAnimation(eventObject) {
  var count = particles.length;

  for (var i = 0; i < count; i++) {
    var particle = particles[i];

  }

}

今回は練習として、この配列を連結リストのオブジェクトに置き換えてみる。連結リストは簡単なクラスで定める。すると、前掲のコードは、新たに連結リストのオブジェクト（particles）を使ってつぎのように書き替えることになる。連結リストから初めのオブジェクトを得たり、そのつぎのオブジェクトを取り出すには、Box2Dと違ってメソッドでなくプロパティ（firstとnext）を用いた。これは、ライブラリをつくつろうというのではなく、あくまで連結リストの学習なので、少し手間を省いたためだ。

function updateAnimation(eventObject) {

  var particle = particles.first;
  while (particle) {

    particle = particle.next;
  }

}

連結リストのクラスを実装する

連結リストのクラスは、どのような機能をもてばよいか。大きくふたつある。

第1に、連結リストは初めと終わりのエレメントを知らなければならない。すべてのエレメントを扱おうとするとき、その初めのオブジェクトから取り出す。また、連結リストに新たなオブジェクトを加えるとき、終わりのエレメントにつなげてゆくことになる。

第2に、連結リストに加えたエレメントには、それぞれの前と後のオブジェクトを教えてあげる。ムカデ競走の隊列と同じで、自分の前の人と後の人さえ覚えていれば、他にメンバーが加わろうが入れ替わろうが知らなくても順番は組める（図1⁠）⁠。

ふたつの機能は、連結リストにエレメントを加えるメソッドで担うことにする。配列（Arrayクラス）に合わせて、メソッド名はpush()としよう。最初に加えたオブジェクトはfirst、最後のエレメントはlastというプロパティで参照をもつ。

連結リスト.push(オブジェクト)

そして、オブジェクトを連結リストに加えるといっても、順番はエレメント任せだ。前後のオブジェクトの参照を、それぞれprevとnextというプロパティで与えるに過ぎない。いってしまえば、連結リスト自身は初めと終わりを覚えているだけで、その間の順番はまったく知らない。

連結リストのクラスLinkedListとそのpush()メソッドは、以下のコード1のように実装した。コンストラクタの関数本体は空なので、初めプロパティは何ももたない。

push()メソッドの引数（element）に初めてオブジェクトを渡すと、lastプロパティがまだないので、if条件の評価がfalseとなって、else文によりその参照がfirstとlastプロパティに与えられる。その後加えるオブジェクトについてはif条件がtrueとされるので、それまで最後だったオブジェクト（_last）のnextプロパティに自らの参照、自分のprevプロパティには最後だったオブジェクトの参照を与える。そして、LinkedListオブジェクトのlastプロパティを、新たに加えたオブジェクトで差し替えた。

コード1　連結リストのクラスとエレメントを加えるメソッド

function LinkedList() {}
LinkedList.prototype.push = function (element) {
  var _last = this.last;
  if (_last) {
    _last.next = element;
    element.prev = _last;
    this.last = element;
  } else {
    this.first = this.last = element;
  }
};

連結リストを使ったエレメントの扱い方

第35回コード1「クラスからつくったたくさんのパーティクルを弾けるようにアニメーションさせる」に前掲コード1の連結リストのクラス（Particle）を採り入れて書き替えよう。まず、変数（particles）には、配列に替えて連結リストのインスタンスを与える。そして、パーティクルをつくる関数（createParticles()）は、でき上がったインスタンスを連結リストに納める。

// var particles = [];
var particles = new LinkedList();

function createParticles(amount) {
  for (var i = 0; i < amount; i++) {

    var particle = new Particle(_x, _y, stageWidth, stageHeight);
    // particles[i] = particle;
    particles.push(particle);

  }
}

つぎに、パーティクルをアニメーションさせる関数（updateAnimation()）は、前述のとおりの処理になる。つまり、連結リストからプロパティ（first）で初めのパーティクルを得る。それを動かしたら、プロパティ（next）からつぎのオブジェクトを取り出す。whileループでオブジェクトがなくなるまでこれを繰り返せばよい。

function updateAnimation(eventObject) {
  // var count = particles.length;

  var particle = particles.first;
  // for (var i = 0; i < count; i++) {
  while (particle) {
    // var particle = particles[i];

    particle = particle.next;
  }
  stage.update();
}

これらを書き直したのが、以下のコード1だ。前回つくったサンプルと同じように、たくさんのパーティクルがマウスポインタの後を追いかけて弾けるように舞い散る（図2⁠）⁠。前掲コード1と重複するが、確認のためクラスの定めをコード3にまとめた。また、jsdo.itのサンプルも併せて掲げる。

コード2　連結リストに入れたパーティクルをマウスポインタに追随させて弾けるように動かす

var stage;
var stageWidth;
var stageHeight;
var mousePoint = new createjs.Point();
var particles = new LinkedList();
var numParticles = 3000;
function initialize() {
  var canvasElement = document.getElementById("myCanvas");
  stageWidth = canvasElement.width;
  stageHeight = canvasElement.height;
  stage = new createjs.Stage(canvasElement);
  mousePoint.x = stageWidth / 2;
  mousePoint.y = stageHeight / 2;
  createParticles(numParticles);
  stage.update();
  stage.addEventListener("stagemousemove", recordMousePoint);
  createjs.Ticker.timingMode = createjs.Ticker.RAF;
  createjs.Ticker.addEventListener("tick", updateAnimation);
}
function recordMousePoint(eventObject) {
  mousePoint.x = eventObject.stageX;
  mousePoint.y = eventObject.stageY;
}
function updateAnimation(eventObject) {
  var mouseX = mousePoint.x;
  var mouseY = mousePoint.y;
  var particle = particles.first;
  while (particle) {
    particle.accelerateTo(mouseX, mouseY);
    particle = particle.next;
  }
  stage.update();
}
function createParticles(amount) {
  for (var i = 0; i < amount; i++) {
    var _x = Math.random() * stageWidth;
    var _y = Math.random() * stageHeight;
    var particle = new Particle(_x, _y, stageWidth, stageHeight);
    particles.push(particle);
    stage.addChild(particle);
  }
}

コード3　パーティクルと連結リストのクラス

// パーティクルのクラス
function Particle(x, y, right, bottom) {
  this.initialize();
  this.x = x;
  this.y = y;
  this.right = right;
  this.bottom = bottom;
  this.velocityX = 0;
  this.velocityY = 0;
  this.friction = 0.95;
  this.radius = 0.5;
  this.drawParticle();
}
Particle.prototype = new createjs.Shape();
Particle.prototype.drawParticle = function () {
  var size = this.radius * 2;
  this.graphics.beginFill("white")
  .drawRect(-this.radius, -this.radius, size, size);
};
Particle.prototype.accelerateTo = function (targetX, targetY) {
  var _x = this.x;
  var _y = this.y;
  var _velocityX = this.velocityX;
  var _velocityY = this.velocityY;
  var differenceX = targetX - _x;
  var differenceY = targetY - _y;
  var square = differenceX * differenceX + differenceY * differenceY;
  var ratio;
  if (square > 0) {
    ratio = 50 / square;
  } else {
    ratio = 0;
  }
  var accelerationX = differenceX * ratio;
  var accelerationY = differenceY * ratio;
  _velocityX += accelerationX;
  _velocityY += accelerationY;
  _velocityX *= this.friction;
  _velocityY *= this.friction;
  _x += _velocityX;
  _y += _velocityY;
  if (_x < 0) {
    _x += this.right;
  } else if (_x > this.right) {
    _x -= this.right;
  }
  if (_y < 0) {
    _y += this.bottom;
  } else if (_y > this.bottom) {
    _y -= this.bottom;
  }
  this.x = _x;
  this.y = _y;
  this.velocityX = _velocityX;
  this.velocityY = _velocityY;
};
// 連結リストのクラス
function LinkedList() {}
LinkedList.prototype.push = function (element) {
  var _last = this.last;
  if (_last) {
    _last.next = element;
    element.prev = _last;
    this.last = element;
  } else {
    this.first = this.last = element;
  }
};

連結リストを使う意味

今回のお題では、初めにパーティクルをまとめて、後はそれをひたすら順に取り出すだけなので、連結リストをあえて使う利点はなく、配列で構わない。連結リストで手間が省けるのは、インデックスをふらないことだ。

だからたとえば、リストの先頭にオブジェクトを加えるという処理がたくさんある場合、配列はそのたびにインデックスをふり直さなければならない。連結リストなら、先頭だったオブジェクトと新たに加えるオブジェクトふたつのプロパティを書き替えるだけで済む。また、今参照しているオブジェクトをリストから除くときも、連結リストならその前後のオブジェクトのプロパティを改めるだけだ[1]⁠。配列だとこの場合も、インデックスのふり直しが起こる。

とはいえ、そうした処理を大量あるいは頻繁に行うことはおそらく少ない。また、ブラウザによるArrayクラスの扱いは最適化が進んでいるため、速さにおいて優れる場合はかぎられたり、環境によりばらついたりもする。使うとすれば、クラスにそうした処理を自らの手で備えるときだろう。また、Box2Dのようにライブラリの実装を理解するときにも役立つ。「⁠デザインパターン」の「Iterator」（⁠繰返しの意）でも、一部この考えが用いられている。

この第36回をもって、本連載を閉じる。1年半以上にわたっておつき合いくださった読者のみなさんに感謝したい。JavaScriptのライブラリCreateJSとCanvasを使った「Flashみたいな」表現とその考え方が少しでもお伝えできたならば幸いだ。なお、この連載と入れ替るかたちで新たな連載「Away3D TypeScriptではじめる3次元表現」が始まった。CreateJSでは難しかった3次元の表現について、やはりサンプルコードをお題として解説している。興味がある方は、ぜひお読みいただきたい。

本連載が終了した後の2014年12月12日付でCreateJSがアップデートされました。連載で書いたコードは、新バージョンでは正しく動かないことがあります。「⁠新しいCreateJSで書くコードはどう変わるのか」が著者のサイトで解説されていますのでご参照ください（04「古いコードを新たに書替えてみる」には新バージョンに書替えたjsdo.itのサンプルが掲載されています⁠）⁠。