経路探索3種でかんたんダンジョン攻略

経路探索アルゴリズム

前回の記事では、迷路アルゴリズムを3種類紹介しました。
今回は、定番の経路探索アルゴリズムを3種類紹介します。

1. 深度優先探索
2. 幅優先探索
3. A*アルゴリズム

ここでは、迷路の描画にOpenProcessingを利用します。
使い方に関しては、p5.jsをかじる本を参考にして頂けると幸いです。

探索対象の迷路

探索対象の迷路は、複数の経路が生まれやすい"壁倒し法"で用意しました。
(近道も出来そうですし、遠回りも出来そうな...)

スタート位置は左上の青い箇所、
ゴール位置は右下の赤い箇所とします。

壁倒し法で作った迷路

深度優先探索

最初に紹介するのは、"深度優先探索"です。
このアルゴリズムの特徴を簡単にまとめると次の通りです。

1. 兎に角先に進む
2. 壁にぶつかったら、直前の分岐点まで戻る(1に戻る)
3. ゴールに辿り着いていたら終了

3つのアルゴリズムでは最も理解しやすいものになります。

具体的な実装例(深度優先)

完成コードは次のとおりです。(クリックでコード全体を見ることができます)

深度優先探索

経路探索では、次の2つの配列が重要な役割を果たします。

配列名	役割	説明
points	探索済み	探索を終了した通路の座標(r, c)を格納します
routes	探索候補	未探索の通路の座標(r, c)を格納します

具体的な処理は、"searchMaze()"関数を確認してみましょう。

routes配列からは、pop()を使って最後尾から通路を取り出す事がポイントです。
取り出した通路がゴールと一致するまで再帰処理で繰り返します。

main.js

// 省略
function searchMaze(){

	const route = routes.pop();// 最後尾から取得(深度優先)
	const sR    = route.r;
	const sC    = route.c;
	const stp   = route.stp;

	// ゴール判定
	if(sR == goal.r && sC == goal.c) return;
	
	// 上下左右の探索方向
	let dirs = [
		{r:-1, c:0}, {r:1, c:0},
		{r:0, c:-1}, {r:0, c:1}
	];

	for(let dir of dirs){
		const oR = sR + dir.r;
		const oC = sC + dir.c;
		if(!isRoad(oR, oC)) continue; // 道でない
		if(isPassed(oR, oC)) continue;// 探索済みである
		const from = {r:oR, c:oC, stp:stp+1, fR:sR, fC:sC};
		points.push(from);// 探索済みに追加
		routes.push(from);// 探索候補に追加
	}

	if(0 < routes.length) searchMaze();// 再帰処理

	return;
}
// 省略

実際に動かしてみると、次の様に探索が進みます。(やりました!!)

深度優先探索

Depth-first search01で動作確認をする事ができます。

探索処理を改善する

先程の探索結果を見てみると、かなり遠回りしている事に気づきます。
(近道を無視してますね)

先程の深度優先探索では、近道かどうかに関わらず"兎に角先に進む"発想で探索し、ゴールが見つかった時点で探索を終了する処理になっている為、探索結果が最短距離である可能性が低いものとなってしまいます。

この点は、次の処理の追加で改善する事が可能です。

1. 分岐点に来たら
2. 上下左右の通路それぞれと、ゴールとの距離を計算する
3. ゴールとの距離が小さい方(近い方)を優先して探索を続ける

分岐点で、"ゴールの方向を優先して探索をする"発想です。

改善した"searchMaze()"関数を確認してみましょう。

main.js

// 省略
function searchMaze(){

	const route = routes.pop();// 最後尾から取得(深度優先)
	const sR    = route.r;
	const sC    = route.c;
	const stp   = route.stp;

	// ゴール判定
	if(sR == goal.r && sC == goal.c) return;
	
	// 上下左右の探索方向
	let dirs = [
		{r:-1, c:0, dist:99}, {r:1, c:0, dist:99},
		{r:0, c:-1, dist:99}, {r:0, c:1, dist:99}
	];

	// マンハッタン距離でゴール方向を優先
	for(let i=0; i<dirs.length; i++){
		const dR = goal.r - (sR+dirs[i].r);
		const dC = goal.c - (sC+dirs[i].c);
		dirs[i].dist = abs(dR + dC);
	}
	dirs = dirs.sort((a, b)=>b.dist - a.dist);

	for(let dir of dirs){
		const oR = sR + dir.r;
		const oC = sC + dir.c;
		if(!isRoad(oR, oC)) continue; // 道でない
		if(isPassed(oR, oC)) continue;// 探索済みである
		const from = {r:oR, c:oC, stp:stp+1, fR:sR, fC:sC};
		points.push(from);// 探索済みに追加
		routes.push(from);// 探索候補に追加
	}

	if(0 < routes.length) searchMaze();// 再帰処理

	return;
}
// 省略

"dirs"配列には上下左右の方向を格納してありますが、
各通路の探索時、次に探索する通路とゴールとの差"dist"を計算し、
それを基準に配列をソートをかけます。
(ゴールに近い順に整列しているだけですね)

main.js

// 上下左右の探索方向
let dirs = [
    {r:-1, c:0, dist:99}, {r:1, c:0, dist:99},
    {r:0, c:-1, dist:99}, {r:0, c:1, dist:99}
];

// マンハッタン距離でゴール方向を優先
for(let i=0; i<dirs.length; i++){
    const dR = goal.r - (sR+dirs[i].r);
    const dC = goal.c - (sC+dirs[i].c);
    dirs[i].dist = abs(dR + dC);
}
dirs = dirs.sort((a, b)=>b.dist - a.dist);

動作させると次の様に探索が進みます。(近道を選んでますね!!)

深度優先探索(改善後)

Depth-first search02で動作確認をする事ができます。

幅優先探索

次に紹介するのは、"幅優先探索"です。
このアルゴリズムの特徴を簡単にまとめると次の通りです。

1. 分岐点にまで進む
2. 分岐点では上下左右それぞれの通路を優先して探索を続行する
3. ゴールに辿り着いていたら終了

幅優先探索では、深度優先探索と違い、
"兎に角先に進む"のではなく、"分岐点で一度立ち止まり、
分岐先を優先して探索する"というイメージです。

具体的な実装例(幅優先)

完成コードは次のとおりです。(クリックでコード全体を見ることができます)

幅優先探索(全体のコード)

具体的な処理は、"searchMaze()"関数を確認してみましょう。

routes配列からは、shift()を使って最後尾から通路を取り出す事がポイントです。
取り出した通路がゴールと一致するまで再帰処理で繰り返します。

main.js

// 省略
function searchMaze(){

	//const route = routes.pop();// 最後尾から取得(深度優先)
	const route = routes.shift();// 先頭から取得(幅優先)
	const sR    = route.r;
	const sC    = route.c;
	const stp   = route.stp;

    // 中略
}
// 省略

動作させると次の様に探索が進みます。(横に広がりながら進んでますね!!)

幅優先探索

Breadth-first searchで動作確認をする事ができます。

A*アルゴリズム

最後に紹介するのはA*(エースター)アルゴリズムです。
簡単な手順は次の通りです。

1. 探索候補を優先度付きキューに格納する
2. 優先度順に探索を進めていく
3. ゴールに辿り着いていたら終了

より"少ないステップ"で"ゴールに近い"通路を優先して探索するイメージです。
3つのアルゴリズムの中では最も優秀なアルゴリズムと言えるでしょう。

具体的な実装例(A*アルゴリズム)

完成コードは次のとおりです。(クリックでコード全体を見ることができます)

A*アルゴリズム(全体のコード)

A*アルゴリズムでは、対象の通路とゴールまでの距離とスタート位置からのステップ数との合計値を優先度とします。

変数名	役割
stp	探索対象の通路までかかったステップ数
hue	探索対象の通路とゴールの位置までの距離

これらの合計値が少ない方を優先して探索を進める訳です。

"searchMaze()"関数を確認してみましょう。

main.js

// 省略
function searchMaze(){

	const route = routes.dequeue().node;// 探索候補から取り出す

	const sR    = route.r;
	const sC    = route.c;
	const stp   = route.stp;

	// ゴール判定
	if(sR == goal.r && sC == goal.c) return;
	
	let dirs = [
		{r:-1, c:0}, {r:1, c:0},
		{r:0, c:-1}, {r:0, c:1}
	];
	for(let dir of dirs){
		const oR = sR + dir.r;
		const oC = sC + dir.c;
		if(!isRoad(oR, oC)) continue; // 道でない
		if(isPassed(oR, oC)) continue;// 探索済みである
		const dR   = goal.r - (sR+dir.r);
		const dC   = goal.c - (sC+dir.c);
		const hue  = abs(dR + dC);// マンハッタン距離
		const from = {r:oR, c:oC, stp:stp+1, fR:sR, fC:sC, hue:hue};
		points.push(from);// 探索済みに追加
		routes.enqueue(from, stp+1 + hue);// 探索候補に追加
	}

	if(0 < routes.size()) searchMaze();// 再帰処理

	return;
}
// 省略

動作させると次の様に探索が進みます。(やりました!!)

A*アルゴリズム

A*Algorithmで動作確認をする事ができます。

最後に

今回は経路探索アルゴリズムを3種類紹介しました。
与えられる迷路によってもその処理回数が変わってくるので遊びながら試してみてくださいね。

冒頭でもお話した通り、迷路アルゴリズム3種であっさりダンジョンにも記事があるのでよろしければ!!

今回は以上です。
ここまで読んでいただき有難うございました。(ง๑•̀ω•́)ง✧