BASIC (ベーシック) であそぼう 5
〜 プログラムで迷路を解く 〜
ScreenToGif を使っています。
2022-09-09 作成 福島
TOP > asob > decbasic-mazesolve
[ TIPS | TOYS | OTAKU | LINK | MOVIE | CGI | AvTitle | ConfuTerm | HIST | AnSt | Asob ]

自分で歩かせる

前章 BASIC であそぼう 4 のプログラムを変更して迷路の中を自動的に移動します。
「プログラミング的思考」の課題と似ています。

迷路を解くには様々なアルゴリズムがありますが、ここでは「場当たり式」と簡素かつ古典的な「右手法」(みぎてほう) で解いてみます。
「右手法」とは、右手で迷路の壁を離さないように前進する方法です。
同様に、「左手法」(ひだりてほう) もあり、こちらは左手で迷路の壁を離さないように前進する方法で、考え方は右手法と同じです。

「アルゴリズム」とは、考え方を「形」にしたものを指します。
その「形」と同じことを実施すれば、誰でも同じことが出来るものです。
「文書」「歯車」「方程式」「プログラム」「電子回路」等、様々な形式があります。
学校で習う科目にはありません。よく「算法」と訳されますが、多くの人はピンとこない事でしょう。

右手法を使うには一つ条件があります。それは、
· 壁が途切れていないこと。(独立した通路がないこと)
ということです。
どこか一か所でも独立した通路が存在すると、たどり着けない場所が出来てしまい、そこにゴールがあると迷路を解くことができません。

本稿では、右手法で作成したプログラムを改良し、右手法だけでは解けない迷路も解いてみます。

0. 事前準備

0-1. この章では、十進 BASIC を使います。
インストールがまだなら、ここ (ラズパイ400) か ここ (CentOS) の gtk2 版か、
ここ (Windows10) を参考にしてインストールしておいてください。
0-2. この章では、別のテキストエディタを使いません。
十進 BASIC には専用のエディタ画面があるので、これを使います。
0-3. 未経験者向けの情報を省いています。
プログラミング未経験の方は、予めこちら (BASIC であそぼう 1) を、
アニメーションの仕組みをまだ考えたことがない方は、こちら (BASIC であそぼう 2) を
学習しておくことを推奨します。

1. 前回 BASIC であそぼう 4 - 第 4 項 のおさらい

1-1. コントロールをクリアできるプログラム
<テキスト10> では以下の様に記述していました。
これを変更していきます。

<テキスト10> ファイル名「program.BAS」
SET WINDOW 0,39,19,0

DIM heya$(7)
LET heya$(1) = "+---------------+"
LET heya$(2) = "|     #       # |"
LET heya$(3) = "| ### # # ### # |"
LET heya$(4) = "| # #   #   # # |"
LET heya$(5) = "| # ####### # # |"
LET heya$(6) = "|     #     #   |"
LET heya$(7) = "+---------------+"

!      X, Y, Mark   コントロールの場所と記号
DATA  2, 5,"a"
DATA 10, 6,"b"
DATA 16, 2,"c"
DIM Controls$(3,3)
MAT READ Controls$

! コントロールを迷路に埋め込む
FOR Mokuhyo = 1 TO 3
   LET mx = VAL(Controls$(Mokuhyo, 1))
   LET my = VAL(Controls$(Mokuhyo, 2))
   LET mm$ = Controls$(Mokuhyo, 3)
   LET heya$(my)(mx:mx) = mm$
NEXT Mokuhyo

! 自分の横位置、縦位置
LET x = 2
LET y = 2

DECLARE EXTERNAL SUB HeyaDisplay
CALL HeyaDisplay(heya$, x, y)

DECLARE EXTERNAL SUB BogusTick
LET BogusTick_before = -1

DECLARE EXTERNAL SUB Search

LET Mokuhyo = 1
LET mx = VAL(Controls$(Mokuhyo, 1))
LET my = VAL(Controls$(Mokuhyo, 2))
LET mm$ = Controls$(Mokuhyo, 3)

DO
   CALL BogusTick(BogusTick_before, 10)

   IF GetKeyState(27) < 0 THEN EXIT DO

   DIM idou(4)
   CALL Search(idou, heya$, x, y)
   LET dx = 0
   LET dy = 0
   IF GetKeyState(39) < 0 THEN LET dx = idou(1)
   IF GetKeyState(37) < 0 THEN LET dx = idou(2)
   IF GetKeyState(40) < 0 THEN LET dy = idou(3)
   IF GetKeyState(38) < 0 THEN LET dy = idou(4)
   LET x = x + dx
   LET y = y + dy

   CALL HeyaDisplay(heya$, x, y)

   IF x = mx AND y = my THEN
      IF mm$ = "c" THEN EXIT DO

      LET heya$(my)(mx:mx) = " "

      LET Mokuhyo = Mokuhyo + 1
      LET mx = VAL(Controls$(Mokuhyo, 1))
      LET my = VAL(Controls$(Mokuhyo, 2))
      LET mm$ = Controls$(Mokuhyo, 3)
   END IF
LOOP

END



! 部屋を表示する副プログラム
EXTERNAL SUB HeyaDisplay(heya$(), x, y)
SET DRAW MODE Hidden
CLEAR
SET COLOR 1
FOR tate = 1 TO 7
   LET gyou$ = heya$(tate)
   FOR yoko = 1 TO 17
      LET kabe$ = mid$(gyou$, yoko, 1)
      PLOT TEXT ,AT yoko,tate:kabe$
   NEXT yoko
NEXT tate

SET COLOR 1
PLOT TEXT ,AT x,y:"A"
SET DRAW MODE Explicit
END SUB



! BogusTick version 1.0 written by fuku@rouge.gr.jp
EXTERNAL SUB BogusTick(before, fps)
IF before >= 0 AND fps > 0 THEN
   LET current = TIME
   IF before > current THEN LET before = before - 24 * 3600
   LET this_wait = 1 / fps - (current - before)
   IF this_wait > 0 THEN WAIT DELAY this_wait
END IF
LET before = TIME
END SUB



! 周囲を調査する副プログラム
EXTERNAL SUB Search(idou(),heya$(),cx,cy)

LET ikeru$ = " abc"

MAT idou = ZER
IF POS(ikeru$, mid$(heya$(cy + 0), cx + 1,1)) > 0 THEN LET idou(1) = +1
IF POS(ikeru$, mid$(heya$(cy + 0), cx - 1,1)) > 0 THEN LET idou(2) = -1
IF POS(ikeru$, mid$(heya$(cy + 1), cx + 0,1)) > 0 THEN LET idou(3) = +1
IF POS(ikeru$, mid$(heya$(cy - 1), cx + 0,1)) > 0 THEN LET idou(4) = -1

END SUB

2. 場当たり式の進行

2-1. 気まぐれに進むプログラムの作成。
深く考えずにとりあえず通路を直進し、曲がり角を見つけたらその場で適当に行き先を決める
という方法で迷路を解いてみます。
「乱数」を使って運任せに方向を変えているので、アルゴリズムとも呼べないほどの解決方法です。
(乱数は、十進 BASIC にあらかじめ用意されている機能「RND」を使います)

また、前項までは自分の位置を「A」として表示していましたが、これに向きを加えて表示するようにします。

曲がり角ではなく、交差点で行き先を決めたほうが効率が良いのですが、
ここではプログラムの簡便さを優先しました。
このプログラムを理解できた人は、交差点で行き先を決めるプログラムに改造してみてください。

<テキスト11> ファイル名「program.BAS」
SET WINDOW 0,39,19,0

DIM heya$(7)
LET heya$(1) = "+---------------+"
LET heya$(2) = "|     #       # |"
LET heya$(3) = "| ### # # ### # |"
LET heya$(4) = "| # #   #   # # |"
LET heya$(5) = "| # ####### # # |"
LET heya$(6) = "|     #     #   |"
LET heya$(7) = "+---------------+"

!      X, Y, Mark   コントロールの場所と記号
DATA  2, 5,"a"
DATA 10, 6,"b"
DATA 16, 2,"c"
DIM Controls$(3,3)
MAT READ Controls$

! コントロールを迷路に埋め込む
FOR Mokuhyo = 1 TO 3
   LET mx = VAL(Controls$(Mokuhyo, 1))
   LET my = VAL(Controls$(Mokuhyo, 2))
   LET mm$ = Controls$(Mokuhyo, 3)
   LET heya$(my)(mx:mx) = mm$
NEXT Mokuhyo

! 自分の横位置、縦位置、方向
LET x = 2
LET y = 2
LET dir = 0  ! 方向 0:↑ / 1:→ / 2:↓ / 3:←
LET myChr$ = "A>V<"

DECLARE EXTERNAL SUB HeyaDisplay
CALL HeyaDisplay(heya$, x, y, MID$(myChr$, 1 + dir, 1))

DECLARE EXTERNAL SUB BogusTick
LET BogusTick_before = -1

DECLARE EXTERNAL SUB Search
DECLARE EXTERNAL SUB GetFPV
DECLARE EXTERNAL SUB HeadTurn

LET Mokuhyo = 1
LET mx = VAL(Controls$(Mokuhyo, 1))
LET my = VAL(Controls$(Mokuhyo, 2))
LET mm$ = Controls$(Mokuhyo, 3)

DO
   CALL BogusTick(BogusTick_before, 10)

   IF GetKeyState(27) < 0 THEN EXIT DO

   DIM idou(4)
   CALL Search(idou, heya$, x, y)
   DIM fpv(4)
   CALL GetFPV(fpv, dir, idou)
   CALL HeadTurn(dir, fpv)
   LET dx = 0
   LET dy = 0
   IF dir = 1 THEN LET dx = idou(1)
   IF dir = 3 THEN LET dx = idou(2)
   IF dir = 2 THEN LET dy = idou(3)
   IF dir = 0 THEN LET dy = idou(4)
   LET x = x + dx
   LET y = y + dy

   CALL HeyaDisplay(heya$, x, y, MID$(myChr$, 1 + dir, 1))

   IF x = mx AND y = my THEN
      IF mm$ = "c" THEN EXIT DO

      LET heya$(my)(mx:mx) = " "

      LET Mokuhyo = Mokuhyo + 1
      LET mx = VAL(Controls$(Mokuhyo, 1))
      LET my = VAL(Controls$(Mokuhyo, 2))
      LET mm$ = Controls$(Mokuhyo, 3)
   END IF
LOOP

END



! 部屋を表示する副プログラム
EXTERNAL SUB HeyaDisplay(heya$(), x, y, cc$)
SET DRAW MODE Hidden
CLEAR
SET COLOR 1
FOR tate = 1 TO 7
   LET gyou$ = heya$(tate)
   FOR yoko = 1 TO 17
      LET kabe$ = mid$(gyou$, yoko, 1)
      PLOT TEXT ,AT yoko,tate:kabe$
   NEXT yoko
NEXT tate

SET COLOR 1
PLOT TEXT ,AT x,y:cc$
SET DRAW MODE Explicit
END SUB



! BogusTick version 1.0 written by fuku@rouge.gr.jp
EXTERNAL SUB BogusTick(before, fps)
IF before >= 0 AND fps > 0 THEN
   LET current = TIME
   IF before > current THEN LET before = before - 24 * 3600
   LET this_wait = 1 / fps - (current - before)
   IF this_wait > 0 THEN WAIT DELAY this_wait
END IF
LET before = TIME
END SUB



! 周囲を調査する副プログラム
EXTERNAL SUB Search(idou(),heya$(),cx,cy)

LET ikeru$ = " abc"

MAT idou = ZER
IF POS(ikeru$, mid$(heya$(cy + 0), cx + 1,1)) > 0 THEN LET idou(1) = +1
IF POS(ikeru$, mid$(heya$(cy + 0), cx - 1,1)) > 0 THEN LET idou(2) = -1
IF POS(ikeru$, mid$(heya$(cy + 1), cx + 0,1)) > 0 THEN LET idou(3) = +1
IF POS(ikeru$, mid$(heya$(cy - 1), cx + 0,1)) > 0 THEN LET idou(4) = -1

END SUB



! 移動の可否を一人称視点の前後左右に変換する副プログラム
EXTERNAL SUB GetFPV(fpv(), dir, idou())

DATA 4,1,2,3
DATA 1,3,4,2
DATA 3,2,1,4
DATA 2,4,3,1
DIM henkan(4,4)
MAT READ henkan

LET fpv(1) = idou(henkan(1 + dir, 1))
LET fpv(2) = idou(henkan(1 + dir, 2))
LET fpv(3) = idou(henkan(1 + dir, 3))
LET fpv(4) = idou(henkan(1 + dir, 4))

END SUB



! 自動で歩かせる副プログラム
EXTERNAL SUB HeadTurn(dir, fpv())

LET mae    = fpv(1)
LET migi   = fpv(2)
LET hidari = fpv(3)
LET ushiro = fpv(4)

IF     migi   <> 0 AND INT(RND * 2) = 0 THEN
   LET dir = MOD(dir + 1, 4)
ELSEIF hidari <> 0 AND INT(RND * 2) = 0 THEN
   LET dir = MOD(dir + 3, 4)
ELSEIF mae = 0 THEN
   LET dir = MOD(dir + 2, 4)
END IF

END SUB
2-2. 気まぐれに進むプログラムの実行
ゴールするまで 2 分以上かかります。
2-3. 気まぐれに進むプログラムの説明
<テキスト11> ファイル名「program.BAS」
SET WINDOW 0,39,19,0

DIM heya$(7)
LET heya$(1) = "+---------------+"
LET heya$(2) = "|     #       # |"
LET heya$(3) = "| ### # # ### # |"
LET heya$(4) = "| # #   #   # # |"
LET heya$(5) = "| # ####### # # |"
LET heya$(6) = "|     #     #   |"
LET heya$(7) = "+---------------+"

!      X, Y, Mark   コントロールの場所と記号
DATA  2, 5,"a"
DATA 10, 6,"b"
DATA 16, 2,"c"
DIM Controls$(3,3)
MAT READ Controls$

! コントロールを迷路に埋め込む
FOR Mokuhyo = 1 TO 3
   LET mx = VAL(Controls$(Mokuhyo, 1))
   LET my = VAL(Controls$(Mokuhyo, 2))
   LET mm$ = Controls$(Mokuhyo, 3)
   LET heya$(my)(mx:mx) = mm$
NEXT Mokuhyo

! 自分の横位置、縦位置、方向
LET x = 2
LET y = 2

! 自分が向いている方向を決めておく。前後左右、どの方向でも構わない。
! 数字が増えるにしたがって時計回りに割り振るものとし、上向きを 0 としている。
LET dir = 0  ! 方向 0:↑ / 1:→ / 2:↓ / 3:←

! 自分の向きを表示するための記号。
myChr$ = "A>V<"

DECLARE EXTERNAL SUB HeyaDisplay
CALL HeyaDisplay(heya$, x, y, MID$(myChr$, 1 + dir, 1))  ! 自分の向きも指定する。

DECLARE EXTERNAL SUB BogusTick
LET BogusTick_before = -1

DECLARE EXTERNAL SUB Search
DECLARE EXTERNAL SUB GetFPV          ! 副プログラムの使用予告
DECLARE EXTERNAL SUB HeadTurn   ! 外部関数の使用予告

LET Mokuhyo = 1
LET mx = VAL(Controls$(Mokuhyo, 1))
LET my = VAL(Controls$(Mokuhyo, 2))
LET mm$ = Controls$(Mokuhyo, 3)

DO
   CALL BogusTick(BogusTick_before, 10)

   IF GetKeyState(27) < 0 THEN EXIT DO

   DIM idou(4)
   CALL Search(idou, heya$, x, y)
   DIM fpv(4)    ! 副プログラム GetFPV() の変換結果を格納する配列変数を用意。
   CALL GetFPV(fpv, dir, idou)   ! ゆか状況を自分視点の前後左右に変換する。
   CALL HeadTurn(dir, fpv)      ! 進路を変更する。
   LET dx = 0
   LET dy = 0
   IF dir = 1 THEN LET dx = idou(1)  ! 右向きなら dx に +1 (または 0) を入れる。
   IF dir = 3 THEN LET dx = idou(2)  ! 左向きなら dx に -1 (または 0) を入れる。
   IF dir = 2 THEN LET dy = idou(3)  ! 下向きなら dy に +1 (または 0) を入れる。
   IF dir = 0 THEN LET dy = idou(4)  ! 上向きなら dy に -1 (または 0) を入れる。
   LET x = x + dx
   LET y = y + dy

   CALL HeyaDisplay(heya$, x, y, MID$(myChr$, 1 + dir, 1))   ! 自分の向きも指定する。

   IF x = mx AND y = my THEN
      IF mm$ = "c" THEN EXIT DO

      LET heya$(my)(mx:mx) = " "

      LET Mokuhyo = Mokuhyo + 1
      LET mx = VAL(Controls$(Mokuhyo, 1))
      LET my = VAL(Controls$(Mokuhyo, 2))
      LET mm$ = Controls$(Mokuhyo, 3)
   END IF
LOOP

END



! 部屋を表示する副プログラム
EXTERNAL SUB HeyaDisplay(heya$(), x, y, cc$) ! 自分の記号を呼び元で指定できるように変更。
SET DRAW MODE Hidden
CLEAR
SET COLOR 1
FOR tate = 1 TO 7
   LET gyou$ = heya$(tate)
   FOR yoko = 1 TO 17
      LET kabe$ = mid$(gyou$, yoko, 1)
      PLOT TEXT ,AT yoko,tate:kabe$
   NEXT yoko
NEXT tate

SET COLOR 1
PLOT TEXT ,AT x,y:cc$    ! 呼び元から指定された自分の記号を描画する。
SET DRAW MODE Explicit
END SUB



! BogusTick version 1.0 written by fuku@rouge.gr.jp
EXTERNAL SUB BogusTick(before, fps)
IF before >= 0 AND fps > 0 THEN
   LET current = TIME
   IF before > current THEN LET before = before - 24 * 3600
   LET this_wait = 1 / fps - (current - before)
   IF this_wait > 0 THEN WAIT DELAY this_wait
END IF
LET before = TIME
END SUB



! 周囲を調査する副プログラム
EXTERNAL SUB Search(idou(),heya$(),cx,cy)

LET ikeru$ = " abc"

MAT idou = ZER
IF POS(ikeru$, mid$(heya$(cy + 0), cx + 1,1)) > 0 THEN LET idou(1) = +1
IF POS(ikeru$, mid$(heya$(cy + 0), cx - 1,1)) > 0 THEN LET idou(2) = -1
IF POS(ikeru$, mid$(heya$(cy + 1), cx + 0,1)) > 0 THEN LET idou(3) = +1
IF POS(ikeru$, mid$(heya$(cy - 1), cx + 0,1)) > 0 THEN LET idou(4) = -1

END SUB



! 移動の可否を一人称視点の前後左右に変換する副プログラム
EXTERNAL SUB GetFPV(fpv(), dir, idou())

! 部屋 → 自分視点の変換テーブル
DATA 4,1,2,3 ! 上向きの場合: 前=-y, 右=+x, 左=-x, 後ろ=+y
DATA 1,3,4,2 ! 右向きの場合: 前=+x, 右=+y, 左=-y, 後ろ=-x
DATA 3,2,1,4 ! 下向きの場合: 前=+y, 右=-x, 左=+x, 後ろ=-y
DATA 2,4,3,1 ! 左向きの場合: 前=-x, 右=-y, 左=+y, 後ろ=+x
DIM henkan(4,4)  ! 変換テーブルを使うための配列を用意。
MAT READ henkan  ! 変換テーブルを配列に読み込む。

! 自分視点に変換する。
LET fpv(1) = idou(henkan(1 + dir, 1))    ! 前方
LET fpv(2) = idou(henkan(1 + dir, 2))    ! 右側
LET fpv(3) = idou(henkan(1 + dir, 3))    ! 左側
LET fpv(4) = idou(henkan(1 + dir, 4))    ! 後方
! 「1 + dir」としているのは、配列の添え字が 1 から始まるのに対し、dir を 0 から始めているため。

END SUB



! 自動で歩かせる副プログラム
! 現在の方向と前後左右のゆか情報を受け取り、新しい方向を返す。
EXTERNAL SUB HeadTurn(dir, fpv())

! 前後左右の情報を読みやすい変数に入れる。
LET mae    = fpv(1)  ! 前方
LET migi   = fpv(2)  ! 右側
LET hidari = fpv(3)  ! 左側
LET ushiro = fpv(4)  ! 後方 (今回は使用しない)

IF     migi   <> 0 AND INT(RND * 2) = 0 THEN
! 右へ進むことができ、そちらへ行くと乱数で決めた場合。*1
   LET dir = MOD(dir + 1, 4) ! 右を向く*2
ELSEIF hidari <> 0 AND INT(RND * 2) = 0 THEN
! 左へ進むことができ、そちらへ行くと乱数で決めた場合。*1
   LET dir = MOD(dir + 3, 4) ! 左を向く*2
ELSEIF mae = 0 THEN
! 右、左、前のどこへも進むことができない場合。
   LET dir = MOD(dir + 2, 4) ! 後ろを向く
END IF

END SUB
*1 このやり方には左よりも右を優先するという偏りがあります。
*2「右を向く」「左を向く」について
どうして 1 や 3 を加算するだけで右向きや左向きが実現できるかというと、
方向を 0 から 1, 2, 3 と時計回りに割り振った数値にして、MOD() 関数で計算していることに意味があります。
(MOD(a,b) は a を b で割った余りを求める関数)

例えば、方向が 0 のときの右は 1 で、左は 3 なので、
Case-A. 前が上 (dir = 0) のとき。
  0 + 1 = 1 → 右
0 + 3 = 3 → 左		    
0
前
 3 左 ↑ 右 1 
後
2  
となることが分かると思います。

同様に、方向が 1 のときの右は 2 で、左は 0 なので、
Case-B. 前が右 (dir = 1) のとき。
  1 + 1 = 2 → 右
1 + 3 = 4 → 左 (?)		    
0
左
 3 後 → 前 1 
右
2
  
となります。
(Case-A, Case-B どちらも +1 で右向き、+3 で左向きになる)

重要なのは MOD() によって、あまりの計算をすることで、これにより Case-B の (?) は、
1 + 3 = 4 ,
MOD(4, 4) = 0 → 左
(4 を 4 で割ったあまりは 0)
とすることが出来ます。

時計の針と同じ理屈です。(以下は長針の例)
· 長針の場合は、右向き: +15 分, 左向き: +45 分。
変更前の長針加える時間変更後の長針
0 分 +15 分15 分
+45 分45 分
15 分 +15 分30 分
+45 分0 分
30 分 +15 分45 分
+45 分15 分
45 分 +15 分0 分
+45 分30 分

3. 分割したプログラム

3-1. プログラムを分割する。
プログラムが長くなったせいで、全体の見通しが悪くなってきました。

十進 BASIC には、別ファイルのプログラムを実行直前に取り込む機能があります。
その機能 (MERGE という命令) を利用してプログラムを 2 つのファイル
  • program.BAS
  • lib.BAS
に分割します。
(もっとたくさん分割することもできますが、細分化すると管理の労力が増えるので、ここでは 2 つにします)

プログラムを分割するにはコツがあって、それは
·変更の少ないプログラムをまとめて別ファイルにする。
というものです。
(専門的には「疎結合の関数群をライブラリ化する」と表現します)

プログラムを分割するに際し、副プログラム HeyaDisplay も変更しています。
表示する画面範囲を固定にしていましたが、これを可変で扱えるようにします。(幅、高さをそれぞれ変数 w, h にします)

<テキスト12> ファイル名「program.BAS」
命令「MERGE」は「プログラムファイルの最後に書かなくてはいけない」というルールがあります。
プログラムを分割しただけなので、内容に変化はありません。
SET WINDOW 0,39,19,0

DIM heya$(7)
LET heya$(1) = "+---------------+"
LET heya$(2) = "|     #       # |"
LET heya$(3) = "| ### # # ### # |"
LET heya$(4) = "| # #   #   # # |"
LET heya$(5) = "| # ####### # # |"
LET heya$(6) = "|     #     #   |"
LET heya$(7) = "+---------------+"

!      X, Y, Mark   コントロールの場所と記号
DATA  2, 5,"a"
DATA 10, 6,"b"
DATA 16, 2,"c"
DIM Controls$(3,3)
MAT READ Controls$

! コントロールを迷路に埋め込む
FOR Mokuhyo = 1 TO 3
   LET mx = VAL(Controls$(Mokuhyo, 1))
   LET my = VAL(Controls$(Mokuhyo, 2))
   LET mm$ = Controls$(Mokuhyo, 3)
   LET heya$(my)(mx:mx) = mm$
NEXT Mokuhyo

! 自分の横位置、縦位置、方向
LET x = 2
LET y = 2
LET dir = 0 ! 方向 0:↑ / 1:→ / 2:↓ / 3:←
LET myChr$ = "A>V<"

DECLARE EXTERNAL SUB HeyaDisplay
CALL HeyaDisplay(heya$, 17, 7, x, y, MID$(myChr$, 1 + dir, 1))

DECLARE EXTERNAL SUB BogusTick
LET BogusTick_before = -1

DECLARE EXTERNAL SUB Search
DECLARE EXTERNAL SUB GetFPV
DECLARE EXTERNAL SUB HeadTurn

LET Mokuhyo = 1
LET mx = VAL(Controls$(Mokuhyo, 1))
LET my = VAL(Controls$(Mokuhyo, 2))
LET mm$ = Controls$(Mokuhyo, 3)

DO
   CALL BogusTick(BogusTick_before, 10)

   IF GetKeyState(27) < 0 THEN EXIT DO

   DIM idou(4)
   CALL Search(idou, heya$, x, y)
   DIM fpv(4)
   CALL GetFPV(fpv, dir, idou)   ! ゆか状況を自分視点の前後左右に変換する。
   CALL HeadTurn(dir, fpv)      ! 進路を変更する。
   LET dx = 0
   LET dy = 0
   IF dir = 1 THEN LET dx = idou(1)  ! 右向きなら dx に +1 (または 0) を入れる。
   IF dir = 3 THEN LET dx = idou(2)  ! 左向きなら dx に -1 (または 0) を入れる。
   IF dir = 2 THEN LET dy = idou(3)  ! 下向きなら dy に +1 (または 0) を入れる。
   IF dir = 0 THEN LET dy = idou(4)  ! 上向きなら dy に -1 (または 0) を入れる。
   LET x = x + dx
   LET y = y + dy

   CALL HeyaDisplay(heya$, 17, 7, x, y, MID$(myChr$, 1 + dir, 1))

   IF x = mx AND y = my THEN
      IF mm$ = "c" THEN EXIT DO

      LET heya$(my)(mx:mx) = " "

      LET Mokuhyo = Mokuhyo + 1
      LET mx = VAL(Controls$(Mokuhyo, 1))
      LET my = VAL(Controls$(Mokuhyo, 2))
      LET mm$ = Controls$(Mokuhyo, 3)
   END IF
LOOP

END



! ## ここにあった副プログラムを「lib.BAS」として別ファイルに切り出した ##



! 自動で歩かせる副プログラム
EXTERNAL SUB HeadTurn(dir, fpv())

LET mae    = fpv(1)
LET migi   = fpv(2)
LET hidari = fpv(3)
LET ushiro = fpv(4)

IF     migi   <> 0 AND INT(RND * 2) = 0 THEN
   LET dir = MOD(dir + 1, 4) ! 右を向く
ELSEIF hidari <> 0 AND INT(RND * 2) = 0 THEN
   LET dir = MOD(dir + 3, 4) ! 左を向く
ELSEIF mae = 0 THEN
   LET dir = MOD(dir + 2, 4) ! 後ろを向く
END IF

END SUB



MERGE "lib.BAS"  ! 別ファイル「lib.BAS」を取り込む。

<テキスト13> ファイル名「lib.BAS」(エル・アイ・ビー・ドット・ビー・エー・エス)
· ファイル保存時の文字コードを Shift-JIS にすること。
·「program.BAS」と同じフォルダーに置くこと。
(Windows10 なら %LOCALAPPDATA%\VirtualStore\Program Files (x86)\Decimal Basic\BASICw32\ の中でも OK)
! 部屋を表示する副プログラム
EXTERNAL SUB HeyaDisplay(heya$(), w, h, x, y, cc$)
SET DRAW MODE Hidden
CLEAR
SET COLOR 1
FOR tate = 1 TO h
   LET gyou$ = heya$(tate)
   FOR yoko = 1 TO w
      LET kabe$ = mid$(gyou$, yoko, 1)
      PLOT TEXT ,AT yoko,tate:kabe$
   NEXT yoko
NEXT tate

SET COLOR 1
PLOT TEXT ,AT x,y:cc$
SET DRAW MODE Explicit
END SUB



! BogusTick version 1.0 written by fuku@rouge.gr.jp
EXTERNAL SUB BogusTick(before, fps)
IF before >= 0 AND fps > 0 THEN
   LET current = TIME
   IF before > current THEN LET before = before - 24 * 3600
   LET this_wait = 1 / fps - (current - before)
   IF this_wait > 0 THEN WAIT DELAY this_wait
END IF
LET before = TIME
END SUB



! 周囲を調査する副プログラム
EXTERNAL SUB Search(idou(),heya$(),cx,cy)

LET ikeru$ = " abc"

MAT idou = ZER
IF POS(ikeru$, mid$(heya$(cy + 0), cx + 1,1)) > 0 THEN LET idou(1) = +1
IF POS(ikeru$, mid$(heya$(cy + 0), cx - 1,1)) > 0 THEN LET idou(2) = -1
IF POS(ikeru$, mid$(heya$(cy + 1), cx + 0,1)) > 0 THEN LET idou(3) = +1
IF POS(ikeru$, mid$(heya$(cy - 1), cx + 0,1)) > 0 THEN LET idou(4) = -1

END SUB



! 移動の可否を一人称視点の前後左右に変換する副プログラム
EXTERNAL SUB GetFPV(fpv(), dir, idou())

! 部屋 → 自分視点の変換テーブル
DATA 4,1,2,3
DATA 1,3,4,2
DATA 3,2,1,4
DATA 2,4,3,1
DIM henkan(4,4)
MAT READ henkan

! 自分視点に変換する。
LET fpv(1) = idou(henkan(1 + dir, 1))    ! 前方
LET fpv(2) = idou(henkan(1 + dir, 2))    ! 右側
LET fpv(3) = idou(henkan(1 + dir, 3))    ! 左側
LET fpv(4) = idou(henkan(1 + dir, 4))    ! 後方

END SUB

4. 高度なアルゴリズム

「2. 場当たり式の進行」では進行方向を乱数で決めていたので、かなりもどかしい動作をしていたと思います。
それなりに面白い動きでしたが、本稿の冒頭で紹介した解法を実装します。

4-1. 右手法によるプログラムの作成
<テキスト14> ファイル名「program.BAS」
SET WINDOW 0,39,19,0

DIM heya$(7)
LET heya$(1) = "+---------------+"
LET heya$(2) = "|     #       # |"
LET heya$(3) = "| ### # # ### # |"
LET heya$(4) = "| # #   #   # # |"
LET heya$(5) = "| # ####### # # |"
LET heya$(6) = "|     #     #   |"
LET heya$(7) = "+---------------+"

!      X, Y, Mark   コントロールの場所と記号
DATA  2, 5,"a"
DATA 10, 6,"b"
DATA 16, 2,"c"
DIM Controls$(3,3)
MAT READ Controls$

! コントロールを迷路に埋め込む
FOR Mokuhyo = 1 TO 3
   LET mx = VAL(Controls$(Mokuhyo, 1))
   LET my = VAL(Controls$(Mokuhyo, 2))
   LET mm$ = Controls$(Mokuhyo, 3)
   LET heya$(my)(mx:mx) = mm$
NEXT Mokuhyo

! 自分の横位置、縦位置、方向
LET x = 2
LET y = 2
LET dir = 0 ! 方向 0:↑ / 1:→ / 2:↓ / 3:←
LET myChr$ = "A>V<"

DECLARE EXTERNAL SUB HeyaDisplay
CALL HeyaDisplay(heya$, 17, 7, x, y, MID$(myChr$, 1 + dir , 1))

DECLARE EXTERNAL SUB BogusTick
LET BogusTick_before = -1

DECLARE EXTERNAL SUB Search
DECLARE EXTERNAL SUB GetFPV
DECLARE EXTERNAL SUB HeadTurn

LET Mokuhyo = 1
LET mx = VAL(Controls$(Mokuhyo, 1))
LET my = VAL(Controls$(Mokuhyo, 2))
LET mm$ = Controls$(Mokuhyo, 3)

DO
   CALL BogusTick(BogusTick_before, 10)

   IF GetKeyState(27) < 0 THEN EXIT DO

   DIM idou(4)
   CALL Search(idou, heya$, x, y)
   DIM fpv(4)
   CALL GetFPV(fpv, dir, idou)   ! ゆか状況を自分視点の前後左右に変換する。
   CALL HeadTurn(dir, fpv)      ! 進路を変更する。
   LET dx = 0
   LET dy = 0
   IF dir = 1 THEN LET dx = idou(1)  ! 右向きなら dx に +1 (または 0) を入れる。
   IF dir = 3 THEN LET dx = idou(2)  ! 左向きなら dx に -1 (または 0) を入れる。
   IF dir = 2 THEN LET dy = idou(3)  ! 下向きなら dy に +1 (または 0) を入れる。
   IF dir = 0 THEN LET dy = idou(4)  ! 上向きなら dy に -1 (または 0) を入れる。
   LET x = x + dx
   LET y = y + dy

   CALL HeyaDisplay(heya$, 17, 7, x, y, MID$(myChr$, 1 + dir , 1))

   IF x = mx AND y = my THEN
      IF mm$ = "c" THEN EXIT DO

      LET heya$(my)(mx:mx) = " "

      LET Mokuhyo = Mokuhyo + 1
      LET mx = VAL(Controls$(Mokuhyo, 1))
      LET my = VAL(Controls$(Mokuhyo, 2))
      LET mm$ = Controls$(Mokuhyo, 3)
   END IF
LOOP

END



! 自動で歩かせる副プログラム
EXTERNAL SUB HeadTurn(dir, fpv())

LET mae    = fpv(1)
LET migi   = fpv(2)
LET hidari = fpv(3)
LET ushiro = fpv(4)

IF migi = 0 THEN
   IF mae = 0 THEN LET dir = MOD(dir + 3, 4)
ELSE
   LET dir = MOD(dir + 1, 4)
END IF

END SUB



MERGE "lib.BAS"
* lib.BAS は前述の<テキスト13>です。program.BAS と同じフォルダーに置いてください。
(Windows10 なら %LOCALAPPDATA%\VirtualStore\Program Files (x86)\Decimal Basic\BASICw32\ の中でも OK)

<テキスト14> は <テキスト11> より簡素になりましたが、これでも迷路を解くことが出来ます。
4-2. 右手法によるプログラムの実行
右側の壁に沿って進んでいることが分かると思います。
4-3. 右手法によるプログラムの説明
<テキスト14> ファイル名「program.BAS」
SET WINDOW 0,39,19,0

DIM heya$(7)
LET heya$(1) = "+---------------+"
LET heya$(2) = "|     #       # |"
LET heya$(3) = "| ### # # ### # |"
LET heya$(4) = "| # #   #   # # |"
LET heya$(5) = "| # ####### # # |"
LET heya$(6) = "|     #     #   |"
LET heya$(7) = "+---------------+"

!      X, Y, Mark   コントロールの場所と記号
DATA  2, 5,"a"
DATA 10, 6,"b"
DATA 16, 2,"c"
DIM Controls$(3,3)
MAT READ Controls$

! コントロールを迷路に埋め込む
FOR Mokuhyo = 1 TO 3
   LET mx = VAL(Controls$(Mokuhyo, 1))
   LET my = VAL(Controls$(Mokuhyo, 2))
   LET mm$ = Controls$(Mokuhyo, 3)
   LET heya$(my)(mx:mx) = mm$
NEXT Mokuhyo

! 自分の横位置、縦位置、方向
LET x = 2
LET y = 2
LET dir = 0 ! 方向 0:↑ / 1:→ / 2:↓ / 3:←
LET myChr$ = "A>V<"

DECLARE EXTERNAL SUB HeyaDisplay
CALL HeyaDisplay(heya$, 17, 7, x, y, MID$(myChr$, 1 + dir , 1))

DECLARE EXTERNAL SUB BogusTick
LET BogusTick_before = -1

DECLARE EXTERNAL SUB Search
DECLARE EXTERNAL SUB GetFPV
DECLARE EXTERNAL SUB HeadTurn

LET Mokuhyo = 1
LET mx = VAL(Controls$(Mokuhyo, 1))
LET my = VAL(Controls$(Mokuhyo, 2))
LET mm$ = Controls$(Mokuhyo, 3)

DO
   CALL BogusTick(BogusTick_before, 10)

   IF GetKeyState(27) < 0 THEN EXIT DO

   DIM idou(4)
   CALL Search(idou, heya$, x, y)
   DIM fpv(4)
   CALL GetFPV(fpv, dir, idou)   ! ゆか状況を自分視点の前後左右に変換する。
   CALL HeadTurn(dir, fpv)      ! 進路を変更する。
   LET dx = 0
   LET dy = 0
   IF dir = 1 THEN LET dx = idou(1)  ! 右向きなら dx に +1 (または 0) を入れる。
   IF dir = 3 THEN LET dx = idou(2)  ! 左向きなら dx に -1 (または 0) を入れる。
   IF dir = 2 THEN LET dy = idou(3)  ! 下向きなら dy に +1 (または 0) を入れる。
   IF dir = 0 THEN LET dy = idou(4)  ! 上向きなら dy に -1 (または 0) を入れる。
   LET x = x + dx
   LET y = y + dy

   CALL HeyaDisplay(heya$, 17, 7, x, y, MID$(myChr$, 1 + dir , 1))

   IF x = mx AND y = my THEN
      IF mm$ = "c" THEN EXIT DO

      LET heya$(my)(mx:mx) = " "

      LET Mokuhyo = Mokuhyo + 1
      LET mx = VAL(Controls$(Mokuhyo, 1))
      LET my = VAL(Controls$(Mokuhyo, 2))
      LET mm$ = Controls$(Mokuhyo, 3)
   END IF
LOOP

END



! 自動で歩かせる副プログラム
EXTERNAL SUB HeadTurn(dir, fpv())

LET mae    = fpv(1)
LET migi   = fpv(2)
LET hidari = fpv(3)
LET ushiro = fpv(4)

IF migi = 0 THEN
! 右側に壁がある*3
   IF mae = 0 THEN LET dir = MOD(dir + 3, 4) ! 前にも壁があるので左を向く*4
ELSE
! 右側に壁がない*5
   LET dir = MOD(dir + 1, 4) ! 右を向く
END IF

END SUB



MERGE "lib.BAS"
*3 *4 *5 は、それぞれ以下の場合を想定しています。
また、行き止まりの場合でも後ろへ向かうことが出来ます。
 *3 右に壁がある場合。→ 進行方向はそのまま前へ。
壁⇑
こっち
  ↑壁
  

右へ曲がることは出来ないが、前に進むことが出来る。

 *4 右と前に壁がある場合。→ 進行方向は左へ。
壁壁
⇐
こっち		↑壁
  

右へ曲がることは出来ない。前に進むこともできない。

 *5 右に壁がない場合。→ 進行方向は右へ。
壁壁
  ↑⇒
こっち
  

右へ曲がることが出来る。

行き止まりの場合。→ 進行方向は後ろへ。(左向きを 2 回)
自動的に *4 を一度行うことになり、そのあと左へ進めるようになる。
壁壁
壁↑壁
  
  ⇒ 
壁壁
壁←壁
 こっち
⇓		 

5. 別ルートも探索するアルゴリズム

冒頭で述べたように、右手法には独立した通路にゴールがあると、そこへたどり着けないという欠点があります。
これを補うため、「右手法によるプログラム」を改良して、右手法だけでは行けない通路へも進行できるようにします。

5-1. 別ルートも探索するプログラムの作成
<テキスト15> ファイル名「program.BAS」
SET WINDOW 0,39,19,0

DIM heya$(7)
LET heya$(1) = "+---------------+"
LET heya$(2) = "|     #       # |"
LET heya$(3) = "| ### # # ### # |"
LET heya$(4) = "| #     #   # # |"    ! 左から 2 番目の # を ' ' に変更する。
LET heya$(5) = "| # ####### # # |"
LET heya$(6) = "|     #     #   |"
LET heya$(7) = "+---------------+"

!      X, Y, Mark   コントロールの場所と記号
DATA  2, 5,"a"
DATA 10, 6,"b"
DATA 16, 2,"c"
DIM Controls$(3,3)
MAT READ Controls$

! コントロールを迷路に埋め込む
FOR Mokuhyo = 1 TO 3
   LET mx = VAL(Controls$(Mokuhyo, 1))
   LET my = VAL(Controls$(Mokuhyo, 2))
   LET mm$ = Controls$(Mokuhyo, 3)
   LET heya$(my)(mx:mx) = mm$
NEXT Mokuhyo

! 自分の横位置、縦位置、方向
LET x = 2
LET y = 2
LET dir = 0 ! 方向 0:↑ / 1:→ / 2:↓ / 3:←
LET myChr$ = "A>V<"

DIM bunkiSpots(100, 3)
LET bunkiMax = 0

DECLARE EXTERNAL SUB HeyaDisplay
CALL HeyaDisplay(heya$, 17, 7, x, y, MID$(myChr$, 1 + dir , 1))

DECLARE EXTERNAL SUB BogusTick
LET BogusTick_before = -1

DECLARE EXTERNAL SUB Search
DECLARE EXTERNAL SUB GetFPV
DECLARE EXTERNAL SUB HeadTurn
DECLARE EXTERNAL SUB BunkiAdd
DECLARE EXTERNAL SUB BunkiDel
DECLARE EXTERNAL FUNCTION BunkiSearch

LET Mokuhyo = 1
LET mx = VAL(Controls$(Mokuhyo, 1))
LET my = VAL(Controls$(Mokuhyo, 2))
LET mm$ = Controls$(Mokuhyo, 3)

DO
   CALL BogusTick(BogusTick_before, 10)

   IF GetKeyState(27) < 0 THEN EXIT DO

   DIM idou(4)
   CALL Search(idou, heya$, x, y)

   ! 過去の分岐点から現在位置と同じものを探す。
   LET turnPoint = BunkiSearch(bunkiSpots, bunkiMax, x, y)
   IF turnPoint > 0 THEN
   ! 過去の分岐点を回収して回頭する。
      LET newDir = bunkiSpots(turnPoint, 1)
      CALL BunkiDel(bunkiSpots, bunkiMax, turnPoint)
      IF newDir = MOD(dir + 2, 4) THEN
      ! 取得した方向が結果的に後ろ向きなら無視する。
      ELSE
         LET dir = newDir
      END IF
   ELSE
   ! 普通に回頭する。
      DIM fpv(4)
      CALL GetFPV(fpv, dir, idou)   ! ゆか状況を自分視点の前後左右に変換する。
      CALL HeadTurn(dir, fpv, otherDir)      ! 進路を変更する。
      IF otherDir <> -1 THEN CALL BunkiAdd(bunkiSpots, bunkiMax, otherDir, x, y)
   END IF

   LET dx = 0
   LET dy = 0
   IF dir = 1 THEN LET dx = idou(1)  ! 右向きなら dx に +1 (または 0) を入れる。
   IF dir = 3 THEN LET dx = idou(2)  ! 左向きなら dx に -1 (または 0) を入れる。
   IF dir = 2 THEN LET dy = idou(3)  ! 下向きなら dy に +1 (または 0) を入れる。
   IF dir = 0 THEN LET dy = idou(4)  ! 上向きなら dy に -1 (または 0) を入れる。
   LET x = x + dx
   LET y = y + dy

   CALL HeyaDisplay(heya$, 17, 7, x, y, MID$(myChr$, 1 + dir , 1))

   IF x = mx AND y = my THEN
      IF mm$ = "c" THEN EXIT DO

      LET heya$(my)(mx:mx) = " "

      LET Mokuhyo = Mokuhyo + 1
      LET mx = VAL(Controls$(Mokuhyo, 1))
      LET my = VAL(Controls$(Mokuhyo, 2))
      LET mm$ = Controls$(Mokuhyo, 3)
   END IF
LOOP

END



! 自動で歩かせる副プログラム
EXTERNAL SUB HeadTurn(dir, fpv(), otherDir)

LET mae    = fpv(1)
LET migi   = fpv(2)
LET hidari = fpv(3)
LET ushiro = fpv(4)

LET otherDir = -1

IF migi = 0 THEN
! 右側に壁がある
   IF mae <> 0 THEN
      IF hidari <> 0 THEN LET otherDir = MOD(dir + 3, 4)
   ELSE
      LET dir = MOD(dir + 3, 4)
   END IF
ELSE
! 右側に壁がない → 右を向く。
   IF mae <> 0 THEN
      LET otherDir = dir
   ELSEIF hidari <> 0 THEN
      LET otherDir = MOD(dir + 3, 4)
   END IF
   LET dir = MOD(dir + 1, 4)
END IF

END SUB



EXTERNAL SUB BunkiAdd(bunkiSpots(,), bunkiMax, dir, x, y)

LET bunkiMax = bunkiMax + 1
LET bunkiSpots(bunkiMax, 1) = dir
LET bunkiSpots(bunkiMax, 2) = x
LET bunkiSpots(bunkiMax, 3) = y

END SUB



EXTERNAL SUB BunkiDel(bunkiSpots(,), bunkiMax, turnPoint)

FOR i = turnPoint TO bunkiMax - 1
   LET bunkiSpots(i, 1) = bunkiSpots(i + 1, 1)
   LET bunkiSpots(i, 2) = bunkiSpots(i + 1, 2)
   LET bunkiSpots(i, 3) = bunkiSpots(i + 1, 3)
NEXT i

LET bunkiMax = bunkiMax - 1
IF bunkiMax < 0 THEN LET bunkiMax = 0

END SUB



EXTERNAL FUNCTION BunkiSearch(bunkiSpots(,), bunkiMax, x, y)

LET turnPoint = 0

FOR i = bunkiMax TO 1 STEP -1
   IF bunkiSpots(i, 2) = x AND bunkiSpots(i, 3) = y THEN
      turnPoint = i
      EXIT FOR
   END IF
NEXT i

LET BunkiSearch = turnPoint

END FUNCTION



MERGE "lib.BAS"
* lib.BAS は前述の<テキスト13>です。program.BAS と同じフォルダーに置いてください。
(Windows10 なら %LOCALAPPDATA%\VirtualStore\Program Files (x86)\Decimal Basic\BASICw32\ の中でも OK)
5-2. 別ルートも探索するプログラムの実行
5-3. 別ルートも探索するプログラムの説明
<テキスト15> ファイル名「program.BAS」
SET WINDOW 0,39,19,0

DIM heya$(7)
LET heya$(1) = "+---------------+"
LET heya$(2) = "|     #       # |"
LET heya$(3) = "| ### # # ### # |"
LET heya$(4) = "| #     #   # # |"    ! 左から 2 番目の # を ' ' に変更する。
LET heya$(5) = "| # ####### # # |"
LET heya$(6) = "|     #     #   |"
LET heya$(7) = "+---------------+"

!      X, Y, Mark   コントロールの場所と記号
DATA  2, 5,"a"
DATA 10, 6,"b"
DATA 16, 2,"c"
DIM Controls$(3,3)
MAT READ Controls$

! コントロールを迷路に埋め込む
FOR Mokuhyo = 1 TO 3
   LET mx = VAL(Controls$(Mokuhyo, 1))
   LET my = VAL(Controls$(Mokuhyo, 2))
   LET mm$ = Controls$(Mokuhyo, 3)
   LET heya$(my)(mx:mx) = mm$
NEXT Mokuhyo

! 自分の横位置、縦位置、方向
LET x = 2
LET y = 2
LET dir = 0 ! 方向 0:↑ / 1:→ / 2:↓ / 3:←
LET myChr$ = "A>V<"

! 履歴用配列の用意と格納数の初期化。
DIM bunkiSpots(100, 3)
LET bunkiMax = 0

DECLARE EXTERNAL SUB HeyaDisplay
CALL HeyaDisplay(heya$, 17, 7, x, y, MID$(myChr$, 1 + dir , 1))

DECLARE EXTERNAL SUB BogusTick
LET BogusTick_before = -1

DECLARE EXTERNAL SUB Search
DECLARE EXTERNAL SUB GetFPV
DECLARE EXTERNAL SUB HeadTurn
DECLARE EXTERNAL SUB BunkiAdd            ! 副プログラムの使用予告。
DECLARE EXTERNAL SUB BunkiDel            ! 副プログラムの使用予告。
DECLARE EXTERNAL FUNCTION BunkiSearch    ! 外部関数の使用予告。

LET Mokuhyo = 1
LET mx = VAL(Controls$(Mokuhyo, 1))
LET my = VAL(Controls$(Mokuhyo, 2))
LET mm$ = Controls$(Mokuhyo, 3)

DO
   CALL BogusTick(BogusTick_before, 10)

   IF GetKeyState(27) < 0 THEN EXIT DO

   DIM idou(4)
   CALL Search(idou, heya$, x, y)

   ! 過去の分岐点から現在位置と同じものを探す。
   LET turnPoint = BunkiSearch(bunkiSpots, bunkiMax, x, y)
   IF turnPoint > 0 THEN
   ! 現在位置と同じものがあった。
   ! 過去の分岐点を回収して回頭する。
      LET newDir = bunkiSpots(turnPoint, 1)  ! 選択しなかった方向を履歴から取得する。
      CALL BunkiDel(bunkiSpots, bunkiMax, turnPoint) ! 方向を取得したので履歴から削除する。
      IF newDir = MOD(dir + 2, 4) THEN
      ! 取得した方向が結果的に後ろ向きなら無視する。
      ELSE
         LET dir = newDir    ! 取得した向きへ回頭する。
      END IF
   ELSE
   ! 普通に回頭する。
      DIM fpv(4)
      CALL GetFPV(fpv, dir, idou)   ! ゆか状況を自分視点の前後左右に変換する。
      CALL HeadTurn(dir, fpv, otherDir)      ! 進路を変更する。

      ! 向きを変える選択肢が他にもあったら履歴に追加する。
      IF otherDir <> -1 THEN CALL BunkiAdd(bunkiSpots, bunkiMax, otherDir, x, y)
   END IF

   LET dx = 0
   LET dy = 0
   IF dir = 1 THEN LET dx = idou(1)  ! 右向きなら dx に +1 (または 0) を入れる。
   IF dir = 3 THEN LET dx = idou(2)  ! 左向きなら dx に -1 (または 0) を入れる。
   IF dir = 2 THEN LET dy = idou(3)  ! 下向きなら dy に +1 (または 0) を入れる。
   IF dir = 0 THEN LET dy = idou(4)  ! 上向きなら dy に -1 (または 0) を入れる。
   LET x = x + dx
   LET y = y + dy

   CALL HeyaDisplay(heya$, 17, 7, x, y, MID$(myChr$, 1 + dir , 1))

   IF x = mx AND y = my THEN
      IF mm$ = "c" THEN EXIT DO

      LET heya$(my)(mx:mx) = " "

      LET Mokuhyo = Mokuhyo + 1
      LET mx = VAL(Controls$(Mokuhyo, 1))
      LET my = VAL(Controls$(Mokuhyo, 2))
      LET mm$ = Controls$(Mokuhyo, 3)
   END IF
LOOP

END



! 自動で歩かせる副プログラム
EXTERNAL SUB HeadTurn(dir, fpv(), otherDir)  ! 他の選択肢を戻す変数 otherDir を追加。

LET mae    = fpv(1)
LET migi   = fpv(2)
LET hidari = fpv(3)
LET ushiro = fpv(4)

LET otherDir = -1    ! 他通路への選択肢は発見するまで「無し」にしておく。

IF migi = 0 THEN
! 右側に壁がある
   IF mae <> 0 THEN
   ! 前側に壁がない → 向きはそのまま。
      IF hidari <> 0 THEN LET otherDir = MOD(dir + 3, 4)   ! 左へも行けることを発見。選択肢を残す。
   ELSE
   ! 右、前ともに壁があるので左を向く。
      LET dir = MOD(dir + 3, 4)
   END IF
ELSE
! 右側に壁がない → 右を向く。
   IF mae <> 0 THEN
   ! 前側に壁がない。
      LET otherDir = dir             ! 前へも行けることを発見。選択肢を残す。
   ELSEIF hidari <> 0 THEN
   ! 前側に壁があるが、左側にはない。
      LET otherDir = MOD(dir + 3, 4) ! 左へも行けることを発見。選択肢を残す。
   END IF
   LET dir = MOD(dir + 1, 4) ! 右を向く。
END IF

END SUB



! 選択しなかった他通路をひとつ履歴用配列に追加する副プログラム。
EXTERNAL SUB BunkiAdd(bunkiSpots(,), bunkiMax, dir, x, y)

LET bunkiMax = bunkiMax + 1  ! 履歴の格納数を 1 つ増やす。
LET bunkiSpots(bunkiMax, 1) = dir    ! 方向を保存する。
LET bunkiSpots(bunkiMax, 2) = x      ! 横位置を保存する。
LET bunkiSpots(bunkiMax, 3) = y      ! 縦位置を保存する。

END SUB



! 他通路の履歴をひとつ履歴用配列から削除する副プログラム。
EXTERNAL SUB BunkiDel(bunkiSpots(,), bunkiMax, turnPoint)

! 指定位置より後ろのデータをすべてひとつずつ前にコピーする。
FOR i = turnPoint TO bunkiMax - 1    !
   LET bunkiSpots(i, 1) = bunkiSpots(i + 1, 1)   ! 方向
   LET bunkiSpots(i, 2) = bunkiSpots(i + 1, 2)   ! 横位置
   LET bunkiSpots(i, 3) = bunkiSpots(i + 1, 3)   ! 縦位置
NEXT i

LET bunkiMax = bunkiMax - 1            ! 履歴の格納数を 1 つ減らす。
IF bunkiMax < 0 THEN LET bunkiMax = 0 ! 減らしすぎても 0 以下にしない。

END SUB



! 履歴用配列に現在位置のデータがあるか検索する外部関数。
! データがあれば、その位置 (添え字) を返す。無ければ 0 を返す。
EXTERNAL FUNCTION BunkiSearch(bunkiSpots(,), bunkiMax, x, y)

LET turnPoint = 0    ! 履歴の位置をデータが無い時の値で初期化しておく。

! 履歴を最新から古いものへ検索する。
FOR i = bunkiMax TO 1 STEP -1
   IF bunkiSpots(i, 2) = x AND bunkiSpots(i, 3) = y THEN
   ! 現在位置に合致するデータが存在する。
   ! 履歴の位置を覚えてループから抜け出す。
      turnPoint = i
      EXIT FOR
   END IF
NEXT i

LET BunkiSearch = turnPoint  ! 発見した履歴の位置を関数の返戻値とする。

END FUNCTION



MERGE "lib.BAS"
履歴用配列について (選択しなかった方向の履歴)
曲がり角において、自分が選択した進行方向と別の進行可能方向があった場合、
その別の進行可能方向を縦位置、横位置とともに履歴用配列に格納 (追加) し、
再度その位置を訪れたら、格納されていた進行可能方向を採用する。
という方法を採っています。
ただし、その進行可能方向が結果的に後ろを指し示した場合は無視します。
(無視しないと、必要ないところで引き返してしまう)

<テキスト15> では、これを 3 つのプロシージャ (ふたつの副プログラムとひとつの外部関数) で実装しています。
  1. BunkiAdd - 履歴にデータを追加する。
    [1] 方向, 横, 縦 [2] 方向, 横, 縦
    		 (追加)← 
    方向, 横, 縦

  2. BunkiDel - 履歴から指定位置のデータを削除する。
    [1] 方向, 横, 縦 [2] 方向, 横, 縦 [3] 方向, 横, 縦
    		 (削除)→ 
    [2] 方向, 横, 縦

  3. BunkiSearch - 履歴から合致する位置を検索する。
    [1] 方向, 横, 縦 [2] 方向, 横, 縦 [3] 方向, 横, 縦
    		 (検索結果)→ 
    2
末尾にデータを追加し、末尾からデータを取り出す方式を LIFO (Last In First Out) やスタックと呼称します。
当プログラムでは、LIFO を改造したデータ構造を取り入れています。
(純粋な LIFO にすると、ループ状の通路に複数の分岐点があった場合にうまく動かない)
この章は、ここで終了です。