🚀
JavaScript で迷路／迷路作成モジュール（１）「通路と壁が同じサイズ」と「薄い壁」
この記事のスナップショット
迷路あれこれ
// 「通路と壁が同じサイズの迷路」の例 // 「薄い壁の迷路」の例
// ############### // +--+--+--+--+--+--+
// #S # # // |SS | |
// # ### # # # # # // +--+--+ + +--+--+
// # # # # # # // | | | |
// # ### # # ### # // + +--+ + +--+ +
// # # # # # # // | | | | | |
// ######### ### # // + +--+--+ + + +
// # # # // | | | |
// # ### ### ##### // +--+ + + + +--+
// # # # G# // | | | GG|
// ############### // +--+--+--+--+--+--+
ソース
動かし方
- ソース一式を WEB サーバ上に配置して、コンソール表示(Ctrl-Shift-I)
概要
迷路作成用のモジュールを用意しました。
-
「通路と壁が同じサイズの迷路」(Maze1.js)
-
「薄い壁の迷路」(Maze2.js)
// 「通路と壁が同じサイズの迷路」の例 // 「薄い壁の迷路」の例 // ############### // +--+--+--+--+--+--+ // #S # # // |SS | | // # ### # # # # # // +--+--+ + +--+--+ // # # # # # # // | | | | // # ### # # ### # // + +--+ + +--+ + // # # # # # # // | | | | | | // ######### ### # // + +--+--+ + + + // # # # // | | | | // # ### ### ##### // +--+ + + + +--+ // # # # G# // | | | | | // ############### // + + + +--+ + + // | | | GG| // +--+--+--+--+--+--+
下記、迷路作成のアルゴリズムを利用できます。
- 棒倒し
- 穴掘り
- 壁伸ばし
- 固定（ユーザ作成のテキストデータを読み込み）
また、迷路を作成するだけでなく、下記機能もあります。
- 最短経路を求める（幅優先、深さ優先、A*）
- 最長経路を求める／最長位置にスタートとゴールを再配置
- 複数の経路経路を求める
- 行き止まりを求める
- 迷路・経路のテキスト表示
| 機能 | Maze1 | Maze2 |
|---|---|---|
| 迷路作成（棒倒し） | O | O |
| 迷路作成（棒倒し・複数経路） | O | O |
| 迷路作成（穴掘り） | O | O |
| 迷路作成（穴掘り・複数経路） | O | O |
| 迷路作成（壁伸ばし） | O | O |
| 迷路作成（壁伸ばし・複数経路） | O | O |
| 迷路作成（穴掘り改・直線多） | O | O |
| 迷路作成（穴掘り改・斜め多） | O | O |
| 経路探索（幅優先・４方向） | O | O |
| 経路探索（深さ優先・４方向） | O | O |
| 経路探索（A*・４方向） | O | O |
| 経路探索（直線／方向転換の重み付き・８方向） | - | O |
| 複数経路探索（幅優先・４方向） | O | O |
| 複数経路探索（A*・４方向） | O | - |
| 複数経路探索（直線／方向転換の重み付き・８方向） | - | O |
| 最長経路（始点終点再配置） | O | O |
| 行き止まり探査 | O | O |
| 迷路・経路のテキスト表示 | O | O |
やったこと
- 「通路と壁が同じサイズの迷路」と「薄い壁の迷路」
- 迷路作成（棒倒し／穴掘り／壁伸ばし／固定）
- 最短経路（幅優先／深さ優先／A*／行き止まり）
- 複数の経路探索
- 最長経路／最長位置にスタートとゴールを再配置
「通路と壁が同じサイズの迷路」と「薄い壁の迷路」
２種類のデータ型で迷路を作成できます。
「通路と壁が同じサイズの迷路」(Maze1)では二次元配列を平面座標(y,x)に見立てて、座標値の値で（１：壁／０：通路）を表します。
-
利点
- データ構造が簡単
- 二次元配列（ｘ、ｙ）で壁／通路（＝１／０）の情報をもつ
- 壁判定／通路判定がしやすい
- データ構造が簡単
-
欠点
- サイズは奇数が基本
- 迷路のサイズが大きくなりがち（壁で１マス使うため）
「通路と壁が同じサイズの迷路」の例// ############### // #S # # // # ### # # # # # // # # # # # # // # ### # # ### # // # # # # # # // ######### ### # // # # # // # ### ### ##### // # # # G# // ###############
「薄い壁の迷路」(Maze2)では二次元配列を平面座標(y,x)と、その座標値のからの向き（東と南）の壁の有無を持たせています。北側と西側は、上隣の座標値の南側、左隣の座標値の東側を確認します。北端と西端は座標値から壁／進入禁止と判断します。
-
利点
- 物理的なサイズを小さくできる
- サイズに制限なし（奇数でもよい）
-
欠点
- データ構造がやや複雑
- 三次元配列（ｘ、ｙ、２方向）で壁／通路（＝１／０）の情報をもつ
- 方向は東（右）と南（下）の方向のみ。境界（領域外）の壁は、別途、座標と方向で判別。
- 壁判定／通路判定がちょっと面倒
- 東（右）と南（下）は、その座標のセルで判断できる。
北（上）は上隣のセルを下方向、西（左）は左隣の右方向の壁の有無を確認する必要あり。
- 東（右）と南（下）は、その座標のセルで判断できる。
「薄い壁の迷路」の例// +--+--+--+--+--+--+ // |SS | | // +--+--+ + +--+--+ // | | | | // + +--+ + +--+ + // | | | | | | // + +--+--+ + + + // | | | | // +--+ + + + +--+ // | | | | | // + + + +--+ + + // | | | GG| // +--+--+--+--+--+--+ - データ構造がやや複雑
迷路作成（棒倒し／穴掘り／壁伸ばし／固定）
他のサイト様でいろいろ説明されているので、アルゴリズムの詳細は割愛します。
-
棒倒し
-
単調／簡単な迷路になりがち
-
初級に使えそう
-
「複数経路あり」は既存の壁を無視して、重複して壁を生成するようにしています。
これにより、「より」複数経路ができやすくなります。
（従来の方法でも複数経路はできます）棒倒し// 従来（壁の有無を確認） //「複数経路あり」版 // +--+--+--+--+--+--+ // +--+--+--+--+--+--+ // |SS | | // |SS | // +--+--+ + +--+--+ // + + + + +--+ + // | | | | // | | | | | | // + +--+ + +--+ + // + + +--+ +--+ + // | | | | | | // | | | | | // + +--+--+ + + + // +--+--+ + + + + // | | | | // | | | | // +--+ + + + +--+ // +--+--+ +--+--+ + // | | | | | // | | | | // + + + +--+ + + // + +--+ + + +--+ // | | | GG| // | | GG| // +--+--+--+--+--+--+ // +--+--+--+--+--+--+棒倒し(Maze1){ let nrow = 11, ncol = 15; let mzdata = new Maze1.MazeData01(nrow, ncol); mzdata.create(10); // 棒倒し法 // mzdata.create(11); // 棒倒し法 複数経路 mzdata.dbgPrintMap(); } { let nrow = 6, ncol = 6; let mzdata = new Maze2.MazeData02(nrow, ncol); mzdata.create(10); // 棒倒し法 // mzdata.create(11); // 棒倒し法 複数経路 mzdata.dbgPrintMap(); }
-
-
穴掘り
-
複雑さのある迷路に
-
複数の経路にするには、一定確率で壁に穴をあけ（通路を作成し）ます。
-
オーソドックスな穴掘りの他、隣接する通路に応じて直線通路／斜め通路の生成確率を調整する方法（穴掘り改）も試作
穴掘り// 従来 //「複数経路あり」版 // +--+--+--+--+--+--+ // +--+--+--+--+--+--+ // |SS| | | // |SS | | // + + + + + + + // +--+ +--+ + + + // | | | | | | | // | | | | | // + +--+ + + +--+ // + +--+ +--+ + + // | | | | // | | | | | // +--+--+--+ +--+ + // + +--+ + + + + // | | | | // | | | // + + + +--+ + + // + + + + +--+ + // | | | | | // | | | // + +--+--+ +--+ + // +--+ + +--+--+ + // | | GG| // | GG| // +--+--+--+--+--+--+ // +--+--+--+--+--+--+ // 穴掘り改（直線の比重を高） //穴掘り改（斜めの比重を高） // +--+--+--+--+--+--+ // +--+--+--+--+--+--+ // |SS | // |SS| | | // +--+--+--+ + + + // + +--+ +--+ + + // | | | // | | | | // + +--+--+--+ + + // +--+ +--+ + + + // | | | | | // | | | | | // + + +--+--+ + + // + + + +--+ + + // | | | | // | | | | | // + + +--+--+ + + // + + +--+ +--+ + // | | | | // | | | | // + +--+ +--+ + + // + +--+--+--+ + + // | GG| // | GG| // +--+--+--+--+--+--+ // +--+--+--+--+--+--+穴掘り(Maze1){ let nrow = 11, ncol = 15; let mzdata = new Maze1.MazeData01(nrow, ncol); mzdata.create(20); // 穴掘り // mzdata.create(21); // 穴掘り 複数経路 // mzdata.create(22); // 穴掘り改 .. 中庸 // mzdata.create(23); // 穴掘り改 .. ななめを多め // mzdata.create(24); // 穴掘り改 .. ストレート多め mzdata.dbgPrintMap(); } { let nrow = 6, ncol = 6; let mzdata = new Maze2.MazeData02(nrow, ncol); mzdata.create(20); // 穴掘り // mzdata.create(21); // 穴掘り 複数経路 // mzdata.create(22); // 穴掘り改 .. 中庸 // mzdata.create(23); // 穴掘り改 .. ななめを多め // mzdata.create(24); // 穴掘り改 .. ストレート多め mzdata.dbgPrintMap(); }
-
-
壁伸ばし
-
壁を伸ばしすぎると外周が通路になりがち
- 「薄い壁」(Maze2)で、伸ばす壁の長さを減衰させる仕組みを導入
- 複数経路を作成するには、外周の壁からではなく、中央の空間から壁を作成します。
壁伸ばし// 従来 //「複数経路あり」版 // +--+--+--+--+--+--+ // +--+--+--+--+--+--+ // |SS | | | // |SS | // + +--+--+--+ + + // + + +--+--+ +--+ // | | | | // | | | | | // + + +--+ +--+ + // + + +--+ +--+ + // | | | // | | | | | // + +--+ +--+ + + // +--+ +--+ +--+ + // | | | | | // | | | | | // + + +--+ +--+ + // + +--+ +--+ + + // | | | | | // | | | | // +--+ +--+ + +--+ // + +--+--+--+--+ + // | | | GG| // | GG| // +--+--+--+--+--+--+ // +--+--+--+--+--+--+壁伸ばし(Maze1){ let nrow = 11, ncol = 15; let mzdata = new Maze1.MazeData01(nrow, ncol); mzdata.create(30); // 壁のばし法 // mzdata.create(31); // 壁のばし法 複数経路 mzdata.dbgPrintMap(); } { let nrow = 6, ncol = 6; let mzdata = new Maze2.MazeData02(nrow, ncol); mzdata.create(30); // 壁のばし法 // mzdata.create(31); // 壁のばし法 複数経路 mzdata.dbgPrintMap(); }
-
-
固定
-
ユーザが作成したテキストデータを迷路データにすることが可能
-
固定の迷路データは(Maze1data.js, Maze2data.js)に用意。
Meze2dataにはマイクロマウスのコースをいくつか再現／掲載固定// ####################################### // #S # // # ### ### ### ### ### ### ### ### ### # // # ### ### ### ### ### ### ### ### ### # // # # // # ### ### ### ### ### ### ### ### ### # // # ### ### ### ### ### ### ### ### ### # // # # // # ### ### ### ### ### ### ### ### ### # // # ### ### ### ### ### ### ### ### ### # // # # // # ### ### ### ### ### ### ### ### ### # // # ### ### ### ### ### ### ### ### ### # // # G# // #######################################固定(Maze1)let stMap = 'sdata65'; { let mzdata = new Maze1.MazeData01(); mzdata.create_from(Maze1data.get_map_data(stMap)); mzdata.dbgPrintMap(); } { let mzdata = new Maze2.MazeData02(); mzdata.create_from(Maze2data.get_map_data(stMap)) mzdata.dbgPrintMap(); }
-
最短経路（幅優先／深さ優先／A*／行き止まり）
-
幅優先(BFS)／最短経路
-
最短経路
幅優先// 最短経路(path2)を表示 // ####################################### // #S # // #.### ### ### ### ### ### ### ### ### # // #.### ### ### ### ### ### ### ### ### # // #. # // #.### ### ### ### ### ### ### ### ### # // #.### ### ### ### ### ### ### ### ### # // #. # // #.### ### ### ### ### ### ### ### ### # // #.### ### ### ### ### ### ### ### ### # // #. # // #.### ### ### ### ### ### ### ### ### # // #.### ### ### ### ### ### ### ### ### # // #....................................G# // #######################################let stMap = 'sdata65'; { let mzdata = new Maze1.MazeData01(); mzdata.create_from(Maze1data.get_map_data(stMap)); mzdata.seekPath2(); // 最短経路(幅優先) mzdata.dbgPrintMap(); } { let mzdata = new Maze2.MazeData02(); mzdata.create_from(Maze2data.get_map_data(stMap)) mzdata.seekPath2(); // 最短経路(幅優先) mzdata.dbgPrintMap(); }
-
-
深さ優先
-
最短経路になってないときがあります
-
「幅優先」を実装のついでに、こちらも用意しました
-
経路の実装が不十分で隣接しているのに回り道をすることがあります
深さ優先// 経路(path3)を表示 // ####################################### // #S ..... ..... ..... ..... # // #.###.###.###.###.###.###.###.###.### # // #.###.###.###.###.###.###.###.###.### # // #. . . . . . . . . # // #.###.###.###.###.###.###.###.###.### # // #.###.###.###.###.###.###.###.###.### # // #. . . . . . . . . # // #.###.###.###.###.###.###.###.###.### # // #.###.###.###.###.###.###.###.###.### # // #. . . . . . . . . # // #.###.###.###.###.###.###.###.###.### # // #.###.###.###.###.###.###.###.###.### # // #..... ..... ..... ..... ....G# // #######################################let stMap = 'sdata65'; { let mzdata = new Maze1.MazeData01(); mzdata.create_from(Maze1data.get_map_data(stMap)); mzdata.seekPath3(); // 深さ優先 mzdata.dbgPrintMap(); } { let mzdata = new Maze2.MazeData02(); mzdata.create_from(Maze2data.get_map_data(stMap)) mzdata.seekPath3(); // 深さ優先 mzdata.dbgPrintMap(); }
-
-
A*
-
流行り？っぽいので実装してみました
-
我流なので少々違うかも
A*// 最短経路(path6)を表示 // ####################################### // #S # // #.### ### ### ### ### ### ### ### ### # // #.### ### ### ### ### ### ### ### ### # // #. # // #.### ### ### ### ### ### ### ### ### # // #.### ### ### ### ### ### ### ### ### # // #. # // #.### ### ### ### ### ### ### ### ### # // #.### ### ### ### ### ### ### ### ### # // #......... # // # ### ###.### ### ### ### ### ### ### # // # ### ###.### ### ### ### ### ### ### # // # ............................G# // #######################################let stMap = 'sdata65'; { let mzdata = new Maze1.MazeData01(); mzdata.create_from(Maze1data.get_map_data(stMap)); mzdata.seekPath6(); // A* mzdata.dbgPrintMap(); } { let mzdata = new Maze2.MazeData02(); mzdata.create_from(Maze2data.get_map_data(stMap)) mzdata.seekPath6(); // A* mzdata.dbgPrintMap(); }
-
-
行き止まり
-
最短経路とは毛色が違いますが、類似ということで
-
行き止まりになる一本道を求め、結果スタートからゴールまでの経路が残る算段です。
-
複数経路を見つけやすくなります。
-
袋小路の行き止まり（〇─のような）は検出できません（行き止まりと判定できていない）
行き止まり// オリジナル // #################### // #S # // # ####### ##### ## # // # # # # // # #### ### ####### # // # # # # G# // #################### // 行き止まり(deadend1)を表示 // #################### // #S # // #x####### ##### ## # // #xxxx# #xxx # // #x#### ### ####### # // #xxxx# # #xxxxG# // ####################{ let stMap = 'sdata74'; let mzdata = new Maze1.MazeData01(); mzdata.create_from(Maze1data.get_map_data(stMap)); mzdata.dbgPrintMap(); mzdata.seekDeadEnd(); // 行き止まり mzdata.dbgPrintMap(); } { let mzdata = new Maze2.MazeData02(); mzdata.create_from(Maze2data.get_map_data("sdata73")) mzdata.seekDeadEnd(); // 行き止まり mzdata.dbgPrintMap(); }
-
複数の経路探索
複数の経路探索を行うには、最初に見つけた経路のどこかを通行止めにして再度経路探索を行います。
「通行止めにする箇所を増やしていく」方法と
「地図をリセットして、通行止めにする箇所をランダムに変更する」方法
を組み合わせて行います。
複数経路のすべての組み合わせを取得したいわけではなく、代表的な経路を知りたいだけなので、すべての組み合わせを試すことはせずに、適当に探索したら打ち切ります。
また、見つけた経路の中で似通った経路は１つにまとめます。任意の２つの経路を見比べ、短い経路の８割以上の点が長い経路にあれば、長い経路を削除します。
ちなみに、各径路の評価として、歩数「walk」、方向転換「turn」も出してますが、
歩数は「経路の地点の数」、
方向転換は「４５度を１としたときの方向転換の角度の和」
になってます。
複数の経路探索、検出結果
// walk= 10 , turn= 2 , path=
// (11) [10, 19, 28, 37, 46, 47, 48, 49, 50, 51, 52]
// 経路(path99)を表示
// #########
// #S #
// #.##### #
// #. #
// #.##### #
// #......G#
// #########
// walk= 10 , turn= 4 , path=
// (11) [10, 19, 28, 29, 30, 31, 32, 33, 34, 43, 52]
// 経路(path99)を表示
// #########
// #S #
// #.##### #
// #.......#
// # #####.#
// # G#
// #########
// walk= 10 , turn= 2 , path=
// (11) [10, 11, 12, 13, 14, 15, 16, 25, 34, 43, 52]
// 経路(path99)を表示
// #########
// #S......#
// # #####.#
// # .#
// # #####.#
// # G#
// #########
{
let stMap = 'sdata10';
let mzdata = new Maze1.MazeData01();
mzdata.create_from(Maze1data.get_map_data(stMap));
mzdata.seekSomePath2(); // 複数経路の探索(幅優先)
// mzdata.seekSomePath6(); // 複数経路の探索 （A*
mzdata.dbgPrintMap();
}
{
let mzdata = new Maze2.MazeData02();
mzdata.create_from(Maze2data.get_map_data("sdata10"))
mzdata.dbgPrintMap();
mzdata.seekSomePath2(); // 複数経路の探索（幅優先)
// mzdata.seekSomePath7(); // 複数経路の探索（斜めあり
mzdata.dbgPrintMap();
}
最長経路／最長位置にスタートとゴールを再配置
-
最長経路
- 最長経路をもとめるには、幅優先アルゴリズムを流用し、ゴールを設置せずに全地点をサーチします。
- 任意の点から開始して、新規に検査した地点で最長距離と判断できたら、
最長距離と座標を更新します。（多分あってるはず）
-
最長位置にスタートとゴールを再配置
- 「最長位置にスタートとゴールを再配置」するには、
「スタート」地点から最長位置にある座標をもとめ「仮のゴール地点」とします。 - 次に「仮のゴール地点」から最長位置にある座標をもとめ「仮のスタート地点」とします。
- 再度「仮のスタート地点」から最長位置にある座標をもとめ「仮のゴール地点」を更新します。
- 再度「仮のゴール地点」から最長位置にある座標をもとめ「仮のスタート地点」を更新します。
- と繰り返していけば、最長位置に収束するだろうという考えです。
（スタート→ゴール）と（ゴール→スタート）を２巡させます。
- 「最長位置にスタートとゴールを再配置」するには、
デフォルトでは左上をスタート地点、右下をゴール地点にしてますが、
再配置によって、より意地悪な迷路に仕上げることができます。
再配置
// オリジナル
// ####################
// #S #
// # ####### ##### ## #
// # # # #
// # #### ### ####### #
// # # # # G#
// ####################
// 再配置した後
// ####################
// # #
// # ####### ##### ## #
// # # # #
// # #### ### ####### #
// # S# # #G #
// ####################
{
stMap = 'sdata74';
let mzdata = new Maze1.MazeData01();
mzdata.create_from(Maze1data.get_map_data(stMap));
mzdata.dbgPrintMap();
mzdata.resetStartGoal(); // スタート・ゴールを最遠方に再配置
mzdata.dbgPrintMap();
}
{
let mzdata = new Maze2.MazeData02();
mzdata.create_from(Maze2data.get_map_data("sdata73"))
mzdata.resetStartGoal(); // スタート・ゴールを最遠方に再配置
mzdata.dbgPrintMap();
}
まとめ・雑感
どこかに迷路作成モジュールが転がってないものかと探した結果、自作・公開することにしました。
利用は自己責任で。
昔、右手法を実装したことがありますが、スパゲッティ具合がひどかった。バグも多かったし。
それ比べ幅優先のなんと簡素で美しいことか。こうありたいものです。
迷路のアルゴリズムの調査の中で知った
「KERI's Lab」さんのサイト（マイクロマウスでの経路分析）は興味深いです。
ロボットは門外漢なのですが、斜め移動／台形加速を考慮した最短経路とかワクワクします。
斜め方向、８方向の移動を考慮した探索については次の記事でお話します。
参考資料
-
迷路作成アルゴリズム（棒倒し、穴掘り、壁伸ばし
-
マイクロマウス迷路の自動生成
-
迷路の最短距離問題(BFS)～Javascriptでの解法～
-
幅優先探索で迷路の特定のスタート地点からゴール地点までの最短距離を出力するプログラム
-
【図解】A*アルゴリズムで最短経路問題を解く方法
-
PathFinding.js
-
全日本マイクロマウス大会
Discussion