Stardust Crown

ホーム
読み物
迷路生成アルゴリズム

迷路生成アルゴリズム

手順
ソースコード
実演

　Stardust Crown で迷路を作成するときに用いているアルゴリズムを紹介します。セルを状態ごとの領域に分割し、順次拡張していく手法ですから“領域拡張法”とでも呼びましょうか。（本当は“ＳｄＣ迷路生成アルゴリズム”と名付けようかと思ったのですが、先人たちで既に同様な手法を考えた人がいそうなので、ちょっと控えめにしておきますね。）

概要

　２次元に敷き詰められた長方形セルを迷路にします。
　ここで、セルは縦横で隣接しているものとし、互いを壁が隔てていなければ移動可能です。境界条件（右端と左端、上端と下端が繋がっているかどうか）はどちらでも構いません。はじめ、すべてのセル間が壁で隔てられているものとし、それから“壁を壊す”ことで迷路を造ります。最終的に「任意のセルと任意のセルの最短移動経路がただ一通り存在する」ような迷路が出来上がります。

　なお、ここでは平面長方形の迷路として説明しますが、実は“孤立している”ノードがなければ、どんな無向グラフにも適用可能（なはず）です。すなわち、長方形でない形状であったり、３次元であったりしても迷路にできます。（隣接の条件は適当に変更しなければなりませんし、よほど複雑な場合は可視化にも工夫が必要になりますが。）

手順

準備するもの

壁状態格納配列 wall

隣接するセル同士の関係を保持します。具体的には壁の有無を表すものとしましょう。

WALL_YES = 0 ：壁あり（移動不可能）
WALL_NO = 1 ：壁なし（移動可能）

セル状態格納配列 cell

セルの状態を保持します。（生成段階でのみ使用し、迷路完成後は破棄して構いません。）

LABYRINTH_IN = 2 ：迷路要素（既に迷路の一部）
LABYRINTH_BORDER = 1 ：迷路境界（次の迷路候補）
LABYRINTH_OUT = 0 ：迷路外（迷路の一部でも迷路の候補でもない）

　定数の数値は適当なもので構いません。また、ある要素数の集合からランダムに１つ取り出す関数を用いるので、乱数の生成が必要です。
　なお、プログラムを高速化するためには cell を状態ごとに分けた方がよいのかもしれませんが（ cell_border, cell_out ）、説明の都合上まとめて記述しています。

アルゴリズム

※わかりにくいときは実演も参照するとよいでしょう。

［０］下準備

上記の、準備に必要な配列等を確保します。

　必要なら（そしてたいてい必要でしょうが）できた迷路を可視化したり、その中をキャラクターが動き回るための処理等も用意しておかなければなりません。

［１］初期化

wall の全要素に WALL_YES を代入します。また、cell の全要素に LABYRINTH_OUT を代入します。

　以下、 wall の要素を“壁”、 cell の要素を“セル”と呼ぶことにします。

［２］スタート地点の選択

cell の全要素の中から、ランダムに１つのセル X_0 を選び LABYRINTH_IN を代入します。
X_0 に隣接するセル {Y_0} すべてに LABYRINTH_BORDER を代入します。

　なお、スタート地点は必ずしもランダムに選ばなくて構いません。真ん中とか左上とか、適当な箇所で大丈夫です。

［３］迷路拡張

状態が LABYRINTH_BORDER であるセルの中から、ランダムに１つのセル X を選びます。
X に隣接するセルの中から、ランダムな順序で、状態が LABYRINTH_IN なものを探索し、はじめの一つ N を取り出します。
X と N を隔てる壁 W に WALL_NO を代入します。
X に LABYRINTH_IN を代入します。
X に隣接するセル {Y} の中で、状態が LABYRINTH_OUT であるものすべてに LABYRINTH_BORDER を代入します。

　LABYRINTH_IN の近傍のみを LABYRINTH_BORDER にしていきますので、２番目の“N の探索”は必ず成功します。
　さらに、３番目で迷路を拡張していますが、N から出発して、既に LABYRINTH_IN であるセルに到達するためには、必ず X を経由しなければならず、しかも X を経由すれば到達可能ですから、任意の段階の（LABYRINTH_IN であるセルの集合としての）迷路は“任意のセルと任意のセルの最短移動経路がただ一通り存在する”ようになります。

※厳密には数学的帰納法によって証明することになります。

［４］終了判定

状態が LABYRINTH_BORDER であるセルがなくなっていれば終了です。そうでない限り［３］を繰り返します。

　LABYRINTH_BORDER であるセルがなくなっていれば、LABYRINTH_OUT であるセルもなくなっています。（すなわち、完成後は wall の全要素が LABYRINTH_IN になっているはずです。）
　さらに、終了後に壁をいくつかランダムに選び、“壊す”などしてもよいでしょう。適度に空いている迷路を作ることができます。

サンプル

ソースコード

　参考のため、Java 言語によるソースコード（の一部）を例示しておきます。

// Programmed by M.Nagase @ Stardust Crown "http://stardustcrown.com/"

// ２次元の例です
int size;
int size_x; // セルの列数です
int size_y; // セルの行数です
int max_direction = 4; // ２次元なので上下左右の４方向です

// wall[Position_X][Position_Y][Direction] に壁の有無を格納します
// メモリーが多少無駄になりますが有向グラフと同じ記憶容量になっています
int[][][] wall;
public static final int WALL_NO = 1;
public static final int WALL_YES = 0;
// ※ cell と同じように一次元配列に変換して処理すると汎用的にできます

// cell[Position_X + Position_Y * size_x] にセルの状態を格納します
int[] cell;
private static final int LABYRINTH_IN = 2;
private static final int LABYRINTH_BORDER = 1;
private static final int LABYRINTH_OUT = 0;

// 効率を上げるため LABYRINTH_BORDER であるセルの数を覚えておきます
int num_of_LABYRINTH_BORDER;
private static final int NO_CELL = -1;

public void createMazeMap(int x, int y) {
  // ２次元のサイズを与えて迷路を作成します
  size_x = x;
  size_y = y;
  size = size_x * size_y;
  wall = new int[size_x][size_y][max_direction];

  //［１］初期化
    // Java ではゼロクリアされているような気もしますが初期化しておきます
    for (int i=0; i < size_x; i++) {
      for (int j=0; j < size_y; j++) {
        for (int k=0; k < max_direction; k++) {
          wall[i][j][k] = WALL_YES;
        }
      }
    }
    cell = new int[size];
    for (int j=0; j < size; j++) {
      cell[j] = LABYRINTH_OUT;
    }
    //num_of_LABYRINTH_BORDER = 0;

  //［２］スタート地点の選択
  int X_0;
  // １番目の処理
    X_0 = (int)((size) * Math.random());
    cell[X_0] = LABYRINTH_IN;
  // ２番目の処理
    num_of_LABYRINTH_BORDER = pickupNeighbor(X_0);
  
  int X, N, X_x, X_y, N_x, N_y, direction;
  
  while (num_of_LABYRINTH_BORDER > 0) { // ［４］終了判定
  //［３］迷路拡張
  // １番目の処理
    X = pickupNextCell();

  // ２番目の処理
    direction = selectNextConnect(X);
    N = neighborCell(X, direction);

  // ３番目の処理
    // １次元データとして処理しているので２次元に戻します
    X_x = X % size_x;  X_y = X / size_x;
    N_x = N % size_x;  N_y = N / size_x;
    // 壁を取り除きます
    wall[X_x][X_y][direction] = WALL_NO;
    // 有向グラフとしているので逆側からも壁を取り除きます
    wall[N_x][N_y][(max_direction-1) - direction] = WALL_NO;
    /*
      (max_direction-1) - direction と direction が、
      逆方向に定義されているものとします
      neighborCell() の実装も参照してください
    */
    
  // ４番目の処理
    cell[X] = LABYRINTH_IN;
    num_of_LABYRINTH_BORDER--; // 状態 LABYRINTH_BORDER が１つ減ることになります
    
  // ５番目の処理
    num_of_LABYRINTH_BORDER += pickupNeighbor(X);
  }

}

private int pickupNeighbor(int x) {
  int c = 0;
  int n;
  for (int i=0; i < max_direction; i++) {
    n = neighborCell(x, i);
    if (n != NO_CELL && cell[n] == LABYRINTH_OUT) {
      cell[n] = LABYRINTH_BORDER; // セルの状態を書き換えます
      c++;
    }
  }
  return c; // 近接するセルの数を返します
}

private int pickupNextCell() {
  int c = (int)(num_of_LABYRINTH_BORDER * Math.random()) + 1;
  int x = -1;
  // LABYRINTH_BORDER である c 番目の セルを返します
  do {
    x = (x + 1) % size;
    if (cell[x] == LABYRINTH_BORDER) {
      c--;
    }
  } while (c > 0);
  return x;
}

private static final int NOTYET = 0;
private static final int DONE = 1;

private int selectNextConnect(int x) {
  int[] d = new int[max_direction];
  for (int i=0; i < max_direction; i++) {
    d[i] = NOTYET; // 検索した方向を記憶しておきます
  }
  int c = max_direction;
  int n, h, s;
  for (int i = max_direction; i > 0; i--) {
    s = -1;
    h = (int)(i * Math.random()) + 1;
    do { // 方向をランダムに選びます
      s = (s + 1) % max_direction;
      if (d[s] == NOTYET) {
        h--;
      }
    } while (h > 0);
    d[s] = DONE;
    h = neighborCell(x, s);
    if (h != NO_CELL && cell[h] == LABYRINTH_IN) {
      return s; // 検索した方向が迷路の一部であればその方向を返します
    }
  }
  // 実際には次の処理に制御が移ることはないはずです
  return NO_CELL;
}

// この関数は２次元専用になりますので拡張時は修正する必要があります
private int neighborCell(int position, int direction) {
  // 境界が崖であるという条件で方向に応じた隣のセルを返します
  switch (direction) {
  // 方向は対になる向きの和が max_direction になるように定義します
  case 0: // 右
    if (position % size_x < size_x-1) return position + 1;
    break;
  case 1: // 上
    if (position / size_x > 0) return position - size_x;
    break;
  case 3: // 左
    if (position % size_x > 0) return position - 1;
    break;
  case 2: // 下
    if (position / size_x < size_y-1) return position + size_x;
    break;
  }
  // 隣のセルが存在しません
  return NO_CELL;
}

※実際の表示には、クラス化して他のクラスから呼び出したり、適切に main 関数を追加したりする等の修正が必要です。

実演

　『迷路の国のマウンス』（のはじめのアニメーション）で迷路生成の様子を確認することができます。 "LABYRINTH_OUT" を黒、 "LABYRINTH_BORDER" を灰色、 "LABYRINTH_IN" を白で示しています。

著作・制作／永施誠
e-mail; webmaster@stardustcrown.com

ページ先頭

迷路生成アルゴリズム

概要

手順

準備するもの

アルゴリズム

［０］ 下準備

［１］ 初期化

［２］ スタート地点の選択

［３］ 迷路拡張

［４］ 終了判定