チュートリアル：迷路生成プログラム

本チュートリアルの説明

本チュートリアルは、自動で迷路を生成するプログラムを生成する過程を説明します。使用する言語はJavaScriptです。迷路生成プログラムでは、再帰関数やクラス構文を実装します。これらに馴染みがない人でも、手を動かしながら実装することですこしでも学びが得られることを目的としています。

このチュートリアルは下記のセクションに分かれています。

迷路の表示： JavaScript で生成した迷路情報を HTML と CSS で表示させます。
迷路の自動生成：迷路構造を自動生成するプログラムを実装します。
迷路の自動探索：迷路の正解ルートを自動探索するプログラムを実装します。

これから作る成果物

このチュートリアルでは、迷路を自動生成します。迷路はプログラムを実行するたびに自動生成され、ただ１つの正解ルートをもちます。迷路の生成と探索にはアルゴリズムを利用しますが、事前の知識は必要ありません。

最終的な成果物を確認する

前提知識

HTML, CSS, JavaScript, jQuery を扱うのに慣れていることを想定しています。関数、オブジェクト、配列、クラスの概念について詳しい説明はしません。サンプルコードの記述に関しては、一部解説をしています。このチュートリアルでは、アロー関数、クラス、 import、 export、分割代入を使用しています。

チュートリアルの準備

このチュートリアルを進めるにあたって、下記のいずれかの方法で開発環境を準備します。

ブラウザでコードを書く

CodePenを利用することで、ブラウザでコードを書くことができます。注意事項として、外部ファイルの読み込みをするので、そのための設定が必要です。こちらに設定の例が記載してあります。

ローカル開発環境でコードを書く

好きなテキストエディタでコードを書きます。注意事項として、外部ファイルの読み込みをするので、そのための設定が必要です。今回は、簡易ローカルサーバを立てることができる拡張機能を導入します。そうしなければ、CORS により外部ファイルが読み込めないためです。例えば、テキストエディタに VSCodeを利用する場合、 Live Severをインストールします。

迷路の表示

まずは、迷路を表示させるために HTML と CSS ファイルを用意しましょう。用意するファイルは２つあります。 index.html と style.css です。今回は、Table タグを装飾することで迷路を表現しています。

index.html

<!DOCTYPE html>
  <body>
    <link rel="stylesheet" href="style.css">
    <table class="maze">
      <tbody>
        <tr>
          <td class="maze-cell -wall"></td>
          <td class="maze-cell -wall"></td>
          <td class="maze-cell -wall"></td>
          <td class="maze-cell -wall"></td>
          <td class="maze-cell -wall"></td>
        </tr>
        <tr>
          <td class="maze-cell -wall"></td>
          <td class="maze-cell -start"></td>
          <td class="maze-cell -path"></td>
          <td class="maze-cell -path"></td>
          <td class="maze-cell -wall"></td>
        </tr>
        <tr>
          <td class="maze-cell -wall"></td>
          <td class="maze-cell -wall"></td>
          <td class="maze-cell -wall"></td>
          <td class="maze-cell -path"></td>
          <td class="maze-cell -wall"></td>
        </tr>
        <tr>
          <td class="maze-cell -wall"></td>
          <td class="maze-cell -path"></td>
          <td class="maze-cell -path"></td>
          <td class="maze-cell -goal"></td>
          <td class="maze-cell -wall"></td>
        </tr>
        <tr>
          <td class="maze-cell -wall"></td>
          <td class="maze-cell -wall"></td>
          <td class="maze-cell -wall"></td>
          <td class="maze-cell -wall"></td>
          <td class="maze-cell -wall"></td>
        </tr>
      </tbody>
    </table>
  </body>
</html>

style.css

*,
*::before,
*::after {
  box-sizing: border-box;
}

.maze {
  border-collapse: collapse;
  margin: 20px auto 0;
}

.maze-cell {
  width: 20px;
  height: 20px;
  padding: 0;
  border: 1px solid #ddd;
}

.maze-cell.-wall {
  background-color: #000;
}

.maze-cell.-path {
  background-color: #fff;
}

.maze-cell.-start {
  background-color: #00f;
}

.maze-cell.-goal {
  background-color: #f00;
}

class の説明

maze-cell: 迷路のセルを表す。通路や壁にも当てはまる共通クラス。
-wall: 迷路の壁を表す。黒色。
-path: 迷路の通路を表す。白色。
-start: 迷路のスタートを表す。青色。
-goal: 迷路のゴールを表す。赤色。

このように、セル（行と列の交わる箇所）を壁や通路として定義し、定義に応じた装飾をすることで迷路を表を用いて表現することができます。

JavaScript で迷路を生成する

HTML と CSS で迷路を表示することができました。しかし、このままでは動的に生成した迷路を表示させることができません。ここからは動的に生成する迷路を表示するプログラムを書いていきましょう。

まずは、 index.html を下記のように修正しましょう。クラス名"maze-wrapper"の div 要素の中身は空っぽです。この中身をプログラムで生成していきます。 CSS だけでなく、jQuery と main.js を読み込んでいることにも注意してください。

index.html

<!DOCTYPE html>
  <link rel="stylesheet" href="style.css">
  <body>
    <div class="maze-wrapper"></div>

    <script src="https://cdnjs.cloudflare.com/ajax/libs/jquery/3.4.1/jquery.min.js"></script>
    <script src="main.js" type="module"></script>
  </body>
</html>

これから、JavaScript で迷路の中身を実装していきましょう。用意する JavaScript のファイルは２つあります。 main.js と Maze.js です。

main.js

import { Maze } from './Maze.js';

const WIDTH = 9;
const HEIGHT = 9;
const maze = new Maze(WIDTH, HEIGHT);

Maze.js

export class Maze {
  constructor(WIDTH, HEIGHT) {
    this.WIDTH = WIDTH;
    this.HEIGHT = HEIGHT;
    this.grid = []; // cellTypeを格納した二次元配列
    this.startCellList = []; // 壁を生成するスタート地点となるセルの候補を格納した二次元配列
    this.start = []; // スタート地点の[row, column]
    this.goal = []; // ゴール地点の[row, column]
    this.cellType = {
      Start: 'S',
      Goal: 'G',
      Path: 0,
      Wall: 1,
      ExtendingWall: 2,
      ExtendingStart: 3,
    };
    this.extendingCounter = 0; // 迷路の壁を拡張するたびにカウンターが増加する
  }
}

２つのファイルの説明

main.js: メインのロジックを実装。 Maze.js で定義したクラスを操作する。
Maze.js: 迷路のクラス(Maze クラス)を定義する。

Maze クラスでは、コンストラクタを定義します。迷路が持つ情報は、全てコンストラクタの中にプロパティとして追加します。 main.js は、 Maze.js で定義したクラスを呼び出して使えるようにしています。

// モジュールからエクスポートをひとつインポートする
import { Maze } from './Maze.js';

// 個々の機能のエクスポート
export class Maze {...}

よって、Maze クラスのインスタンスを生成することが可能です。

const maze = new Maze(WIDTH, HEIGHT);

迷路を二次元配列で表現する

Maze クラスでは、迷路の構造に関する情報を定義します。オセロや将棋盤のような盤面を表現するのには、二次元配列が便利です。今回は、下記のように行(Row)と列(Column)で座標を表すように定義します。

二次元配列で指定したセルの値は、cellType で用意している状態を表します。壁にしたいセルの値は 1 で、ゴールにしたいセルの値は"G"です。

`👍gridのタイプをリスト形式で定義する`

ここでポイント 👍 を紹介します。下記のように、grid の中に格納するセルのタイプをリスト形式で定義しておきましょう。理由は、意味のない文字や数字を記述するとコードの可読性が低くなるからです。少なくとも、人間が目で見て管理する範囲に関しては、人間が理解しやすいような表記を意識してコードを記述します。

this.cellType = {
  Start: 'S',
  Goal: 'G',
  Path: 0,
  Wall: 1,
  ExtendingWall: 2,
  ExtendingStart: 3,
};

cellType の説明

ExtendingWall: 拡張中の壁であることを表す。
ExtendingStart: 壁を拡張する時の拡張開始位置候補であることを表す。

例として、リスト形式で表示しない場合のプログラムの一部を示します。

// 指定セルがWallではないなら、ExtendingWallに状態を変更する
if (this.grid[row][column] !== 1) {
  this.grid[row][column] = 2;
  isExtendingSuccess = this.extendWall(row, column);
}

次に、リスト形式で表示した場合のプログラムの一部です。

// 指定セルがWallではないなら、ExtendingWallに状態を変更する
if (this.grid[row][column] !== this.cellType.Wall) {
  this.grid[row][column] = this.cellType.ExtendingWall;
}

上記の２つは、内部的には同じ処理をしています。ただ、上記のプログラムは、コードを読む前に 1 が壁を表すことや、2 が拡張中の壁であることを表すことが頭にないと、読んだときに理解することができません。プログラムを読むときに頭に入れておかなければいけない情報はなるべく少なくした方が、読む人にとっての負担が少ないと言えます。もちろん、全ての場合に当てはまる書き方ではないので、場合によって使い分けましょう。

迷路の初期状態を作って表示する

では、早速迷路の初期状態を生成してみましょう。初期状態は、大枠の壁以外が全て通路になるように grid を生成します。 grid を生成するサンプルコードを見てみましょう。generateGrid()と initializeCellType()という２つのクラスメソッドを追加します。このメソッドでは、grid の二次元配列を生成する過程で、条件式の判定に応じたセルに壁や道の値を代入しています。

Maze.js

// HEIGHT行,WIDTH列の行列を生成
  generateGrid() {
    for (let row = 0; row < this.HEIGHT; row++) {
      let rowList = [];
      for (let column = 0; column < this.WIDTH; column++) {
        rowList.push(this.initializeCellType(row, column));
      }
      this.grid.push(rowList);
    }
  }

  // rowとcolumの値に応じたcellTypeの初期化を実施
  // 大外は壁に設定
  initializeCellType(row, column) {
    if (row === 0 || row === this.HEIGHT - 1) {
      return this.cellType.Wall;
    } else {
      if (column === 0 || column === this.WIDTH - 1) {
        return this.cellType.Wall;
      } else {
        return this.cellType.Path;
      }
    }
  }

次に、grid の情報を元に DOM を生成するコードを用意しましょう。

Maze.js

// インスタンスのデータを元に、DOMを生成
drowMyself() {
  ++this.extendingCounter;
  let className = `maze step${this.extendingCounter}`;
  $('.maze-wrapper').append(
    $(`<table class="${className}"><caption>${className}</caption>`).append(
      $('<tbody>')
    )
  );

  for (let row = 0; row < this.HEIGHT; row++) {
    let tr = $('<tr>');
    for (let column = 0; column < this.WIDTH; column++) {
      if (this.grid[row][column] === this.cellType.Wall) {
        tr.append($('<td class="maze-cell -wall"></td>'));
      } else if (this.grid[row][column] === this.cellType.ExtendingWall) {
        tr.append($('<td class="maze-cell -extending-wall"></td>'));
      } else if (this.grid[row][column] === this.cellType.ExtendingStart) {
        tr.append($('<td class="maze-cell -extending-start"></td>'));
      } else if (this.grid[row][column] === this.cellType.Start) {
        tr.append($('<td class="maze-cell -start"></td>'));
      } else if (this.grid[row][column] === this.cellType.Goal) {
        tr.append($('<td class="maze-cell -goal"></td>'));
      } else {
        tr.append($('<td class="maze-cell -path"></td>'));
      }
    }

    $(`.maze.step${this.extendingCounter} tbody`).append(tr);
  }
}

Maze.js で定義したインスタンスメソッドは、 main.js で実行します。

main.js

maze.generateGrid();
maze.drowMyself();

ブラウザで確認すると、大外が壁になった迷路が描画できているはずです。

コンソールに迷路インスタンスの情報を出力してみましょう。

main.js

console.log(maze);

maze.grid で参照可能な二次元配列の迷路構造が、描画した迷路構造と同じであることが確認できますね。

これまでの手順で、二次元配列で迷路を表現できるということがわかりました。迷路生成プログラムの流れを整理してみましょう。

迷路クラスで定義した、迷路インスタンスを生成
迷路インスタンスのプロパティとして、迷路構造を表す二次元配列を生成
迷路インスタンスのメソッドを実行して、プロパティを更新
迷路インスタンスの情報を元に迷路を表示

迷路を生成するには、迷路クラスで定義したインスタンスメソッドを実行して、迷路インスタンスのプロパティを更新していきます。次は、迷路を自動で生成するメソッドを実装していきましょう。

この時点でのコードを確認する

Maze.js はこちら

迷路の自動生成

ここまでの実装で、迷路の初期状態を生成することができました。次に、迷路の自動生成を実装していきましょう。迷路インスタンスのメソッドを実行して、プロパティを更新していきます。

迷路を自動で生成するアルゴリズムはいくつかあるようなのですが、今回は「壁伸ばし法」を採用します。壁伸ばし法で壁を拡張する処理のフローは、下記の通りです。

`🧩アルゴリズム：壁伸ばし法`

迷路生成のフロー

row, column がともに偶数となるセルを、壁伸ばし開始地点(候補)としてリストに追加
ランダムでリストからセルを選び、壁かどうかを確認
- 壁でない場合、3 の処理へ
- 壁の場合、5 の処理へ
選んだセルを拡張中の壁に更新
壁の拡張を実行
- 成功した場合、5 の処理へ
- 失敗した場合、7 の処理へ
拡張中の壁を壁に更新
選んだセルはリストから削除して、8 の処理へ
拡張中の壁を元に戻して、2 の処理へ
リストが空かどうかを確認
- 空ではない場合、2 の処理へ
- 空の場合、処理を終了

壁の拡張のフロー

現在のセルから、4 方向全てについて壁を伸ばせるかどうか確認
- 壁を伸ばせる方向がある場合、2 の処理へ
- 壁を伸ばせる方向がなければ、壁伸ばし失敗をリターン
壁を伸ばせる方向を全てリストに追加
ランダムでリストから壁を伸ばす方向を選ぶ
2 セル先までを拡張中の壁に更新
2 セル先が壁かどうかを確認
- 壁と接続していない場合、1 の処理へ
- 壁と接続した場合、6 の処理へ
拡張中の壁を、壁に更新
壁伸ばし成功をリターン

フローをコードで書く

壁を拡張する処理をフローで表したので、実際にコードを書いていきましょう。まずは、迷路生成のフローを書いていきます。

Maze.js

generateMaze() {
  this.addStartCellList();

  while (this.startCellList.length) {
    let { randIndex, startRow, startColumn } = this.getStartCell();
    let isExtendingSuccess = false;

    if (this.grid[startRow][startColumn] === this.cellType.ExtendingStart) {
      this.grid[startRow][startColumn] = this.cellType.ExtendingWall;
      isExtendingSuccess = this.extendWall(startRow, startColumn);

      if (isExtendingSuccess) {
        this.updateExtendingWall(this.cellType.Wall);
        this.removeStartCellList(randIndex);
      } else {
        this.updateExtendingWall(this.cellType.Path);
      }
    } else {
      this.removeStartCellList(randIndex);
    }
  }
}

generateMaze の最初の処理は、壁を生成するスタート地点となるセルの候補を列挙することです。 addStartCellList()は、row, column ともに偶数となるセルを壁伸ばし開始地点(候補)としてリストに格納するメソッドです。

Maze.js

addStartCellList() {
  for (let row = 1; row < this.HEIGHT - 1; row++) {
    for (let column = 1; column < this.WIDTH - 1; column++) {
      if (row % 2 === 0 && column % 2 === 0) {
        this.startCellList.push([row, column]);
        this.grid[row][column] = this.cellType.ExtendingStart;
      }
    }
  }
}

9 マス四方の場合、壁を生成するスタート地点の候補は下記の通りになります。

迷路の自動生成では、壁の拡張を迷路が完成するまで繰り返し実行します。壁伸ばし開始地点(紫のセル)が全て壁に置き換わった時点で、迷路の生成は完了です。

removeStartCellList()は、壁の拡張が終わったらリストから壁を生成するスタート地点となったセルを削除します。

Maze.js

removeStartCellList(index) {
    this.startCellList.splice(index, 1);
}

removeStartCellList()は、壁の拡張が終わったら迷路の情報を更新する関数です。 extendWall を実行中、拡張中の壁だけが ExtendingWall となるようにします。更新後の迷路は、cellType が Path と Wall のみになっているはずです。

Maze.js

updateExtendingWall(nextCellType) {
  for (let row = 0; row < this.HEIGHT; row++) {
    for (let column = 0; column < this.WIDTH; column++) {
      if (this.grid[row][column] === this.cellType.ExtendingWall) {
        this.grid[row][column] = nextCellType;

        if (
          nextCellType === this.cellType.Path &&
          row % 2 === 0 &&
          column % 2 === 0
        ) {
          this.grid[row][column] = this.cellType.ExtendingStart;
        }
      }
    }
  }
}

次は、ランダムでリストからセルを選び、壁かどうかを確認しましょう。分割代入で代入したのは、addStartCellList の内ランダムに選んだインデックスと、セルの行列です。インデックスは、後の処理でリストから選んだセルを削除するために使います。また、行と列はセルの位置を示す情報ですので、壁の拡張をしながら更新していく値です。

let { randIndex, startRow, startColumn } = this.getStartCell();

Maze.js

getStartCell() {
  let nextRandIndex = Math.floor(Math.random() * this.startCellList.length);
  let nextStartRow = this.startCellList[nextRandIndex][0];
  let nextStartColumn = this.startCellList[nextRandIndex][1];
  return {
    randIndex: nextRandIndex,
    startRow: nextStartRow,
    startColumn: nextStartColumn
  };
}

壁伸ばし開始地点を選んだら、壁の拡張を実行します。

isExtendingSuccess = this.extendWall(startRow, startColumn);

ここで、壁を拡張するプロセスを確認しましょう。

ランダムに選ばれた紫のセルから壁が伸びていく様子がわかります。そして、拡張中の壁は既存の壁にぶつかった時点で壁に更新します。この壁の拡張は、終了条件を満たすまで繰り返し実行します。最終的に、最初にリストアップした紫のセルが、全て黒の壁に置き換わっていることが確認できますね。

では、壁の拡張をする関数を書きましょう。

Maze.js

extendWall(row, column) {
  const DISTANCE = 2; // 進行距離
  let isConnectedWall = false;
  let clearDirectionList = this.addClearDirectionList(row, column, DISTANCE);

  if (clearDirectionList.length) {
    let rand = Math.floor(Math.random() * clearDirectionList.length);
    ({ row, column, isConnectedWall } = this.updateExtendingWallOnDirection(
      row,
      column,
      clearDirectionList[rand],
      DISTANCE
    ));
    //迷路の生成過程を描画する
    this.drowMyself();

    if (!isConnectedWall) {
      return this.extendWall(row, column);
    } else {
      console.log('壁伸ばし成功');
      return true;
    }
  } else {
    console.log('壁伸ばし失敗');
    return false;
  }
}

まずは、現在のセルから、4 方向全てについて壁を伸ばせるかどうか確認します。

Maze.js

addClearDirectionList(row, column, DISTANCE) {
  const clearDirectionList = [];
  // 上方向
  if (this.grid[row - DISTANCE][column] !== this.cellType.ExtendingWall) {
    clearDirectionList.push('UP');
  }
  // 下方向
  if (this.grid[row + DISTANCE][column] !== this.cellType.ExtendingWall) {
    clearDirectionList.push('DOWN');
  }
  // 左方向
  if (this.grid[row][column - DISTANCE] !== this.cellType.ExtendingWall) {
    clearDirectionList.push('LEFT');
  }
  // 右方向
  if (this.grid[row][column + DISTANCE] !== this.cellType.ExtendingWall) {
    clearDirectionList.push('RIGHT');
  }
  return clearDirectionList;
}

壁を伸ばせる方向のみ、clearDirectionList に追加します。

今度は宣言のない分割代入で、clearDirectionList の内ランダムに選んだ方向に 2 セル進んだ先のセルの行列と、壁と接続したかの判定結果を代入します。

({ row, column, isConnectedWall } = this.updateExtendingWallOnDirection(
  row,
  column,
  clearDirectionList[randIndex],
  DISTANCE
));

Maze.js

updateExtendingWallOnDirection(row, column, direction, DISTANCE) {
  let isConnectedWall;

  switch (direction) {
    case 'UP':
      isConnectedWall =
        this.grid[row - DISTANCE][column] === this.cellType.Wall;
      for (let i = 0; i < DISTANCE; i++) {
        this.grid[--row][column] = this.cellType.ExtendingWall;
      }
      break;
    case 'DOWN':
      isConnectedWall =
        this.grid[row + DISTANCE][column] === this.cellType.Wall;
      for (let i = 0; i < DISTANCE; i++) {
        this.grid[++row][column] = this.cellType.ExtendingWall;
      }
      break;
    case 'LEFT':
      isConnectedWall =
        this.grid[row][column - DISTANCE] === this.cellType.Wall;
      for (let i = 0; i < DISTANCE; i++) {
        this.grid[row][--column] = this.cellType.ExtendingWall;
      }
      break;
    case 'RIGHT':
      isConnectedWall =
        this.grid[row][column + DISTANCE] === this.cellType.Wall;
      for (let i = 0; i < DISTANCE; i++) {
        this.grid[row][++column] = this.cellType.ExtendingWall;
      }
      break;
  }
  return {
    row: row,
    column: column,
    isConnectedWall: isConnectedWall
  };
}

再帰関数の実行

ここで、再度 extendWall の処理を確認します。下記の擬似コードの通り、extendWall のフローでは壁の更新処理があります。この更新結果に応じて、以降の処理が分岐していきます。更新処理を終えても壁と接続していない場合、更新後の行列を引数に指定して再度 extendWall を実行します。

このように、自身の関数を呼び出す関数を再帰関数と呼びます。今回の例では、毎回異なる引数(セルの行列)とその時点での迷路の状態における計算結果を繰り返し出力します。

extendWall(row, column) {
  let isConnectedWall = false;

  if (clearDirectionList.length) {
    // ランダムな方向に壁を伸ばす処理を実行
    // rowとcolumは進んだ先のセルの行列に更新
    // 壁と接続したら、isConnectedWall = trueに更新

    if (!isConnectedWall) {
      return this.extendWall(row, column);
    } else {
      console.log('壁伸ばし成功');
      return true;
    }
  } else {
    console.log('壁伸ばし失敗');
    return false;
  }
}

自動迷路生成プログラムでは、毎回違った構造の迷路を出力します。それは、以下の条件で再帰関数を実行しているからです。

壁を伸ばす方向が毎回ランダムである
迷路の状態が更新されるので実行時の状態が毎回異なる

ここまで実装できたら、迷路の自動生成ができているはずです。せっかくなので、スタート地点とゴール地点を設定するプログラムも用意しましょう。

Maze.js

setUpperLeftStart() {
  let startRow = 1;
  let startColumn = 1;
  this.start = [startRow, startColumn];
  this.grid[startRow][startColumn] = this.cellType.Start;
}

setUnderRightGoal() {
  let goalRow = this.HEIGHT - 2;
  let goalColumn = this.WIDTH - 2;
  this.goal = [goalRow, goalColumn];
  this.grid[goalRow][goalColumn] = this.cellType.Goal;
}

これで、迷路クラスのメソッドを定義できました。実行する前に、index.html と main.css を次の通りに修正しましょう。

index.html

<!DOCTYPE html>
  <link rel="stylesheet" href="style.css">
  <body>
    <div class="description">
      <ul class="description__list">
        <li class="description__list-item">
          <span class="color-blue">■</span>：スタート
        </li>
        <li class="description__list-item">
          <span class="color-red">■</span>：ゴール
        </li>
        <li class="description__list-item">
          <span class="color-gray">■</span>：拡張中の壁
        </li>
        <li class="description__list-item">
          <span class="color-purple">■</span
          >：壁を作成するスタート地点となるセルの候補
        </li>
      </ul>
    </div>

    <div class="maze-wrapper"></div>

    <script src="https://cdnjs.cloudflare.com/ajax/libs/jquery/3.4.1/jquery.min.js"></script>
    <script src="main.js" type="module"></script>
  </body>
</html>

main.css

*,
*::before,
*::after {
  box-sizing: border-box;
}

.description {
  margin: 16px auto;
  text-align: center;
  display: block;
}

.description__list {
  padding-left: 0;
  list-style: none;
  display: inline-block;
}

.description__list-item {
  text-align: left;
}

.color-blue {
  color: #00f;
}

.color-red {
  color: #f00;
}

.color-gray {
  color: #808080;
}

.color-purple {
  color: #a757a8;
}

.maze {
  border-collapse: collapse;
  margin: 20px auto 0;
}

.maze-cell {
  width: 20px;
  height: 20px;
  padding: 0;
  border: 1px solid #ddd;
}

.maze-cell.-wall {
  background-color: #000;
}

.maze-cell.-extending-wall {
  background-color: #808080;
}

.maze-cell.-extending-start {
  background-color: #a757a8;
}

.maze-cell.-path {
  background-color: #fff;
}

.maze-cell.-answer-route.show {
  background-color: #0f0;
}

.maze-cell.-start {
  background-color: #00f;
}

.maze-cell.-goal {
  background-color: #f00;
}

.maze-wrapper {
  margin: 20px auto 0;
  display: grid;
  grid-template-columns: 1fr 1fr 1fr 1fr;
}

それでは、 main.js で迷路インスタンスの generateMaze を実行してみましょう。

main.js

import { Maze } from './Maze.js';

//サイズは必ず5以上の奇数で生成する
const WIDTH = 9;
const HEIGHT = 9;
const maze = new Maze(WIDTH, HEIGHT);
maze.generateGrid();
maze.generateMaze();
maze.setUpperLeftStart();
maze.setUnderRightGoal();
maze.drowMyself();

迷路の自動生成ができていれば、実行するごとに異なる迷路が表示されるはずです。

`🚨既存の壁に到達しないパターン`

壁の拡張のフローを確認すると、

壁を伸ばせる方向がなければ、壁伸ばし失敗をリターン

とありますが、それはどのような時に起こりうるでしょうか。

それは、拡張中の壁に四方を囲まれてしまった場合です。このパターンに陥った場合は、拡張中の壁に関する変更を破棄して再度壁を作り直します。

`👍テストを書いて動作を確認する`

さて、これまでは実装した後にブラウザで動作を確認していましたね。しかし、今回は壁伸ばしが本当に失敗した時にも正しく動作するのかを状況を再現して確認する必要があります。理由は、ランダムで迷路を生成する過程で上記のパターンに陥る可能性が高くないからです。 9 マス四方の場合、四隅のスタート地点から時計回りと反時計回りに壁を生成したパターンが該当するので、4×2 の合計 8 パターンしかないのです。そこで、壁を拡張している最中に拡張中の壁に囲まれた状態を再現するコードを書く必要があるという訳です。

今回は、テストを書くためのライブラリを使用せず、ブラウザの console 機能でテストを実行します。

Maze.js

extendWall_ng_falseClearDirectionListAndFalseIsConnectedWall() {
  // 1.前提条件を満たす状態変更
  // this.grid(4,4)が拡張中の壁に囲まれる状態にする
  const DISTANCE = 2; // 進行距離
  let isConnectedWall = false;
  let row = 2;
  let column = 2;
  let extendingDirectionList = [
    'DOWN',
    'DOWN',
    'RIGHT',
    'RIGHT',
    'UP',
    'UP',
    'LEFT',
    'DOWN'
  ];
  this.grid[row][column] = this.cellType.ExtendingWall;

  for (let i = 0; i < extendingDirectionList.length; i++) {
    ({ row, column, isConnectedWall } = this.updateExtendingWallOnDirection(
      row,
      column,
      extendingDirectionList[i],
      DISTANCE
    ));
    this.drowMyself();
  }

  // 2.実行
  let result = this.extendWall(4, 4);

  // 3.結果表示
  // 壁拡張中、拡張中の壁に囲まれたらテスト成功をコンソールに出力
  if (!result) {
    console.log('テスト成功:', this.grid);
  } else {
    console.log('テスト失敗:', this.grid);
  }

  // 4.結果をリターン
  return result;
}

generateMaze でテストを実行してみましょう。

Maze.js

generateMaze() {
  this.addStartCellList();

  while (this.startCellList.length) {
    let { randIndex, startRow, startColumn } = this.getStartCell();
    let isExtendingSuccess = false;

    if (this.grid[startRow][startColumn] === this.cellType.ExtendingStart) {
      // 一旦コメントアウト
      // this.grid[startRow][startColumn] = this.cellType.ExtendingWall;
      // isExtendingSuccess = this.extendWall(startRow, startColumn);

      // falseがリターンされるテスト
      isExtendingSuccess = this.extendWall_ng_falseClearDirectionListAndFalseIsConnectedWall();

      if (isExtendingSuccess) {
        this.updateExtendingWall(this.cellType.Wall);
        this.removeStartCellList(randIndex);
      } else {
        console.log('拡張中の壁を元にもどし、再度壁を拡張します');
        this.updateExtendingWall(this.cellType.Path);
        return; // テストを実行する時はreturnを記述してwhileループを抜ける
      }
    } else {
      this.removeStartCellList(randIndex);
    }
  }
}

実行後にブラウザの console を確認してみましょう。想定通り、壁伸ばしが失敗して、テストが成功していることを確認できました。

drowMyself で途中経過を描画すると、ブラウザで迷路の状態を確認できます。これで、壁の拡張が失敗しても壁の拡張をやり直すことができるので、迷路が完成するまで処理が止まることがないですね。

この時点でのコードを確認する

Maze.js はこちら

迷路の自動探索

迷路の自動生成ができたので、次は正解ルートの自動探索を実装します。正解ルートの探索のために、新たに Explorer.js を用意します。

Explorer.js は迷路探索のクラス(Explorer クラス)を定義するファイルです。役割は、迷路構造を元に正解ルートを探索して、正解ルートの情報を迷路情報に更新することです。 Explorer は、Maze の地図を見ながら正解ルートを探索し、ゴールに到達したらその道を Maze に報告するというイメージです。

Explorer.js

export default class Explorer {
  // mazeの情報からexplorerを生成する
  // ObjectはDeepCopyする
  constructor(WIDTH, HEIGHT) {
    this.WIDTH = WIDTH;
    this.HEIGHT = HEIGHT;
    this.grid = []; // cellTypeを格納した二次元配列
    this.start = []; // スタート地点の[row, column]
    this.beforeGoal = []; // ゴール手前の[row, column]
    this.cellType = {
      Start: 'S',
      Goal: 'G',
      Path: 0,
      Wall: 1,
      AnswerRoute: 'A',
      FromUp: 'U',
      FromRight: 'R',
      FromDown: 'D',
      FromLeft: 'L',
    };
  }
}

`👍Explorerの迷路構造は、Mazeの迷路構造をディープコピーする`

上記のフロー図で迷路構造をコピーとありますが、ここで注意すべきはシャローコピーではなくディープコピーをするという点です。迷路構造は二次元配列なので、シャローコピーしてしまうと Explorer インスタンスの変更が Maze インスタンスに影響を与えてしまいます。下記に、それぞれの例を示します。

シャローコピーの例

let a = [[1, 1], 2, 3];
let b = Array.from(a);

console.log(a); // => [[1, 1], 2, 3]
console.log(b); // => [[1, 1], 2, 3]
console.log(a === b); // => false

b[0][1] = 'X';
b[2] = 'X';

console.log(a); // => [[ 1, 'X'], 2, 3]
console.log(b); // => [[ 1, 'X'], 2, 'X']

ディープコピーの例

let a = [[1, 1], 2, 3];
let b = JSON.parse(JSON.stringify(a));

console.log(a); // => [[1, 1], 2, 3]
console.log(b); // => [[1, 1], 2, 3]

b[0][1] = 'X';
b[2] = 'X';

console.log(a); // => [[1, 1], 2, 3]
console.log(b); // => [[1, 'X'], 2, 'X']

これから迷路の自動探索をするメソッドを実装していきますが、Explorer メソッドで変更するのは、Explorer プロパティです。 Explorer プロパティをディープコピーで定義することで、Maze プロパティに影響を与えないようにします。

Explorer.js

deepCopyMaze(grid, start, goal) {
  // 二次元配列のDeepCopy
  this.grid = JSON.parse(JSON.stringify(grid));
  $.extend(this.start, start);
}

Explorer クラスのインスタンスを生成し、インスタンスメソッドを main.js で実行します。

main.js

import Explorer from './Explorer.js';

const explorer = new Explorer(maze.WIDTH, maze.HEIGHT);
explorer.deepCopyMaze(maze.grid, maze.start);
console.log('explorer:', explorer);

コンソールで出力して確認すると、迷路構造をコピーできていることがわかります。

`🧩アルゴリズム：幅優先探索`

ここまでの実装で、迷路の情報を持った Explorer インスタンスを生成することができました。次に、迷路の自動探索アルゴリズムを実装していきましょう。 Explorer インスタンスのメソッドを実行して、プロパティを更新していきます。

迷路を自動で探索するアルゴリズムはいくつかあるようなのですが、今回は「幅優先探索」を採用します。幅優先探索で正解ルートを探索する処理のフローは、下記の通りです。

幅優先探索のフロー

根ノード(スタート地点)を探索キューに追加
探索キューからセルを取り出す
取り出したセルのゴール判定
- ゴールの場合、処理を終了
隣接セル探索の実行
探索したセルを探索キューに追加
探索キューが空かどうかを確認
- 空ではない場合、2 の処理へ
- 空の場合、処理を終了

隣接セル探索のフロー

現在地の隣接セルが、通路もしくはゴールかどうか確認
- 通路の場合、2 の処理へ
- ゴールの場合、5 の処理へ
- どちらでもない場合、4 の処理へ
探索済の印(どの方向から来たのかを示す)をつける
対象の隣接セルを探索済リストに追加
4 方向全て探索完了したか
- 未完了の場合、1 の処理へ
- 完了した場合、7 の処理へ
現在地をゴール手前のセルとして更新
対象の隣接セルを探索済リストに追加
探索済リストをリターン

フローをコードで書く

迷路を自動で探索する処理をフローで表したので、実際にコードを書いていきましょう。まずは、幅優先探索の処理を下記に示します。

Explorer.js

breadthFirstSearch(start) {
  let searchQueue = [start];

  while (searchQueue.length) {
    let [row, column] = searchQueue.shift();

    if (this.grid[row][column] === this.cellType.Goal) {
      return;
    }

    searchQueue.push(...this.checkNextCell(row, column));
  }
}

次に、隣接セル探索の処理を下記に示します。

Explorer.js

checkNextCell(row, column) {
  const nextSearchQueue = [];
  const DISTANCE = 1; // 探索距離

  for (let i = 0; i < 4; i++) {
    let nextRow;
    let nextColumn;
    let nextcellType;
    if (i === 0) {
      // 上方向
      nextRow = row - DISTANCE;
      nextColumn = column;
      nextcellType = this.cellType.FromDown;
    } else if (i === 1) {
      // 右方向
      nextRow = row;
      nextColumn = column + DISTANCE;
      nextcellType = this.cellType.FromLeft;
    } else if (i === 2) {
      // 下方向
      nextRow = row + DISTANCE;
      nextColumn = column;
      nextcellType = this.cellType.FromUp;
    } else if (i === 3) {
      // 左方向
      nextRow = row;
      nextColumn = column - DISTANCE;
      nextcellType = this.cellType.FromRight;
    }

    if (this.grid[nextRow][nextColumn] === this.cellType.Path) {
      this.grid[nextRow][nextColumn] = nextcellType;
      nextSearchQueue.push([nextRow, nextColumn]);
    } else if (this.grid[nextRow][nextColumn] === this.cellType.Goal) {
      this.beforeGoal = [row, column];
      nextSearchQueue.push([nextRow, nextColumn]);
      return nextSearchQueue;
    }
  }

  return nextSearchQueue;
}

幅優先探索の大まかな流れを下記に示します。

探索順序をみると、起点となるスタート地点から網羅的にゴールを探索しているのがわかります。下記の左図の場合、13 回目の探索でゴールを見つけることができたので、その時点で探索を終了します。

探索後は、探索済の印をつけます。下記の中央図の通り、どこからきたのかがわかるような印にすると、あとでゴールから道筋を辿ることができます。そのために、ゴール地点手前のセルをExplorer.beforeGoalに記録しておきましょう。 記号の意味は、U: UP, D: DOWN, L: LEFT, R: RIGHT

探索終了時は、迷路構造が下記の右図の通りになります。

スタートからゴールまでの道のりを更新する

探索が終了したら、ゴールまでの道のりを更新します。探索時につけた探索済の印で、どこからきたのかが追えるようになっています。 Explorer.beforeGoal からきた道を辿って、スタート地点に戻る処理を実装しましょう。

updateAnswerRoute() {
  let [row, column] = this.beforeGoal;

  // ゴールからスタートの道を辿り、AnswerRouteに更新
  while (this.grid[row][column] !== this.cellType.Start) {
    switch (this.grid[row][column]) {
      case this.cellType.FromUp:
        this.grid[row][column] = this.cellType.AnswerRoute;
        --row;
        break;
      case this.cellType.FromRight:
        this.grid[row][column] = this.cellType.AnswerRoute;
        ++column;
        break;
      case this.cellType.FromDown:
        this.grid[row][column] = this.cellType.AnswerRoute;
        ++row;
        break;
      case this.cellType.FromLeft:
        this.grid[row][column] = this.cellType.AnswerRoute;
        --column;
        break;
    }
  }

  // AnswerRoute以外の探索済の印は、全てPathに更新
  for (let row = 0; row < this.HEIGHT; row++) {
    for (let column = 0; column < this.WIDTH; column++) {
      if (
        this.grid[row][column] === this.cellType.FromUp ||
        this.grid[row][column] === this.cellType.FromDown ||
        this.grid[row][column] === this.cellType.FromLeft ||
        this.grid[row][column] === this.cellType.FromRight
      ) {
        this.grid[row][column] = this.cellType.Path;
      }
    }
  }
}

main.js で実行して、迷路構造が更新されているかを確認しましょう。

main.js

explorer.breadthFirstSearch();
explorer.updateAnswerRoute();

下記のように、コンソールで出力すると正解ルートが更新できているのを確認できます。

console.log('explorer.grid:', JSON.parse(JSON.stringify(explorer.grid)));

正解ルートを描画する

ここまでは、Explorer クラスで迷路の正解ルートを探索するプログラムを実装しました。最後に、正解ルートを描画する処理を実装してプログラムを完成させましょう。

まずは、Explorer クラスの迷路構造を Maze クラスの迷路構造に反映します。 Maze の迷路構造は、Explorer の迷路構造をディープコピーしましょう。

Maze.js

updateMazeAnserRoute(grid) {
  this.grid = JSON.parse(JSON.stringify(grid));
}

main.js

maze.updateMazeAnserRoute(explorer.grid);

これで、Maze クラスの迷路構造に正解ルートの情報が反映されました。 Maze クラスには描画メソッドがあるので、下記のように修正します。

Maze.js

// インスタンスのデータを元に、DOMを生成
drowMyself() {
  ++this.extendingCounter;
  let className = `maze step${this.extendingCounter}`;
  $('.maze-wrapper').append(
    $(`<table class="${className}">`).append($('<tbody>'))
  );

  for (let row = 0; row < this.HEIGHT; row++) {
    let tr = $('<tr>');
    for (let column = 0; column < this.WIDTH; column++) {
      if (this.grid[row][column] === this.cellType.Wall) {
        tr.append($('<td class="maze-cell -wall"></td>'));
      } else if (this.grid[row][column] === this.cellType.ExtendingWall) {
        tr.append($('<td class="maze-cell -extending-wall"></td>'));
      } else if (this.grid[row][column] === this.cellType.ExtendingStart) {
        tr.append($('<td class="maze-cell -extending-start"></td>'));
      } else if (this.grid[row][column] === this.cellType.Start) {
        tr.append($('<td class="maze-cell -start"></td>'));
      } else if (this.grid[row][column] === this.cellType.Goal) {
        tr.append($('<td class="maze-cell -goal"></td>'));
      } else if (this.grid[row][column] === this.cellType.AnswerRoute) {
        tr.append($('<td class="maze-cell -answer"></td>'));
      } else {
        tr.append($('<td class="maze-cell -path"></td>'));
      }
    }

    $(`.maze.step${this.extendingCounter} tbody`).append(tr);
  }
}

正解ルートは、ボタンを押して表示と非表示を切り替えるようにしたいです。表示切り替えボタンは、下記の通り実装します。

main.js

$('.answer').click((e) => {
  e.preventDefault();
  $(e.target).toggleClass('active');
  $('.maze-cell.-answer').toggleClass('show');
});

最後に main.js , index.html , style.css を下記のように修正します。

迷路の WIDTH と HEIGHT を 49 に変更
セルの width と height を 10px に変更
セルの枠線スタイルをコメントアウト
AnswerRoute 関連の CSS 追記
表示切り替えボタンの CSS 追記

コードを記載するので、関数の実行順序やスタイルに誤りがないかを確認しましょう。

main.js

import { Maze } from './Maze.js';
import Explorer from './Explorer.js';

// 正解ルートの表示切り替え
$('.answer').click((e) => {
  e.preventDefault();
  $(e.target).toggleClass('active');
  $('.maze-cell.-answer').toggleClass('show');
});

//サイズは必ず5以上の奇数で生成する
const WIDTH = 49;
const HEIGHT = 49;

const maze = new Maze(WIDTH, HEIGHT);
maze.generateGrid();
maze.generateMaze();
maze.setUpperLeftStart();
maze.setUnderRightGoal();

const explorer = new Explorer(maze.WIDTH, maze.HEIGHT);
explorer.deepCopyMaze(maze.grid, maze.start);
explorer.breadthFirstSearch();
explorer.updateAnswerRoute();

maze.updateMazeAnserRoute(explorer.grid);
maze.drowMyself();

index.html

<!DOCTYPE html>
  <link rel="stylesheet" href="css/style.css" />
  <body>
    <div class="description">
      <ul class="description__list">
        <li class="description__list-item">
          <span class="color-blue">■</span>：スタート
        </li>
        <li class="description__list-item">
          <span class="color-red">■</span>：ゴール
        </li>
        <li class="description__list-item">
          <span class="color-green">■</span>：正解ルート
        </li>
      </ul>
    </div>

    <div class="contoroller">
      <button class="answer">正解ルート表示</button>
    </div>

    <div class="maze-wrapper"></div>

    <script src="https://code.jquery.com/jquery-3.4.1.min.js"></script>
    <script src="js/main.js" type="module"></script>
  </body>
</html>

style.css

*,
*::before,
*::after {
  box-sizing: border-box;
}

.contoroller {
  text-align: center;
}

.contoroller .answer {
  font-size: 16px;
  text-decoration: none;
  color: inherit;
  display: inline-block;
  line-height: 40px;
  margin-top: 20px;
  padding: 0 20px;
  border: 1px #333 solid;
  background: rgba(0, 0, 0, 0);
  transition: all 0.3s;
}

.contoroller .answer.active {
  background: rgba(0, 255, 0, 1);
}

.description {
  margin: 16px auto;
  text-align: center;
  display: block;
}

.description__list {
  padding-left: 0;
  list-style: none;
  display: inline-block;
}

.description__list-item {
  text-align: left;
}

.color-blue {
  color: #00f;
}

.color-red {
  color: #f00;
}

.color-gray {
  color: #808080;
}

.color-purple {
  color: #a757a8;
}

.color-green {
  color: #0f0;
}

.maze {
  border-collapse: collapse;
  margin: 20px auto 0;
}

.maze-cell {
  width: 10px;
  height: 10px;
  padding: 0;
  /* border: 1px solid #ddd; */
}

.maze-cell.-wall {
  background-color: #000;
}

.maze-cell.-extending-wall {
  background-color: #808080;
}

.maze-cell.-extending-start {
  background-color: #a757a8;
}

.maze-cell.-path {
  background-color: #fff;
}

.maze-cell.-answer.show {
  background-color: #0f0;
}

.maze-cell.-start {
  background-color: #00f;
}

.maze-cell.-goal {
  background-color: #f00;
}

.maze-wrapper {
  margin: 20px auto 0;
  /* display: grid;
  grid-template-columns: 1fr 1fr 1fr 1fr; */
}

ここまで実装できたら、表示を確認してみましょう。下記のような動作をしていれば、実装は完了です。

この時点でのコードを確認する

Maze.js はこちら

Explorer.js はこちら

Name		Name	Last commit message	Last commit date
Latest commit History 34 Commits
img		img
README.md		README.md
deep-copy.js		deep-copy.js
shallow-copy.js		shallow-copy.js

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

img

img

README.md

README.md

deep-copy.js

deep-copy.js

shallow-copy.js

shallow-copy.js

Repository files navigation

チュートリアル：迷路生成プログラム

本チュートリアルの説明

これから作る成果物

前提知識

チュートリアルの準備

ブラウザでコードを書く

ローカル開発環境でコードを書く

迷路の表示

JavaScript で迷路を生成する

迷路を二次元配列で表現する

`👍gridのタイプをリスト形式で定義する`

迷路の初期状態を作って表示する

迷路の自動生成

`🧩アルゴリズム：壁伸ばし法`

フローをコードで書く

再帰関数の実行

`🚨既存の壁に到達しないパターン`

`👍テストを書いて動作を確認する`

迷路の自動探索

`👍Explorerの迷路構造は、Mazeの迷路構造をディープコピーする`

`🧩アルゴリズム：幅優先探索`

フローをコードで書く

スタートからゴールまでの道のりを更新する

正解ルートを描画する

About

Releases

Packages

Languages

matsuhaya/generate-maze-tutorial

Folders and files

Latest commit

History

Repository files navigation

チュートリアル： 迷路生成プログラム

本チュートリアルの説明

これから作る成果物

前提知識

チュートリアルの準備

ブラウザでコードを書く

ローカル開発環境でコードを書く

迷路の表示

JavaScript で迷路を生成する

迷路を二次元配列で表現する

👍gridのタイプをリスト形式で定義する

迷路の初期状態を作って表示する

迷路の自動生成

🧩アルゴリズム： 壁伸ばし法

フローをコードで書く

再帰関数の実行

🚨既存の壁に到達しないパターン

👍テストを書いて動作を確認する

迷路の自動探索

👍Explorerの迷路構造は、Mazeの迷路構造をディープコピーする

🧩アルゴリズム： 幅優先探索

フローをコードで書く

スタートからゴールまでの道のりを更新する

正解ルートを描画する

About

Resources

Stars

Watchers

Forks

Languages

チュートリアル：迷路生成プログラム

`👍gridのタイプをリスト形式で定義する`

`🧩アルゴリズム：壁伸ばし法`

`🚨既存の壁に到達しないパターン`

`👍テストを書いて動作を確認する`

`👍Explorerの迷路構造は、Mazeの迷路構造をディープコピーする`

`🧩アルゴリズム：幅優先探索`