第66回 プログラミングについて『迷路を通ろう！（その3）』
今回も前回に続いて迷路プログラムを作っていきましょう。
前回までに紹介したプログラムのリストです。
/* ヘッダーファイルのインクルード */
#include <stdio.h>
#include <sys\timeb.h>
#include <time.h>
#include <stdlib.h>
#include <malloc.h>
/* 動的なメモリの確保／解放を行なうマクロ */
#define NEW(type,element) (type *)malloc(sizeof(type)*(element))
#define DELETE(addr) free(addr)
/* マトリクス（迷路）のサイズ */
#define XSIZE 78
#define YSIZE 22
/* マトリクスの各要素に設定する値 */
#define ROUT1 1 /* 経路探索時の印１に使用 */
#define ROUT2 2 /* 経路探索時の印２に使用 */
#define FIXED 3 /* 決定した経路に使用 */
#define DOOR1 4 /* 入口 */
#define DOOR2 5 /* 出口 */
#define WALL 6 /* 壁（障害物）*/
/* マトリクス */
char matrix[XSIZE+1][YSIZE+1];
/* 経路探索時に使用します */
struct rout_data_strct{
int x,y;
struct rout_data_strct *prev,*next;
};
struct rout_data_strct *rout_data=NULL;
main()
{
clear_screen(); /* 画面の消去 */
initialize_random(); /* ランダム関数の初期化 */
set_frame(); /* マトリクスの周辺に壁を設定する */
set_door(); /* 入口、出口の設定 */
make_maze(); /* 迷路の作成 */
redraw_matrix(); /* 迷路の再描画 */
routing(); /* 経路の探索、決定 */
move_cursor(1,YSIZE+1);
}
clear_screen()
{
printf("%c[2J",0x1b);
fflush(stdout);
}
initialize_random()
{
struct _timeb t;
_ftime(&t);
srand(t.millitm);
}
set_frame()
{
int x,y;
for(x=1;x<=XSIZE;x++){
for(y=1;y<=YSIZE;y++){
matrix[x][y]=0;
}
}
for(x=1;x<=XSIZE;x++){
matrix[x][1 ]=WALL;
matrix[x][YSIZE]=WALL;
}
for(y=1;y<=YSIZE;y++){
matrix[1 ][y]=WALL;
matrix[XSIZE][y]=WALL;
}
}
redraw_matrix()
{
int x,y;
for(x=1;x<=XSIZE;x++){
for(y=1;y<=YSIZE;y++){
if(matrix[x][y]==WALL){
move_cursor(x,y);
putchar('#');
}
else if(matrix[x][y]==FIXED){
move_cursor(x,y);
putchar('.');
}
else if(matrix[x][y]==DOOR1
|| matrix[x][y]==DOOR2){
move_cursor(x,y);
putchar('O');
}
}
}
}
move_cursor(x,y)
int x,y;
{
printf("%c[%d;%dH",0x1b,y,x);
fflush(stdout);
}
set_door()
{
int x,y;
int drc,loop,door;
int doorx,doory;
drc=rand()%2; /* ドアを作る方向を決定します */
for(loop=0;loop<=1;loop++){
if(loop==0)door=DOOR2; /* loop==0 のときには出口を */
else door=DOOR1; /* loop==1 のときには入口を設定します */
y=rand()%(YSIZE-2)+2;
doory=y;
if(drc==0){ /* drc==0 のときには左に出口、右に入口 */
doorx=1+loop*(XSIZE-1);
matrix[1+loop*(XSIZE-1)][y ]=door; /* ドア */
matrix[2+loop*(XSIZE-3)][y-1]=WALL; /* ドアの脇の壁 */
matrix[2+loop*(XSIZE-3)][y+1]=WALL; /* ドアの脇の壁 */
}
else{ /* drc==1 のときには左に入口、右に出口 */
doorx=XSIZE-loop*(XSIZE-1);
matrix[XSIZE -loop*(XSIZE-1)][y ]=door; /* ドア */
matrix[XSIZE-1-loop*(XSIZE-3)][y-1]=WALL; /* ドアの脇の壁 */
matrix[XSIZE-1-loop*(XSIZE-3)][y+1]=WALL; /* ドアの脇の壁 */
}
}
/* 上のループの終了後、doorx,doory に入口のドアの座標値が代入されますので、その座標値を add_rout_data()関数に渡し、経路の検索開始位置とします */
add_rout_data(doorx,doory);
}
add_rout_data(x,y)
int x,y;
{
struct rout_data_strct *rtc;
rtc=NEW(struct rout_data_strct,1);
rtc->x =x;
rtc->y =y;
rtc->prev=NULL;
rtc->next=rout_data;
if(rout_data)rout_data->prev=rtc;
rout_data=rtc;
}
make_maze()
{
int xc,yc,x,y;
int i,j,k;
for(i=0;i<=20;i++){
xc=rand()%(XSIZE-2)+2;
yc=rand()%(YSIZE-2)+2;
if(is_enable_add_wall(xc,yc)==1)matrix[xc][yc]=WALL;
else i--;
}
for(i=0;i<=1000;i++){
xc=rand()%(XSIZE-2)+2;
yc=rand()%(YSIZE-2)+2;
j=is_enable_add_wall(xc,yc);
if(j>=2){
matrix[xc][yc]=WALL;
for(k=0;k<=400;k++){
x=rand()%5-2+xc;
if(x<1 || x>XSIZE)continue;
y=rand()%5-2+yc;
if(y<1 || y>YSIZE)continue;
j=is_enable_add_wall(x,y);
if(j>=2){
matrix[x][y]=WALL;
xc=x;
yc=y;
}
}
}
}
for(i=0;i<=300;i++){
xc=rand()%(XSIZE-2)+2;
yc=rand()%(YSIZE-2)+2;
if(is_enable_add_wall(xc,yc)==4)matrix[xc][yc]=WALL;
}
for(i=0;i<=100;i++){
xc=rand()%(XSIZE-2)+2;
yc=rand()%(YSIZE-2)+2;
j=is_enable_add_wall(xc,yc);
if(j>=2){
matrix[xc][yc]=WALL;
for(k=0;k<=200;k++){
x=rand()%7-3+xc;
if(x<1 || x>XSIZE)continue;
y=rand()%7-3+yc;
if(y<1 || y>YSIZE)continue;
j=is_enable_add_wall(x,y);
if(j>=2){
matrix[x][y]=WALL;
xc=x;
yc=y;
}
}
}
}
for(i=0;i<=1000;i++){
xc=rand()%(XSIZE-2)+2;
yc=rand()%(YSIZE-2)+2;
j=is_enable_add_wall(xc,yc);
if(j>=2){
matrix[xc][yc]=WALL;
for(k=0;k<=200;k++){
x=rand()%7-3+xc;
if(x<1 || x>XSIZE)continue;
y=rand()%7-3+yc;
if(y<1 || y>YSIZE)continue;
j=is_enable_add_wall(x,y);
if(j>=2){
matrix[x][y]=WALL;
xc=x;
yc=y;
}
}
}
}
}
is_enable_add_wall(x,y)
int x,y;
{
int total;
int i,j,k;
int dx[9]={-1, 0, 1, 1, 1, 0,-1,-1,-1};
int dy[9]={-1,-1,-1, 0, 1, 1, 1, 0,-1};
/* 周辺の壁の個数を取得します */
total=0;
for(i=0;i<=7;i++){
if(matrix[x+dx[i]][y+dy[i]])total++;
}
if(total==0)return total+1; /* 周辺に壁がない */
/* 周辺の壁の個数が１個 */
if(total==1){
j=0;
for(i=0;i<=7;i+=2){
if(matrix[x+dx[i]][y+dy[i]])j++;
}
if(j==0)return total+1;
}
/* 周辺の壁の個数が２個 */
if(total==2){
j=0;
for(i=0;i<=8;i++){
if(matrix[x+dx[i]][y+dy[i]]){
if(++j==2)return total+1;
}
else{
j=0;
}
}
}
/* 周辺の壁の個数が３個 */
if(total==3){
for(i=0;i<=7;i+=2){
for(j=0;j<=2;j++){
if(!matrix[x+dx[i+j]][y+dy[i+j]])break;
}
if(j>2)return total+1;
}
}
return 0;
}
最後に残っている関数 routing() を説明します。この関数は迷路探索法で経路を検索するものです。探索の開始位置はマトリクスの要素の値が DOOR1の座標で、この座標は関数 set_door() の最後に関数 add_rout_data() で rout_data リストに１つだけ設定されています。
routing()
{
struct rout_data_strct *rtc,*rtn;
int rout;
int x,y;
int found;
found=0;
rout=ROUT1;
while(!found){ /* DOOR2 に到達するまで繰返します */
/* 経路の探索は rout_data リストの先頭から順に行ないます */
rtc=rout_data;
while(rtc){
/* 関数 routine_task() に検索時にマトリクス設定する値と座標値を渡し、経路を探索させます。DOOR2 に到達したときにはその座標値が x と y に設定され、関数値が１になります */
if(routing_task(rout,rtc->x,rtc->y,&x,&y)){
found=1;
break;
}
/* 検索した座標は不要なので削除します */
rtn=rtc->next;
delete_rout_data(rtc);
rtc=rtn;
}
/* 次の検索時にマトリクスに設定する値を切り替えます */
if(rout==ROUT1)rout=ROUT2;
else rout=ROUT1;
}
/* 経路の探索が終了したら、DOOR2 の座標から逆に DOOR1 に向かって経路を決定します */
fix_rout(x,y);
}
この関数の内容は理解してもらえると思いますが、問題は関数 routing_task() です。この関数は最初に指定された座標の上下左右を検査します。このとき経路が発見できたら、その座標値の上下左右について再び検査し、経路を発見できたらその座標値を次の検索座標にするために関数 add_rout_data() で rout_data リストに追加します。また、この検査の途中で DOOR2 が発見されたら経路の探索が終了しますので、DOOR2 の座標値と、関数値１を返します。
routing_task(rout,xc,yc,xr,yr)
int rout;
int xc, yc;
int *xr,*yr;
{
static int dx[4]={ 1, 0,-1, 0};
static int dy[4]={ 0, 1, 0,-1};
int x1,y1,x2,y2;
int i,j;
for(i=0;i<=3;i++){ /* 指定された場所の周辺を調べる */
x1=xc+dx[i];
if(x1<1 || x1>XSIZE)continue;
y1=yc+dy[i];
if(y1<1 || y1>YSIZE)continue;
if(matrix[x1][y1]==0){ /* 指定された場所の周辺に空きがある */
matrix[x1][y1]=rout;
move_cursor(x1,y1); /* 画面に表示を行なう */
printf("%d",rout);
delay(0.03);
for(j=0;j<=3;j++){ /* 更にその周辺を調べる */
x2=x1+dx[j];
if(x2<1 || x2>XSIZE)continue;
y2=y1+dy[j];
if(y2<1 || y2>YSIZE)continue;
if(matrix[x2][y2]==0){ /* 空きがある */
matrix[x2][y2]=rout;
move_cursor(x2,y2); /* 画面に表示を行なう */
printf("%d",rout);
delay(0.03);
add_rout_data(x2,y2); /* この場所を次の経路検索を行なうためにrout_data リストに追加 */
}
else if(matrix[x2][y2]==DOOR2){ /* 出口に到達 */
*xr=x2;
*yr=y2;
return 1;
}
}
}
else if(matrix[x1][y1]==DOOR2){ /* 出口に到達 */
*xr=x1;
*yr=y1;
return 1;
}
}
return 0;
}
この関数で呼び出している delay() も４７回目に説明してあるもので、指定した時間遅延を行なうものです。
delay(delta)
double delta;
{
struct _timeb to,tn;
int dt;
dt=(int)(delta*1000.0);
_ftime(&to);
while(1){
_ftime(&tn);
if(tn.millitm-to.millitm>dt)break;
}
}
関数 routing() は routing_task() に検索場所指定したら、その場所はもう検索の必要はないので、関数 delete_rout_data() で rout_data からリストを削除しています。また、関数 routing_task() は経路が発見される毎に新しい検索場所を rout_data リストに追加しています。先にも説明したように、リストに追加する関数 add_rout_data() は末尾ではなく、先頭に追加していきます。このようにしているおかげでプログラムが非常にスッキリするのです。
次の図が経路を検索しているときの rout_data リスト、関数 routing() および関数routing_task() の関係です。
rout_data→位置７→位置６→位置５→位置４→位置３→位置２→位置１
↑ ↑
routing_task()が新しい routing()は検索する位置を
検索位置をリストの先頭 routing_task()に教えた後に
に追加。 このデータを消去し、次の位
置を検索位置とする。リスト
の最後を処理したら、設定す
る値を切り替えて、再びリスト
の先頭から処理を繰返す。
リストの最後に追加する方法をとるとすれば、構造体 rout_data_strct に検索時に設定する値を保持するメンバーを追加し、routing_task() が add_rout_data() に新しい位置を追加するときに、次の検索時に使用する値も指定するようにすれば、 routing() はもう少し簡単になる可能性がありますので、試してみて下さい。
関数 delete_rout_data() は次のものです。
delete_rout_data(rtc)
struct rout_data_strct *rtc;
{
if(rtc->prev==NULL)rout_data =rtc->next;
else rtc->prev->next=rtc->next;
if(rtc->next)rtc->next->prev=rtc->prev;
DELETE(rtc);
}
最後に、経路の探索が終了した後に経路を決定する関数 fix_rout() です。
fix_rout(xr,yr)
int xr,yr;
{
static int dx[4]={ 1, 0,-1, 0};
static int dy[4]={ 0, 1, 0,-1};
int x,y;
int rout;
int i;
int loop,found;
found=0;
rout =0;
while(!found){ /* 出発点が発見されるまで繰返します */
for(loop=0;loop<=1 && !found;loop++){ /* 出発点が発見されるまで経路を２つずつ検索します */
for(i=0;i<=3;i++){ /* 上下左右の４方向を検索 */
x=xr+dx[i];
if(x<1 || x>XSIZE)continue;
y=yr+dy[i];
if(y<1 || y>YSIZE)continue;
/* rout が 0 のときは目的地点の周辺を検索しているときで、最初に発見したものを rout の初期値にします*/
if(rout!=0 && matrix[x][y]==rout
|| rout==0 && matrix[x][y]==ROUT1
|| rout==0 && matrix[x][y]==ROUT2){
/* 発見した経路を新しい位置とし、その位置に値 FIXED を代入します */
xr=x;
yr=y;
rout=matrix[xr][yr];
matrix[xr][yr]=FIXED;
/* 決定した経路を表示します */
move_cursor(xr,yr);
putchar('.');
delay(0.03);
break;
}
else if(matrix[x][y]==DOOR1){ /* 出発点に到達したら終了 */
found=1;
break;
}
}
}
/* 検索する経路の値を切り替えます */
if(rout==ROUT1)rout=ROUT2;
else rout=ROUT1;
}
}
この関数もじっと見ていただけば、理解できると思います。非常に単純に記述してありますので、必ずしも最適な経路を決定する訳ではありません。できる限り折れ曲がらないようにするには、経路を発見したときには上下左右のどの方向で発見したかを記憶しておき、次の経路の検索時にその方向から検索するようにします。
プログラムのリストが長いので、全文をまとめたリストは掲載しませんが、今回のプログラムのリスト部分のみを取り出してコンパイルすれば動作しますので試してみて下さい。結構面白いので、しばらくは飽きないかと思います。
今回の迷路を通るプログラムをベースにして、Ｘウインドウを使って３次元的に迷路を実際に歩いているようなゲームも、ＵＮＩＸ上でも以前作ったことがありますが、紹介するスペースがないので残念です。
そのうちには『テトリス』ゲームでも連載してみようかと考えていますので、楽しみにしていて下さい。
それではまた次回。
