Escape Labyrinth【NandGame編】
はじめに
いつもブログをご覧いただきありがとうございます。
FIRE生活中のIPUSIRONです😀
Escape Labyrinthレベル
Escape Labyrinthレベルのゴールは、火星の迷宮に迷い込んでしまったコンピューターを脱出させるプログラムを書くことです。
コンピューターには車輪と前方障害検知器が備わっています。コンピューターを脳として搭載した、一種のロボットあるいはローバーのようなものと想像してよいでしょう。この両者の外部デバイスは、アドレス0x7FFFにメモリーマッピングされています。
2～4ビット目は外部デバイスへの出力用であり、車輪を動かします。
| ビット目（右側から0スタート） | 1をセットすることによる挙動 |
|---|---|
| 2 | 前進（1ステップ） |
| 3 | （90度分を）左旋回 |
| 4 | （90度分を）右旋回 |
ビットが0から1に変化した時点で移動・旋回を開始しますが、完了までに時間がかかります。移動・旋回が終わったかどうかは、前方障害検知器によってわかります。
8～10ビット目は外部デバイスからの入力用であり、前方障害検知器による検知具合によってビットが切り替わります。
| ビット目（右側から0スタート） | 1にセットされるときの状態 |
|---|---|
| 8 | 前方に障害物あり |
| 9 | 旋回中 |
| 10 | 前進中 |
Escape Labyrinthレベルを解く
いきなり難易度が上がったような気がしますが、落ち着いてプログラムを設計していきましょう。「困難は分割せよ」というように、いきなり全体を解決しようとするのではなく、個別に処理していき、それらを積み上げていくのです。
1：迷宮を解く方法を検討する
迷宮のマップは与えられていません。その状況下で脱出するということは、迷路脱出アルゴリズムを利用することになります。
ここでは左手法（あるいは右手法）という迷路脱出アルゴリズムを採用します。Turing CompleteのThe Mazeステージでも左手法を扱いましたので、参考にしてください。
https://akademeia.info/?p=30359前方障害検出器の仕様上、左と前方を同時にチェックできません。そこで、次のようにして、左手法を再現します。
| 処理番号 | 処理内容 |
|---|---|
| ① | 前方をチェックする。 (a) 障害物なら、右を向く。①に戻る。 (b) 障害物でなければ、前進して、左を向く。①に戻る。 |
2：移動・旋回には時間がかかることを考慮する
次に考えるべきポイントは、移動・旋回が完了するまで余計な処理をしてはいけないことです。よって、常に移動・旋回中か否かを監視し、そうでないときだけ次のステップに進めるようにします。
9と10ビット目が0になっていれば問題なしとなります。そのためには、「現在のアドレス0x7FFFの16ビットデータ」と「0x0000 0110 0000 0000b（＝0x0600）」をAND演算をして、結果が0x0000であれば9と10ビットの両方ともが0と判断できます。
3：アセンブリー言語で実装する
以上を踏まえてアセンブリー言語で実装すると次のようになります。
# Assembler code
MAIN:
# 移動・旋回中なら待機.
A = 0x7fff
D = *A
A = 0x0600
D = D & A
A = MAIN
D ; JNE
# 前方をチェックする.
A = 0x7fff
D = *A
A = 0x0100
D = D & A
A = NO_OBSTRUCTION_AHEAD
D ; JEQ
OBSTRUCTION_AHEAD:
# 前方に障害物があるので右を向く.
A = 0x7fff
D = *A
A = 0x0010
D = D | A
A = 0x7fff
*A = D
A = MAIN
JMP
NO_OBSTRUCTION_AHEAD:
# 前方に障害物がないので前進して左を向く.
A = 0x7fff
D = *A
A = 0x0004
D = D | A
A = 0x7fff
*A = D
## 前進に移動中は待機.
STANDBY_FOR_MOVING:
A = 0x7fff
D = *A
A = 0x0600
D = D & A
A = STANDBY_FOR_MOVING
D ; JNE
## 待機を終えたら左を向く.
A = 0x7fff
D = *A
A = 0x0008
D = D | A
A = 0x7fff
*A = D
A = MAIN
JMP
4：テストする
[Tick]ボタンで手動のステップ実行、[Run]ボタンで自動のステップ実行できます。
プログラム内でハイライトされた行が移動しつつ、computer内部の状態が変化していきます。その右側にはコンピューターの挙動が逐一表示されていきます。
ここに次々に"Turn"と"Moved"が続いていれば、問題なく動作していると推測できます。
もし、"tried to move forward, but could not move because of obstacle."というメッセージが表示されていれば、障害物があったのに前進しようとしており、プログラムのどこかにミスがあります。
十数行表示させて問題なさそうなら、[Stop]ボタンで止めます。
[Reset state]ボタンで初期状態に戻してから、[Check solution]ボタンを押します。
プログラムに問題がなければ、"Level successfully completed!"と表示されて、当該レベルをクリアしたことになります。
