セルオートマトンによる交通流シミュレーション


## はじめに

作成したプログラムは、一本道を多くの人(あるいは車)が一列で歩く場合のシミュレーションをするというものです。
セルの上には、一つのエージェントが存在し、進行方向にあるセルの状態によって、そのエージェントが進むか留まるかが決めるという極めて単純な交通流モデルになっています。

車を運転していると、なぜここで渋滞が発生しているんだろうと疑問に思うことがあります。運転していたらいつの間にか渋滞が解消されていたなんて経験をすることもよくあります。その疑問の答えになるかどうかはわかりませんが、簡単なモデルで車の流れをシミュレーションしてみようというものです。

今はコンピュータの能力も高く、ここで示したプログラムよりももっと複雑なシミュレーションが実際には行われていると思いますが、400行ほどの小さいプログラムでも、それなりに興味深い動きを確認できます。

## 作成するプログラムのルールを定める

ここでは、人や車をAgentと呼ぶことにします。 作成したプログラムでは、３つの特徴をもったAgentを用意しました。

 1. 前に空きがあると一歩進む。
 2. 前に３つの空きがあると一歩進む。
 3. ランダムに停止したり進んだりする。停止する時間もある範囲でランダムに決定される。

画面上区別がつくように、グレー、青、赤色分けをしています。 なお、3のagentは１つだけ存在することとします。

このAgentは常に一方向に進み、その道は環状とします。

初期状態は、ある隙間でAgentが並んだ状態です。 開始ボタンを押すと、シミュレーションが開始します。 
つまり、赤信号から青信号になり車が動き出す状態と見なすことができます。 

## 実行例


### 初期状態

![スクリーンショット 2019-04-16 13.28.46.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/29415/a64b25ca-7f02-56fb-90a7-55a6b9d70ef3.png "スクリーンショット 2019-04-16 13.28.46.png")


### スムーズに進んでいる状態

![スクリーンショット 2019-04-16 13.29.24.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/29415/1bb2a806-f83a-dd42-5fd1-c757cadd72d0.png "スクリーンショット 2019-04-16 13.29.24.png")


### 渋滞が発生している状態

![スクリーンショット 2019-04-16 13.30.21.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/29415/3d16f0e3-2226-373e-f410-925713885eb8.png "スクリーンショット 2019-04-16 13.30.21.png")



このページの最後にCodePenのコードを張り付けてますので、そこで動きを確認できます。

## 観察してみた結果

赤のAgentは、列の最後に配置しているので、最初のうちは渋滞はありません。
しかし、根気よく眺めていると、先頭だったAgentが、赤のAGentに追い付き、そこから渋滞が発生します。
つまり、3の赤のAgentが渋滞の原因を作り出していることが分かります。
また、それ以外のAgenthは、渋滞の原因にはほとんど関係ないということもわかります。

「clearLazyCar」ボタンを押すと、3番(赤)の車は、1の車と同じ動きに変わります。そうすると、徐々に渋滞が解消されていくのがわかります。3番(赤)の車に戻す機能をつけていないので、再度初期状態から動かしたい場合は、ページをリロードしてください。

僕は、この手の専門家ではないし知識もほとんど無いので、このモデルというか、僕が作成したプログラムがどれくらい現実的なものなのかはわかりませんが、 まあ、それなりにおもしろい動きになっていると思います。 

信号機の場所を一箇所設けて、ある周期で赤と青になるようにしたり、1台1台スピードの概念を導入すれば、もっと面白い動きが見られるかもしれませんね。


## 作成したクラス

このプログラムは、６つのソースから成っています。 

### program.js  

画面の表示部分を受け持っています。UIがらみと、simulationクラスの呼び出しを担当しています。
Agentを描画する際の座標計算が面倒くさい（僕の数学的素養だとこれが精いっぱい）ですが、それ以外は、それほど複雑なことはやっていません。

Simulationクラス内で、全てのAgentのwalkメソッドを１回ずつ呼び出し終わると、イベントが発生しpaintメソッドが呼ばれます。
paintメソッドがその時の状態をCanvasに描画することで、Agentが動いているように見えます。

### simulation.js 

このシミュレーション全体を管理します。startメソッドで全てのAgentが動き始めます。stopメソッドが呼ばれるまで、Agentは動き続けます。

本当は、スレッドのようなものを使ってAgentを動かしたかったのですが、JavaScriptでどう実現するかわからなかったので、普通の繰り返し文で複数のAgentの処理をしています。
ただ、それだと描画のタイミングがないので、setTimeout関数を使ってます。

### road.js

道路を表します。道路は複数のセルが環状につながったものです。一つのセルに一つのAgentが存在できます。何もないところはnullが入っています。

ただし描画とは完全に独立しています。あくまでも論理的な道路で描画は行いません。

### agent.js

Agentを表します。このクラスは、プロパティに次に示すcharactorオブジェクトを保持していて、そのオブジェクトの性質で動作が変わります。
Agentクラスは１台のエージェントを表します。 どのような動きをするのかは、Agentクラスのメンバーに保持しているcharactorオブジェクト（後述）が受け持ちます。 
このコードの特徴は、それぞれのAgentにcharacterというプロパティを宣言し、 このcharacterオブジェクトが、どういった性格（色と進むかどうかの判断）なのかを 表している点です。いわゆる「ストラテジーパターン」を使っています。 いろんな性格のcharacterクラスを定義してみると面白いかもしれません。

### charactor.js

Agentの３つの性質を表すクラスを定義しています。
NormalCharacterは、前が開いていたら進みます。
CarefulCharacterは、前が３つ空いていたら進みます。
LazyCharacterは、気まぐれな性質を持っていて、進んだり止まったりします。

JavaScriptで面白いと思うのは、抽象クラスやインターフェースを作らなくても、同じメソッドを持っていればポリモーフィズムが使えるという点ですね。
このプログラムでも、この３つの継承元となるクラスは定義していません。


### canvas.js

HTML5のCanvasAPIをラッピングしているクラスで、このプログラムで利用する描画機能だけを定義したものです。

`drawLine`(線を引く),  `drawPoint`(点を打つ),  `clearAll`(全てをクリアする) という３つのメソッドを実装しています。


## HTML/JavaScriptのコード

ちょっと長めのコードですが、それぞれのクラスはそれほど複雑なことをしているわけではないので、 読んでいただければご理解いただけると思います。

### HTML

```html
<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  <title>Traffic flow</title>
  <style>
      canvas {
          margin: 11px;
      }
  </style>
</head>
<body>
  <div>
  <input id="startButton" type="button" value="Start" >
  <input id="stopButton" type="button" value="Stop" >
  <input id="clearLazyCar" type="button" value="clearLazyCar" >
</div>
  <div>
      <canvas id="mycanvas"></canvas>
  </div>
  <div id="status"></div>

  <script type="module">
      import { Program } from './program.js';

  </script>
</body>
</html>
```

### program.js


```js
import { MyCanvas } from './canvas.js';
import { Simulation } from './simulation.js';
import { Road } from './road.js';
import { NormalCharacter, CarefulCharacter,LazyCharacter } from './character.js';
import { Agent } from './agent.js';

export class Program {
    constructor() {
        this.pointSize = 5;
        this.sideLength = 100;
        this.sideHeight = 5;
        let width = this.sideLength * this.pointSize + 40;
        let height = this.sideHeight * 6 * this.pointSize + 40;
        this.canvas = new MyCanvas('mycanvas', width, height);
        
        this.agents = this.createAgents();
        this.road = new Road(this.getRoadLength(), this.agents);
        
        this.simulation = new Simulation(this.road, this.agents);
        this.paint();
        this.simulation.OnChanged = () => {
            this.paint();
        };
    }

    getRoadLength() {
        return this.sideLength * 6 + this.sideHeight * 4 + 4;
    }

    
    createAgents() {
        let normal = new NormalCharacter();
        let careful = new CarefulCharacter();
        let lazy = new LazyCharacter();
        let roadLen = this.getRoadLength(this.sideLength);
        let agents = [];
        // 道の初期化 （エージェントを置く)
        for (let i = 0; i < roadLen / 3 - 20 ; i++) {
            let chr = (i % 30 == 0) ? careful : normal;
            if (i == 0)
                 chr = lazy;
            agents.push(new Agent(i*3, chr));
        }
        return agents;
    }
    
    run() {
        document.getElementById('startButton')
            .addEventListener('click', () => this.start(), false);
        document.getElementById('stopButton')
            .addEventListener('click', () => this.stop(), false);
        document.getElementById('clearLazyCar')
            .addEventListener('click', () => this.clearLazyCar(), false);
    };

    start() {
        this.simulation.start();

    };

    stop() {
        this.simulation.stop();
    };
    
    clearLazyCar() {
        this.simulation.clearLazyCar();
    };

    // 描画 （初期状態の描画 と 途中の状態の描画）
    paint() {
        var agents = this.road.getAgents();
        for (let i = 0; i < agents.length; i++) {
            let agent = agents[i];
            if (agent != null)
                this.setPixel(i, agent.color);
            else
                this.clearPixcel(i);
        }
    }
    
    // pos 地点に指定した色で■を描く
    setPixel(pos, color) {
        let loc = this.calcLocation(pos);
        this.canvas.drawPoint(loc[0], loc[1], color);
    }

    // pos 地点の色をクリアする
    clearPixcel(pos) {
        let loc = this.calcLocation(pos);
        this.canvas.drawPoint(loc[0], loc[1], '#fff');
    }
    
    // x,y座標に変換する. 計算をもっと簡単にしたいが... 三角関数で丸を描いたほうが良かったかも。
    calcLocation(pos) {
        let x = 0;
        let y = 0;
        let wp = pos - 2;
        let r = Math.floor(wp / this.sideLength);
        if (r < 0)
            r = 0;
        let c = wp % this.sideLength
        switch (r) {
            case 0:
            case 2:
            case 4:
                x = c + 2
                y = r * this.sideHeight;
                if (c >= this.sideLength - (this.sideHeight - 1)) {
                    let d = c - this.sideLength + this.sideHeight;
                    x -= d;
                    y += d;
                }
                break;
            case 1:
            case 3:
            case 5:
                x = this.sideLength - c - (this.sideHeight - 2);
                y = r * this.sideHeight;
                if (r < 5) {
                    if (c >= this.sideLength - (this.sideHeight - 1)) {
                        let d = c - this.sideLength + this.sideHeight;
                        x += d;
                        y += d;
                    }
                } else {
                    if (x < 0) {
                        y += x;
                        x = 0;
                    }
                }
                break;
            default:
                x = 0;
                y = this.sideHeight * 5 - (c + this.sideHeight - 2);
                break;
        }
        x = x * this.pointSize + 20;
        y = y * this.pointSize + 20;
        return [x, y];
    }

}

var program = new Program();
program.run();
```

### simulation.js


```js
import { NormalCharacter, CarefulCharacter,LazyCharacter } from './character.js';

export class Simulation {

    constructor(road, agents) {
        this.road = road;
        this.agents = agents;
        this.isStop = false;
        this.OnChanged = null;   
    }

    // 開始する
    start() {
        this.isStop = false;
        this.run();
    }

    // 停止する
    stop() {
        this.isStop = true;
    }
    
    clearLazyCar() {
        let agent = this.agents.find(x => x.character instanceof LazyCharacter);    
        agent.character = new NormalCharacter();
    }
    
    // 一つのエージェントの処理
    run() {
        if (this.isStop)
            return false;
        setTimeout(() => {
            let agents = this.agents.reverse();
            for (let agent of agents) {
                agent.walk(this.road);
            }
            if (this.OnChanged != null) {
                this.OnChanged();
            }
            this.run();
        }, 50);        
        return true;
    }
}
```

### road.js

```js
import { Agent } from './agent.js';

// 道路を表すクラス
export class Road {
    constructor(size, agents) {
        this._cells = [];
        for (let i = 0; i < size; i++)
            this._cells.push(null);
        for (let agent of agents)
            this._cells[agent.position] = agent;
            
        this.length = size;
    }
    
    get(index) {
        return this._cells[index % this.length];
    }

    set(index, value) {
        this._cells[index % this.length] = value; 
    }
    
    getAgents() {
        return this._cells;
    }
}
```

### agent.js

```js
export class Agent {
    constructor(position, character) {
        this.position = position;
        this.character = character;
    }
    
    get color() {
        return this.character.color;
    }
    
    // 歩く 
    walk(road) {        
        let np = (this.position + 1) % road.length;

        // characterにより動作が異なる 
        if (this.character.canForward(road, np))
            this.goForward(road, np);
    }

    // nextの地点に進む。
    goForward(road, next) {
        road.set(this.position, null);
        road.set(next,this);
        this.position = next;
    }  

}
```

### charactor.js

```js

// 前が空いていたら進む
export class NormalCharacter  {
    canForward(road, next) {
        return (road.get(next) == null);
    }

    get color() {
        return '#CCE4F7';
    }
}

// 前に3つ空いていないと進まない
export class CarefulCharacter  {
    canForward(road, next) {
        let n2 = (next + 1) % road.length;
        let n3 = (n2 + 1) % road.length;
        
        return (road.get(next) == null && (road.get(n2) == null) && (road.get(n3) == null));
    }
    
    get color() {
        return '#00A0E1';
    }
}

// 気まぐれで進む
// これは1台だけという前提。
export class LazyCharacter {
    constructor() {
        this.stopcount = 0;        
    }
    
    canForward(road, next) {
        if (road.get(next) !== null)
            return false;
        if (this.stopcount > 0) {
            this.stopcount--;
            return false;
        }
        let min = 0;
        let max = 50;
        var r = this.getRandom(min, max);
        if (r > 5)
            return true;
        r = this.getRandom(min, max);
        if ( r > 45) {
            this.stopcount = this.getRandom(20, 50);
        }
        return false;
    }

    getRandom(min, max) {
        return Math.floor(Math.random() * (max - min) + min);
    }
    
    
    get color() {
        return '#FF0000';
    }
}
```

### canvas.js

```js
export class MyCanvas {
    constructor (id, width, height) {
        this.canvas = document.getElementById(id);
        this.ctx = this.canvas.getContext('2d');
        if (width)
            this.ctx.canvas.width = width;
        if (height)
            this.ctx.canvas.height = height;
        this.width = this.ctx.canvas.width;
        this.height =  this.ctx.canvas.height;
        // ユーザが定義するイベントハンドラ
        this.onClick = null;

        //let self = this;
        this.canvas.onclick = (e) => {
            let x = e.clientX - this.canvas.offsetLeft;
            let y = e.clientY - this.canvas.offsetTop;
            if (this.onClick)
            this.onClick(x, y);
        };
    }

    // 線
    drawLine(x1, y1, x2, y2, color = null, width = 1) {
        this.ctx.save();
        if (color != null)
            this.ctx.strokeStyle = color;
        this.ctx.lineWidth = width;
        this.ctx.beginPath();
        this.ctx.moveTo(x1, y1);
        this.ctx.lineTo(x2, y2);
        this.ctx.closePath();
        this.ctx.stroke();
        this.ctx.restore();
    }

    drawPoint(x1, y1, color, size = 5) {
        this.ctx.save();
        this.ctx.beginPath();
        this.ctx.fillStyle = color;
        this.ctx.fillRect(x1 - Math.ceil(size/2), y1-Math.ceil(size/2), size, size);
        this.ctx.restore();
    }

    // すべてをクリア
    clearAll() {
        this.ctx.clearRect(0, 0, this.width, this.height);
    }
}
```

## CodePenのページを埋め込んでおく


CodePenのページを埋め込んでみたので、ここで動作を確認できます。

左ペインの[JS]ボタンをクリックすると、全体が[Result]画面になるので、それから、Startボタンを押してください。


<p class="codepen" data-height="400" data-theme-id="0" data-default-tab="js,result" data-user="gushwell" data-slug-hash="wZPEGJ" style="height: 265px; box-sizing: border-box; display: flex; align-items: center; justify-content: center; border: 2px solid black; margin: 1em 0; padding: 1em;" data-pen-title="TraficFlowSim">
  <span>See the Pen <a href="https://codepen.io/gushwell/pen/wZPEGJ/">
  TraficFlowSim</a> by Gushwell (<a href="https://codepen.io/gushwell">@gushwell</a>)
  on <a href="https://codepen.io">CodePen</a>.</span>
</p>
<script async src="https://static.codepen.io/assets/embed/ei.js"></script>



## 最後に

ところで、JavaScriptのモジュールをimportする際に、文法エラーがあると、ブラウザの開発ツールを使ってもどこでエラーになるのかわからないんですね。
これがわかる方法ってないのかな？ ESlintはつかってるけど、完ぺきじゃないからもれが出ちゃうんですよね。
C#のようにコンパイルして事前にエラーがわかれば便利なんですけどね。
そういう意味では、TypeScript使ったほうがいいのかな？

機会があれば、TypeScriptに移植してみようかな...