迷路生成

たびたび質問して申し訳ありません。
迷路生成を穴掘り法を使って作ろうと思ったのですが
うまくいきません。
ROAD=0,WALL=1
/*迷路の構造体*/
typedef struct Mazestruct{
/*迷路のサイズ（size[0]:横のサイズsize[1]:縦のサイズ）*/
int size[2];
/*スタートの座標(st[0]:横座標st[1]:縦座標(一番左上を(0,0))*/
int st[2];
/*ゴールの座標(goal[0]:横座標goal[1]:縦座標*/
int goal[2];
/*壁と通路のデータ*/
int maze_d[wid_max][len_max];
}Mazestruct;
void wall_make(int x,int y,Mazestruct *maze)
{
int x1,y1,px,py;
int gx[2]={1,-1},gy[2]={1,-1};

while(maze->maze_d[x][y]==ROAD){
while(1){
x1=x;
y1=y;
while(1){
px=rand()%2;
py=rand()%2;
if(maze->maze_d[x1+gx[px]*2][y1+gy[py]*2]==WALL){
maze->maze_d[x1+gx[px]][y1+gy[py]]=maze->maze_d[x1+gx[px]*2][y1+gy[py]*2]=ROAD;
x1=x1+gx[px]*2;
y1=y1+gy[py]*2;
}
else if(maze->maze_d[x1+1][y1]==ROAD&&
maze->maze_d[x1-1][y1]==ROAD&&
maze->maze_d[x1][y1+1]==ROAD&&
maze->maze_d[x1][y1-1]==ROAD){
goto quit;
}
}
}
}
quit:;
}
(px,py)を回転させるというところと
四方向をチェックするところをどのようにしたらよいか分りません。
回転させる方法が分らないので乱数をもう一度得るようにして四方向のチェックに関しては
四方向が道ならループをやめるようにしました。

No.1 ベストアンサー 回答者： togino 回答日時： 2004/07/19 03:32

すごく頑張っているのがよく分かるのですが、

少々ebinamori さんには荷が重い課題なのかもしれません・・・

> (px,py)を回転させるというところ

この意味が分かりませんでした。
ただプログラムをみて気になったのは

> int gx[2]={1,-1},gy[2]={1,-1};
> px=rand()%2; py=rand()%2;
> maze_d[x1+gx[px]*2][y1+gy[py]*2] == WALL

「右上」「左上」「右下」「左下」の４方向に
なっちゃうのでは（汗）

４方向は (0,1) (1,0) (0,-1) (-1,0) なので

int gx[4]={0,1,0,-1},gy[4]={1,0,-1,0};
direct = rand() % 4;
maze_d[x1+gx[direct]*2][y1+gy[direct]*2] == WALL

じゃないのかなぁ・・・と。
# プログラムを見ても、何をしたがってるのだろう？
# って首をかしげちゃう所が多いので、僕が誤解している
# 可能性も多いですが・・・

---
http://revy-hsp.hp.infoseek.co.jp/zakki/hori/
にありますが、「穴掘り法」

1.掘る方向は毎回ランダム
2.必ず、二マス掘る
3.二マス先が既に掘られていた場合、その方向へ掘る事はできない。
4.どの方向へも掘る事ができないなら、前行った場所を戻る。

と書いてあります。このと～りにプログラムすれば
いいだけなんですがね。
（難しいのは「前行った場所を戻る」の所でしょう）

http://flex.ee.uec.ac.jp/japanese/riron/tool/bui …
にもアルゴリズムが書いてありますね。

よ～く読んで頑張ってください。

参考URL：http://flex.ee.uec.ac.jp/japanese/riron/tool/bui …

この回答へのお礼

何とか作ることができました。

というかこれも奇数のサイズの迷路しか作れませんでした・・・(涙

こうなったら壁を一つ作るごとに解探索をして
いくしかないのかなと思っています。

本当にご迷惑おかけしました。
有難うございました。

お礼日時：2004/07/19 14:40

No.2 回答者： Jitta 回答日時： 2004/07/20 23:01

前回の、本当に解が求まりました？「ゴールまで行けるか？」を出すだけなら、あれでもいいのでしょうが。

　今回のですが、まず、設計しましょうよ。設計したら、コメントで「何をする」というのを埋めましょう。すると、ソースを組み立てながらでも、「しなければいけないこと」を見失わずにすみます。

　それで、奇数偶数ということですが、１つずつ進んでいくとですね、、、

□道
■壁


■□■■■
■□□■■
■□□□■
■■■□■


ってことにもなりますよ(^^; これの予防策も考えなければなりません。「２つ進む」というのは、１つの予防策なんですね。だから、本当に奇数も偶数も対応しなければならないのか、というところを、もう一度考え直すべき、と思います。



　それから、迷路の座標ですが、
typedef struct POINT {
　int x;
　int y;
} Point;

typedef enum MAZEWALL {
　NODEF = -1,
　ROAD = 0,
　WALL = 1
} MazeWall;

typedef struct MAZE {
　Point size;
　Point start;
　Point goal;
　MazeWall wall[width_max][height_max];
} Maze;

かなぁ？
＃＃＃＃＃
　やっぱり、２０年近く前に作ったプログラムは、きれいさっぱり忘れてるなぁ(^^;　もし残っていても、５インチフロッピーだし。。。

この回答へのお礼

御礼が遅くなり申し訳ありませんでした。

前回のは解があることが確かめられる事が
最低限の条件だったので良しとしました。
最短経路を求めるというは解があることが分っているならば
もとめる事ができるやつを作りました。

私が作った迷路生成のやつは奇数×奇数しかできないんですよね。

期限があったので仕方なく
乱数を一つ得るごとに解探索するという方法を
とりました。
出来上がりは見事に迷路っぽくありません。

迷路に関するアルゴリズムについて集中的に
書いてある本でも有ればよいのですが見つからず
残念です。
この夏休みの間に達成したいと思います。

ほんとに何度も何度もご迷惑をおかけして
申し訳ありませんでした。

お礼日時：2004/07/26 03:39