⛳
JavaScript で迷路／迷路作成モジュール（２）斜め移動を考慮
この記事のスナップショット
斜めありの経路
// ###############################
// # #
// # S . . . . #
// # | #
// # + ################### #
// # \\ #
// # . +--+--+--+--+--+--+ . #
// # \\ #
// # ################### + #
// # | #
// # . . . . G #
// # #
// ###############################
ソース
動かし方
- ソース一式を WEB サーバ上に配置して、コンソール表示(Ctrl-Shift-I)
概要
前回、迷路作成用のモジュールを用意しましたが、主に縦横移動、４方向の移動を基にしたものでした。
今回は斜めも含めた８方向の移動も考慮したデータ構造およびモジュール(Maze3)を紹介します。
-
「薄い壁の迷路で斜め移動を考慮した迷路」(Maze3.js)
// ############################### // # # // # S . . . . # // # | # // # + ################### # // # \\ # // # . +--+--+--+--+--+--+ . # // # \\ # // # ################### + # // # | # // # . . . . G # // # # // ###############################
マイクロマウスの経路探索に触発されて、
「薄い壁の迷路」（Maze2）をベースにして、斜め移動を考慮したデータ構造、探索を行うモジュールになります。
迷路作成のアルゴリズムは下記を利用できますが、基本は Maze2 でデータを作って、Maze3用に変換します。
- 棒倒し
- 穴掘り
- 壁伸ばし
- 固定（ユーザ作成のテキストデータを迷路化）
また、迷路を作成するだけでなく、下記機能もありますが、Maze2と比べると一部の機能（スタート・ゴールの再配置など）をカットしています。
- 経路を求める（幅優先、斜めあり）
- 複数の経路経路を求める
- 行き止まりを求める
- 迷路・経路のテキスト表示
| 機能 | Maze1 | Maze2 | Maze3 |
|---|---|---|---|
| 迷路作成（棒倒し） | O | O | O |
| 迷路作成（棒倒し・複数経路） | O | O | O |
| 迷路作成（穴掘り） | O | O | O |
| 迷路作成（穴掘り・複数経路） | 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 | O | O |
| 複数経路探索（A*・４方向） | O | - | - |
| 複数経路探索（直線／方向転換の重み付き・８方向） | - | O | O |
| 最長経路（始点終点再配置） | O | O | - |
| 行き止まり探査 | O | O | O |
| 迷路・経路のテキスト表示 | O | O | O |
やったこと
- 斜め移動のための再定義(Maze3)
- Maze3での迷路作成
- Maze3での経路探索
- Maze3での複数の経路探索
- Maze3で未対応の機能
- マイクロマウスの迷路での探索
斜め移動のための再定義(Maze3)
Maze2 で斜め移動を含めた経路探索を行い、表示すると次のような結果になります。
// オリジナル
// 経路(path7)を表示
// +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
// |SS <> <> <> <> <> |
// + +--+ +--+ +--+ +--+ +--+ +--+ +--+ +
// | | | | | | |<>| | | | | | | | |
// + +--+ +--+ +--+ +--+ +--+ +--+ +--+ +
// | <> |
// + +--+ +--+ +--+ +--+ +--+ +--+ +--+ +
// | | | | | | | | |<>| | | | | | |
// + +--+ +--+ +--+ +--+ +--+ +--+ +--+ +
// | <> |
// + +--+ +--+ +--+ +--+ +--+ +--+ +--+ +
// | | | | | | | | | | |<>| | | | |
// + +--+ +--+ +--+ +--+ +--+ +--+ +--+ +
// | <> |
// + +--+ +--+ +--+ +--+ +--+ +--+ +--+ +
// | | | | | | | | | | | | |<>| | |
// + +--+ +--+ +--+ +--+ +--+ +--+ +--+ +
// | <> GG|
// +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
let stMap = 'sdata65';
let mzdata = new Maze2.MazeData02();
mzdata.create_from(Maze2data.get_map_data(stMap))
mzdata.seekPath7(); // 斜めあり
mzdata.dbgPrintMap();
これを見て「斜め方向もできた」と思っていた自分が恥ずかしい。
上記は、自身の体積を無視した移動で、実際には斜めにまっすぐ移動できないことがわかります。
そもそもの移動の考え方がおかしいことに気が付いたので、改めて「空間」と「移動可能な箇所」について考え直します。
まず迷路の空間として２×２のエリアがあったとします。
#---------#---------#
| | |
| | |
| | |
| | |
| | |
#---------#---------#
| | |
| | |
| | |
| | |
| | |
#---------#---------#
このエリア内で移動／配置可能な箇所を(O)で示すと次のような感じ。
O====O====O====O====O
[＼／:＼／[＼／:＼／[
]／＼:／＼]／＼:／＼]
O - -O - -O - -O - -O
[＼／:＼／[＼／:＼／[
]／＼:／＼]／＼:／＼]
O====O====O====O====O
[＼／:＼／[＼／:＼／[
]／＼:／＼]／＼:／＼]
O - -O - -O - -O - -O
[＼／:＼／[＼／:＼／[
]／＼:／＼]／＼:／＼]
O====O====O====O====O
これは通路・壁が同じ大きさの迷路の場合（斜め移動あり）と同じと見て取れそうです。
#----#----#----#----#----#
| | | | | |
| | | | | |
#----#----#----#----#----#
| | | | | |
| | | | | |
#----#----#----#----#----#
| | | | | |
| | | | | |
#----#----#----#----#----#
| | | | | |
| | | | | |
#----#----#----#----#----#
| | | | | |
| | | | | |
#----#----#----#----#----#
たとえば次のような壁の配置があった場合、
#---------# #
| |
| |
| |
| |
| |
# # #
| |
| |
| |
| |
| |
#---------# #
このとき移動可能な位置(O)は次のように表すことができます。
*====*====* O - -O
[ [ :＼／:
] ] :／＼:
* O * O - -O
[ : [ : ／
] : ] :／
* O * O *
[ :＼ ／: [
] : ＼ ／ : ]
* O - -O - -O *
[ ＼ : [
] ＼: ]
*====*====* O *
上記を迷路(Maze1)であらわすとこんな感じに。
#----#----#----#----#----#
|####|####|####| | |
|####|####|####| | |
#----#----#----#----#----#
|####| |####| | |
|####| |####| | |
#----#----#----#----#----#
|####| |####| |####|
|####| |####| |####|
#----#----#----#----#----#
|####| | | |####|
|####| | | |####|
#----#----#----#----#----#
|####|####|####| |####|
|####|####|####| |####|
#----#----#----#----#----#
つまり Maze2 から 2N+1 倍したサイズの Maze1 を用意して、斜めの経路を考慮して経路問題を解けばよさげです。
このようにデータ構造を再定義し、斜めを含む探索が可能な迷路モジュールが Maze3 になります。
ちなみに、Maze3 で最初の迷路を解くと次のようになり、確かに斜めにまっぐには進めないことがわかります。
// 経路(path7)を表示
// ###########################################################################################
// # #
// # S--+--+--+--+--+--+--+--+--+--+--+ . . . . . . . . . #
// # \\ #
// # ####### ####### ####### + ####### ####### ####### ####### #
// # # # # # # # | # # # # # # # # #
// # . # . # . # . # . # . # + # . # . # . # . # . # . # . # . #
// # # # # # # # | # # # # # # # # #
// # ####### ####### ####### + ####### ####### ####### ####### #
// # \\ #
// # . . . . . . . +--+--+ . . . . . . . #
// # \\ #
// # ####### ####### ####### ####### + ####### ####### ####### #
// # # # # # # # # # | # # # # # # #
// # . # . # . # . # . # . # . # . # + # . # . # . # . # . # . #
// # # # # # # # # # | # # # # # # #
// # ####### ####### ####### ####### + ####### ####### ####### #
// # \\ #
// # . . . . . . . . . +--+--+ . . . . . #
// # \\ #
// # ####### ####### ####### ####### ####### + ####### ####### #
// # # # # # # # # # # # | # # # # #
// # . # . # . # . # . # . # . # . # . # . # + # . # . # . # . #
// # # # # # # # # # # # | # # # # #
// # ####### ####### ####### ####### ####### + ####### ####### #
// # \\ #
// # . . . . . . . . . . . +--+--+ . . . #
// # \\ #
// # ####### ####### ####### ####### ####### ####### + ####### #
// # # # # # # # # # # # # # | # # #
// # . # . # . # . # . # . # . # . # . # . # . # . # + # . # . #
// # # # # # # # # # # # # # | # # #
// # ####### ####### ####### ####### ####### ####### + ####### #
// # \\ #
// # . . . . . . . . . . . . . +--+--+--G #
// # #
// ###########################################################################################
Maze3での迷路作成
Maze3では、Maze2で作った／読み込んだ迷路データを 2N+1 倍して Maze3 用の迷路データとします。
つまり、Maze2で作成可能な迷路が、Maze3で作成可能な迷路となります。
Maze2での迷路データ（上）と同じデータから作られたMaze3の迷路データ（下）
// +--+--+--+--+--+
// |SS |
// + +--+--+--+ +
// | |
// + +--+--+--+ +
// | GG|
// +--+--+--+--+--+
// 格子＋壁(debug用)の表示
// ###############################
// # #
// # S . . . . #
// # #
// # ################### #
// # #
// # . . . . . #
// # #
// # ################### #
// # #
// # . . . . G #
// # #
// ###############################
Maze3の迷路生成
{
let nrow = 6, ncol = 6;
let mzdata = new Maze3.MazeData03(nrow, ncol);
mzdata.create(10); // 棒倒し法
// mzdata.create(11); // 棒倒し法（複数経路）
// mzdata.create(20); // 穴掘り
// mzdata.create(21); // 穴掘り 複数経路
// mzdata.create(22); // 穴掘り改 .. 中庸
// mzdata.create(23); // 穴掘り改 .. ななめを多め
// mzdata.create(24); // 穴掘り改 .. ストレート多め
// mzdata.create(30); // 壁のばし法
// mzdata.create(31); // 壁のばし法 複数経路
mzdata.dbgPrintMap();
}
{
// 固定の場合
let mzdata = new Maze3.MazeData03();
let mzdata2 = new Maze2.MazeData02();
mzdata2.create_from(Maze2data.get_map_data('sdata78'))
mzdata.create_from_maze2(mzdata2);
mzdata.dbgPrintMap();
}
Maze3での経路探索
経路探索のアルゴリズムは、簡単に「幅優先」（４方向）と「斜めあり」（８方向）のみとします。
幅優先
// 最短経路(path2)を表示
// ###############################
// # #
// # S . . . . #
// # | #
// # + ################### #
// # | #
// # + . . . . #
// # | #
// # + ################### #
// # | #
// # +--+--+--+--+--+--+--+--G #
// # #
// ###############################
let stMap = 'sdata10';
let mzdata = new Maze3.MazeData03();
let mzdata2 = new Maze2.MazeData02();
mzdata2.create_from(Maze2data.get_map_data(stMap))
mzdata.create_from_maze2(mzdata2);
mzdata.seekPath2(); // 最短経路(幅優先)
mzdata.dbgPrintMap();
斜めあり
// 経路(path7)を表示
// ###############################
// # #
// # S . . . . #
// # | #
// # + ################### #
// # \\ #
// # . +--+--+--+--+--+--+ . #
// # \\ #
// # ################### + #
// # | #
// # . . . . G #
// # #
// ###############################
let stMap = 'sdata10';
let mzdata = new Maze3.MazeData03();
let mzdata2 = new Maze2.MazeData02();
mzdata2.create_from(Maze2data.get_map_data(stMap))
mzdata.create_from_maze2(mzdata2);
mzdata.seekPath7(); // 斜めあり
mzdata.dbgPrintMap();
「行き止まり」は Maze1, Maze2 と同様に一本道の行き止まりを検出し、袋小路の行き止まりは未検出です。
行き止まり、オリジナル（上）と行き止まりの表示（下）
// 格子＋壁(debug用)の表示
// ###################################################################
// # #
// # S . . . . . . . . . . #
// # #
// # ######################### ############# ####### #
// # # # #
// # . . . # . . . . # . . . . #
// # # # #
// # ######################### ######################### #
// # # # # #
// # . . . # . . . . # . . . # . #
// # # # # #
// # ############# ############# # ############# #
// # # # # #
// # . . . # . . . . # . # . . G #
// # # # # #
// ###################################################################
// 行き止まり(deadend1)を表示
// ###################################################################
// # #
// # S . . . . . . . . . . #
// # #
// #XXXXX######################### ############# ####### #
// #XXXXXXXXXXXXXXXXX#XXXXXXXXXXXX XXXXXX#XXXXXX #
// #XXXXXXXXXXXXXXXXX#XXXXXXXXXXXX . XXXXXX#XXXXXX . . . #
// #XXXXXXXXXXXXXXXXX#XXXXXXXXXXXX XXXXXX#XXXXXX #
// #XXXXX######################### ######################### #
// #XXXXXXXXXXXXXXXXX# #XXXXXXXXXXXXXXXXX# #
// #XXXXXXXXXXXXXXXXX# . . . . #XXXXXXXXXXXXXXXXX# . #
// #XXXXXXXXXXXXXXXXX# #XXXXXXXXXXXXXXXXX# #
// #XXXXX############# ############# #XXXXX############# #
// #XXXXXXXXXXXXXXXXX# #XXXXX#XXXXXXXXXXXX #
// #XXXXXXXXXXXXXXXXX# . . . . #XXXXX#XXXXXXXXXXXX G #
// #XXXXXXXXXXXXXXXXX# #XXXXX#XXXXXXXXXXXX #
// ###################################################################
let mzdata = new Maze3.MazeData03(nrow, ncol);
let mzdata2 = new Maze2.MazeData02(nrow, ncol);
mzdata2.create_from(Maze2data.get_map_data("sdata73"))
mzdata.create_from_maze2(mzdata2);
mzdata.dbgPrintMap();
mzdata.seekDeadEnd(); // 行き止まり
mzdata.dbgPrintMap();
Maze3での複数の経路探索
複数の経路探索は、「幅優先」と「斜めあり」を使ったもので利用可能です。
複数の経路探索：斜めあり
// walk= 10 , turn= 4 , path=
// (11) [12, 23, 35, 36, 37, 38, 39, 40, 41, 53, 64]
// 経路(path99)を表示
// ###############################
// # #
// # S . . . . #
// # | #
// # + ################### #
// # \\ #
// # . +--+--+--+--+--+--+ . #
// # \\ #
// # ################### + #
// # | #
// # . . . . G #
// # #
// ###############################
// walk= 11 , turn= 2 , path=
// (12) [12, 23, 34, 45, 57, 58, 59, 60, 61, 62, 63, 64]
// 経路(path99)を表示
// ###############################
// # #
// # S . . . . #
// # | #
// # + ################### #
// # | #
// # + . . . . #
// # | #
// # + ################### #
// # \\ #
// # . +--+--+--+--+--+--+--G #
// # #
// ###############################
// walk= 11 , turn= 2 , path=
// (12) [12, 13, 14, 15, 16, 17, 18, 19, 31, 42, 53, 64]
// 経路(path99)を表示
// ###############################
// # #
// # S--+--+--+--+--+--+--+ . #
// # \\ #
// # ################### + #
// # | #
// # . . . . + #
// # | #
// # ################### + #
// # | #
// # . . . . G #
// # #
// ###############################
let stMap = 'sdata10';
let mzdata = new Maze3.MazeData03();
let mzdata2 = new Maze2.MazeData02();
mzdata2.create_from(Maze2data.get_map_data(stMap))
mzdata.create_from_maze2(mzdata2);
// mzdata.seekSomePath2(); // 複数経路・幅優先探索
mzdata.seekSomePath7(); // 複数経路・斜めあり
mzdata.dbgPrintMap();
Maze3で未対応の機能
「スタート・ゴールの再配置」はありません。
こちらは Maze2 で再配置したものを Maze3 に変換してください。
...
mzdata2.resetStartGoal(); // スタート・ゴールを最遠方に再配置
mzdata3.create_from_maze2(mzdata2);
...
マイクロマウスの迷路での探索
これが見たかった。本当にこれが見たかった。
let stMap = 'sdatamm2018classic';
let mzdata3 = new Maze3.MazeData03();
let mzdata2 = new Maze2.MazeData02();
mzdata2.create_from(Maze2data.get_map_data(stMap));
mzdata3.create_from_maze2(mzdata2);
mzdata3.seekPath7(); // 斜めあり
mzdata3.dbgPrintMap();
個人的にお気に入りは、2016年のハーフ・エキスパート競技 決勝のコース。
「幅優先の最短経路」と「直進／斜めを加味した経路」で経路が違うのが素敵。
- 参考）
- 2016：第３７回全日本マイクロマウス大会ハーフ・エキスパート競技 決勝
- 過去の全日本マイクロマウス大会32x32迷路の分析
まとめ・雑感
マイクロマウスの記事を見ると、よく迷路の経路探索がアップされていて、同じようなことをやりたかった、似た経路を見つけたかったのが動機です。
でもアルゴリズムの説明ってアップされてないんですよね。なので想像で補間して作ってみました。
似たような経路になっているので多分近いのでしょう。満足です。
いや、本当はここまで深入りするつもりはなかったです。
Maze1, Maze2 ができた段階で、他に展開する予定だったのですが、そちらはまた別の記事で。
Discussion