迷路を表す二次元グリッドと開始・終了位置
このツールは,迷路を行と列からなる二次元配列として保持します.各マスは行番号r,列番号cと,壁・通路・スタート・ゴール・探索中・探索済み・解答経路のいずれかを表すtypeを持ちます.画面で選べる大きさは15×15,21×21,31×31,41×41で,いずれも奇数です.生成関数には偶数が渡された場合に1を加える処理もありますが,現在の操作画面から選択できるのは前記の4種類です.
外周は壁として扱い,スタートは左上の外周から一マス内側にある座標[1, 1],ゴールは右下の外周から一マス内側にある座標[サイズ−2, サイズ−2]です.生成処理の最後にはこの二つのマスへ専用の種類を設定し,ゴールの左隣と上隣を通路にします.この後処理はゴールへ接続しやすくするためのものですが,生成直後の位相を変更するため,生成方式について「完全迷路である」「経路が必ず一意である」とは説明できません.
初回表示では,サーバー描画とクライアント描画の差を避けるため,固定値から作る疑似乱数を使って21×21の穴掘り法の盤面を用意します.「新しい迷路を生成」を押した場合や,サイズ・生成方法を変更した場合はMath.randomを使います.利用者がシード値を指定したり,後から同じ盤面を復元したりする機能はありません.
穴掘り法・棒倒し法・再帰分割法の実装範囲
穴掘り法は,全マスが壁の配列から[1, 1]を通路にし,上下左右の二マス先を候補として再帰的に掘ります.二マス先が外周の内側にあり,まだ壁なら,中間の一マスと移動先を通路にして同じ処理を続けます.候補方向の順序は乱数で並べ替えます.これは本実装の具体的な掘り方を示すものであり,盤面の難しさ,袋小路の数,遊びやすさを他の方式より優れていると保証するものではありません.
棒倒し法は,まず外周を除く内側を通路にし,偶数行・偶数列の交点へ柱となる壁を置きます.最初の柱の行では上下左右から一方向,それ以降の行では下・左・右から一方向を乱数で選び,柱に隣接する一マスも壁にします.最後に外周を壁へ戻します.この方向制限は,上方向へ伸ばした壁が既存の壁と重なる組合せを避けるための実装上の規則です.「標準的な難易度」「必ずバランスがよい」といった評価をツールは計算していません.
再帰分割法は,外周を壁,内側を通路にした領域から始めます.領域の高さが幅より大きければ水平,幅が高さより大きければ垂直,同じなら乱数で向きを決めます.選んだ向きに壁を引き,その壁に一つの開口部を残して,分かれた二領域へ同じ処理を適用します.画面上の名称は「再帰分割法(Recursive Division)」であり,穴掘り法や探索用DFSとは別の生成処理です.
どの方式についても,一意解や特定の難易度を判定する検査は行いません.
手動攻略,移動判定,手数と経過時間
生成後はプレイ状態になり,方向ボタン,キーボードの矢印キー,またはW・A・S・Dで上下左右へ一マスずつ移動できます.移動先が配列の範囲内で,壁でない場合だけプレイヤー座標を更新します.壁へ向けた入力は移動として数えず,実際に通路へ進んだ回数だけ手数へ加算します.斜め移動や壁越しの移動はありません.
経過時間はプレイ状態の間,setIntervalを使って一秒ずつ増やします.ゴール座標へ移動すると状態をsolvedへ変更し,タイマーを止めます.表示値は一秒刻みであり,高精度タイマーによる競技用計測ではありません.ブラウザのバックグラウンドタブ制御や端末負荷によってコールバックの実行時刻が遅れる可能性もあります.迷路を作り直すとプレイヤーをスタートへ戻し,経過時間と手数を0へリセットします.
テーマはサイバーネオン,レトロゲーム,クラシック,ミニマルの4種類です.テーマはマスのCSS表現を切り替えるもので,壁と通路の配列,探索順序,経路の長さを変更しません.手動攻略の途中で自動探索を開始すると,状態は探索中へ移り,手動移動は受け付けなくなります.
BFS・DFS・A*の探索順序と経路復元
自動探索を始めると,以前の探索済み・解答経路・探索中の印を通常の通路へ戻し,[1, 1]から右・下・左・上の順で隣接マスを候補にします.各候補には,そのマスへ初めて到達した親座標を記録します.ゴールを見つけた後は,親座標を逆にたどってスタートまで戻り,配列を反転して解答経路を描画します.画面の手数は,この経路に含まれるマス数から1を引いた値へ更新されます.
BFSは候補配列の先頭から取り出すキューとして動きます.上下左右の一回の移動コストがすべて1で,候補を初めて追加した時点で訪問済みにするため,本ツールの無重み格子では,到達可能なゴールまでの最短手数を求めます.一方,DFSは候補配列の末尾から取り出すスタックとして動き,一方向へ深く調べます.ゴールに到達する経路を得られても,その経路が最短である保証はありません.
A*は,スタートから現在位置までの移動回数gと,現在位置からゴールまでのManhattan距離hを足したfを計算し,fが小さい候補から取り出します.ただし本実装は,候補へ追加した時点で訪問済みにし,後からより小さいgが見つかった場合のコスト更新や候補の再登録を行いません.
そのため,一般的なA*の最短経路証明を本実装へ無条件に適用せず,Manhattan距離を使った優先探索の可視化として扱うのが適切です.
探索アニメーションと速度設定の意味
探索中は,現在調べているマスをscanning,調査を終えたマスをvisitedとして順次表示します.ゴールが見つかると,親座標から復元した経路の内部マスをsolutionへ変えます.探索速度は5〜200ミリ秒の範囲で,探索した一マスごとの待ち時間として使います.値が小さいほど画面更新の間隔が短くなります.経路描画の待ち時間は探索速度の半分を基準にし,最小10ミリ秒です.
この設定はアルゴリズム自体の計算量を変えるものではありません.また,ブラウザのタイマーは指定した時間より前に実行しないための目安であり,描画負荷や端末性能によって実際の間隔は長くなる場合があります.「探索停止」や迷路の再生成では実行中フラグを下げ,予約済みのタイマーを解除します.停止直後の表示には,それまでに付けた探索状態が残ることがありますが,次回の自動探索開始時には探索表示を通路へ戻します.
探索アニメーションが示すのは,本実装が候補を取り出した順序と,その親情報から復元した経路です.全候補の優先度値,キューやスタックの中身,計算時間の厳密な比較は表示しません.生成法ごとの優劣や迷路の難易度を測るベンチマークでもありません.
TXT・SVG出力の内容と利用上の制約
TXT保存では,壁を全角幅の「██」,スタートを「S」,ゴールを「G」,それ以外を空白二文字として行ごとに書き出します.そのため,通常の通路だけでなく,探索済み,探索中,解答経路も空白になります.フォントによる文字幅の違いで表示がずれる場合があるので,等幅フォントで開くか,保存後の内容を確認してください.ファイル名には選択中の迷路サイズが入ります.
SVG保存では,一マスを10×10のrect要素にして,盤面全体を矩形の集合として書き出します.壁,スタート,ゴールには別の塗り色を使い,その他のマスは同じ通路色です.画面で選んだテーマ,プレイヤーの位置,訪問済みの色,解答経路,手数,経過時間は含みません.SVGは盤面の矩形要素を直接生成しますが,印刷用紙への余白調整やPDF生成,PNG生成はこのツールの保存機能にはありません.
迷路の生成・探索・ファイル組み立てはページ上のJavaScriptで行い,編集中の盤面をサーバーへ保存する機能は設けていません.ただし,この実装事実だけからページ全体の無通信,オフライン動作,情報保護を保証するものではありません.盤面は永続保存されず,ページを再読み込みすると初期状態へ戻ります.教材や印刷物へ利用するときは,経路の到達可否,目的に合う難易度,保存結果を利用者自身で確認してください.