【JavaScript & Canvas】Boids アルゴリズム 習作

「群制御みたいなもの」をなんか作ってみたいなーと調べていたらたどり着いた Boids アルゴリズム。
まずはアルゴリズムを理解するのに、良く書かれているコードの内容を見て、整理しながら書いてみました。

作成物

正方形領域だと移動範囲が狭いので、縦長にしました。

技術要素

Boids アルゴリズム？

詳しい記事はいっぱいあるので、そちらを参照したほうが詳しくなれると思います。( とりあえず作りたかったので、私もそこまで調べてない。。)

ルールとしては、各オブジェクト (= boid) について、
・近くの集団 (群れ) 同士で近づくようにする。
・近すぎる boid 同士は離れるようにする。
・群れの速度はそれぞれ合わせるようにする。

という条件を持たせることで、一定の集団が作られて協調しながら動いている (ように見える) のがこのアルゴリズムですね。

今回のコードは参照記事の github のコードを読んで、自分なりに書いてみたものなので、
関数名はほぼそのまま参照元のコードから持ってきています。

Boids クラス処理 :

////////////////////
//
// Boids
//
class Boids {

    constructor(width, height, count) {

        // 領域サイズ
        this.width = width;
        this.height = height;

        // 個数
        this.count = count;
        this.boids = [];
        for (let i = 0; i < this.count; i++) {
            this.boids.push(new Boid(RAND() * width, RAND() * height, RAND() * 10 - 5, RAND() * 10 - 5));
        }
    }

    update(ctx) {

        for (let idx = 0; idx < this.count; idx++) {

            // 
            // 移動量 (dx, dy) を更新
            //

            // 群れの中心に近づく
            this.#flyTowardsCenter(idx);

            // 周囲と近すぎる場合に離れる
            this.#avoidOthers(idx);

            // 群れと速度を合わせる
            this.#matchVelocity(idx);

            // 速くなり過ぎた場合の速度調整
            this.#limitSpeed(idx);

            // 境界に近づいた場合の調整
            this.#keepWithinBounds(idx);

            //
            // 位置 (x, y) 更新
            //
            const boid = this.boids[idx];
            boid.x += boid.dx;
            boid.y += boid.dy;
            this.boids[idx].update(boid);

            // 描画
            boid.draw(ctx);
        }
    }

    // 群れの中心に近づく
    #flyTowardsCenter(idx) {
        const boid = this.boids[idx];

        // 群れの中心位置を算出
        let center_x = 0; let center_y = 0;
        let neighbors_count = 0;
        for (let i = 0; i < this.boids.length; i++) {
            if (i == idx) continue;
            if (boid.distance2(this.boids[i]) < BOIDS_VISUAL_RANGE_2) {
                center_x += this.boids[i].x; center_y += this.boids[i].y;
                neighbors_count++;
            }
        }

        // 移動量調整
        if (neighbors_count > 0) {
            center_x /= neighbors_count; center_y /= neighbors_count;

            boid.dx += (center_x - boid.x) * BOID_CENTERING_FACTOR;
            boid.dy += (center_y - boid.y) * BOID_CENTERING_FACTOR;

            // Update
            this.boids[idx].update(boid);
        }
    }

    // 周囲と近すぎる場合に離れる
    #avoidOthers(idx) {
        const boid = this.boids[idx];

        // 近くの Boid の距離を取得
        let move_x = 0; let move_y = 0;
        for (let i = 0; i < this.boids.length; i++) {
            if (i == idx) continue;
            if (boid.distance2(this.boids[i]) < BOIDS_AVOID_MIN_DISTANCE_2) {
                move_x += boid.x - this.boids[i].x;
                move_y += boid.y - this.boids[i].y;
            }
        }

        // 移動量調整
        boid.dx += move_x * BOID_AVOID_FACTOR;
        boid.dy += move_y * BOID_AVOID_FACTOR;
        this.boids[idx].update(boid);
    }

    // 群れと速度を合わせる
    #matchVelocity(idx) {
        const boid = this.boids[idx];

        // 群れの移動量を取得
        let avg_dx = 0; let avg_dy = 0;
        let neighbors_count = 0;
        for (let i = 0; i < this.boids.length; i++) {
            if (i == idx) continue;
            if (boid.distance2(this.boids[i]) < BOIDS_VISUAL_RANGE_2) {
                avg_dx += this.boids[i].dx; avg_dy += this.boids[i].dy;
                neighbors_count += 1;
            }
        }

        // 移動量調整
        if (neighbors_count > 0) {
            avg_dx /= neighbors_count; avg_dy /= neighbors_count;
            boid.dx += (avg_dx - boid.dx) * BOID_MATCHING_FACTOR;
            boid.dy += (avg_dy - boid.dy) * BOID_MATCHING_FACTOR;
            this.boids[idx].update(boid);
        }
    }

    // 速くなり過ぎた場合の速度調整
    #limitSpeed(idx) {
        const boid = this.boids[idx];
        const speed2 = boid.dx * boid.dx + boid.dy * boid.dy;
        if (speed2 > BOID_SPEED_LIMIT_2) {
            const speed = Math.sqrt(speed2);
            boid.dx = (boid.dx / speed) * BOID_SPEED_LIMIT;
            boid.dy = (boid.dy / speed) * BOID_SPEED_LIMIT;
            this.boids[idx].update(boid);
        }
    }

    // 境界に近づいた場合の調整
    #keepWithinBounds(idx) {

        // Margin 混みで境界に近づいた時、移動量調整
        const boid = this.boids[idx];
        if (boid.x < MARGIN) {
            boid.dx += BOID_TERN_FACTOR;
        }
        if (boid.x > this.width - MARGIN) {
            boid.dx -= BOID_TERN_FACTOR;
        }
        if (boid.y < MARGIN) {
            boid.dy += BOID_TERN_FACTOR;
        }
        if (boid.y > this.height - MARGIN) {
            boid.dy -= BOID_TERN_FACTOR;
        }
        this.boids[idx].update(boid);
    }
}

Boid の形状

1つ1つはどんな形状が見やすいんだろう…？
ここでは簡単に、進行方向と動いていることが分かればよいので、現在位置 (x, y) から進行方向に引いた線分を軸とした二等辺三角形を引いています。

Boid クラスの描画処理 :

////////////////////
//
// Boid
// Boid 単体の管理クラス
//
class Boid {

    (略)

    // ctx に Boid を描画
    // 位置 (x, y) から進行方向に伸ばした線分を軸とした二等辺三角形
    draw(ctx) {
        // NOTE: 画面座標系では Y 座標が逆

        // 角度
        const angle = Math.atan2(-this.dy, this.dx);
        const angle_p = angle + PI_half;

        // 頂点
        const pos1_x = this.x + BOID_HEIGHT * Math.cos(angle);
        const pos1_y = this.y - BOID_HEIGHT * Math.sin(angle);

        // 底辺両端
        const bottom_half = BOID_BOTTOM / 2.0;
        const pos2_x = this.x + bottom_half * Math.cos(angle_p);
        const pos2_y = this.y - bottom_half * Math.sin(angle_p);
        const pos3_x = this.x - bottom_half * Math.cos(angle_p);
        const pos3_y = this.y + bottom_half * Math.sin(angle_p);

        // 描画
        ctx.fillStyle = BOID_FILL_COLOR;
        ctx.strokeStyle = BOID_STROKE_COLOR;
        ctx.beginPath();
        ctx.moveTo(pos1_x, pos1_y);
        ctx.lineTo(pos2_x, pos2_y);
        ctx.lineTo(pos3_x, pos3_y);
        ctx.lineTo(pos1_x, pos1_y);
        ctx.fill();
        ctx.stroke();
    }
}

その他工夫

Boids アルゴリズムはそれぞれの Boid 間の距離を算出して動きを決めます。
一般的に sqrt 計算は時間がかかるとされているので、通常の L2 距離を求めるとすると、大量の sqrt が使われることになります。

Unity 辺りではよく使われる小技ですが、
比較用の定数等予め2乗しておき、距離算出も

    // 別の boid との2乗距離を算出
    distance2(other) {
        return Math.pow(this.x - other.x, 2) + Math.pow(this.y - other.y, 2);        
    }

と、sqrt しない距離との比較を行うことにより、一部計算をサボっています。
( どれだけ高速化に貢献しているかは測ってないのでわかりません。)

まとめ

Boids アルゴリズムを書き下し、基本形の中身を理解することができました。
既に完成しているものを書き下しただけなので、もう少し工夫を入れて、面白い連携具合になるようにしてみます。

参照

• Boids アルゴリズムで鳥の群れを作ってみた
• beneater/boids (github)

今回のコード全文

以下に貼っておきます。

<div id="canvas_base"></div>

<script>

// Canvas 紐づけ要素 ID
const BASE_ID = "canvas_base";

// 描画エリアサイズ
const WIDTH = 540;
const HEIGHT = 720;

// アイキャッチ画像撮影用大き目
// const WIDTH = 1000;
// const HEIGHT = 1000;

// はみ出したときの許容量
const MARGIN = 100;

// 色設定
const BACKGROUND_STROKE_COLOR = 'rgb(119, 196, 187)'; // 描画外枠色
const BACKGROUND_FILL_COLOR = 'rgb(209, 235, 231)'; // 背景色
const BOID_STROKE_COLOR = 'rgb(196, 120, 130)'; // Boid 外枠色
const BOID_FILL_COLOR = 'rgb(219, 173, 180)'; // Boid 内部色

// Boid 個数
const BOIDS_COUNT = 70;

// Boid 描画サイズ
const BOID_BOTTOM = 20;
const BOID_HEIGHT = 40;

// Boids パラメータ
const BOIDS_VISUAL_RANGE = 75; // 近くにいる Boid を群れとみなす距離
const BOIDS_AVOID_MIN_DISTANCE = 20; // 近すぎる Boid を避ける距離

const BOID_SPEED_LIMIT = 15; // 速度最大値

const BOID_CENTERING_FACTOR = 0.005; // flyTowardsCenter
const BOID_AVOID_FACTOR = 0.05; // avoidOthers
const BOID_MATCHING_FACTOR = 0.05; // matchingVelocity
const BOID_TERN_FACTOR = 1; // keepWithinBounds

// NOTE: 計算速度を鑑みてsqrtは使わず事前に2乗しておく。
const BOIDS_VISUAL_RANGE_2 = Math.pow(BOIDS_VISUAL_RANGE, 2);
const BOIDS_AVOID_MIN_DISTANCE_2 = Math.pow(BOIDS_AVOID_MIN_DISTANCE, 2);
const BOID_SPEED_LIMIT_2 = Math.pow(BOID_SPEED_LIMIT, 2);

// 計算用定数等
const PI = Math.PI;
const PI_half = Math.PI / 2.0;

function RAND() { return Math.random(); }


////////////////////
//
// Boid
// Boid 単体の管理クラス
//
class Boid {

    constructor(x, y, dx, dy) {
        this.x = x; this.y = y;
        this.dx = dx; this.dy = dy;
    }

    // 位置更新
    update(boid) {
        this.x = boid.x; this.y = boid.y;
        this.dx = boid.dx; this.dy = boid.dy;
    }

    // 別の boid との2乗距離を算出
    distance2(other) {
        return Math.pow(this.x - other.x, 2) + Math.pow(this.y - other.y, 2);        
    }

    // ctx に Boid を描画
    // 位置 (x, y) から進行方向に伸ばした線分を軸とした二等辺三角形
    draw(ctx) {
        // NOTE: 画面座標系では Y 座標が逆

        // 角度
        const angle = Math.atan2(-this.dy, this.dx);
        const angle_p = angle + PI_half;

        // 頂点
        const pos1_x = this.x + BOID_HEIGHT * Math.cos(angle);
        const pos1_y = this.y - BOID_HEIGHT * Math.sin(angle);

        // 底辺両端
        const bottom_half = BOID_BOTTOM / 2.0;
        const pos2_x = this.x + bottom_half * Math.cos(angle_p);
        const pos2_y = this.y - bottom_half * Math.sin(angle_p);
        const pos3_x = this.x - bottom_half * Math.cos(angle_p);
        const pos3_y = this.y + bottom_half * Math.sin(angle_p);

        // 描画
        ctx.fillStyle = BOID_FILL_COLOR;
        ctx.strokeStyle = BOID_STROKE_COLOR;
        ctx.beginPath();
        ctx.moveTo(pos1_x, pos1_y);
        ctx.lineTo(pos2_x, pos2_y);
        ctx.lineTo(pos3_x, pos3_y);
        ctx.lineTo(pos1_x, pos1_y);
        ctx.fill();
        ctx.stroke();
    }
}


////////////////////
//
// Boids
//
class Boids {

    constructor(width, height, count) {

        // 領域サイズ
        this.width = width;
        this.height = height;

        // 個数
        this.count = count;
        this.boids = [];
        for (let i = 0; i < this.count; i++) {
            this.boids.push(new Boid(RAND() * width, RAND() * height, RAND() * 10 - 5, RAND() * 10 - 5));
        }
    }

    update(ctx) {

        for (let idx = 0; idx < this.count; idx++) {

            // 
            // 移動量 (dx, dy) を更新
            //

            // 群れの中心に近づく
            this.#flyTowardsCenter(idx);

            // 周囲と近すぎる場合に離れる
            this.#avoidOthers(idx);

            // 群れと速度を合わせる
            this.#matchVelocity(idx);

            // 速くなり過ぎた場合の速度調整
            this.#limitSpeed(idx);

            // 境界に近づいた場合の調整
            this.#keepWithinBounds(idx);

            //
            // 位置 (x, y) 更新
            //
            const boid = this.boids[idx];
            boid.x += boid.dx;
            boid.y += boid.dy;
            this.boids[idx].update(boid);

            // 描画
            boid.draw(ctx);
        }
    }

    // 群れの中心に近づく
    #flyTowardsCenter(idx) {
        const boid = this.boids[idx];

        // 群れの中心位置を算出
        let center_x = 0; let center_y = 0;
        let neighbors_count = 0;
        for (let i = 0; i < this.boids.length; i++) {
            if (i == idx) continue;
            if (boid.distance2(this.boids[i]) < BOIDS_VISUAL_RANGE_2) {
                center_x += this.boids[i].x; center_y += this.boids[i].y;
                neighbors_count++;
            }
        }

        // 移動量調整
        if (neighbors_count > 0) {
            center_x /= neighbors_count; center_y /= neighbors_count;

            boid.dx += (center_x - boid.x) * BOID_CENTERING_FACTOR;
            boid.dy += (center_y - boid.y) * BOID_CENTERING_FACTOR;

            // Update
            this.boids[idx].update(boid);
        }
    }

    // 周囲と近すぎる場合に離れる
    #avoidOthers(idx) {
        const boid = this.boids[idx];

        // 近くの Boid の距離を取得
        let move_x = 0; let move_y = 0;
        for (let i = 0; i < this.boids.length; i++) {
            if (i == idx) continue;
            if (boid.distance2(this.boids[i]) < BOIDS_AVOID_MIN_DISTANCE_2) {
                move_x += boid.x - this.boids[i].x;
                move_y += boid.y - this.boids[i].y;
            }
        }

        // 移動量調整
        boid.dx += move_x * BOID_AVOID_FACTOR;
        boid.dy += move_y * BOID_AVOID_FACTOR;
        this.boids[idx].update(boid);
    }

    // 群れと速度を合わせる
    #matchVelocity(idx) {
        const boid = this.boids[idx];

        // 群れの移動量を取得
        let avg_dx = 0; let avg_dy = 0;
        let neighbors_count = 0;
        for (let i = 0; i < this.boids.length; i++) {
            if (i == idx) continue;
            if (boid.distance2(this.boids[i]) < BOIDS_VISUAL_RANGE_2) {
                avg_dx += this.boids[i].dx; avg_dy += this.boids[i].dy;
                neighbors_count += 1;
            }
        }

        // 移動量調整
        if (neighbors_count > 0) {
            avg_dx /= neighbors_count; avg_dy /= neighbors_count;
            boid.dx += (avg_dx - boid.dx) * BOID_MATCHING_FACTOR;
            boid.dy += (avg_dy - boid.dy) * BOID_MATCHING_FACTOR;
            this.boids[idx].update(boid);
        }
    }

    // 速くなり過ぎた場合の速度調整
    #limitSpeed(idx) {
        const boid = this.boids[idx];
        const speed2 = boid.dx * boid.dx + boid.dy * boid.dy;
        if (speed2 > BOID_SPEED_LIMIT_2) {
            const speed = Math.sqrt(speed2);
            boid.dx = (boid.dx / speed) * BOID_SPEED_LIMIT;
            boid.dy = (boid.dy / speed) * BOID_SPEED_LIMIT;
            this.boids[idx].update(boid);
        }
    }

    // 境界に近づいた場合の調整
    #keepWithinBounds(idx) {

        // Margin 混みで境界に近づいた時、移動量調整
        const boid = this.boids[idx];
        if (boid.x < MARGIN) {
            boid.dx += BOID_TERN_FACTOR;
        }
        if (boid.x > this.width - MARGIN) {
            boid.dx -= BOID_TERN_FACTOR;
        }
        if (boid.y < MARGIN) {
            boid.dy += BOID_TERN_FACTOR;
        }
        if (boid.y > this.height - MARGIN) {
            boid.dy -= BOID_TERN_FACTOR;
        }
        this.boids[idx].update(boid);
    }
}


////////////////////
//
// Canvas 操作クラス
//
class CanvasOp {

    constructor(width, height, base_id = null) {

        this.width = width;
        this.height = height;

        // 描画用 Canvas およびダブルバッファリング用 Canvas を作成
        this.canvas = document.createElement("canvas");
        this.canvas_buff = document.createElement("canvas");     
        this.canvas_buff.hidden = true;

        // サイズ設定
        this.canvas.width = width;
        this.canvas.height = height;
        this.canvas_buff.width = width;
        this.canvas_buff.height = height;

        // canvas を親要素に紐づけ
        if (base_id == null) {
            // 未指定なら document.body に紐づける
            document.body.appendChild(this.canvas);
            document.body.appendChild(this.canvas_buff);
        }
        else {
            const base = document.getElementById(base_id);
            base.appendChild(this.canvas);
            base.appendChild(this.canvas_buff);        
        }

        // 操作用 Context
        if (this.canvas.getContext && this.canvas_buff.getContext) {
            this.context = this.canvas.getContext("2d");
            this.context_buff = this.canvas_buff.getContext("2d");
        }
        else {
            this.context = null;
            this.context_buff = null;
            console.error("Error: Canvas not supported.");
        }

        // Boids
        this.boids = new Boids(this.width, this.height, BOIDS_COUNT);
    }

    // 更新処理
    update(timestamp)
    {
        // context 空なら停止
        if (this.context == null) {
            return;
        }

        //////
        /// buff に描画
        ///

        // Clear
        this.context_buff.clearRect(0, 0, this.width, this.height);

        // 外枠
        this.context_buff.fillStyle = BACKGROUND_FILL_COLOR;
        this.context_buff.strokeStyle = BACKGROUND_STROKE_COLOR;
        this.context_buff.fillRect(0, 0, this.width, this.height);
        this.context_buff.strokeRect(0, 0, this.width, this.height);
       
        // Boids 更新
        this.boids.update(this.context_buff);

        //////
        /// Canvas に転送
        ///
        const data = this.context_buff.getImageData(0, 0, this.width, this.height);
        this.context.putImageData(data, 0, 0);

        // Update
        window.requestAnimationFrame((timestamp) => this.update(timestamp));
    }
}


////////////////////
//
// onload
//
window.onload = function()
{
    let canvas = new CanvasOp(WIDTH, HEIGHT, BASE_ID);
    canvas.update(0);
}

</script>

アイキャッチ用