迷路の自動作成

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
shims him
記事: 2
登録日時: 7ヶ月前

迷路の自動作成

#1

投稿記事 by shims him » 7ヶ月前

迷路の自動作成するプログラムを穴掘り法を用いて作成しようとしたのですが、スタートからゴールまでの道筋が複数本できてしまう場合があります。
どのように修正すれば良いのか、どなたかご教授願います。
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

Butter
記事: 15
登録日時: 8ヶ月前
住所: <個人情報保護法に基づき削除されました>(適当)

Re: 迷路の自動作成

#2

投稿記事 by Butter » 7ヶ月前

解答ではありませんが、
ソースを貼りつけるときは
/code
ではなく
[/code]
のように
[と]で囲って下さい
C言語歴1年弱の中学生です
・dxlib中心にやってるので、たまに不可解な発言をします
・実行チェックはしない主義。時間が無いので…(言い訳)
どうぞよろしくお願いします
By Butter.

shims him
記事: 2
登録日時: 7ヶ月前

Re: 迷路の自動作成

#3

投稿記事 by shims him » 7ヶ月前

shims him さんが書きました:
7ヶ月前
迷路の自動作成するプログラムを穴掘り法を用いて作成しようとしたのですが、スタートからゴールまでの道筋が複数本できてしまう場合があります。
どのように修正すれば良いのか、どなたかご教授願います。

コード:

#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");
    }
}

アバター
usao
記事: 1635
登録日時: 7年前

Re: 迷路の自動作成

#4

投稿記事 by usao » 7ヶ月前

デバッグしてください.

srand()に適当なSEED値を入れて実行することで,「道筋が複数本」になるようなSEEDを探してください.
それを見つければ,何度でも同じ処理を再現できますから,デバッグしやすいでしょう.

穴を掘るたびに状況を表示するようにするなりして動作を見ていけば,
どこかの時点で「道筋が複数本」になることを観測できるでしょう.
そのときの処理の進み方を詳細にチェックすればロジックのミスが見つかるでしょう.

アバター
あたっしゅ
記事: 428
登録日時: 10年前
住所: 東京23区
連絡を取る:

Re: 迷路の自動作成

#5

投稿記事 by あたっしゅ » 7ヶ月前

コード:

    srand(2); //乱数初期化
の時に、道筋が 2 本になりますね。
VTuber:
東上☆海美☆(とうじょう・うみみ)
http://atassyu.rosx.net/vtuber/index.html
レスがついていないものを優先して、レスすみみ。時々、見当外れなレスしみみ。

中の人:
手提鞄あたっしゅ、[MrAtassyu]
http://ameblo.jp/mratassyu/
Pixiv: 666303
手提鞄屋魚有店(てさげかばんやうおありてん)

返信

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