第65回 プログラミングについて『迷路を通ろう！（その２）』
今回も前回に続いて迷路プログラムを作っていきましょう。
前回紹介したプログラムのリストです。
/* ヘッダーファイルのインクルード */
#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() を先に紹介します。
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');
}
}
}
}
特に難しいところはありませんが、壁を # で、ドア（入口、出口）を O、決定した経路を . で表示することにしてあります。この関数で使用している move_cursor()は４6回目に説明してあるもので、指定した位置にカーソルを移動させます。
move_cursor(x,y)
int x,y;
{
printf("%c[%d;%dH",0x1b,y,x);
fflush(stdout);
}
継ぎはドア（入口、出口）を設定する関数 set_door() です。この関数はちょっと面倒です。行なっていることは、set_frame() 関数でマトリクスの周辺に作った壁に入口と出口を作ることです。こう説明するとすごく難しいようですが、簡単に言うと、マトリクスの周辺のどこかの要素に、DOOR1 と DOOR2 の値を代入することです。基本的にはこれだけなのですが、その他にも行なっていることがあります。
１つは、迷路を作成する関数 make_maze()で計算が楽になるように、ドアの両脇に壁を作っています。下の図のようにドア O の両脇に１つずつ壁を作っておきます。
#####O#############
# # # #
# #
# #
# #
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() は、次の経路検索開始位置を保持する rout_data リストに新しい検索位置を追加するものです。
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;
}
特に難しい内容の関数ではありませんが、rout_data_strct 構造体は削除を行ないやすいように双方向リストにしてあり、リストの末尾にではなく先頭に追加を行ないます。
次は迷路を作成する関数です。この関数は急いで作成したので、あまり参考にはならないとは思いますが、とりあえず迷路ができます。すごく面倒な計算をしているようですが、やっていることはごく単純なもので、関数 rand() でＸとＹの座標値を取得してその位置に壁を作っていいのか否かを判断する関数 is_enable_add_wall() が 0 以外の値を返してきたときにそのマトリクスの要素に値 WALL を代入しているだけです。何度か試して迷路らしくなるようにしているだけですので、実験される方はこの関数は適当に変更してみて下さい。
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() がどのように判断しているのかです。この関数は下の図のように指定された点Ｐの周辺に何もないときには１を返します（図１）。周辺に壁が１つあるときには、上下左右のときにのみ２を返します（図２）。周辺に壁が２つあるときには、壁が並んでいるときにのみ３を返します（図３）。周辺に壁が３つあるときには、壁が１列に並んでいるときにのみ４を返します（図４）。それ以外のときには０を返します。
このようにすることで、どんなにランダムに壁を発生させようとしても経路は必ず存在するように迷路を作ることができます。
・・・
・Ｐ・
・・・
図１
・＃・ ・・・ ・・・ ・・・
・Ｐ・ ・Ｐ＃ ・Ｐ・ ＃Ｐ・
・・・ ・・・ ・＃・ ・・・
図２
＃＃・ ・＃＃ ・・＃ ・・・ ・・・ ・・・ ・・・ ＃・・
・Ｐ・ ・Ｐ・ ・Ｐ＃ ・Ｐ＃ ・Ｐ・ ・Ｐ・ ＃Ｐ・ ＃Ｐ・
・・・ ・・・ ・・・ ・・＃ ・＃＃ ＃＃・ ＃・・ ・・・
図３
＃＃＃ ・・＃ ・・・ ＃・・
・Ｐ・ ・Ｐ＃ ・Ｐ・ ＃Ｐ・
・・・ ・・＃ ＃＃＃ ＃・・
図４
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;
}
また長くなってしまいましたので、続きは次回にしましょう。
