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

迷路を生成する

大きな迷路を人が作成するには時間と根気が必要になります。
迷路に特別なこだわりがあるなら人の手によって作成すべきですが、そうでないならコンピュータに任せることもできます。
また、コンピュータや誰かが作った迷路を、自分好みに手を加えたら時間の節約になるかもしれません。

プログラムで迷路を生成するには様々なアルゴリズムがあり、ここでは「壁伸ばし法」を利用します。
「壁伸ばし法」の他に「棒倒し法」「穴掘り法」「クラスタ法」「深さ優先探索法」等があります。
(「プログラムで」と断っていますが、方眼紙とサイコロと鉛筆があれば、手作業で作成することもできます)

壁伸ばし法とは、どこか適当な場所から無作為に曲がりながら壁を伸ばし続け、
伸ばせなくなったら、また別の適当な場所から同じように壁を伸ばす方法です。
壁を伸ばす場所がすべてなくなったら迷路の完成です。このとき、右手法 (みぎてほう) で解ける迷路が出来上がります。

壁伸ばし法の開始位置の取り方は 2 種類あり、「A·周囲の壁から伸ばす方法」と「B·任意のゆかから伸ばす方法」です。
ここでは、実装がより簡単な「A·周囲の壁から伸ばす方法」を掲載します。

迷路を生成出来たら、前稿の探索プログラムで解いてみます。


0. 事前準備

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


1. 迷路生成プログラムの作成

<テキスト16> ファイル名「makemaze.BAS」
データのシャッフル (Xorshift128, DustShuffle) はこちらを使っています。
DECLARE EXTERNAL SUB WallExtend     ! 副プログラムの使用予告
DECLARE EXTERNAL SUB PrintMaze      ! 副プログラムの使用予告

LET maze_w = 37 ! 横方向の大きさ。
LET maze_h = 17 ! 縦方向の大きさ。

DIM maze$(maze_h)                       ! 迷路格納変数。(ここに迷路を作る)
CALL WallExtend(maze$, maze_w, maze_h)  ! 迷路生成副プログラムを呼び出す。
CALL PrintMaze(maze$, maze_h)           ! 生成した迷路を表示する。

END


! 壁伸ばし法による迷路生成の副プログラム ! 迷路の大きさは 奇数×奇数 にすること。 EXTERNAL SUB WallExtend(maze$(), w, h) DECLARE EXTERNAL FUNCTION Validate ! 外部関数の使用予告 DECLARE EXTERNAL FUNCTION BitCount ! 外部関数の使用予告 DECLARE EXTERNAL FUNCTION BitSelect ! 外部関数の使用予告 DECLARE EXTERNAL SUB Xorshift128 ! 副プログラムの使用予告 DECLARE EXTERNAL SUB DustShuffle ! 副プログラムの使用予告 DIM xorshift_state(4) DATA 123456789, 123456761, 123456757, 123456731 ! すべてが 0 にならないように初期化する。*1 MAT READ xorshift_state ! 迷路の幅・高さを、指定された大きさを越えない奇数にそろえる LET w = w - (1 - MOD(w, 2)) LET h = h - (1 - MOD(h, 2)) ! 幅・高さのどちらかが 3 以下だと迷路にできない。 IF w <= 3 OR h <= 3 THEN EXIT SUB ! 部屋の上辺と下辺の壁を作成する。 LET maze$(1) = "+" LET maze$(h) = "+" FOR x = 2 TO w - 1 LET maze$(1) = maze$(1) & "-" LET maze$(h) = maze$(h) & "-" NEXT x LET maze$(1) = maze$(1) & "+" LET maze$(h) = maze$(h) & "+" ! 2 行目からの部屋を作成する。 FOR y = 2 TO h - 1 LET maze$(y) = "|" ! 左端を壁にする。 FOR x = 2 TO w - 1 ! 左端と右端の間を空白で埋める。 LET maze$(y) = maze$(y) & " " NEXT x LET maze$(y) = maze$(y) & "|" ! 右端を壁にする。 NEXT y LET pointMax = INT(w / 2 + 1) * INT(h / 2 + 1) DIM kabePosTmp(pointMax, 2) ! 伸ばす起点の壁の位置 LET kabePosMax = 0 ! Label-01 ! 上辺の開始位置を記憶する。 FOR x = 3 TO w - 2 STEP 2 LET kabePosMax = kabePosMax + 1 LET kabePosTmp(kabePosMax, 1) = x LET kabePosTmp(kabePosMax, 2) = 1 NEXT x ! 下辺の開始位置を記憶する。 FOR x = 3 TO w - 2 STEP 2 LET kabePosMax = kabePosMax + 1 LET kabePosTmp(kabePosMax, 1) = x LET kabePosTmp(kabePosMax, 2) = h NEXT x ! 2 行目からの左端の開始位置を記憶する。 FOR y = 3 to h - 2 STEP 2 LET kabePosMax = kabePosMax + 1 LET kabePosTmp(kabePosMax, 1) = 1 LET kabePosTmp(kabePosMax, 2) = y NEXT y ! 2 行目からの右端の開始位置を記憶する。 FOR y = 3 to h - 2 STEP 2 LET kabePosMax = kabePosMax + 1 LET kabePosTmp(kabePosMax, 1) = w LET kabePosTmp(kabePosMax, 2) = y NEXT y DIM idx(kabePosMax) CALL DustShuffle(idx, kabePosMax, xorshift_state) ! インデックスをかき混ぜる。 ! 初期の検索リストを作成する。 DIM kabePosQueue(pointMax, 2) ! 十進 BASIC は配列の再定義ができないため、最大を確保する。 FOR i = 1 TO kabePosMax LET kabePosQueue(i, 1) = kabePosTmp(idx(i), 1) LET kabePosQueue(i, 2) = kabePosTmp(idx(i), 2) NEXT i ! Label-02 ! 検索リストが空になるまで壁の拡張を続ける。 DO WHILE kabePosMax > 0 ! Label-03 ! 先頭の項目を取り出す。 LET x = kabePosQueue(1, 1) LET y = kabePosQueue(1, 2) ! 取り出したので先頭の項目を削る。 FOR i = 1 TO kabePosMax LET kabePosQueue(i, 1) = kabePosQueue(i + 1, 1) LET kabePosQueue(i, 2) = kabePosQueue(i + 1, 2) NEXT i LET kabePosMax = kabePosMax - 1 ! Label-04 ! 壁を伸ばせるか確認する。 LET d = Validate(maze$, w, h, x, y) ! Label-05 ! ビットのどれかを選択して延ばす。 IF d <> 0 THEN ! ↓ 途中経過を見たい場合はこの行を有効にして実行してください。 !PRINT x; y; d !CALL PrintMaze(maze$, h) ! Label-06 ! 探索済みの開始位置を検索リストの最後に追加する。 LET kabePosMax = kabePosMax + 1 LET kabePosQueue(kabePosMax, 1) = x LET kabePosQueue(kabePosMax, 2) = y ! Label-07 LET bitCnt = BitCount(d) ! 伸ばせる方向の格納数を求める。 CALL XorShift128(xorshift_state) LET nextDirPos = MOD(xorshift_state(1), bitCnt) LET nextDir = BitSelect(d, nextDirPos) ! 伸ばせる方向は 2 の指数*2 LET dx = 0 LET dy = 0 IF nextDir = 0 THEN dy = -1 ! 上へ延ばす。 IF nextDir = 1 THEN dx = +1 ! 右へ延ばす。 IF nextDir = 2 THEN dy = +1 ! 下へ延ばす。 IF nextDir = 3 THEN dx = -1 ! 左へ延ばす。 ! 壁を 2 コマ伸ばす。 ! 1 コマ先の分。 LET wx1 = x + dx * 1 LET wy1 = y + dy * 1 maze$(wy1)(wx1:wx1) = "#" ! 2 コマ先の分。 LET wx2 = x + dx * 2 LET wy2 = y + dy * 2 maze$(wy2)(wx2:wx2) = "#" ! Label-08 ! 2 コマ伸ばした先が候補を持つなら検索リストの先頭に追加する。 LET nextD = Validate(maze$, w, h, wx2, wy2) IF nextD <> 0 THEN LET kabePosMax = kabePosMax + 1 FOR i = kabePosMax TO 2 STEP -1 LET kabePosQueue(i, 1) = kabePosQueue(i - 1, 1) LET kabePosQueue(i, 2) = kabePosQueue(i - 1, 2) NEXT i LET kabePosQueue(1, 1) = wx2 LET kabePosQueue(1, 2) = wy2 END IF END IF LOOP ! Label-09 END SUB
! 迷路を表示する副プログラム EXTERNAL SUB PrintMaze(maze$(), h) FOR y = 1 TO h PRINT CHR$(34) & maze$(y) & CHR$(34) ! CHR$(34) は「"」の意味。"···" の形式で表示する。 NEXT y END SUB
! 乱数発生器 EXTERNAL SUB Xorshift128(state()) LET t = MOD(state(4), 2^32) ! fool proof LET s = MOD(state(1), 2^32) ! fool proof LET state(4) = state(3) LET state(3) = state(2) LET state(2) = s LET t = MOD(bitXOR(t, t * 2^11), 2^32) ! t ^= t << 11 LET t = bitXOR(t, INT(t / 2^8)) ! t ^= t >> 8 LET state(1) = MOD(bitXOR(bitXOR(t, s), INT(s / 2^19)), 2^32) ! t ^ s ^ (s >> 19) END SUB
! ダステンフェルドのシャッフル EXTERNAL SUB DustShuffle(arr(), cnt, state()) FOR i = 1 TO cnt LET arr(i) = i NEXT i FOR i = cnt TO 1 STEP -1 CALL Xorshift128(state) LET p = MOD(state(1), i) + 1 LET n = arr(p) LET arr(p) = arr(i) LET arr(i) = n NEXT i END SUB
! 有効な候補だけを選別する関数。 EXTERNAL FUNCTION Validate(maze$(), w, h, x, y) ! 2 個先 (壁となるコマ) に空きが無ければ該当ビットを削る。 LET d = 15 ! 15 = 00001111b IF (y - 2) < 1 THEN d = bitAND(d, bitNOT(2^0)) ! 上壁より上は外なので無効。 IF (x + 2) > w THEN d = bitAND(d, bitNOT(2^1)) ! 右壁より右は外なので無効。 IF (y + 2) > h THEN d = bitAND(d, bitNOT(2^2)) ! 下壁より下は外なので無効。 IF (x - 2) < 1 THEN d = bitAND(d, bitNOT(2^3)) ! 左壁より左は外なので無効。 ! 壁の内側でもすでに先がゆか以外なら無効。 IF bitAND(d, 2^0) <> 0 AND MID$(maze$(y - 2), x, 1) <> " " THEN d = bitAND(d, bitNOT(2^0)) ! 上側 IF bitAND(d, 2^1) <> 0 AND MID$(maze$(y), x + 2, 1) <> " " THEN d = bitAND(d, bitNOT(2^1)) ! 右側 IF bitAND(d, 2^2) <> 0 AND MID$(maze$(y + 2), x, 1) <> " " THEN d = bitAND(d, bitNOT(2^2)) ! 下側 IF bitAND(d, 2^3) <> 0 AND MID$(maze$(y), x - 2, 1) <> " " THEN d = bitAND(d, bitNOT(2^3)) ! 左側 Validate = d END FUNCTION
! ビットを数える関数。 EXTERNAL FUNCTION BitCount(n) LET cnt = 0 DO WHILE n > 0 ! すべてのビットを調べるまで繰り返す。(負の数は扱わない) cnt = cnt + bitAND(n, 1) ! 最下位ビットの有無を加算する。 n = INT(n / 2) ! n を右シフトする。 LOOP BitCount = cnt END FUNCTION
! ビットを選択する関数。 ! p 番目に 1 となっているビット位置を返す。(p は 0 オリジン) ! 該当のビットが無ければ -1 を返す。 EXTERNAL FUNCTION BitSelect(n, p) LET BitSelect = -1 ! 発見できなかった場合の値を保持しておく。 IF p < 0 THEN Exit FUNCTION ! 何番目かを指定するのは 0 以上であること。 LET times = 0 DO WHILE n <> 0 ! すべてのビットを調べるまで繰り返す。 IF bitAND(n, 2^times) <> 0 THEN p = p - 1 IF p < 0 THEN EXIT DO END IF n = bitAND(n, bitNOT(2^times)) ! 調べたビットを無効にする。 times = times + 1 ! 指数をひとつ進める。 LOOP IF p < 0 THEN LET BitSelect = times ! 発見したビット (指数) を返す。 END FUNCTION
*1違う迷路を生成したいときは、ここの数字を 0 以外に書き換えてください。
*2数えたビットから選択しているのでビットを発見できないケースは考えなくても大丈夫。

このプログラムは、以下 Label-01Label-09 を順に実行しています。
Label-01 : 上下左右の四辺に壁の開始位置を設け、すべてを検索リストに追加する。*3
Label-02 : 検索リストに開始位置が残っていれば下記 Label-03Label-09 を繰り返す。
Label-03 : 検索リストの先頭から開始位置をひとつ取り出して削る。
Label-04 : 取り出した開始位置から、壁を伸ばせない方向を捨てる。
Label-05 : 壁を伸ばす選択肢が残っていないなら Label-09 へ。
Label-06 : Label-03 で取り出した開始位置を検索リストの最後に追加する。*4
Label-07 : 選択肢から伸長方向をひとつ選択して壁を 2 コマ伸ばす。
Label-08 : 2 コマ伸ばした先がさらに壁を伸ばせそうなら、そこを開始位置として検索リストの先頭に追加する。*5*6
Label-09 : Label-02 へ戻る。

*3偶数番目の縦・横はゆか (通路) なので、壁の開始位置の縦・横は必ず奇数番目となる。
*4Label-05 の結果により追加されなくなる。→ Label-03 により、検索リストが短くなっていく。
*5壁を伸ばせないなら開始位置を追加しない。→ Label-03 により、検索リストが短くなっていく。
*6Label-03 で先頭を削った後に先頭へ追加するので、この場合は検索リストの長さが変わらない。
壁を伸ばす方向には以下の意味を持たせています。
0000 1111b (b は 2 進数の意味)
     |||+- 20: 上方向 
     ||+-- 21: 右方向 
     |+--- 22: 下方向 
     +---- 23: 左方向 

各ビットが 2 の累乗を意味していることを利用して、
そのビットの有無によって壁を延伸できる情報を格納しています。

例えば、12 (1100b) は、下と左へ壁を伸ばせるという意味です。


2. 迷路生成プログラムの実行

迷路生成プログラムを実行すると、実行結果<テキスト17>が表示されます。
これはただの文字列なので「コピー&ペースト」することにより、当 BASIC だけでなく他言語のプログラムに組み込むこともできます。
(他言語のプログラムに組み込むときは、その言語の文法に合わせてください)

<テキスト17> 実行結果
"+-----------------------------------+"
"| #   # #     #     #               |"
"| ### # # ##### # ### ### ##### ### |"
"|   # #   #     # #   # # #   # # # |"
"| ### # ### ### # # ### # ### ### # |"
"| #   # #   # # # # #       #     # |"
"| # ### # ### # ### # ##### # ##### |"
"| # #     #   #     # #   # # #     |"
"| # ### ### # ##### # ### # # ### ##|"
"|     # #   #     # #   #   #   # # |"
"|## ### ####### # # # ####### # ### |"
"| # # #       # # # #         #     |"
"| # # # ### ### ### # ####### ######|"
"| # #   # # #       # #             |"
"| # ##### ### ####### ### ######### |"
"|             #         # #         |"
"+-----------------------------------+"


3. 生成された迷路を組み込んだプログラムの作成

前章で作成した迷路探索プログラム<テキスト15>に、今回の迷路生成プログラムで生成した迷路<テキスト17>を組み込みます。

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

LET maze_w = 37
LET maze_h = 17

DATA "+-----------------------------------+"
DATA "| #   # #     #     #               |"
DATA "| ### # # ##### # ### ### ##### ### |"
DATA "|   # #   #     # #   # # #   # # # |"
DATA "| ### # ### ### # # ### # ### ### # |"
DATA "| #   # #   # # # # #       #     # |"
DATA "| # ### # ### # ### # ##### # ##### |"
DATA "| # #     #   #     # #   # # #     |"
DATA "| # ### ### # ##### # ### # # ### ##|"
DATA "|     # #   #     # #   #   #   # # |"
DATA "|## ### ####### # # # ####### # ### |"
DATA "| # # #       # # # #         #     |"
DATA "| # # # ### ### ### # ####### ######|"
DATA "| # #   # # #       # #             |"
DATA "| # ##### ### ####### ### ######### |"
DATA "|             #         # #         |"
DATA "+-----------------------------------+"
DIM heya$(maze_h)
MAT READ heya$

!      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$, maze_w, maze_h, 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$, maze_w, maze_h, 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" ! *7
*7 lib.BASBASIC であそぼう 5<テキスト13>です。program.BAS と同じフォルダーに置いてください。
(Windows10 なら %LOCALAPPDATA%\VirtualStore\Program Files (x86)\Decimal Basic\BASICw32\ の中でも OK)


4. 生成された迷路を組み込んだプログラムの実行

うまく解けました。

ところで、迷路データを変更する前の<テキスト15>は、右手法だけでは行けない通路も進行できるはずのプログラムでした。
そして「壁伸ばし法」では、右手法で解ける迷路が生成されています。

この<テキスト18>でも、プログラム部は変わっていないので、
壁がどこか途切れていても (右手法で行けない通路があったとしても) 解くことができるはずです。

各自、<テキスト18>の迷路部分を手作業で変更して、それが自動で解かれるかどうかを確認してください。
この章は、ここで終了です。