5: Pathfinding(経路探索) Breadth-First Search(幅優先探索) アルゴリズム p5.js – 移植3

最後に、グリッドの数を増やし、ボタンのクリックでスタートするように修正します。
またpathFind()関数が返した最短経路をアニメーションで表示します。

p5.jsのボタンを使用するので、アドオンのp5.dom.jsライブラリを次のようにして読み込んでおきます。

<script src="https://cdnjs.cloudflare.com/ajax/libs/p5.js/0.8.0/p5.min.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/p5.js/0.9.0/addons/p5.dom.js"></script>
<script src="js/Square.js"></script>
<script src="sketch.js"></script>

Square.jsとskecth.jsは次のように変更します。

Square.js

class Square {
    constructor(fromTop, fromLeft, w, status, path = []) {
        this.fromTop = fromTop;
        this.fromLeft = fromLeft;
        this.w = w;
        this.status = status;
        this.setColor(this.status);
        this.path = path;
    }
    setStatus(status) {
        this.status = status;
        this.setColor(this.status);
    }

    getStatus() {
        return this.status;
    }

    getFromTop() {
        return this.fromTop;
    }

    getFromLeft() {
        return this.fromLeft;
    }

    getPath() {
        return this.path;
    }

    setColor(status) {
        if (status === 'start') {
            this.col = 'yellow';
        }
        else if (status === 'goal') {
            this.col = 'red';
        }
        else if (status === 'obstacle') {
            this.col = 'black';
        }
        else if (status === 'empty') {
            this.col = 'white';
        }
        else if (status === 'visited') {
            this.col = 'lightgray';
            // 追加
        }
        else if (status === 'result') {
            this.col = 'lightgreen';
        }
    }

    display() {
        fill(this.col);
        rect(this.fromLeft * this.w, this.fromTop * this.w, this.w, this.w);
        fill(100);
        // 文字の位置を調整
        text('(' + this.fromTop + ',' + this.fromLeft + ')', this.fromLeft * this.w + 7, this.fromTop * this.w + 20);
    }
}

sketch.js

// 8 x 8 のグリッド
const gridSize = 8;
let gridWidth;
let grid = [];
let startSquare;

// 追加
let isStart = false;
let index = 0;
let topN, leftN;

function setup() {
    createCanvas(320, 320);
    background(200);
    stroke(120);
    // 文字サイズをデフォルトに変える
    //textSize(20);
    gridWidth = width / gridSize;
    for (let i = 0; i < gridSize; i++) {
        grid[i] = [];
        for (let j = 0; j < gridSize; j++) {
            const square = new Square(i, j, gridWidth, 'empty');
            grid[i][j] = square;
            square.display();
        }
    }
    // スタート用Squareオブジェクトを設定、状態は上書きして表示
    startSquare = grid[0][4];
    startSquare.setStatus("start");
    startSquare.display();

    // ゴール用quareオブジェクトを設定、状態は上書きして表示
    grid[6][2].setStatus("goal");
    grid[6][2].display();

    // 障害物用quareオブジェクトを設定、状態は上書きして表示
    grid[1][1].setStatus("obstacle");
    grid[1][1].display();

    grid[1][2].setStatus("obstacle");
    grid[1][2].display();

    grid[1][3].setStatus("obstacle");
    grid[1][3].display();

    grid[2][1].setStatus("obstacle");
    grid[2][1].display();

    grid[1][7].setStatus("obstacle");
    grid[1][7].display();

    grid[2][7].setStatus("obstacle");
    grid[2][7].display();

    grid[3][7].setStatus("obstacle");
    grid[3][7].display();

    grid[4][4].setStatus("obstacle");
    grid[4][4].display();

    grid[4][5].setStatus("obstacle");
    grid[4][5].display();

    grid[4][3].setStatus("obstacle");
    grid[4][3].display();

    grid[4][2].setStatus("obstacle");
    grid[4][2].display();

    grid[5][1].setStatus("obstacle");
    grid[5][1].display();

    grid[6][6].setStatus("obstacle");
    grid[6][6].display();

    grid[5][5].setStatus("obstacle");
    grid[5][5].display();

    // [GO !]ボタンのクリックで経路探索をスタート!
    const findButton = setButton('GO !', {
        x: 20,
        y: 350
    });

    findButton.mousePressed(() => {
        result = pathFind(startSquare);
        if (result) {
            // startSquareの(top, left)位置
            topN = startSquare.getFromTop();
            leftN = startSquare.getFromLeft();
            isStart = true;
        }
        else {
            print('経路はない')
        }
    });
}

function draw() {
    // 探索結果が出たら
    if (isStart) {
        if (index >= result.length - 1) {
            noLoop();
        }
        // frameCountを使ってアニメーション表現する
        if (frameCount % 12 === 0) {
            drawResult(result[index]);
            index++;
        }
    }
}

// 経路に当たる正方形を特定し、色を変えていく
function drawResult(direction) {
    if (direction === 'north') {
        topN -= 1;
    }
    else if (direction === 'south') {
        topN += 1;
    }
    else if (direction === 'east') {
        leftN += 1;
    }
    else if (direction === 'west') {
        leftN -= 1;
    }
    grid[topN][leftN].setStatus('result');
    grid[topN][leftN].display();
}

function setButton(label, pos) {
    const button = createButton(label);
    button.size(100, 30);
    button.position(pos.x, pos.y);
    return button;
}

// スタート用Squareオブジェクトを受け取り、
// スタート位置からゴール位置までの1マスごとの移動方向を含む配列(最短経路)を返す
function pathFind(startSquare) {
    // startSquareを含む配列queueを作成
    // アルゴリズムの(1)
    const queue = [startSquare];

    // queue配列に要素が含まれている限り繰り返す
    // アルゴリズムの(5)
    while (queue.length > 0) {
        // アルゴリズムの(2)
        // queueの最初の要素を取り出す。取り出した要素はqueueから削除される
        // => 先入れ先出しのキュー構造(Array.shift()メソッド)
        const targetSquare = queue.shift();

        // 暫定的なSquareオブジェクト
        let tempSquare;

        // 取り出したSquareオブジェクトを方向別に調べ、
        // 結果を、実際のSquareオブジェクトと同等の暫定Squareオブジェクトとして得る
        // 返されるtempSquareは、それまでに通過できた方向を持つpath配列と、
        // 実際の状態を表すstatusプロパティを持っている

        // 北側
        tempSquare = checkNeighborSquare(targetSquare, 'north');
        // tempSquareの状態がゴールなら
        if (tempSquare.getStatus() === 'goal') {
            // 調べた方向のパスを返して終了
            // アルゴリズムの(3)
            return tempSquare.getPath();
            // tempSquareの状態が有効なら
        }
        else if (tempSquare.getStatus() === 'valid') {
            // queueにtempSquareを追加 => whileループはさらにつづく
            // アルゴリズムの(4)
            queue.push(tempSquare);
        }
        // 南側
        tempSquare = checkNeighborSquare(targetSquare, 'south');
        // アルゴリズムの(3)
        if (tempSquare.getStatus() === 'goal') {
            return tempSquare.getPath();
        }
        else if (tempSquare.getStatus() === 'valid') {
            // アルゴリズムの(4)
            queue.push(tempSquare);
        }
        // 東側
        tempSquare = checkNeighborSquare(targetSquare, 'east');
        // アルゴリズムの(3)
        if (tempSquare.getStatus() === 'goal') {
            return tempSquare.getPath();
        }
        else if (tempSquare.getStatus() === 'valid') {
            // アルゴリズムの(4)
            queue.push(tempSquare);
        }
        // 西側
        tempSquare = checkNeighborSquare(targetSquare, 'west');
        // アルゴリズムの(3)
        if (tempSquare.getStatus() === 'goal') {
            return tempSquare.getPath();
        }
        else if (tempSquare.getStatus() === 'valid') {
            // アルゴリズムの(4)
            queue.push(tempSquare);
        }
        // 確認用
        for (let i = 0; i < queue.length; i++) {
            // queue内のSquareオブジェクトを出力
            print(queue[i]);
            // そのSquareオブジェクトのpath配列を出力
            print(queue[i].getPath())
        }
        print('---------------------');
        // tempSquareはお役御免
        tempSquare = null;
    }
    // 経路がない場合はfalseを返す
    return false;
}

// 渡されたSquareオブジェクトのdirection側(東西南北)について調べ、
// 同等で、調べた方向をpathプロパティに持つ暫定Squareオブジェクトを返す
function checkNeighborSquare(currentSquare, direction) {
    print('(' + currentSquare.getFromTop() + ', ' + +currentSquare.getFromLeft() + ')の' + direction + 'を探索中');

    // currentSquareのpath配列をそのままコピー
    const nextDirection = currentSquare.path.slice();
    // その配列にdirection(調べたい方向)を加える
    // => たとえば、pathに"south"を持っているcurrentSquareに、direction="south"が指定されている場合には、
    // nextDirectionは["south","south"]になる => ["前に通過できた方向","次に通過したい方向"]
    // このnextDirectionは、この後作成する暫定的なSquareオブジェクト(tempSquare)のpathプロパティに指定される
    nextDirection.push(direction);

    // currentSquareの(top, left)位置
    let top = currentSquare.getFromTop();
    let left = currentSquare.getFromLeft();

    // 方向別に、調べたい(top, left)位置を設定
    // => 北向きに調べるのなら、その位置は(top-1, left)になる
    if (direction === 'north') {
        top -= 1;
    }
    else if (direction === 'south') {
        top += 1;
    }
    else if (direction === 'east') {
        left += 1;
    }
    else if (direction === 'west') {
        left -= 1;
    }

    // 調べたい(top, left)位置の、暫定的なSquareオブジェクトを作成する
    // nextDirectionは['これまで通過できた方向(ある場合)','次に調べたい方向']
    const tempSquare = new Square(top, left, gridWidth, 'unknown', nextDirection);
    // 暫定的なSquareオブジェクトと同じ位置にある、実際のSquareオブジェクトの状態を調べる
    const status = getSquareStatus(tempSquare);
    // 暫定的なSquareオブジェクトをその状態に設定する
    tempSquare.setStatus(status);
    // 状態が有効なら
    if (tempSquare.getStatus() === 'valid') {
        // grid内の実際のSquareオブジェクトの状態を書き換え、描画し直す
        // => 調べたSquareオブジェクトはライトグレーになる
        grid[top][left].setStatus('visited');
        grid[top][left].display();
    }
    // 確認用
    print(' -> ' + tempSquare.getStatus());
    // 結果を暫定Squareオブジェクトで返す
    return tempSquare;
}

// 渡された暫定Squareオブジェクトと同じ位置にある、実際のSquareオブジェクトの状態を調べて返す
function getSquareStatus(square) {
    // (top, left)位置を特定
    const top = square.getFromTop();
    const left = square.getFromLeft();

    // グリッドの範囲外なら無効
    if (top < 0 || top >= gridSize || left < 0 || left >= gridSize) {
        return 'invalid';
        // グリッドの範囲内なら
    }
    else {
        // 暫定Squareオブジェクトと同じ位置にある実際のSquareオブジェクトを特定
        const targetSquare = grid[top][left];
        // その状態
        const status = targetSquare.getStatus();
        // 状態別に結果を返す
        if (status === 'goal') {
            return 'goal';
            // 'obstacle'か'visited'か、'start'のいずれか
        }
        else if (status !== 'empty') {
            return 'blocked';
        }
        else {
            return 'valid';
        }
    }
}

ボタンをクリックすると、下図の結果が描画されます。