JavaScriptで迷路自動生成プログラム
迷路を自動生成してcanvasに描画するプログラムを作成しました。
See the Pen
Untitled by Imai (@imai1)
on CodePen.
四角マップ状の迷路を生成
迷路の構造
まずは、このプログラムにおける（四角マップ版の）迷路の定義を説明します。
- マス目を碁盤状に並べる。
- 各マスの面が空間を表し、罫線が壁を表す。面の色で空間／壁を表すタイプではない。
- 隣接する二つのマスの共有辺に罫線がなければ、そのマスは繋がっている。
- 全てのマスから別の全てのマスに到達する経路が必ず一つ存在する。
- ゆえに、スタートとゴールはランダムに2点を選べば良い。
上記の３番目の要件が曲者ですが、あとの二つは単純です。よってまず先に、迷路のデータ構造と、それを描画する関数を説明します。
迷路のデータ構造
本プログラムでは、以下のRectangularMapクラスで四角マップ版の迷路のデータ構造を管理します。
class RectangularMap { static UP = 0; static RIGHT = 1; static DOWN = 2; static LEFT = 3; constructor(width, height) { this.width = width; this.height = height; this.initializeConnection(); this.buildConnection(); } initializeConnection() { this.connection = new Array(this.height); for (let y = 0; y < this.height; ++y) { this.connection[y] = new Array(this.width); for (let x = 0; x < this.width; ++x) { this.connection[y][x] = new Array(4).fill(false); } } } buildConnection() { // 「全てのマスから別の全てのマスに到達する経路が必ず一つ存在する。」を満たすように接続を生成する。 } }
connectionプロパティはマス目の二次元配列で、更に各マスは上下左右の四方向に壁があるかどうかを表す固定長配列です。後述の、接続を生成するbuildConnection関数のみやや複雑ですが、それ以外はシンプルではないかと思います。
迷路の描画
canvasへの描画は以下のdrawRectanuglarMapToCanvas関数にRectangularMapのインスタンスを与えます。
function drawRectangularMapToCanvas(canvasId, rectangularMap, cellWidth, cellHeight) { const canvas = document.getElementById(canvasId); const context = canvas.getContext("2d"); context.clearRect(0, 0, canvas.width, canvas.height); context.strokeStyle = "black"; for (let y = 0; y < rectangularMap.height; ++y) { for (let x = 0; x < rectangularMap.width; ++x) { if (!rectangularMap.connection[y][x][RectangularMap.UP]) { context.beginPath(); context.moveTo(cellWidth * x, cellHeight * y); context.lineTo(cellWidth * (x + 1), cellHeight * y); context.stroke(); } /* 右・下・左についても同様 */ } } }
RectangularMapのconnectionプロパティを走査して、壁があれば対応する座標に罫線を引くだけの単純な関数です。迷路の接続生成のアルゴリズムに依存していないため、簡単な処理になっています。少し改変すればcanvas以外の描画方法も簡単に実装できるのではないかと思います。
迷路の接続の自動生成
最後に「全てのマスから別の全てのマスに到達する経路が必ず一つ存在する」ような接続の自動生成を説明します。計算機科学的な概念については本項では細かく説明しませんが、各語に補足のためのリンクを貼り付けました。
生成にはグラフ理論を利用します。
まず、本稿の定義の迷路において、全ての辺に壁が無い迷路は、マス目が頂点、罫線が辺の、格子グラフです。あとは、この格子グラフから全域木という部分グラフを取り出して、全域木の辺に対応する壁にのみ穴を開ければ、それだけで迷路の完成です。
あるグラフの全域木とは、そのグラフの全ての頂点を含む木グラフのことです。木は、木の中に含まれる各二頂点間の経路を必ずただ一つだけ持つようなグラフであるため、それだけで「全てのマスから別の全てのマスに到達する経路が必ず一つ存在する」が満たされます。
迷路生成部分
この処理に対応するRectangularMap.buildConnectionを以下に示します。
buildConnection() { // 格子グラフを構築 const graph = new Array(); // 辺(片方の頂点の座標＋方向, もう片方の頂点の座標＋方向)のリスト。 for (let y = 0; y < this.height; ++y) { for (let x = 0; x < this.width; ++x) { if (x < this.width - 1) { graph.push([x, y, RectangularMap.RIGHT, x + 1, y, RectangularMap.LEFT]); } if (y < this.height - 1) { graph.push([x, y, RectangularMap.DOWN, x, y + 1, RectangularMap.UP]); } } } // 全域木を抽出 const edges = graph.map((v) => [this.indexOf(v[0], v[1]), this.indexOf(v[3], v[4])]); const spanningTree = makeSpanningTree(this.width * this.height, edges); // 全域木の辺に穴を開ける let i = 0; for (let i = 0; i < edges.length; ++i) { const connected = spanningTree[i]; if (connected) { this.connection[graph[i][1]][graph[i][0]][graph[i][2]] = true; this.connection[graph[i][4]][graph[i][3]][graph[i][5]] = true; } } }
ランダムな全域木の生成
全域木の生成には、クラスカル法を改変したアルゴリズムを使いました。
function makeSpanningTree(numVertices, edges) { const disjointSet = new DisjointSet(numVertices); const connection = new Array(edges.length); for (const index of shuffle(makeIndexList(edges.length))) { const [vertex1, vertex2] = edges[index]; const group1 = disjointSet.find(vertex1); const group2 = disjointSet.find(vertex2); if (group1 != group2) { connection[index] = true; disjointSet.union(vertex1, vertex2); } else { connection[index] = false; } } return connection; }
最小全域木を生成するためにコストの小さい順に辺を走査するのではなく、辺集合をランダムにシャッフルして走査します。それ以外はクラスカル法と同様に、着目している辺の両端の頂点が既に繋がっていたらその辺は破棄し、未接続であればその辺を全域木に加える、という処理を繰り返すだけです。この方法で、ランダムな全域木が生成できます。誰かが既に考えている気がしますが名前はないのでしょうか？
素集合データ構造
辺の両端の頂点が過去に調べた辺で接続されているかどうかは、素集合データ構造を利用します。素集合データ構造とは、要素の集合に対して、以下の二つの操作を行うデータ構造です。
- 二つの要素が同じ集合に属しているか調べる
- 二つの部分集合を合体させて大きな部分集合を作る
迷路の生成においては、要素＝グラフの頂点＝マス目の面、です。makeSpanningTreeの各イテレーションにおいて、それまでに採用した辺によって互いに行き来できるマス目の集合を一つの部分集合として管理します。
このデータ構造の実現のために本プログラムではUnion-Findアルゴリズムを実装しました。実用的には素集合データ構造とUnion-Findアルゴリズムはほぼ等価なものとして扱われている気がします。
class DisjointSet { constructor(num) { this.num = num; this.parentOf = new Array(num); this.rankOf = new Array(num); for (let i = 0; i < this.num; ++i) { this.parentOf[i] = i; this.rankOf[i] = 0; } } find(index) { const parent = this.parentOf[index]; if (parent == index) { return index; } else { const root = this.find(parent); this.parentOf[index] = root; return root; } } union(index1, index2) { const root1 = this.find(index1); const root2 = this.find(index2); const rank1 = this.rankOf[root1]; const rank2 = this.rankOf[root2]; if (rank1 > rank2) { this.parentOf[root2] = root1; } else if (rank1 < rank2) { this.parentOf[root1] = root2; } else if (root1 != root2) { this.parentOf[root2] = root1; this.rankOf[root1] += 1; } } }
細かい関数の説明は省略しましたが、以上で四角マップの迷路を生成するプログラムの完成です。
六角マップ状の迷路を生成
四角形のマス目を碁盤状に並べるという制約を取り去っても、同じ方法で様々な構造の迷路を生成できます。
- 各タイルの面が空間を表し、罫線が壁を表す。
- 隣接する二つのタイルの共有辺に罫線がなければ、そのタイルは繋がっている。
- 全てのタイルから別の全てのタイルに到達する経路が必ず一つ存在する。
- ゆえに、スタートとゴールはランダムに2点を選べば良い。
例として本稿では、冒頭のCodePenの通り、六角マップ状の迷路も実装してみました。
class HexagonalMap { static UPPER_RIGHT = 0; static RIGHT = 1; static LOWER_RIGHT = 2; static LOWER_LEFT = 3; static LEFT = 4; static UPPER_LEFT = 5; constructor(width, height) { this.width = width; this.height = height; this.initializeConnection(); this.buildConnection(); } initializeConnection() { this.connection = new Array(this.height); for (let y = 0; y < this.height; ++y) { this.connection[y] = new Array(this.width); for (let x = 0; x < this.width; ++x) { this.connection[y][x] = new Array(6).fill(false); } } } buildConnection() { // 元になるグラフを構築 const graph = new Array(); for (let y = 0; y < this.height; ++y) { for (let x = 0; x < this.width; ++x) { if (x < this.width - 1) { graph.push([x, y, HexagonalMap.RIGHT, x + 1, y, HexagonalMap.LEFT]); } if (y < this.height - 1) { if (y % 2 == 0) { graph.push([x, y, HexagonalMap.LOWER_RIGHT, x, y + 1, HexagonalMap.UPPER_LEFT]); if (x > 0) { graph.push([x, y, HexagonalMap.LOWER_LEFT, x - 1, y + 1, HexagonalMap.UPPER_RIGHT]); } } else { graph.push([x, y, HexagonalMap.LOWER_LEFT, x, y + 1, HexagonalMap.UPPER_RIGHT]); if (x < this.width - 1) { graph.push([x, y, HexagonalMap.LOWER_RIGHT, x + 1, y + 1, HexagonalMap.UPPER_LEFT]); } } } } } // あとの処理はRectangularMapと全く同じ // 全域木を抽出 // 全域木の辺に穴を開ける } }
タイルの形は六角形ですが、タイルの配列は行列状に並べることにしました。シミュレーションゲームなどでもそのような配置です。そのため、coordinateは長さ6の配列の二次元配列になります。buildConnectionでmakeSpanningTreeに与えるグラフを生成する処理以外は、RectangularMapと同じコードです。
drawHexagonalMapToCanvasも、HexagonalMapの各タイルの各辺を調べて、壁があったら対応する座標に線を引くだけです。内容をご覧になりたい場合はCodePenのコードを参照ください。
三角タイリングでも、ボロノイ図でも、makeSpanningTreeに与えるグラフをコーディングできれば、元になるグラフとして任意の平面グラフを使用可能です。
