[Java3Djp:01126] Re: 迷路生成アルゴリズム

[yasuyuki@xxxxxxxxxx]

┏━━━━━━━━━━━━━┓
┃  名刺作成ソフトの決定版  ┃ ★★★★  好評につき再開決定！ ★★★★
┃                          ┃                   ↓
┃      名刺郎 Ver.5        ┃ ★★★★  いますぐ【 CLICK 】  ★★★★
┃                          ┃                   ↓
┃   毎週５名様プレゼント！ ┃ ★★★  http://www.swave.co.jp/  ★★★
┗━━━━━━━━━━━━━┛

えんどうです。

> わからないこと：
> ・「穴堀り法」についてはまだわからない。

三橋さんからメールをいただきました。

穴掘り法のアルゴリズムとサンプルソース (C言語) です。

三橋さんに転載許可をいただいたので転載します。
どうもありがとうございます＞三橋さん

--8<--begin--8<--

三橋です。

おそらく私の解説よりもソースをご覧いただいた方がはるかにあいまいさがあ
りませんし、なによりソースをお読みになるのはお上手でしょうから、アルゴ
リズムについてはほんとに簡単に述べさせていただく程度にさせていただきま
す。

1. 迷路作成する人を配置します。
   迷路の周りにはダミーで掘ってある事にしておきます。
   (これで作成人が配列を飛び出して行かないようにしてます。)

2. 作成人は常に2歩づつ移動します。
   よって作成人は常に2つ先の上下左右が掘れるか否かチェックすることにな
   ります。
   
3. まずランダムに移動しながら仮堀をします。

4. その際に周りをチェックして全て仮堀の状態になったら、そこで一旦仮堀
   をやめます。

5. 仮堀した場所(自分のすぐ隣り)を調べながら、本堀をしながら移動してい
   きます。本堀する度、仮堀が出来るかチェックします。仮堀が出来るよう
   であれば本堀をやめ、また仮堀をします。(3へ)

6. と仮堀と本堀をしていき、両方とももう出来なくなり身動きが取れなくなっ
   たとき迷路が出来上がっています。

7. 最後にどこか2個所に出口を空けてやれば完成です。

下手な文章で本当にすみません。
以下がそのソースです。


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

#define SIZE            79

#define RND(min, max)  ((random () % (int)((max) - (min - 1))) + (min - 1) + 1)

#define U                map[y-1][x]
#define D                map[y+1][x]
#define L                map[y][x-1]
#define R                map[y][x+1]

#define UU               map[y-2][x]
#define DD               map[y+2][x]
#define LL               map[y][x-2]
#define RR               map[y][x+2]

#define BLK              '@xxxxxxxxxx'
#define DIG              'x'
#define SPC              ' '

int main()
{
    static char map[SIZE][SIZE+1];
    int       	i,j,k;
    int         x,y;
    int         mx,my;
    int         mov,movf;
    int         f[4];
    int         ff;

    for (i = 0; i < SIZE; i++) {
        for (j = 0; j < SIZE; j++) {
            map[j][i] = BLK;
        }
    }
    for (k = 0; k < SIZE; k++) {
        map[0][k] = map[SIZE - 1][k] = map[k][0] = map[k][SIZE - 1] = SPC;
    }
    for (k = 0; k < SIZE; k++) {
        map[k][SIZE] = NULL;
    }

    srandom ((unsigned)time (NULL));
    x = RND(1, SIZE / 2 - 1) * 2;
    y = RND(1, SIZE / 2 - 1) * 2;

    map[y][x] = DIG;
    movf = 1;

    do {
        if (movf) {
            f[0] = f[1] = f[2] = f[3] = 1;
        }

        f[0] = !(UU != BLK);
        f[1] = !(DD != BLK);
        f[2] = !(LL != BLK);
        f[3] = !(RR != BLK);

        movf = 0;
        mov  = RND(1, 4);
        ff = mov % 2 ? -1 : 1;
        if (mov <= 2) {
            if (map[y + 2 * ff][x] == BLK) {
                map[y + 1 * ff][x] = DIG;
                map[y + 2 * ff][x] = DIG;
                y = y + 2 * ff;
                movf = 1;
            }
        } else {
            mov = mov - 2;
            if (map[y][x + 2 * ff] == BLK) {
                map[y][x + 1 * ff] = DIG;
                map[y][x + 2 * ff] = DIG;
                x = x + 2 * ff;
                movf = 1;
            }
        }

        if (!f[0] && !f[1] && !f[2] && !f[3]) {
            map[y][x] = SPC;
            mx = my = 0;

            my = (D == DIG) - (U == DIG);
            mx = (R == DIG) - (L == DIG);

            if (mx || my) {
                map[y + my    ][x + mx   ] = SPC;
                map[y + my * 2][x + mx *2] = SPC;
                x = x + mx * 2;
                y = y + my * 2;
                movf = 2;
            }
        }
    } while (movf == 2 || f[0] || f[1] || f[2] || f[3]);

    x = RND(1, SIZE / 2 - 1) * 2;
    map[1][x] = SPC;
    x = RND(1, SIZE / 2 - 1) * 2;
    map[SIZE - 2][x] = SPC;

    for (k = 0; k < SIZE; k++) {
        printf ("\n%s", map[k]);
    }

    putchar ('\n');
}

-- 
三橋雅昭 masaaki@xxxxxxxxxx


-->8--end-->8--

---
ENDO Yasuyuki <yasuyuki@xxxxxxxxxx>
http://www.javaopen.org/jfriends/index.html (Japanese Only)