こんにちは。新人のYoです。
前回は初めてのマイクロマウス地区大会出場でした。
今回は「拡張左手法」の実装について書いていこうと思います。
「拡張左手法」実装手順
プログラミングが苦手な人間が一朝一夕で実装できるものではないため、
何度か段階を踏みながら実装していきます。
① 拡張左手法の動作順序を考え、条件を書き出す
↓
② 拡張左手法のアルゴリズムをフローチャートに書き起こす
↓
③ フローチャートをプログラムに書き換えて実装する
↓
④ 修正点を踏まえて再度フローチャートを書き出し、実装する
① 拡張左手法の動作順序を考え、条件を書き出す
拡張左手法については前々回のブログで説明しているので今回はある程度割愛しますが、
この段階では拡張左手法を実装する上で必要になるであろう条件を以下のように定義しました。
一部私の独自解釈が入っているので、本来の理論とは異なっていると思われます。
- 基本的には左手法で進む
- 袋小路区画に突入した場合、未探索の区画がある分岐点まで左手法で進み続ける
- 袋小路区画でないかつ次の区画が探索済かつ左右に壁がある場合、
前方区画に仮想壁を建てて未探索の区画分岐点まで左手法で進み続ける - 複数の進入可能区画が存在し左手法で進入する区画が探索済かつ
左手法では本来進入しない区画が未探索の場合、本来進む予定だった区画に仮想壁を建てる
2 と 3 のような分岐点まで引き返す動作のことを「バックトラック」と呼ぶそうです。
これら4つの条件だけだと終了条件がないので、終了条件は「スタート区画への帰還」とします。
他にも、ゴール到達までに必要なので「マップデータ保存」は使用します。
② 拡張左手法のアルゴリズムをフローチャートに書き起こす
拡張左手法のアルゴリズムをプログラミングをしやすくするために理解度の確認も兼ねて
フローチャートとして書き起こします。左手法なら次のようなフローチャートになります。
①のフローチャート全てを書き起こしたところ、量が多くなりすぎたため画像は割愛します。
完成したフローチャートを確認しながら迷路探索のルートを確認したところ迷路によっては
ゴールまで探索できていなかったようだったので、先述 3 の条件を「袋小路区画でないかつ
次の区画が探索済かつ3方向の区画の壁が1箇所だけ抜けている場合、そこへ仮想壁を建てて
未探索の区画分岐点まで左手法で進み続ける」へと少しだけ改変します。
③フローチャートをプログラムに書き換えて実装する
②で書き起こしたフローチャートの内容をプログラムに書き換えていきます。
フローチャートの量から分かっていたことではありますが、プログラムの方も
途轍もない長さになってしまいました。
読みづらい上にif文処理が多い長文プログラムになってしまったため改良が必要そうです。
④ 修正点を踏まえて再度フローチャートを書き出し、実装する
③までのルールを少し変更しつつ、仮想壁を建てるパターンのみを考えるのが
最良だと感じたため最終的に辿り着いたフローチャートは次のようになりました。
探索中に判断されるのは全15パターンで、仮想壁を建てる条件は4パターンになりました。
分かりやすく図で説明すると、仮想壁を建てる4パターンは次のようになります。
左区画探索済かつ前方区画未探索のパターン
左区画探索済かつ前方区画に壁アリかつ右区画未探索のパターン
左区画に壁アリかつ前方区画探索済かつ右区画未探索のパターン
左区画探索済かつ前方区画探索済かつ右画区画未探索のパターン
ここまでで察していますが、なんか拡張左手法のアルゴリズムと違うような気がします。
プログラムの方もif文の部分は15パターン書けば実装できます。
void add_virtualwall(unsigned char * now_pos){
if(g_sen_l.is_wall == false){ //左壁ナシ
// 左側が未探索かどうか
if(check_one_dir_unknown_section(left) == true){ //左未探索
setLED(1);
return;
}
else{ //左探索済
if(g_sen_fr.is_wall == false){ //前壁ナシ
if(check_one_dir_unknown_section(front) == true){ //前未探索
g_map_control.setVWallData(now_pos[0],now_pos[1],local_to_glob_dir(left));
//左に仮想壁を建てる
setLED(2);
return;
}
else{ //前探索済
if(g_sen_r.is_wall == false){ //右壁ナシ
if(check_one_dir_unknown_section(right) == true){ //右未探索
g_map_control.setVWallData(now_pos[0],now_pos[1],local_to_glob_dir(left));
g_map_control.setVWallData(now_pos[0],now_pos[1],local_to_glob_dir(front));
//左と前に壁を建てる
setLED(3);
return;
}
else{ //右探索済
setLED(4);
return;
}
}
else{ //右壁アリ
setLED(5);
return;
}
}
}
else{ //前壁アリ
if(g_sen_r.is_wall == false){ //右壁ナシ
if(check_one_dir_unknown_section(right) == true){ //右未探索
g_map_control.setVWallData(now_pos[0],now_pos[1],local_to_glob_dir(left));
//左に壁を建てる
setLED(6);
return;
}
else{ //右探索済
setLED(7);
return;
}
}
else{ //右壁アリ
setLED(8);
return;
}
}
}
}
else{ //左壁アリ
if(g_sen_fr.is_wall == false){ //前壁ナシ
if(check_one_dir_unknown_section(front) == true){ //前未探索
setLED(9);
return;
}
else{ //前探索済
if(g_sen_r.is_wall == false){ //右壁ナシ
if(check_one_dir_unknown_section(right) == true){ //右未探索
g_map_control.setVWallData(now_pos[0],now_pos[1],local_to_glob_dir(front));
//前に壁を建てる
setLED(10);
return;
}
else{ //右探索済
setLED(11);
return;
}
}
else{ //右壁アリ
setLED(12);
return;
}
}
}
else{ //前壁アリ
if(g_sen_r.is_wall == false){ //右壁ナシ
if(check_one_dir_unknown_section(right) == true){ //右未探索
setLED(13);
return;
}
else{ //右探索済
setLED(14);
return;
}
}
else{ //右壁アリ
setLED(15);
return;
}
}
}
}
少し長いですがこれで15パターン書けました。setLEDはデバック用に入れてあります。
探索アルゴリズム以外の条件追加
迷路を走らせてみたところ、実装したアルゴリズムにいくつかの欠点が見つかったので
それらを解決するための条件をいくつか考えていきます。
- 迷路によってはゴール到達前にスタート区画へ戻ってきてしまう
（ゴール到達前はスタート区画に戻ってきてはならない）
→ スタート直後からゴールするまで、スタート区画に仮想壁を建てて戻れないようにする - ゴール区画が前方または右にあっても左手法を遵守していると通り過ぎてしまう
→ 割り込みでゴール区画に突入させる、この場合も上記のスタート区画仮想壁を抜く
といった具合に先述のアルゴリズムとは別に条件を2つ追加しました。
結果
結果として、最終的に拡張左手法とは異なる探索アルゴリズムが誕生しました。
異なる点としては、拡張左手法の「同じ区画は行きと帰りの二度しか通らない」と
「探索済区画に到達したら分岐点までバックトラックするように進行する」という
2つのルールが完全無視されていることが挙げられます。
過去に出題された大会の迷路を使用して確認した限りでは、このオリジナルに近いアルゴリズム
でも迷路探索でゴールに到達することができ、迷路によっては拡張左手法を使用するよりも早く
ゴールに到達できてしまう場合がありました。
主に拡張左手法だと長距離バックトラックさせられる迷路であった場合、こちらの
アルゴリズムの方が早くなるようです。
次回予告
果たして今回実装した拡張左手法は地区大会で完走できるのでしょうか。