Escape Labyrinth【NandGame編】

2023年11月6日

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ステージでも左手法を扱いましたので、参考にしてください。

前方障害検出器の仕様上、左と前方を同時にチェックできません。そこで、次のようにして、左手法を再現します。

処理番号	処理内容
①	前方をチェックする。 (a) 障害物なら、右を向く。①に戻る。 (b) 障害物でなければ、前進して、左を向く。①に戻る。

2：移動・旋回には時間がかかることを考慮する

次に考えるべきポイントは、移動・旋回が完了するまで余計な処理をしてはいけないことです。よって、常に移動・旋回中か否かを監視し、そうでないときだけ次のステップに進めるようにします。

9と10ビット目が0になっていれば問題なしとなります。そのためには、「現在のアドレス0x7FFFの16ビットデータ」と「0x0000 0110 0000 0000b（＝0x0600）」をAND演算をして、結果が0x0000であれば9と10ビットの両方ともが0と判断できます。

3：アセンブリー言語で実装する

以上を踏まえてアセンブリー言語で実装すると次のようになります。

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!"と表示されて、当該レベルをクリアしたことになります。