English

blog

穴堀り法 迷路生成アルゴリズム

穴掘り法とは

穴掘り法は迷路生成アルゴリズムの一つです。他にも棒倒し法・壁伸ばし法等がありますが、ここでは穴掘り法をJavaのコードを見ながら説明したいと思います。再帰法を使って紹介します。

穴掘り法の主な考え方は、ランダムな開始地点から開いている方向に2マス単位で進みながら通路を作っていきます。4方向共行き止まりになったら、方向が一つでも開いているマスへ戻り、そこからまた掘っていきます。

説明

迷路を表現するのに、縦横奇数の大きさの2次元配列を使います。0を通路、1を壁とします。(解説の絵では0をオレンジ、1を黒で表現)縦の列をcol(column)、横の列をrowと呼びます。

Explanation 1

全てのマスを1(壁)にします。

Explanation 2

次に、開始地点を決めましょう。ランダムな奇数の数字をrowとcolの二つ作ります。その地点を0(通路)にします。最後に進んだ地点を現在の地点として変数で保持してください。上の図ではrow=3、col=5ですね。図では赤で表します。

Explanation 3

次に進む方向を上下左右からランダムに選びます。この図では下に移動しています。移動する時は、その方向が迷路の外になってないか確認してください。もし2マス先が1(壁)なら、その2マス目と一つ前のマスを0(通路)にします。これで1つの通路が繋がりました。進んだ後は現地点を更新してください。row=5、col=5です。

Explanation 4

上の図のように進んでいきますと、いずれ4方向共進めない状態になりますよね。そうしたら、一つ前に戻ってください。現地点はrow=7、col=7ですので、row=7、col=5に戻します。再帰法やスタックを使えば通ってきた道を辿れます。

Explanation 5

図で見やすいように詰まる度に矢印の色を変えてみました。そのまま続けて通路を探していきます。

Explanation 6

最終的にはこうなります。この迷路の大きさだと単純すぎるものになってしまいますが、大きさを広げるとそれなりに複雑になっていきます。

アプレットサンプル




再帰法使用

開始地点を決めた後、そのrowとcolを再帰メソッドに渡してください。下記は再帰メソッドの中での定義です。

  1. 上下左右それぞれを意味するint型変数をランダムに生成し、それらを所持する配列を作ります。
  2. for loopを4回回します。(上下左右=4回)
  3. switchを使い、それぞれの方向の処理をします。
  4. その方向の2マス先が迷路の外かすでに通路ができている場合はなにもしません。
  5. もしそのマスが壁なら、そのマスまで通路を繋ぎ、新しい現在地点を再帰メソッドに渡して呼びます。
  6. 上の処理が全て終わったら完成です。
コードサンプル
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
 /**
  * 穴掘り法を使って迷路を作ります。
  * @return 迷路を表現する2次元配列
  */
 public int[][] generateMaze(){
    int[][] maze = new int[height][width];
    // 初期化
    for (int i = 0; i < height; i++)
        for (int j = 0; j < width; j++)
            maze[i][j] = 1;
 
     Random rand = new Random();
     // rはrow、cはcolumn
     // rのランダム奇数
     int r = rand.nextInt(height);
     while (r % 2 == 0){
         r = rand.nextInt(height);
     }
     // cのランダム奇数
     int c = rand.nextInt(width);
     while (c % 2 == 0){
         c = rand.nextInt(width);
     }
     // 開始地点
     maze[r][c] = 0;
 
     // 再帰メソッド
     recursion(r, c);
 
     return maze;
 }
 
 /**
  * 穴掘り法を用いて迷路を生成。
  * @param r 現在のrow
  * @param c 現在のcolumn
  */
 public void recursion(int r, int c){
     // 4つの方向をランダムな順に配列へ
     int[] randDirs = generateRandomDirections();
     // 順番にその方向に進む
     for (int i = 0; i < randDirs.length; i++){
 
         switch(randDirs[i]){
         case 1: // 上
             // 上2マス先が迷路の外か
             if (r - 2 <= 0)
                 continue;
             if (maze[r - 2][c] != 0){
                 maze[r-2][c] = 0;
                 maze[r-1][c] = 0;
                 recursion(r - 2, c);
             }
             break;
         case 2: // 右
             // 右2マス先が迷路の外か
             if (c + 2 >= width - 1)
                 continue;
             if (maze[r][c + 2] != 0){
                 maze[r][c + 2] = 0;
                 maze[r][c + 1] = 0;
                 recursion(r, c + 2);
             }
             break;
         case 3: // 下
             // 下2マス先が迷路の外か
             if (r + 2 >= height - 1)
                 continue;
             if (maze[r + 2][c] != 0){
                 maze[r+2][c] = 0;
                 maze[r+1][c] = 0;
                 recursion(r + 2, c);
             }
             break;
         case 4: // 左
             // 左2マス先が迷路の外か
             if (c - 2 <= 0)
                 continue;
             if (maze[r][c - 2] != 0){
                 maze[r][c - 2] = 0;
                 maze[r][c - 1] = 0;
                 recursion(r, c - 2);
             }
             break;
         }
     }
 
 }
 
 /**
 * 左右上下の方向を表す4つの数字をランダムな順に配列として生成。
 * @return 方向を表す4つの数字をもった配列
 */
 public Integer[] generateRandomDirections() {
      ArrayList<Integer> randoms = new ArrayList<Integer>();
      for (int i = 0; i < 4; i++)
           randoms.add(i + 1);
      Collections.shuffle(randoms);
 
     return randoms.toArray(new Integer[4]);
 }