The Maze【Turing Complete編】

2023年9月12日

The Mazeステージ

The Mazeステージは、Programmingセクションの最終ステージです。

当ステージのゴールは、ロボットを迷路から脱出させることです。

CPUから数値を出力することで、ロボットを制御できます。どの数値でどういった制御ができるのかについては、Spacial Invasionステージで解説しました。

Spacial Invasion【Turing Complete編】

Spacial Invasionステージ 「貨物船に宇宙ネズミが住み着いている。君のコンピューターを我々の先進的 ...

 https://akademeia.info/?p=30182

これまで学習した内容を復習する形で、迷路脱出アルゴリズムを実装します。

迷路の仕様

・迷路は固定。ランダムに生成されない。

⇒（条件分岐を使わない）ごり押しのプログラムで解ける。ただし、別の迷路になると解けなくなる。

⇒テストでは8つの迷路を解くことになる。1つ目の迷路が終わると、2つ目の迷路が現れる。

⇒あらゆる迷路にも対応したプログラムを作る必要がある。

・すべての経路を探索するわけではない。

・最短の経路を見つけるわけではない。

・ロボットのスタート位置は右下。ゴールは左上のドア。

・迷路のゲームにはコインが存在するが、今ステージではコインを取る必要はない。

※すべてのコインを拾うという条件はない。

・コインの先にゴールはないので、一種の障害物を認識しても支障はない。

・Spacial Invasionステージで登場したロボットと同じなので、レーザーを撃てる。今ステージでは不要。

・ドアは空いていない。ドアに重なることはできない。レーザーをドアを破壊できない。ドアに向かってaction（物体調査）をすればOK。

・ドアの物体コード3、壁は1、コインは8である。

左手法で迷路を攻略する

迷路を脱出するための必勝法として、左手法（左手の法則）があります^[1]https://ja.wikipedia.org/wiki/%E8%BF%B7%E8%B7%AF。

左手法とは、左手伝いに進めば出口にたどり着くという手法です。

左手を迷路の壁に当てながら、道に沿ってずっと進んでいきます。途中で壁にぶつかったとしても、左手を当てながら戻っていきます。

ただし、次のような特殊な迷路については、左手法では脱出できないことがあります。

• 途中に落とし穴など進んではいけない場所がある迷路
• ゴールが迷路の中のに存在する迷路^[2]大半のマイクロマウス競技では中央にゴールのある迷路が採用されます。

左手ではなく、右手を使っても脱出できます。これを右手法といいます。

左手法の具体的な実装方針

素朴に実装するには、二方向を調べられる必要がある

左手法を素朴に実装するには、左隣（左手が触れる方向）と前方（目の方向）の状況を把握する必要があります。

今回のロボットは前方しか調べられませんので、左隣を識別するにはそちらの方向を向く必要があります。

三方向を同時に調べらられれば、より効率的な動きができる

ロボットマウスのように前・左・右の方向にセンサーを取り付けられれば、一度に三方向を調べられます。つまり、次のように4パターンに分類でき、素早くアクションを取れます。

※Uターンができる分、効率的です。

※前進した直後は、後ろに壁がありません。そうでなければその場所に移動不可能だからです。

Ftech 教育教材ロボット 迷路解析の基本１～左手法～

Ftech 教育教材ロボット 迷路解析の基本１～左手法～ 技 術 創 造 企 業　fertile technology 電話: 02 ...

 https://www.ftech-net.co.jp/robot/howto/micromouse02.html

センサーで壁の有無を判断し、迷路内を自律走行!!：マイクロマウスで始める組み込み開

市販の組み立てキットで「マイクロマウス」の開発を進めている北上くんとえみちゃん。これまで開発して ...

 https://monoist.itmedia.co.jp/mn/articles/1306/03/news001_3....

The Mazeステージを解く

1：ロボットの動作に対応する数値を定数化する

プログラムの冒頭で、ロボットの動作に対応する数値を定数化しておきます。

const LEFT 0
const FORWARD 1
const RIGHT 2
const ENJOY 3
const ACTION 4
const SHOOT 5

2：ゼロであるとき、ゼロでないときにジャンプする命令を定義する

ゼロであるときにジャンプする命令を"JZE"、ゼロでないときにジャンプする命令を"JNZ"という名前で定義します。

※今回のプログラムではJZEを使いますが、JNZを使いません。

3：プログラムの実装内容を検討する

左手法を実装するのに、ヒントが役立ちます。

この方法であれば左と前方を同時にチェックできなくても、左手法を再現できています。

上記の障害物の判定処理で留意することがあります。

障害物の有無だけをチェックすると、せっかくゴールのドア手前に来ても、ドアを障害物と認識してしまいます。そこで、単純にゼロかどうかではなく、壁（物体コード1）かどうかの条件が必要になります^[3]ドア（物体コード3）かどうかの条件を組み込むアプローチでもうまくいきますが、壁の有無をチェックするのが自然です。。

「前方の物体コード」から1（壁の物体コード）を引いて、それが0かどうかを判定条件にします。

そのために、1を引く命令を定義します。命令名は"sub"としました。

4：プログラムを実装する

次のプログラムが完成しました。

const LEFT 0
const FORWARD 1
const RIGHT 2
const ENJOY 3
const ACTION 4
const SHOOT 5

const OBJ_WALL 1 # 壁の物体コード

label main_loop
####################################
# 前方チェック.                     #
# 前方に壁があればジャンプ.           #
####################################
ACTION
execute
IN # REG0←前方の物体コード.
reg0_to_reg1
OBJ_WALL # REG0←1（壁の物体コード）.
reg0_to_reg2
sub # 計算結果はREG3へ.
wall_case # ジャンプ先を設定.
JZE # REG3に対して条件チェック.
#### 前方チェックここまで.

# 壁がないので、前進して左を向く.
FORWARD
execute
LEFT
execute
main_loop
JMP

# 壁ありなら右を向く.
label wall_case
RIGHT
execute
main_loop
JMP

5：テストする

最初の目標は1つ目の迷路を脱出することです。

※コインを拾いながら進みます。

2つ目の迷路をうまく脱出できたら、あとは放置しておきましょう。8つの迷路を脱出するまでにある程度の時間が掛かります。

※待つのが嫌な場合は、[Run faster]ボタンを左クリックしてください。指定の周波数で動作するので、高速・低速を自由に調整できます。デフォルトでは高速に動作します。右クリックすれば、周波数を変更できます。

すべての迷路を脱出することでクリアとなります。