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

はじめに

自分は小学生の頃、自由帳に書くものといえば、キン肉マンか迷路。これが２大コンテンツでした。ある日「惡魔の迷図」（悪魔の迷図）（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;
    }
  }
}