C言語で穴掘り法の迷路を作っているのですが…

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら　　※コードを貼り付ける場合は [code] と [/code] で囲って下さい。詳しくはこちら
閉鎖
ASH

C言語で穴掘り法の迷路を作っているのですが…

#1

投稿記事 by ASH » 16年前

今年C言語を初めて習っている私が、10月29日までにC言語の再帰を使って穴掘り方の迷路を作らないといけません。
ですが再帰自体があまり理解できず、取り敢えず作ってみたんですが…
#include<stdio.h>
#include<time.h>
#include<stdlib.h>

#define UP 0
#define RIGHT 1
#define DOWN 2
#define LEFT 3
#define ROAD 4
#define WALL 5
#define SMAX 17
#define ENTRANCE 6
#define EXIT 7

void init();
void randnum();
void go();
void stop();
int exca(int);

int x, y, xx, yy, dir, px, py;
char M[SMAX][SMAX];

int main(void){

	init();

	while(M[y][x] != EXIT){
		randnum();
		xx = x + px * 2;
		yy = y + py * 2;
		if(M[yy][xx] == WALL) exca(dir);
		else if(M[yy][xx] == ROAD) stop(dir);
	}

	for(y = 0; y < SMAX; y++){			// 配列の表示
		for(x = 0; x < SMAX; x++){
			if(M[y][x] == ENTRANCE) printf("▽");
			else if(M[y][x] == EXIT) printf("▽");
			else if(M[y][x] == ROAD) printf("　");
			else if(M[y][x] == WALL) printf("■");
		}
		printf("\n");
	}

	return 0;
}





void init(){
	for(y = 0; y < SMAX; y++){			// 配列の初期化
		for(x = 0; x < SMAX; x++){
			M[y][x] = WALL;				// 全部『壁』のフラグを立てる。
			M[0][x] = ROAD;				// 一番上の横1行を『道』のフラグを立てる。
			M[SMAX - 1][x] = ROAD;		// 一番下の横1行を『道』のフラグを立てる。
			M[y][0] = ROAD;				// 一番左の縦1列を『道』のフラグを立てる。
			M[y][SMAX - 1] = ROAD;		// 一番右の縦1列を『道』のフラグを立てる。
			M[1][2] = ENTRANCE;			// スタート位置のフラグを立てる。
			M[SMAX-2][SMAX-3] = EXIT;	// ゴール位置のフラグを立てる。
		}
	}
	x = 2;
	y = 2;
	px = 0;
	py = 0;
	M[y][x] = ROAD;		// 起点
}

void randnum(){
	srand((unsigned)time(NULL));								// 乱数
	dir = rand();
	dir = dir % 4;
	go(dir);
}

int exca(dir){
	if((dir == UP) || (dir == DOWN)){					// 穴掘り作業
		M[yy][xx] = ROAD;
		M[yy - 1][xx] = ROAD;
		y = yy;
		x = xx;
	}
	else if(dir == RIGHT){
		M[yy][xx] = ROAD;
		M[yy][xx - 1] = ROAD;
		y = yy;
		x = xx;
	}
	else{
		M[yy][xx] = ROAD;
		M[yy][xx - 1] = ROAD;
		y = yy;
		x = xx;
	}
}

void stop(dir){									// 2マス先が『道』だったので、計算されたyy・xxの添え字を戻す。
	yy = y;
	xx = x;
	randnum();
	exca(dir);
}

void go(dir){									// 2マス先の値
	if(dir == UP) py = -1;
	else if(dir == RIGHT) px = 1;
	else if(dir == DOWN) py = 1;
	else px = -1;
}


というソースを作りました。
一応、コンパイルは出来るのですが…いざ起動させてみよう！とすると表示されません。
全体的におかしいと思いますが、『どこが どうで 動かない』のかが分かりません。

親切な回答をお願いします。
ページトップ
conio

Re:C言語で穴掘り法の迷路を作っているのですが…

#2

投稿記事 by conio » 16年前 

まず、関数の引数がおかしいです。型を指定してください。
-----------------------------------------------------------------
int exca(int dir){
	if((dir == UP) || (dir == DOWN)){	// 穴掘り作業
		M[yy][xx] = ROAD;
		M[yy - 1][xx] = ROAD;
		y = yy;
		x = xx;
	}
	else if(dir == RIGHT){
		M[yy][xx] = ROAD;
		M[yy][xx - 1] = ROAD;
		y = yy;
		x = xx;
	}
	else{
		M[yy][xx] = ROAD;
		M[yy][xx - 1] = ROAD;
		y = yy;
		x = xx;
	}
}

void stop(int dir){	// 2マス先が『道』だったので、計算されたyy・xxの添え字を戻す。
	yy = y;
	xx = x;
	randnum();
	exca(dir);
}

void go(int dir){	// 2マス先の値
	if(dir == UP) py = -1;
	else if(dir == RIGHT) px = 1;
	else if(dir == DOWN) py = 1;
	else px = -1;
}
-----------------------------------------------------------------

また、go();とstop();に関しては、プロトタイプ宣言と、実際の引数が一致していません。
int型を渡したいのであれば、intとしてください。
----------------------------------------
void go();　　→　void go(int);
void stop();　　→　void stop(int);
----------------------------------------

あと、exca();はint型の戻り値があるのにも拘らず、return文がありません。
とりあえず、int型の変数などを戻り値として渡すようにしてください。
（具体的にどんな情報を渡そうとしているのかは不明ですが）

それとinit();の内部についてですが、M[1][2] = ENTRANCE;みたいに
固定された情報はfor文の中に入れる必要はありません。
現状では、一度でいいのに　代入を数百回以上繰り返してます。

そして下記の部分ですが、わざわざ変数を使う必要は無いのではないでしょうか？
-------------------------------------
x = 2;
y = 2;
px = 0;
py = 0;
M[y][x] = ROAD;		// 起点
-------------------------------------
↓これでよいと思います。
-------------------------------------
px = 0;
py = 0;
M[2][2] = ROAD;		// 起点
-------------------------------------


init();の内部はこんな感じになるかな、と。
--------------------------------------------------------------
for(y = 0; y < SMAX; y++){			// 配列の初期化
    for(x = 0; x < SMAX; x++){
        if( y % (SMAX - 1) == 0 || x % (SMAX - 1) == 0)
            M[y][x] = ROAD;            //周辺は道にする。
        else
            M[y][x] = WALL;
    }
}
M[1][2] = ENTRANCE;	// スタート位置のフラグを立てる。
M[SMAX-2][SMAX-3] = EXIT;	// ゴール位置のフラグを立てる。
M[2][2] = ROAD;		// 起点
px = 0;
py = 0;
--------------------------------------------------------------

自分の環境ではコンパイルすら通らなかったので修正をお願いします。

【追記】
とりあえず、完成させました。画像も添付しておきます。
実行結果はこんな感じでよろしいでしょうか？
ページトップ
box

Re:C言語で穴掘り法の迷路を作っているのですが…

#3

投稿記事 by box » 16年前

乱数の初期化は、「プログラム全体の中で」一度だけにしましょう。
ページトップ
ASH

Re:C言語で穴掘り法の迷路を作っているのですが…

#4

投稿記事 by ASH » 16年前

conioさんの画像の処理であっています。
そんな感じに出します。
ソース中の赤字は変更した場所です。
#include<stdio.h>
#include<time.h>
#include<stdlib.h>

#define UP 0
#define RIGHT 1
#define DOWN 2
#define LEFT 3
#define ROAD 4
#define WALL 5
#define SMAX 17
#define ENTRANCE 6
#define EXIT 7

void init();
void randnum();
void go(int);
void stop(int);
int exca(int);

int x, y, xx, yy, dir, px, py,p;
char M[SMAX][SMAX];

int main(void){
	
	srand((unsigned)time(NULL));
	
	init();

	while(M[y][x]　!= EXIT){
		randnum();
		go(dir);
		xx = x + px * 2;
		yy = y + py * 2;
		if((M[yy][xx] == WALL)) exca(dir);
		//else if(M[yy][xx] == ROAD) stop(dir);いらない気がしてきましたので、一応コメント
	}

	for(y = 0; y < SMAX; y++){			// 配列の表示
		for(x = 0; x < SMAX; x++){
			if(M[y][x] == ENTRANCE) printf("▽");
			else if(M[y][x] == EXIT) printf("▽");
			else if(M[y][x] == ROAD) printf("　");
			else if(M[y][x] == WALL) printf("■");
		}
		printf("\n");
	}
	return 0;
}





void init(){
	for(y = 0; y < SMAX; y++){			// 配列の初期化
		for(x = 0; x < SMAX; x++){
			if( y % (SMAX - 1) == 0 || x % (SMAX - 1) == 0)
				M[y][x] = ROAD;            //周辺は道にする。
			else
				M[y][x] = WALL;
		}
	}
	M[1][2] = ENTRANCE;					// スタート位置のフラグを立てる。
	M[SMAX-2][SMAX-3] = EXIT;			// ゴール位置のフラグを立てる。
	M[2][2] = ROAD;						// 起点
	x = 2;
	y = 2;
	px = 0;
	py = 0;
}勝手ながらお借りしました。

void randnum(){											// 乱数
	dir = rand();
	dir = dir % 4;

}

int exca(int dir){
	if(((dir == UP)) || (dir == DOWN)){					// 穴掘り作業
		M[yy][xx] = ROAD;
		M[yy - 1][xx] = ROAD;
		y = yy;
		x = xx;
	}
	else if(dir == RIGHT){
		M[yy][xx] = ROAD;
		M[yy][xx - 1] = ROAD;
		y = yy;
		x = xx;
	}
	else{
		M[yy][xx] = ROAD;
		M[yy][xx - 1] = ROAD;
		y = yy;
		x = xx;
	}
	return 0;
}

void stop(int dir){									// 2マス先が『道』だったので、計算されたyy・xxの添え字を戻す。
	yy = y;
	xx = x;
}いらない気がしてきました。

void go(int dir){									// 2マス先の値
	if(dir == UP) py = -1;
	else if(dir == RIGHT) px = 1;
	else if(dir == DOWN) py = 1;
	else px = -1;
}
-------------------------------------------------------

と、今のところのソースになっています。


while(M[y][x] != EIXT){
処理
}


このwhileの条件文がおかしいと思いますが、表示されません。
何故でしょうか?

------------------------------------------------------------

boxさん、助言ありがとうございます。
ページトップ
conio

Re:C言語で穴掘り法の迷路を作っているのですが…

#5

投稿記事 by conio » 16年前 

条件文の前に、致命的な問題があります。
再帰関数が使われていない事です。
（while文で、特定の関数を繰り返し実行するものは再帰関数ではありません。）


再帰関数とは、ある関数の中で、その関数自身を呼び出すというものです。
（正確には、自分自身と同じ関数を「別途呼び出す」、というもの）

例えを出すと、下記の様なものです。
--------------------------------------------------------------------
#include<stdio.h>
void Test(int Num)
{
	printf("%dです。\n", Num);

	if(Num > 0)
		Test(Num - 1);
}
int main(void){
    Test(5);

    return 0;
}
--------------------------------------------------------------------
この場合は、まず5を仮引数としてTest関数を呼び出します。

すると「5です。」と表示したあと、if(5　>　0)でif文が成立し、
Test(4)という風に、Test関数の中でまたTest関数を呼び出しています。

その後も同じように
Test(3)、Test(2)、Test(1)という風に呼び出されます。

最後は、Test(0)で呼び出されたときにif(0 > 0)が成立しなくなるため、
Test()の呼び出しがされる事は無くなり、プログラムは終了します。
（ちゃんと条件を指定しなければ永遠に呼び出し続けるので気をつけてください）


再帰は、なかなか理解しにくいものだと思うので、簡単なヒントを。
------------------------------------------------------------------------
#include<stdio.h>
#include<time.h>
#include<stdlib.h>

#define UP 0
#define RIGHT 1
#define DOWN 2
#define LEFT 3
#define ROAD 4
#define WALL 5
#define SMAX 17
#define ENTRANCE 6
#define EXIT 7

void init();
void Draw(void);

char M[SMAX][SMAX];
int x,y;


void Test(int x, int y){
    if(M[y + 2][x] != ROAD){
        M[y + 2][x] = M[y + 1][x] = ROAD;
        Test(x, y + 2);
    }
}

int main(void){
    init();
    Test(2,2);
    Draw();
    
    return 0;
}

void init(){
	for(y = 0; y < SMAX; y++){			// 配列の初期化
		for(x = 0; x < SMAX; x++){
			if( y % (SMAX - 1) == 0 || x % (SMAX - 1) == 0)
				M[y][x] = ROAD;
			else
				M[y][x] = WALL;
		}
	}
	M[1][2] = ENTRANCE;			// スタート位置のフラグを立てる。
	M[SMAX-2][SMAX-3] = EXIT;	// ゴール位置のフラグを立てる。
	M[2][2] = ROAD;		// 起点
}

void Draw(void){
	for(y = 0; y < SMAX; y++){
		for(x = 0; x < SMAX; x++){
			if(M[y][x] == WALL)
				printf("■");
			else if(M[y][x] == ROAD)
				printf("×");
			else if(M[y][x] == EXIT)
				printf("◎");
			else if(M[y][x] == ENTRANCE)
				printf("Ｓ");
		}
		puts(" ");
	}
}
------------------------------------------------------------------------
このプログラムは、「yが２つ下の値がROADで無ければ、ずっとWALLをROADにし続ける」という状態になってます。
なので、実行結果はずっと下まで掘って停止した状態になっているはずです。


これを、右に掘ったり上に掘ったり、掘る方向をランダムにしたり出来るように改造してみてください。
コードは自由に引用してもらって構いませんよ（^^）
ページトップ
ASH

Re:C言語で穴掘り法の迷路を作っているのですが…

#6

投稿記事 by ASH » 16年前

度々すみません。

-----------------------------------------------
void init();
void randnum();
void check(int, int, int);
void exca(int, int, int);
void stop(int, int, int);

int x, y, dir;
char M[SMAX][SMAX];

int main(void){

	srand((unsigned)time(NULL));
	init();
	randnum();
	exca(2, 2, dir);

         ※配列の表示は省略

	return 0;
}





void init(){
	for(y = 0; y < SMAX; y++){										// 配列の初期化
		for(x = 0; x < SMAX; x++){
			if( y % (SMAX - 1) == 0 || x % (SMAX - 1) == 0)
				M[y][x] = ROAD;										//周辺は道にする。
			else
				M[y][x] = WALL;
		}
	}
	M[1][2] = ENTRANCE;												// スタート位置のフラグを立てる。
	M[SMAX-2][SMAX-3] = EXIT;										// ゴール位置のフラグを立てる。
	M[2][2] = ROAD;													// 起点
}





void randnum(){														// 乱数
	dir = rand();
	dir = dir % 4;
}





void exca(int y, int x, int dir){									// 穴掘り作業
	
	if((M[y - 2][x] != WALL) || (M[y][x + 2] != WALL) || (M[y + 2][x] != WALL) || (M[y][x - 2] != WALL)){
		if((M[y - 2][x] != WALL) && (M[y - 1][x] != ENTRANCE) && (M[y - 1][x] != M[1][x]))	M[y - 1][x] = ROAD;
		else if((M[y][x + 2] != WALL) && (M[y][x + 1] != M[y][SMAX - 2]))	M[y][x + 1] = ROAD;
		else if((M[y + 2][x] != WALL) && (M[y + 1][x] != EXIT) && (M[y + 1][x] != M[SMAX - 2][x]))	M[y + 1][x] = ROAD;
		else if((M[y][x - 2] != WALL) && (M[y][x - 1] != M[y][1]))	M[y][x - 1] = ROAD;
		
		check(y, x, dir);
	}
	
	if((dir == UP) && (M[y - 2][x] != ROAD)){
		M[y - 2][x] = ROAD;
		M[y - 1][x] = ROAD;
		randnum();
		exca(y - 2, x, dir);
	}
	else if((dir == RIGHT) && (M[y][x + 2] != ROAD)){
		M[y][x + 2] = ROAD;
		M[y][x + 1] = ROAD;
		randnum();
		exca(y, x + 2, dir);
	}
	else if((dir == DOWN) && (M[y + 2][x] != ROAD)){
		M[y + 2][x] = ROAD;
		M[y + 1][x] = ROAD;
		randnum();
		exca(y + 2, x, dir);
	}
	else if((dir == LEFT) && (M[y][x - 2] != ROAD)){
		M[y][x - 2] = ROAD;
		M[y][x - 1] = ROAD;
		randnum();
		exca(y, x - 2, dir);
	}
}





void check(int y, int x, int dir){									// 4方向チェック?
	if(M[y - 2][x] != ROAD)	dir = 0;
	else if(M[y][x + 2] != ROAD)	dir = 1;
	else if(M[y + 2][x] != ROAD)	dir = 2;
	else if(M[y][x - 2] != ROAD)	dir = 3;
	else	stop(y, x, dir);
}





void stop(int y, int x, int dir){									// 座標を増減する
	if(dir == UP)	y = y + 2;
	else if(dir == RIGHT)	x = x - 2;
	else if(dir == DOWN)	y = y - 2;
	else if(dir == LEFT)	x = x + 2;
}
--------------------------------------------------------------

と書きました。

赤字は『上下左右の2マス先が道だったら』→『かつ、1マス先が外壁じゃない時に1マス先を道にしてください。
そして check で他の方向をチェックしてみてください。』

緑字は『他の方向をチェックして、2マス先に進める方向があったら dir にその方向のフラグを入れて exca に戻ります。』
『全部方向をチェックしても進めなかったら stop に行ってください。』

青字は dir に入っている方向のフラグを見て、『上だったら y を+2してみて check に戻って確認してみてください。』


そんな風に作ったんですが、どうも私のトレースはコンパイルより悪いです。
やっぱり、全体的におかしいのでしょうか？
ページトップ
conio

Re:C言語で穴掘り法の迷路を作っているのですが…

#7

投稿記事 by conio » 16年前 

あぁ有効範囲のバグに引っ掛かっていますね。
問題なのはグローバル変数のdirと、
関数の引数としてのdir（ローカル変数）がある事です。

色々と省略してますが下記のプログラムを見てください。
---------------------------------------------------------------------

int dir;

void randnum(){														// 乱数
	dir = rand();
	dir = dir % 4;
}

void exca(int y, int x, int dir){									// 穴掘り作業
	if((dir == UP) && (M[y - 2][x] != ROAD)){
		M[y - 2][x] = ROAD;
		M[y - 1][x] = ROAD;
		randnum();
		exca(y - 2, x, dir);
	}
	else if((dir == RIGHT) && (M[y][x + 2] != ROAD)){
		M[y][x + 2] = ROAD;
		M[y][x + 1] = ROAD;
		randnum();
		exca(y, x + 2, dir);
	}
	else if((dir == DOWN) && (M[y + 2][x] != ROAD)){
		M[y + 2][x] = ROAD;
		M[y + 1][x] = ROAD;
		randnum();
		exca(y + 2, x, dir);
	}
	else if((dir == LEFT) && (M[y][x - 2] != ROAD)){
		M[y][x - 2] = ROAD;
		M[y][x - 1] = ROAD;
		randnum();
		exca(y, x - 2, dir);
	}
}
---------------------------------------------------------------------

randnum();で値の変更を行っているのはグローバル変数のdirです。
グローバル変数のdirをいくら変更したところで、仮引数のdir（ローカル変数）は変化しません。

なので、最初にexca(2, 2, 1);と呼び出せばずっと右に掘られることになりますし、
exca(2, 2, 2);と呼び出せばずっと下に掘られることになります。
（0と3の場合は、掘れないので即座に終了。）

グローバル変数は、同名のローカル変数があった場合、見えなくなるので気をつけてください。
----------------------------------------
#include<stdio.h>

int x = 5;
int main(void){
   int x = 3;
   printf("%dです。\n", x);
   return 0;
}
----------------------------------------
この場合は、ローカル変数のxによってグローバル変数のxが隠されて見えなくなります。
よって、実行結果は「3です。」となります。


とりあえず、ランダムな方向に進むサンプルを作っておきます。
このプログラムは、
-------------------------------------
最初は右から掘るように固定されている
掘れなくなった時点ですぐ止まる
-------------------------------------
といった欠点などがあるので、これを改善してみてもいいですし、
参考にするだけで独自の方法を用いて実装していっても良いでしょう。
-----------------------------------------------------------------------
#include<stdio.h>
#include<time.h>
#include<stdlib.h>

#define UP 0
#define RIGHT 1
#define DOWN 2
#define LEFT 3
#define ROAD 4
#define WALL 5
#define SMAX 17
#define ENTRANCE 6
#define EXIT 7

void init();
void Draw(void);

int dir,x,y;
char M[SMAX][SMAX];

int Check(int y, int x, int dir){
	int result = 0;
	switch(dir){
		case 0:
				if(M[y - 2][x] != ROAD)
					result = 1;
				break;
		case 1:
				if(M[y][x + 2] != ROAD)
					result = 1;
				break;
		case 2:
				if(M[y + 2][x] != ROAD)
					result = 1;
				break;
		case 3:
				if(M[y][x - 2] != ROAD)
					result = 1;
				break;
		default:break;
	}
	return result;
}
void exca(int y, int x, int dir){									// 穴掘り作業
	if((dir == UP) && (M[y - 2][x] != ROAD)){
		M[y - 2][x] = ROAD;
		M[y - 1][x] = ROAD;
		dir = rand() % 4;
		if(Check(y - 2, x, dir))
			exca(y - 2, x, dir);
	}
	else if((dir == RIGHT) && (M[y][x + 2] != ROAD)){
		M[y][x + 2] = ROAD;
		M[y][x + 1] = ROAD;
		dir = rand() % 4;
		if(Check(y, x + 2, dir))
			exca(y, x + 2, dir);
	}
	else if((dir == DOWN) && (M[y + 2][x] != ROAD)){
		M[y + 2][x] = ROAD;
		M[y + 1][x] = ROAD;
		dir = rand() % 4;
		if(Check(y + 2, x, dir))
			exca(y + 2, x, dir);
	}
	else if((dir == LEFT) && (M[y][x - 2] != ROAD)){
		M[y][x - 2] = ROAD;
		M[y][x - 1] = ROAD;
		dir = rand() % 4;
		if(Check(y, x - 2, dir))
			exca(y, x - 2, dir);
	}
}

int main(void){
	srand((unsigned int)time(NULL));

	init();
	exca(2,2,1);
	Draw();

	return 0;
}

void init(){
	for(y = 0; y < SMAX; y++){			// 配列の初期化
		for(x = 0; x < SMAX; x++){
			if( y % (SMAX - 1) == 0 || x % (SMAX - 1) == 0)
				M[y][x] = ROAD;
			else
				M[y][x] = WALL;
		}
	}
	M[1][2] = ENTRANCE;			// スタート位置のフラグを立てる。
	M[SMAX-2][SMAX-3] = EXIT;	// ゴール位置のフラグを立てる。
	M[2][2] = ROAD;		// 起点
}

void Draw(void){
	for(y = 0; y < SMAX; y++){
		for(x = 0; x < SMAX; x++){
			if(M[y][x] == WALL)
				printf("■");
			else if(M[y][x] == ROAD)
				printf("×");
			else if(M[y][x] == EXIT)
				printf("◎");
			else if(M[y][x] == ENTRANCE)
				printf("Ｓ");
		}
		puts(" ");
	}
}
-----------------------------------------------------------------------
ページトップ
ASH

Re:C言語で穴掘り法の迷路を作っているのですが…

#8

投稿記事 by ASH » 16年前

あの、なんか出来たような出来てないような感じですけど・・・。

こんなソースでも良いんでしょうか？


--------------------------------------------------------------------------------------


#include<stdio.h>
#include<time.h>
#include<stdlib.h>

#define UP 0
#define RIGHT 1
#define DOWN 2
#define LEFT 3
#define ROAD 4
#define WALL 5
#define SMAX 17
#define ENTRANCE 6
#define EXIT 7

void init();
void randnum();
void check(int, int, int);
void exca(int, int, int);
void stop(int, int, int);

int x, y, dir;
char M[SMAX][SMAX];

int main(void){

	srand((unsigned)time(NULL));
	init();
	randnum();
	exca(2, 2, dir);

	for(y = 0; y < SMAX; y++){										// 配列の表示
		for(x = 0; x < SMAX; x++){
			if(M[y][x] == ENTRANCE) printf("▽");
			else if(M[y][x] == EXIT) printf("▽");
			else if(M[y][x] == ROAD) printf("　");
			else if(M[y][x] == WALL) printf("■");
		}
		printf("\n");
	}
	return 0;
}





void init(){
	for(y = 0; y < SMAX; y++){										// 配列の初期化
		for(x = 0; x < SMAX; x++){
			if( y % (SMAX - 1) == 0 || x % (SMAX - 1) == 0)
				M[y][x] = ROAD;										//周辺は道にする。
			else
				M[y][x] = WALL;
		}
	}
	M[1][2] = ENTRANCE;												// スタート位置のフラグを立てる。
	M[SMAX-2][SMAX-3] = EXIT;										// ゴール位置のフラグを立てる。
	M[2][2] = ROAD;													// 起点
}





void randnum(){														// 乱数
	dir = rand();
	dir = dir % 4;
}





void exca(int y, int x, int dir){									// 穴掘り作業
	
	
	
	if((dir == UP) && (M[y - 2][x] != ROAD)){
		M[y - 2][x] = ROAD;
		M[y - 1][x] = ROAD;
		dir = rand() % 4;
		exca(y - 2, x, dir);
	}
	else if((dir == RIGHT) && (M[y][x + 2] != ROAD)){
		M[y][x + 2] = ROAD;
		M[y][x + 1] = ROAD;
		dir = rand() % 4;
		exca(y, x + 2, dir);
	}
	else if((dir == DOWN) && (M[y + 2][x] != ROAD)){
		M[y + 2][x] = ROAD;
		M[y + 1][x] = ROAD;
		dir = rand() % 4;
		printf("%d - %d [%d]\n",y,x,dir);
		exca(y + 2, x, dir);
	}
	else if((dir == LEFT) && (M[y][x - 2] != ROAD)){
		M[y][x - 2] = ROAD;
		M[y][x - 1] = ROAD;
		dir = rand() % 4;
		exca(y, x - 2, dir);
	}

	if((M[y - 2][x] != WALL) || (M[y][x + 2] != WALL) || (M[y + 2][x] != WALL) || (M[y][x - 2] != WALL)){
		if((M[y - 2][x] != WALL) && (M[y - 1][x] != ENTRANCE) && (M[y - 1][x] != M[1][x]))	M[y - 1][x] = ROAD;
		else if((M[y][x + 2] != WALL) && (M[y][x + 1] != M[y][SMAX - 2]))	M[y][x + 1] = ROAD;
		else if((M[y + 2][x] != WALL) && (M[y + 1][x] != EXIT) && (M[y + 1][x] != M[SMAX - 2][x]))	M[y + 1][x] = ROAD;
		else if((M[y][x - 2] != WALL) && (M[y][x - 1] != M[y][1]))	M[y][x - 1] = ROAD;
		
		check(y, x, dir);
	}
}





void check(int y, int x, int dir){									// 4方向チェック?
	if(M[y - 2][x] != ROAD){
		dir = 0;
		exca(y, x, dir);
	}
	else if(M[y][x + 2] != ROAD){
		dir = 1;
		exca(y, x, dir);
	}
	else if(M[y + 2][x] != ROAD){
		dir = 2;
		exca(y, x, dir);
	}
	else if(M[y][x - 2] != ROAD){
		dir = 3;
		exca(y, x, dir);
	}
	
	else	stop(y, x, dir);
}





void stop(int y, int x, int dir){									// 座標を増減する
	if(dir == UP)			y = y + 2;
	else if(dir == RIGHT)	x = x - 2;
	else if(dir == DOWN)	y = y - 2;
	else if(dir == LEFT)	x = x + 2;
}



---------------------------------------------------


ちなみに穴掘り作業 exca の
if((dir == UP) && (M[y - 2][x] != ROAD)){
		M[y - 2][x] = ROAD;
		M[y - 1][x] = ROAD;
		randnum();
		exca(y - 2, x, dir);
	}

を↓

if((dir == UP) && (M[y - 2][x] != ROAD)){
		M[y - 2][x] = ROAD;
		M[y - 1][x] = ROAD;
		dir = rand() % 4;
		exca(y - 2, x, dir);
	}


に、しただけなんですけど・・・。
ページトップ
conio

Re:C言語で穴掘り法の迷路を作っているのですが…

#9

投稿記事 by conio » 16年前 

以前　説明したように、whileでループさせて関数を呼んだり、別の関数から関数を呼んだとしても再帰関数とは言えません。

再帰関数は自身と同じ関数を呼ぶ必要があります。
check()の中でexca()を呼ぶのは　再帰関数ではありません。↓
---------------------------------------------------------
void check(int y, int x, int dir){									// 4方向チェック?
	if(M[y - 2][x] != ROAD){
		dir = 0;
		exca(y, x, dir);
	}
	else if(M[y][x + 2] != ROAD){
		dir = 1;
		exca(y, x, dir);
	}
	else if(M[y + 2][x] != ROAD){
		dir = 2;
		exca(y, x, dir);
	}
	else if(M[y][x - 2] != ROAD){
		dir = 3;
		exca(y, x, dir);
	}
	else	stop(y, x, dir);
}
---------------------------------------------------------

流れとしては、
main関数でexca()を呼び出して、その後はずっとexca()の中でexca()を呼び出すという形になります。

あとstop関数は何の意味も成しません。
先ほど述べたように局所変数（ローカル変数）はグローバル変数を隠します。

よってstop関数に仮引数として渡されたx、y、dirを変更したところで
グローバル変数の方のx、y、dirの値は何も変化しません。
（randnum()と全く同じ状態ですね。)

完全に削除してしまっても動くはずです。


あとこの長い条件文も不要です。
if文を削除してcheck()だけ残しておいても問題ないでしょう。
---------------------------------------------------------------------------------------
	if((M[y - 2][x] != WALL) || (M[y][x + 2] != WALL) || (M[y + 2][x] != WALL) || (M[y][x - 2] != WALL)){
		if((M[y - 2][x] != WALL) && (M[y - 1][x] != ENTRANCE) && (M[y - 1][x] != M[1][x]))	M[y - 1][x] = ROAD;
		else if((M[y][x + 2] != WALL) && (M[y][x + 1] != M[y][SMAX - 2]))	M[y][x + 1] = ROAD;
		else if((M[y + 2][x] != WALL) && (M[y + 1][x] != EXIT) && (M[y + 1][x] != M[SMAX - 2][x]))	M[y + 1][x] = ROAD;
		else if((M[y][x - 2] != WALL) && (M[y][x - 1] != M[y][1]))	M[y][x - 1] = ROAD;
---------------------------------------------------------------------------------------

ともかく、再帰関数になっていない部分を何とかすれば課題は満たす事になりますね。
あともう少しです。
ページトップ
ASH

Re:C言語で穴掘り法の迷路を作っているのですが…

#10

投稿記事 by ASH » 16年前

exca の中で exca を呼ぶ

と結構 悩んだ結果、check() を消して

全ての処理を exca ですることにしました。

----------------------------------------------------------------------
void exca(int y, int x, int dir){									// 穴掘り作業
	if((dir == UP) && (M[y - 2][x] != ROAD)){
		M[y - 2][x] = ROAD;
		M[y - 1][x] = ROAD;
		dir = rand() % 4;
		exca(y - 2, x, dir);
	}
	else if((dir == RIGHT) && (M[y][x + 2] != ROAD)){
		M[y][x + 2] = ROAD;
		M[y][x + 1] = ROAD;
		dir = rand() % 4;
		exca(y, x + 2, dir);
	}
	else if((dir == DOWN) && (M[y + 2][x] != ROAD)){
		M[y + 2][x] = ROAD;
		M[y + 1][x] = ROAD;
		dir = rand() % 4;
		exca(y + 2, x, dir);
	}
	else if((dir == LEFT) && (M[y][x - 2] != ROAD)){
		M[y][x - 2] = ROAD;
		M[y][x - 1] = ROAD;
		dir = rand() % 4;
		exca(y, x - 2, dir);
	}
		if(M[y - 2][x] != ROAD){               // 4方向チェック
			dir = 0;
			exca(y, x, dir);
		}
		else if(M[y][x + 2] != ROAD){
			dir = 1;
			exca(y, x, dir);
		}
		else if(M[y + 2][x] != ROAD){
			dir = 2;
			exca(y, x, dir);
		}
		else if(M[y][x - 2] != ROAD){
			dir = 3;
			exca(y, x, dir);
		}
		if((M[y - 2][x] != ROAD) && (M[y - 2][x] != WALL))	exca(y + 2, x, dir);			// 四方塞がりなら
		else if((M[y][x + 2] != ROAD) && (M[y][x + 2] != WALL))	exca(y, x - 2, dir);
		else if((M[y + 2][x] != ROAD) && (M[y - 2][x] != ROAD))	exca(y - 2, x, dir);
		else if((M[y][x - 2] != ROAD) && (M[y][x - 2] != WALL))	exca(y, x + 2, dir);
}

----------------------------------

これでまだ再帰ではなかったら、私は多分・・・絶望に駆られると思います。
ページトップ
Poco

Re:C言語で穴掘り法の迷路を作っているのですが…

#11

投稿記事 by Poco » 16年前

一応再帰っぽくなっていますが、もう一粘りされてみては？

全ての分岐の中でやっていることは、
　・新しいdirの決定
　・新しいxの決定
　・新しいyの決定
　・exca(x,y,dir)の呼び出し
となっています。

だったら、exca()の中でexca()が一回しか登場しないようにしてみては
どうでしょうか？
そうすることでかなり再帰っぽく見えます。

＃あれ？終了条件がない・・・これ動いています？
ページトップ
conio

Re:C言語で穴掘り法の迷路を作っているのですが…

#12

投稿記事 by conio » 16年前 

再帰的に呼び出されているので、一応　再帰関数になっていると思います。
（課題の要件を満たす）

ただ、
----------
右へ掘る
左へ掘る
上へ掘る
下へ掘る
----------
の４つの状態において再帰的に呼び出したほうが分かりやすく纏まるんじゃないかな、と。
（excaの呼び出しは四箇所のみ）


無駄があるのですが、自分はとりあえず下記の様な感じにしました。
掘って進んだ地点で、上下左右全て掘ろうと試みます。
掘る事が出来たら、また上下左右全て掘ろうと試みます。
（実際は再帰的に呼び出されるので、ずっと一本道で掘っていって、
　　　掘れなくなったら以前の掘った場所からまた掘り始めているように見えます。）

掘られていく様子が分かるように、Sleep関数を使っています。
-----------------------------------------------------------------------------
#include<stdio.h>
#include<time.h>
#include<stdlib.h>
#include<windows.h>

#define SMAX 17

enum MapID{
	MAP_ROAL,
	MAP_WALL,
	MAP_ENTRANCE,
	MAP_EXIT
};

enum DirectID{
	DIR_RIGHT,
	DIR_LEFT,
	DIR_UP,
	DIR_DOWN,
	DIR_MAX
};

void init();
void Draw(void);

int x, y;
char M[SMAX][SMAX];


void Dig(int x, int y){
	int flag[DIR_MAX] = {0};
	int Check = 0;
	int d_flag;

	Sleep(800);
	Draw();

	while(Check != DIR_MAX){
		d_flag = rand() % DIR_MAX;
		switch(d_flag){
			case DIR_RIGHT:
						if(flag[DIR_RIGHT] == 0){
							flag[DIR_RIGHT] = 1;
							++Check; 
							if(x + 2 < SMAX && M[y][x + 2] != MAP_ROAL){
								M[y][x + 1] = M[y][x + 2] = MAP_ROAL;
								Dig(x + 2, y);
							}
						}
						break;
			case DIR_LEFT:
						if(flag[DIR_LEFT] == 0){
							flag[DIR_LEFT] = 1;
							++Check; 
							if(x - 2 >= 0 && M[y][x - 2] != MAP_ROAL){
								M[y][x - 1] = M[y][x - 2] = MAP_ROAL;
								Dig(x - 2, y);
							}
						}
						break;
			case DIR_UP:
						if(flag[DIR_UP] == 0){
							flag[DIR_UP] = 1;
							++Check; 
							if(y - 2 >= 0 && M[y - 2][x] != MAP_ROAL){
								M[y - 1][x] = M[y - 2][x] = MAP_ROAL;
								Dig(x, y - 2);
							}
						}
						break;
			case DIR_DOWN:
						if(flag[DIR_DOWN] == 0){
							flag[DIR_DOWN] = 1;
							++Check; 
							if(y + 2 < SMAX && M[y + 2][x] != MAP_ROAL){
								M[y + 1][x] = M[y + 2][x] = MAP_ROAL;
								Dig(x, y + 2);
							}
						}
						break;
			default:break;
		}
	}
}

int main(void){
	srand((unsigned int)time(NULL));

	init();
	Draw();
	Dig(2,2);
	Draw();

	return 0;
}

void init(){
	for(y = 0; y < SMAX; y++){			// 配列の初期化
		for(x = 0; x < SMAX; x++){
			if( y % (SMAX - 1) == 0 || x % (SMAX - 1) == 0)
				M[y][x] = MAP_ROAL;
			else
				M[y][x] = MAP_WALL;
		}
	}
	M[1][2] = MAP_ENTRANCE;			// スタート位置のフラグを立てる。
	M[SMAX-2][SMAX-3] = MAP_EXIT;	// ゴール位置のフラグを立てる。
	M[2][2] = MAP_ROAL;		// 起点
}

void Draw(void){
	for(y = 0; y < SMAX; y++){
		for(x = 0; x < SMAX; x++){
			if(M[y][x] == MAP_WALL)
				printf("■");
			else if(M[y][x] == MAP_ROAL)
				printf("×");
			else if(M[y][x] == MAP_EXIT)
				printf("◎");
			else if(M[y][x] == MAP_ENTRANCE)
				printf("Ｓ");
		}
		puts(" ");
	}
}
-----------------------------------------------------------------------------
ページトップ
ASH

Re:C言語で穴掘り法の迷路を作っているのですが…

#13

投稿記事 by ASH » 16年前

すみません。
『掘れなくなったら以前の掘った場所からまた掘り始める。』
というようにするには、どんな風に考えれば良いのでしょうか？


こんな考えは駄目なんでしょうか？（while・switchを使うとして）

①掘り始めが右のフラグが立っていて、2マス先が掘れます→掘ります。

②再帰で exca(y, x - 2) をしますが、その前に、前もって宣言していた int backflg(= 0) というような変数が0の時、これまた適当に宣言していた int xx, yy に xx = x - 2; yy = y; を入れておいて、 backflg を1にします。（なので、exca(y, x - 2, backflg)になると思います。）

③ backflg が0の時にしか xx, yy の値を変えないので、大丈夫・・・だと思いますが、掘り進んだ先が道になっていたら再帰が出来なくなり、一旦止めます。

④そしたら xx, yy の値を x, y に入れて、whileなので条件に満たない場合回るので、上に戻る・・・？



まだ考え中ですが、↓

while(～～){
		dir = rand() % 4;
		switch(dir){
		case RIGHT:
			if(M[y][x + 2] == WALL){
				M[y][x + 2] = ROAD;
				M[y][x + 1] = ROAD;
				if(backflg == 0){
					xx = x + 2;
					yy = y ;
					backflg = 1;
				}
		exca(y, x + 2, backflg,dedflg);
				break;
			}
:
:
:
if((2マス先が道だった) && (backflg == 1)){
			x = xx;
			y = yy;
			backflg = 0;
		}

whileの条件もどうしようかと考えています。
ページトップ
Poco

Re:C言語で穴掘り法の迷路を作っているのですが…

#14

投稿記事 by Poco » 16年前

>『掘れなくなったら以前の掘った場所からまた掘り始める。』
>というようにするには、どんな風に考えれば良いのでしょうか？

これって、conioさんが提示した方法の考え方が分からないということでしょうか？
それとも別の方法を考えたいということでしょうか？

別の方法を考えたいのであれば、正直ASHさんの考えが分かりません。
変数backlfg、dedflg、xx、yyの役割を「明確な日本語」で説明願います。
ページトップ
ドラ

Re:C言語で穴掘り法の迷路を作っているのですが…

#15

投稿記事 by ドラ » 16年前

>『掘れなくなったら以前の掘った場所からまた掘り始める。』
exca関数で4方向すべてに掘り進める処理を書いておけば、呼び出し元のexca関数に戻るだけです。
再帰処理のイメージがつかめておらず、難しく考えすぎている気がします。

関数を呼び出すと、仮引数や自動変数がメモリ上に確保されますね？
再帰の場合も（exca関数の中でexca関数を呼び出しても）同じです。
呼び出し元のexca関数の仮引数や自動変数とは別の領域に
新たに呼び出されたexca関数の仮引数や自動変数が確保されます。

新たに呼び出したexca関数で掘り進む方向がなくなって関数を抜けると
新たに呼び出したexca関数で確保した仮引数や自動変数は消滅しますが、
呼び出し元のexca関数で確保した仮引数や自動変数はまだ存在しています。
その残っていた情報を元に、別方向に掘っていけば良いことになります。


私が書くならこのような疑似コードになります。
/* 実引数で渡された座標を起点に上下左右4方向に穴を掘る関数 */
void exca(int x, int y)
{
    int dir[4] = {UP, RIGHT, DOWN, LEFT};
    int i;

    ・ここでdir配列をシャッフルすると良いでしょう

    for (i = 0; i < 4; ++i)
    {
        if ( dirの方向に掘ることが可能なら )
        {
            ・dirの方向に掘る
            ・掘り進んだ先の座標を実引数にしてexca()を呼び出し
        }
    }
}
ページトップ
ASH

Re:C言語で穴掘り法の迷路を作っているのですが…

#16

投稿記事 by ASH » 16年前

すみません。
出来るだけ独自のソースを考えようとしていたのですが、逆に空回りしているみたいです。

dedflg は消し忘れでした。

xx, yy は x, y の添え字を入れて、行き止まったら xx, yy を x, y に戻し、他の進行方向に行ってもらうというような為に作った変数で、
（M[y][x - 2]掘れる！→　xx = x - 2, yy = y, backflg = 1・①exca(y, x - 2, backflg)→　M[y + 2][x]掘れる！→　backflg != 0の為、xx, yy は上書きされない・exca(y + 2, x, backflg)→　M[y - 2][x]掘れない→　x = xx, y = yy, backflg = 0→　①の位置から掘り始める・・・みたいな感じです。）

backflg はその xx, yy が毎回更新されないようにするためのフラグです。
なので、行き止まったら xx, yy が x, y に戻した後に backflg も0に戻して次の処理をしてもらおうとしていましたが・・・

やっぱり無理みたいでした。
分からず屋で申し訳ないです。


----------------------------------------------


ドラさん、ありがとうございました。
変な風に思いこんでいました。

再帰についてはまだまだ分からない事があると思いますが、今さっきの説明でどんな風に流れるのかが想像出来ました。

実際に実行したらちゃんと出来ました。


みなさんに大変ご迷惑お掛けしました・・・

ありがとうございました。
ページトップ
羽流布

Re:C言語で穴掘り法の迷路を作っているのですが…

#17

投稿記事 by 羽流布 » 16年前

割り込み失礼しますm(_ _)m

この記事を参考に迷路自動生成のミニゲーム風サンプルを作ってみました。
下記ＵＲＬからダウンロードできますので、宜しければ(;^^

http://ux.getuploader.com/dzware/downlo ... %83%AB.zip

このサンプルでは迷路自動生成に加え、ポテンシャル法を利用した自動解答機能も実装しております。
また、迷路生成後に十字キーで歩くことができます。

あと、Ｄ言語となりますがソースコードも添付いたしました。
ソースコードは自由に引用・改変してくださって構いません。

では、お邪魔しました。
ページトップ
閉鎖

“C言語何でも質問掲示板” へ戻る