当サイトの一部ページには、アフィリエイト・アドセンス・アソシエイト・プロモーション広告を掲載しています。

Amazonのアソシエイトとして、Security Akademeiaは適格販売により収入を得ています。

広告配信等の詳細については、プライバシーポリシーページに掲載しています。

消費者庁が、2023年10月1日から施行する景品表示法の規制対象(通称:ステマ規制)にならないよう、配慮して記事を作成しています。もし問題の表現がありましたら、問い合わせページよりご連絡ください。

参考:令和5年10月1日からステルスマーケティングは景品表示法違反となります。 | 消費者庁

Escape Labyrinth【NandGame編】

はじめに

いつもブログをご覧いただきありがとうございます。

コーストFIRE中のIPUSIRONです😀

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

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

処理番号処理内容
前方をチェックする。
(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!"と表示されて、当該レベルをクリアしたことになります。