| HSP3 ゲームのプログラミング | |
| 迷路・ゲーム制作 |    |
| HSP3 ゲームのプログラミング | |
| 迷路・ゲーム制作 | |
今回作成した迷路の回答を作成する。すなわち、ゴールまでの道を探すプログラム（サブルーチン）を作成する。
迷路のデータは配列mazeに格納されている。このデータを元にスタートからゴールまでの道を探す。スタートは左上、ゴールは右下の角とする。マス目の座標で表すとスタートは(1,
1)、ゴールは(bx - 2, by - 2)となる。
(2) 迷路探索
迷路を探索するアルゴリズムはいろいろとある。「左手法（右手法）」、「拡張左手法（拡張右手法）」、「トレモー法」、「求心法」、「足立法」などがある。（これらのキーワードで検索して調べてみよう。）
ここでは、「右手法」で作成していくことにする。今回作成した迷路は、スタートからゴールまでの道筋が１つしかなく、それ以外の区画が全て袋小路である迷路なので右壁に沿って進んでいけばいつかはゴールに達する。この法則を利用してゴールまでの道を探す。
迷路の上を方角の北と表す。下が南、右が東、左が西という方向になる。進む方向によって右手の方向も決まる。その右手に壁があることを確認しながら進む。現在のマス目座標を(xx, yy)とする。移動先と調べる条件は次の通りである。
進行方向 右手方向 移動先 移動先
状況移動先
の右手結 果 東 南 (xx + 1, yy) 道 道 移動先の右手(xx + 1, yy + 1)へ進む。進行方向を南に転換 壁 移動先(xx + 1, yy)へ進む。 壁 −− 進行方向を「北」に変える。 西 北 (xx - 1, yy) 道 道 移動先の右手(xx - 1, yy - 1)へ進む。進行方向を北に転換 壁 移動先(xx - 1, yy)へ進む。 壁 −− 進行方向を「南」に変える。 南 西 (xx, yy + 1) 道 道 移動先の右手(xx - 1, yy + 1)へ進む。進行方向を西に転換 壁 移動先(xx, yy + 1)へ進む。 壁 −− 進行方向を「東」に変える。 北 東 (xx, yy - 1) 道 道 移動先の右手(xx + 1, yy - 1)へ進む。進行方向を東に転換 壁 移動先(xx, yy - 1)へ進む。 壁 −− 進行方向を「西」に変える。
進行方向によって、移動先のマス目座標などが違うので、まずは次のように判定文ができる。
if 進行方向=東 {
東の処理
} else if 進行方向=西 {
西の処理
} else if 進行方向=南 {
南の処理
} else if 進行方向=北 {
北の処理
}
※HSPにはelse ifが内ので、
右のような構造になる。→ if 進行方向=東 {
東の処理
} else {
if 進行方向=西 {
西の処理
} else {
if 進行方向=南 {
南の処理
} else {
if 進行方向=北 {
北の処理
}
}
}
}
次に、「東の処理」を考える。まず、移動先の状況（道／壁）の判定、道ならば右手方向の状況（道／壁）の判定となる。
＜＜東の処理＞＞
if maze(xx + 1, yy) = 0 { ;東移動先:道
xx += 1 ;移動先へ進む
if maze(xx, yy + 1) = 0 { ;右手(南):道
yy += 1 ;右手方向へ進む
ff = 3 ;南へ方向転換
}
} else { ;東移動先:壁
ff = 4 ;北へ方向転換
}
(maze13.hsp)
右手法によってゴールまでの道を探索する。
;maze13.hsp #define bsize 8 ;ブロックサイズ(正方形) #define bx 79 ;迷路のサイズ(マス目単位) #define by 49 #define winx1 bx * bsize ;ウィンドウサイズ #define winy1 by * bsize dim maze, bx, by ;迷路データ 0:道、1:壁 randomize buffer 1, winx1, winy1 ;迷路描画用 gosub *maze_make ;迷路作成 screen 0, winx1, winy1 ;メインウィンドウ pos 0, 0 : gcopy 1, 0, 0, winx1, winy1 ;迷路画像コピー gosub *maze_tansaku stop ;迷路探索（右手法） ----- *maze_tansaku xx = 1 : yy = 1 ;スタート ex = bx - 2 : ey = by - 2 ;ゴール ff = 1 ;進行方向、1東,2西,3南,4北 repeat if ff = 1 { ;1東 if maze(xx + 1, yy) = 0 { ;東移動先:道 xx += 1 ;移動先へ進む if maze(xx, yy + 1) = 0 { ;右手(南):道 yy += 1 ;右手方向へ進む ff = 3 ;南へ方向転換 } } else { ;東移動先:壁 ff = 4 ;北へ方向転換 } } else { if ff = 2 { ;2西 if maze(xx - 1, yy) = 0 { ;西移動先:道 xx -= 1 ;移動先へ進む if maze(xx, yy - 1) = 0 { ;右手(北):道 yy -= 1 ;右手方向へ進む ff = 4 ;北へ方向転換 } } else { ;西移動先:壁 ff = 3 ;南へ方向転換 } } else { if ff = 3 { ;3南 if maze(xx, yy + 1) = 0 { ;南移動先:道 yy += 1 ;移動先へ進む if maze(xx - 1, yy) = 0 { ;右手(西):道 xx -= 1 ;右手方向へ進む ff = 2 ;西へ方向転換 } } else { ;南移動先:壁 ff = 1 ;東へ方向転換 } } else { if ff = 4 { ;4北 if maze(xx, yy - 1) = 0 { ;北移動先:道 yy -= 1 ;移動先へ進む if maze(xx + 1, yy) = 0 { ;右手(東):道 xx += 1 ;右手方向へ進む ff = 1 ;東へ方向転換 } } else { ;北移動先:壁 ff = 2 ;西へ方向転換 } } } } } if xx = ex & yy = ey { dialog "GOAL", 0 break } color 255, 255, 255 circle xx1 * bsize + 1, yy1 * bsize + 1, xx1 * bsize + 7, yy1 * bsize + 7 color 255, 0,0 circle xx * bsize + 1, yy * bsize + 1, xx * bsize + 7, yy * bsize + 7 xx1 = xx : yy1 = yy await 10 loop return ;迷路作成（棒倒し法） ----- *maze_make ＜＜ 省略 ＞＞ return
迷路が描画され、赤い円が迷路を移動してゴールに到着する。ゴールに到着するまで多少時間がかかる。
(3) 最短距離探索
迷路探索では、袋小路で戻ったり、同じ道を通って遠回りをしている。探索したゴールまでの道から最短距離を探し出したい。移動した座標をすべて記憶しておき、同じ座標の部分を削除していく方法が考えられるが、データ量が非常に多くなりそうである。
ここでは、迷路データの配列mazeと同じ大きさの配列tmazeを用意して、マス目に来た回数をカウントし、カウント数の少ないマス目をたどって最短距離を求めることにする。
プログラムでは、コメントの「○○○へ進む」のあとに回数をカウントする式を追加する。ゴールまでたどり着いたら、スタートから東西南北の座標のカウント数を調べ少ない方向に進む。
(maze14.hsp)
ゴールまで最短距離の道を探索する。
;maze14.hsp #define bsize 8 ;ブロックサイズ(正方形) #define bx 79 ;迷路のサイズ(マス目単位) #define by 49 #define winx1 bx * bsize ;ウィンドウサイズ #define winy1 by * bsize dim maze, bx, by ;迷路データ 0:道、1:壁 dim tmaze, bx, by ;探索用 randomize buffer 1, winx1, winy1 ;迷路描画用 gosub *maze_make ;迷路作成 screen 0, winx1, winy1 ;メインウィンドウ pos 0, 0 : gcopy 1, 0, 0, winx1, winy1 ;迷路画像コピー gosub *maze_tansaku stop ;迷路探索（右手法） ----- *maze_tansaku ＜＜ 省略 ＞＞ color 255, 255, 255 circle xx1 * bsize + 1, yy1 * bsize + 1, xx1 * bsize + 7, yy1 * bsize + 7 color 255, 0,0 circle xx * bsize + 1, yy * bsize + 1, xx * bsize + 7, yy * bsize + 7 xx1 = xx : yy1 = yy await 10 loop ;最短距離探索 xx = 1 : yy = 1 ;スタート repeat color 255, 0, 0 circle xx * bsize + 1, yy * bsize + 1, xx * bsize + 7, yy * bsize + 7 ;マーク min = 9 ;最小値用 if tmaze(xx + 1, yy) < min & tmaze(xx + 1, yy) ! 0 { min = tmaze(xx + 1, yy) ff = 1 ;東へ進む } if tmaze(xx - 1, yy) < min & tmaze(xx - 1, yy) ! 0 { min = tmaze(xx - 1, yy) ff = 2 ;西へ進む } if tmaze(xx, yy + 1) < min & tmaze(xx, yy + 1) ! 0 { min = tmaze(xx, yy + 1) ff = 3 ;南へ進む } if tmaze(xx, yy - 1) < min & tmaze(xx, yy - 1) ! 0 { min = tmaze(xx, yy - 1) ff = 4 ;北へ進む } tmaze(xx, yy) = 0 if ff = 1 : xx += 1 ;東へ if ff = 2 : xx -= 1 ;西へ if ff = 3 : yy += 1 ;南へ if ff = 4 : yy -= 1 ;北へ if xx = ex & yy = ey { color 255, 0,0 circle xx * bsize + 1, yy * bsize + 1, xx * bsize + 7, yy * bsize + 7 ;マーク dialog "GOAL", 0 break } await 10 loop return ;迷路作成（棒倒し法） ----- *maze_make ＜＜ 省略 ＞＞ return
右手法による探索が終わると、赤い円で最短経路が表示される。
探索処理に2カ所あるawait 10をawait 0に変更すると早くなる。
最初の3行の値を変更して、いろいろなサイズの迷路が作れることを確認せよ。
#define bsize 8 ;ブロックサイズ(正方形)
#define bx 79 ;迷路のサイズ(マス目単位)
#define by 49
迷路のサイズは5以上の奇数にすること。
| 迷路・ゲーム制作 | |
| 2007 © Hiroshi Masuda | |