再帰的バックトラッキングによる迷路生成

はじめに

自分は小学生の頃、自由帳に書くものといえば、キン肉マンか迷路。これが２大コンテンツでした。ある日「惡魔の迷図」（悪魔の迷図）（DEVIL'S MAZES）で遊んで（買ってもらったのか、ねだったのか、兄か親かも、おぼえてないけど）これは本当に楽しかった。

悪魔の迷図とは巨大なA1サイズの巨大迷路で、解くと絵が出るやつです。
ほどなく、書店で見かけることはなくなり（自分じゃないけど）、待望する気持ちだけが子供心に残りました。
何種類かやったけど、いま調べた感じで最低でも6種類(2520/3551/4335/8311/8693/4438)、推測では25種類あるみたいですね。

https://www.kosho.or.jp/products/detail.php?product_id=282227072
https://note.com/shiroyukimin/n/n69334f087d14

やっぱり、自分は迷路好き、ということの再確認。

迷路プログラム

題材として、定番でしょうか。大別して、穴掘り法と、壁生成法があった気がします。

経緯のメモ

上のサイトから、以下のローグライクダンジョン生成サイトを知り、

以下の迷路アルゴリズム一覧サイトを知り、

以下の再帰的バックトラッキングアルゴリズムをたどりました。
様々な迷路生成アルゴリズムが紹介されている中で、一番美しく感じました。

そして、AIに変換してもらったものがこちらです。
テキスト出力版をグラフィカルにして、さらに、アニメーションも。
AIは、こちらの心を見透かして、先回りしてくれました。

再帰的バックトラッキングによる迷路生成

int cols, rows;
int w = 40;
Cell[][] grid;
ArrayList<Cell> stack = new ArrayList<Cell>();

void setup() {
  size(800, 800);
  frameRate(60);
  cols = floor(width / w);
  rows = floor(height / w);
  grid = new Cell[cols][rows];

  // グリッド初期化
  for (int j = 0; j < rows; j++) {
    for (int i = 0; i < cols; i++) {
      grid[i][j] = new Cell(i, j);
    }
  }

  grid[0][0].visited = true;
  stack.add(grid[0][0]);
}

void draw() {
  background(255);
  
  // グリッド描画
  for (int j = 0; j < rows; j++) {
    for (int i = 0; i < cols; i++) {
      grid[i][j].show();
    }
  }

  // 探索処理
  if (!stack.isEmpty()) {
    Cell current = stack.get(stack.size() - 1);
    Cell next = current.checkNeighbors();
    if (next != null) {
      next.visited = true;
      stack.add(next);
      removeWalls(current, next);
    } else {
      stack.remove(stack.size() - 1);
    }
  }
}

// 壁を削除
void removeWalls(Cell a, Cell b) {
  int x = a.i - b.i;
  int y = a.j - b.j;
  if (x == 1) {
    a.walls[3] = false;
    b.walls[1] = false;
  } else if (x == -1) {
    a.walls[1] = false;
    b.walls[3] = false;
  } else if (y == 1) {
    a.walls[0] = false;
    b.walls[2] = false;
  } else if (y == -1) {
    a.walls[2] = false;
    b.walls[0] = false;
  }
}

// セルクラス
class Cell {
  int i, j;
  boolean[] walls = { true, true, true, true }; // top, right, bottom, left
  boolean visited = false;

  Cell(int i, int j) {
    this.i = i;
    this.j = j;
  }

  void show() {
    int x = i * w;
    int y = j * w;
    stroke(0);
    if (walls[0]) line(x, y, x + w, y);
    if (walls[1]) line(x + w, y, x + w, y + w);
    if (walls[2]) line(x + w, y + w, x, y + w);
    if (walls[3]) line(x, y + w, x, y);
    if (visited) {
      noStroke();
      fill(200, 0, 255, 100);
      rect(x, y, w, w);
    }
  }

  Cell checkNeighbors() {
    ArrayList<Cell> neighbors = new ArrayList<Cell>();
    if (i > 0) {
      Cell left = grid[i - 1][j];
      if (!left.visited) neighbors.add(left);
    }
    if (i < cols - 1) {
      Cell right = grid[i + 1][j];
      if (!right.visited) neighbors.add(right);
    }
    if (j > 0) {
      Cell top = grid[i][j - 1];
      if (!top.visited) neighbors.add(top);
    }
    if (j < rows - 1) {
      Cell bottom = grid[i][j + 1];
      if (!bottom.visited) neighbors.add(bottom);
    }

    if (neighbors.size() > 0) {
      int r = int(random(neighbors.size()));
      return neighbors.get(r);
    } else {
      return null;
    }
  }
}

追記 2025/11/02

メモ（うまくいってない）
１，ハミルトン路問題
NP問題になり、正攻法では解決は困難。

２，パリティの説明
市松模様に塗った場合、数が同じでなければならない。

３，constraint-based maze
要文献調査

int cols, rows;
int w = 40;
Cell[][] grid;
ArrayList<Cell> stack = new ArrayList<Cell>();

boolean[][] mask;     // 黒Zだけtrue（通ってよい）
Cell[] waypoints = new Cell[4];

void setup() {
  size(800, 800);
  frameRate(60);

  cols = width / w;
  rows = height / w;

  // グリッド初期化
  grid = new Cell[cols][rows];
  for (int j = 0; j < rows; j++) {
    for (int i = 0; i < cols; i++) {
      grid[i][j] = new Cell(i, j);
    }
  }

  // 1. マスク読み込み（黒だけ通る）
  mask = loadMask("z.png", cols, rows);

  // 2. 中継地点をマスク上にスナップしておく
  waypoints[0] = snapToMask(0, 0);                 // (0,0)
  waypoints[1] = snapToMask(cols-5, 3);            // (39,0)
  waypoints[2] = snapToMask(4, rows-4);            // (0,39)
  waypoints[3] = snapToMask(cols-1, rows-1);       // (39,39)

  // 3. (0,0) → (39,0) を「DFS迷路」で掘る
  carveSegmentDFS(waypoints[0], waypoints[1]);

  // 4. (39,0) → (0,39)
  carveSegmentDFS(waypoints[1], waypoints[2]);

  // 5. (0,39) → (39,39)
  carveSegmentDFS(waypoints[2], waypoints[3]);

  // 6. 残りを埋めるために最後の地点から通常DFSを続ける
  waypoints[3].visited = true;
  stack.add(waypoints[3]);
}

void draw() {
  background(255);

  // 描画
  for (int j = 0; j < rows; j++) {
    for (int i = 0; i < cols; i++) {
      grid[i][j].show();
    }
  }

  // 残っているマスク領域を普通のDFSで埋める
  if (!stack.isEmpty()) {
    Cell current = stack.get(stack.size()-1);
    Cell next = current.checkNeighborsMask();  // マスク内だけ見る
    if (next != null) {
      next.visited = true;
      removeWalls(current, next);
      stack.add(next);
    } else {
      stack.remove(stack.size()-1);
    }
  } else {
    // まだ未訪問のマスクがあれば、そこからまたDFSを始める
    Cell c = findUnvisitedMaskCell();
    if (c != null) {
      c.visited = true;
      stack.add(c);
    }
  }
}

/* =========================================================
   画像 → マスク（黒だけtrue）
   ========================================================= */
boolean[][] loadMask(String fname, int cols, int rows) {
  PImage img = loadImage(fname);
  img.resize(cols, rows);
  img.loadPixels();

  boolean[][] m = new boolean[cols][rows];
  for (int y = 0; y < rows; y++) {
    for (int x = 0; x < cols; x++) {
      int c = img.pixels[y*cols + x];
      if (brightness(c) < 128) {
        m[x][y] = true;   // 黒なら通れる
      } else {
        m[x][y] = false;
      }
    }
  }
  return m;
}

/* =========================================================
   指定した(x,y)が白だったとき、近くの黒に寄せる
   ========================================================= */
Cell snapToMask(int x, int y) {
  x = constrain(x, 0, cols-1);
  y = constrain(y, 0, rows-1);

  if (mask[x][y]) return grid[x][y];

  int maxR = max(cols, rows);
  for (int r = 1; r < maxR; r++) {
    for (int dy = -r; dy <= r; dy++) {
      for (int dx = -r; dx <= r; dx++) {
        int nx = x + dx;
        int ny = y + dy;
        if (nx < 0 || nx >= cols || ny < 0 || ny >= rows) continue;
        if (mask[nx][ny]) {
          return grid[nx][ny];
        }
      }
    }
  }
  // なければとりあえず元のセル
  return grid[x][y];
}

/* =========================================================
   「再帰的バックトラッキング風」で start→goal を掘る
   途中で goal に着いたら止める
   ========================================================= */
void carveSegmentDFS(Cell start, Cell goal) {
  ArrayList<Cell> localStack = new ArrayList<Cell>();
  if (!start.visited) start.visited = true;
  localStack.add(start);

  while (!localStack.isEmpty()) {
    Cell cur = localStack.get(localStack.size()-1);

    // ここが「途中で止める」ポイント
    if (cur == goal) {
      break;
    }

    // マスク内だけから未訪問を探す（順序はランダム）
    ArrayList<Cell> neighbors = cur.unvisitedMaskNeighbors();
    if (neighbors.size() > 0) {
      // ランダムに選んでDFSらしくする
      int r = int(random(neighbors.size()));
      Cell next = neighbors.get(r);
      next.visited = true;
      removeWalls(cur, next);
      localStack.add(next);
    } else {
      // 行き止まりなので戻る
      localStack.remove(localStack.size()-1);
    }
  }
}

/* =========================================================
   残ってるマスクのセルを探す
   ========================================================= */
Cell findUnvisitedMaskCell() {
  for (int y = 0; y < rows; y++) {
    for (int x = 0; x < cols; x++) {
      if (mask[x][y] && !grid[x][y].visited) {
        return grid[x][y];
      }
    }
  }
  return null;
}

/* =========================================================
   壁を削除（あなたの元と同じ）
   ========================================================= */
void removeWalls(Cell a, Cell b) {
  int x = a.i - b.i;
  int y = a.j - b.j;
  if (x == 1) {
    a.walls[3] = false;
    b.walls[1] = false;
  } else if (x == -1) {
    a.walls[1] = false;
    b.walls[3] = false;
  } else if (y == 1) {
    a.walls[0] = false;
    b.walls[2] = false;
  } else if (y == -1) {
    a.walls[2] = false;
    b.walls[0] = false;
  }
}

/* =========================================================
   セルクラス
   ========================================================= */
class Cell {
  int i, j;
  boolean[] walls = { true, true, true, true };
  boolean visited = false;

  Cell(int i, int j) {
    this.i = i;
    this.j = j;
  }

  void show() {
    int x = i * w;
    int y = j * w;

    if (!mask[i][j]) {
      // 通れないところ（背景）
      noStroke();
      fill(255);
      rect(x, y, w, w);
      stroke(220);
      noFill();
      rect(x, y, w, w);
      return;
    }

    stroke(0);
    if (walls[0]) line(x, y, x + w, y);
    if (walls[1]) line(x + w, y, x + w, y + w);
    if (walls[2]) line(x + w, y + w, x, y + w);
    if (walls[3]) line(x, y + w, x, y);

    if (visited) {
      noStroke();
      fill(220, 190, 255, 110);
      rect(x, y, w, w);
    }

    // 見やすくするなら中継点を色付けしてもいい
    if (this == waypoints[0]) {
      noStroke(); fill(0,200,0,200); rect(x+1, y+1, w-9, w-9);
    }
    if (this == waypoints[1]) {
      noStroke(); fill(200,200,0,200); rect(x+1, y+1, w-9, w-9);
    }
    if (this == waypoints[2]) {
      noStroke(); fill(0,200,200,200); rect(x+1, y+1, w-9, w-9);
    }
    if (this == waypoints[3]) {
      noStroke(); fill(200,0,0,200); rect(x+1, y+1, w-9, w-9);
    }
  }

  // draw() で使う「マスク内だけ」のneighbors
  Cell checkNeighborsMask() {
    ArrayList<Cell> ns = unvisitedMaskNeighbors();
    if (ns.size() > 0) {
      int r = int(random(ns.size()));
      return ns.get(r);
    }
    return null;
  }

  // マスク内かつ未訪問の隣を全部返す
  ArrayList<Cell> unvisitedMaskNeighbors() {
    ArrayList<Cell> ns = new ArrayList<Cell>();
    if (i > 0) {
      if (mask[i-1][j] && !grid[i-1][j].visited) ns.add(grid[i-1][j]);
    }
    if (i < cols-1) {
      if (mask[i+1][j] && !grid[i+1][j].visited) ns.add(grid[i+1][j]);
    }
    if (j > 0) {
      if (mask[i][j-1] && !grid[i][j-1].visited) ns.add(grid[i][j-1]);
    }
    if (j < rows-1) {
      if (mask[i][j+1] && !grid[i][j+1].visited) ns.add(grid[i][j+1]);
    }
    return ns;
  }
}