迷路の自動作成するプログラムを穴掘り法を用いて作成しようとしたのですが、スタートからゴールまでの道筋が複数本できてしまう場合があります。
どのように修正すれば良いのか、どなたかご教授願います。
code
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 21
#define ROAD 0
#define WALL 1
#define START 2
#define GOAL 3
int maze[N][N];
void set_maze(); //迷路初期化
void make_maze(); //迷路作成
void _maze(int x, int y); //ある位置から穴を掘る
void disp(); //迷路を画面に表示
int main()
{
srand(time(NULL)); //乱数初期化
set_maze(); //迷路初期化
make_maze(); //迷路作成
disp(); //迷路を表示
}
//迷路初期化
void set_maze()
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
maze[j] = WALL;
}
}
maze[1][0] = START;
maze[N - 2][N - 1] = GOAL;
}
//迷路作成
void make_maze()
{ //穴掘り法
int x, y;
while (1)
{
x = 1 + rand() % (N - 2);
if (x % 2 == 1)
break;
}
while (1)
{
y = 1 + rand() % (N - 2);
if (y % 2 == 1)
break;
}
_maze(x, y);
}
//ある位置から穴を掘る
void _maze(int x, int y)
{
int xp[4] = {0, 1, 0, -1};
int yp[4] = {-1, 0, 1, 0};
int d = rand() % 4;
int temp = d;
while (1)
{
int px = x + xp[d] * 2;
int py = y + yp[d] * 2;
if (px < 0 || px > N - 1 || py < 0 || py > N - 1 || maze[py][px] != WALL)
{
d = (d + 1) % 4;
if (d == temp)
return;
continue;
}
maze[y + yp[d]][x + xp[d]] = ROAD;
maze[py][px] = ROAD;
_maze(px, py);
d = rand() % 4;
temp = d;
}
}
//迷路を画面に表示
void disp()
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (maze[j] == ROAD)
{
printf(" ");
}
else if (maze[j] == WALL)
{
printf("■ ");
}
else if (maze[j] == START)
{
printf("ス");
}
else if (maze[j] == GOAL)
{
printf("ゴ");
}
}
printf("\n");
}
}
/code
迷路の自動作成
Re: 迷路の自動作成
shims him さんが書きました: ↑3年前迷路の自動作成するプログラムを穴掘り法を用いて作成しようとしたのですが、スタートからゴールまでの道筋が複数本できてしまう場合があります。
どのように修正すれば良いのか、どなたかご教授願います。#include <stdio.h> #include <stdlib.h> #include <time.h> #define N 21 #define ROAD 0 #define WALL 1 #define START 2 #define GOAL 3 int maze[N][N]; void set_maze(); //迷路初期化 void make_maze(); //迷路作成 void _maze(int x, int y); //ある位置から穴を掘る void disp(); //迷路を画面に表示 int main() { srand(time(NULL)); //乱数初期化 set_maze(); //迷路初期化 make_maze(); //迷路作成 disp(); //迷路を表示 } //迷路初期化 void set_maze() { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { maze[i][j] = WALL; } } maze[1][0] = START; maze[N - 2][N - 1] = GOAL; } //迷路作成 void make_maze() { //穴掘り法 int x, y; while (1) { x = 1 + rand() % (N - 2); if (x % 2 == 1) break; } while (1) { y = 1 + rand() % (N - 2); if (y % 2 == 1) break; } _maze(x, y); } //ある位置から穴を掘る void _maze(int x, int y) { int xp[4] = {0, 1, 0, -1}; int yp[4] = {-1, 0, 1, 0}; int d = rand() % 4; int temp = d; while (1) { int px = x + xp[d] * 2; int py = y + yp[d] * 2; if (px < 0 || px > N - 1 || py < 0 || py > N - 1 || maze[py][px] != WALL) { d = (d + 1) % 4; if (d == temp) return; continue; } maze[y + yp[d]][x + xp[d]] = ROAD; maze[py][px] = ROAD; _maze(px, py); d = rand() % 4; temp = d; } } //迷路を画面に表示 void disp() { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (maze[i][j] == ROAD) { printf(" "); } else if (maze[i][j] == WALL) { printf("■ "); } else if (maze[i][j] == START) { printf("ス"); } else if (maze[i][j] == GOAL) { printf("ゴ"); } } printf("\n"); } }
Re: 迷路の自動作成
デバッグしてください.
srand()に適当なSEED値を入れて実行することで,「道筋が複数本」になるようなSEEDを探してください.
それを見つければ,何度でも同じ処理を再現できますから,デバッグしやすいでしょう.
穴を掘るたびに状況を表示するようにするなりして動作を見ていけば,
どこかの時点で「道筋が複数本」になることを観測できるでしょう.
そのときの処理の進み方を詳細にチェックすればロジックのミスが見つかるでしょう.
srand()に適当なSEED値を入れて実行することで,「道筋が複数本」になるようなSEEDを探してください.
それを見つければ,何度でも同じ処理を再現できますから,デバッグしやすいでしょう.
穴を掘るたびに状況を表示するようにするなりして動作を見ていけば,
どこかの時点で「道筋が複数本」になることを観測できるでしょう.
そのときの処理の進み方を詳細にチェックすればロジックのミスが見つかるでしょう.
Re: 迷路の自動作成
VTuber:
東上☆海美☆(とうじょう・うみみ)
http://atassyu.php.xdomain.jp/vtuber/index.html
レスがついていないものを優先して、レスするみみ。時々、見当外れなレスしみみ。
中の人:
手提鞄あたッしュ、[MrAtassyu] 手提鞄屋魚有店
http://ameblo.jp/mratassyu/
Pixiv: 666303
Windows, Mac, Linux, Haiku, Raspbery Pi, Jetson Nano, 電子ブロック 持ち。
東上☆海美☆(とうじょう・うみみ)
http://atassyu.php.xdomain.jp/vtuber/index.html
レスがついていないものを優先して、レスするみみ。時々、見当外れなレスしみみ。
中の人:
手提鞄あたッしュ、[MrAtassyu] 手提鞄屋魚有店
http://ameblo.jp/mratassyu/
Pixiv: 666303
Windows, Mac, Linux, Haiku, Raspbery Pi, Jetson Nano, 電子ブロック 持ち。