Chapter 92

迷路生成

miku
miku
2021.11.19に更新

棒倒し法


サイズが奇数×奇数の二次元配列を用意する。配列の外側はすべて壁で埋め、内部は1マスおきに壁を配置していく。

3行目に配置した内部の壁があるが、それを一つずつ倒す、つまり上下左右いずれか一つに壁を作る。この際、すでに置かれている壁のところには作らないように注意する。

5行目も同じように倒していくが、上に倒してはいけない、という制約も付け加える。7行目、9行目、11行目…と内部に配置した壁の行を5行目と同じように上以外の方向に壁を倒せば迷路の完成となる。

棒倒し法の実装例

const CellType = {
  Floor: "floor",
  Wall: "wall",
};

const tileWidth = 59;
const tileHeight = 41;
const tileSize = 10;
let map;

function setup() {
  createCanvas(windowWidth, windowHeight);

  map = [];
  for (let y = 0; y < tileHeight; y++) {
    map[y] = [];
    for (let x = 0; x < tileWidth; x++) {
      map[y][x] = CellType.Floor;

      if (x === 0 || x === tileWidth - 1 || y === 0 || y === tileHeight - 1) {
        map[y][x] = CellType.Wall;
      }
      if (x % 2 === 0 && y % 2 === 0) {
        map[y][x] = CellType.Wall;
      }
    }
  }

  for (let y = 2; y < tileHeight - 1; y += 2) {
    for (let x = 2; x < tileWidth - 1; x += 2) {
      const directions = [
        { x: 1, y: 0 },
        { x: 0, y: 1 },
        { x: -1, y: 0 },
      ];
      if (y === 2) {
        directions.push({ x: 0, y: -1 });
      }
      while (true) {
        const dir = random(directions);
        const tx = x + dir.x;
        const ty = y + dir.y;

        if (0 <= tx && tx < tileWidth && 0 <= ty && ty < tileHeight && map[ty][tx] === CellType.Floor) {
          map[ty][tx] = CellType.Wall;
          break;
        }
      }
    }
  }

  clear();
  fill("#666");
  strokeWeight(1);

  for (let y = 0; y < tileHeight; y++) {
    for (let x = 0; x < tileWidth; x++) {
      const tile = map[y][x];
      if (tile === CellType.Wall) {
        const tx = x * tileSize;
        const ty = y * tileSize;
        rect(tx, ty, tileSize, tileSize);
      }
    }
  }
}

穴掘り法


サイズが奇数×奇数の二次元配列を用意して、配列をすべて壁で埋めておく。

ランダムな偶数位置の座標を選び、そこを通路にする。

上下左右いずれかの方向の2マス先が壁ならそこまで通路して掘り進める。

掘り進めた先で同じように上記処理をさせ、この処理ができなくなるまで繰り返す。

2マス前の位置まで戻り、別の方向の2マス先が掘れるなら、その方向を掘り進める。

上記処理を繰り返すことで迷路が完成する。

穴掘り法の実装例

const CellType = {
  Floor: "floor",
  Wall: "wall",
};

const tileWidth = 59;
const tileHeight = 41;
const tileSize = 10;
const directions = [
  { x: 0, y: -1 },
  { x: 1, y: 0 },
  { x: 0, y: 1 },
  { x: -1, y: 0 },
];
let map;
let positions;

function setup() {
  createCanvas(windowWidth, windowHeight);

  map = [];
  for (let y = 0; y < tileHeight; y++) {
    map[y] = [];
    for (let x = 0; x < tileWidth; x++) {
      map[y][x] = CellType.Wall;
    }
  }

  positions = [];

  const sx = floor(random((tileWidth - 1) / 2 - 1)) * 2 + 1;
  const sy = floor(random((tileHeight - 1) / 2 - 1)) * 2 + 1;
  map[sy][sx] = CellType.Floor;
  positions.push({ x: sx, y: sy });

  while (0 < positions.length) {
    const next = positions.pop();
    dig(next.x, next.y);
  }

  clear();
  fill("#666");
  strokeWeight(1);

  for (let y = 0; y < tileHeight; y++) {
    for (let x = 0; x < tileWidth; x++) {
      const tile = map[y][x];
      if (tile === CellType.Wall) {
        const tx = x * tileSize;
        const ty = y * tileSize;
        rect(tx, ty, tileSize, tileSize);
      }
    }
  }
}

function dig(x, y) {
  const dirs = shuffle(directions);

  for (const dir of dirs) {
    const tx = x + dir.x;
    const ty = y + dir.y;
    const tx2 = x + dir.x * 2;
    const ty2 = y + dir.y * 2;

    if (0 <= tx2 && tx2 < tileWidth && 0 <= ty2 && ty2 < tileHeight && map[ty2][tx2] === CellType.Wall) {
      map[ty][tx] = CellType.Floor;
      map[ty2][tx2] = CellType.Floor;

      positions.push({ x, y });
      positions.push({ x: tx2, y: ty2 });

      return { x: tx2, y: ty2 };
    }
  }

  return null;
}

壁のばし法


サイズが奇数×奇数の二次元配列を用意する。配列の外側をすべて壁で埋めておく。縦横奇数番目の壁の座標をすべて取得し配列に格納して、配列の要素をランダムに並び替えておく。

下記処理を配列の中身が空になるまで繰り返す。

  1. 配列の先頭から要素(座標)を一つ取り出す。
  2. 取り出した座標から上下左右それぞれを見て、それらの方向の1マス先と2マス先が通路なら、その1マス先と2マス先を壁にする。
  3. 2マス先の座標を配列の先頭に登録。
  4. 取り出した座標を配列の末尾に登録。
  5. 上下左右をチェックするループを強制的に抜ける。

例えば上下左右のうち、上に進めそうなら、そのまま上の2マス先まで壁を埋め、2マス先の座標を配列の先頭に登録する。先頭に登録するのはこのすぐあとにそこからまたスタートしたいからである。

上に進んだ場合、まだ確認していない方向を見ずに上下左右ループを抜ける。取り出した座標を末尾に登録しているので、後に他の方向をチェックできるからである。

上記探索が終了すると迷路が完成する。

壁のばし法の実装例

const CellType = {
  Floor: "floor",
  Wall: "wall",
};

const tileWidth = 59;
const tileHeight = 41;
const tileSize = 10;
const directions = [
  { x: 0, y: -1 },
  { x: 1, y: 0 },
  { x: 0, y: 1 },
  { x: -1, y: 0 },
];
let map;
let positions;

function setup() {
  createCanvas(windowWidth, windowHeight);

  map = [];
  for (let y = 0; y < tileHeight; y++) {
    map[y] = [];
    for (let x = 0; x < tileWidth; x++) {
      if (x === 0 || x === tileWidth - 1 || y === 0 || y === tileHeight - 1) {
        map[y][x] = CellType.Wall;
      } else {
        map[y][x] = CellType.Floor;
      }
    }
  }

  positions = [];
  for (let y = 0; y < tileHeight; y += 2) {
    positions.push({ x: 0, y });
    positions.push({ x: tileWidth - 1, y });
  }

  for (let x = 0; x < tileWidth; x += 2) {
    positions.push({ x, y: 0 });
    positions.push({ x, y: tileHeight - 1 });
  }

  shuffle(positions);

  while (0 < positions.length) {
    const next = positions.shift();
    createWall(next.x, next.y);
  }

  clear();
  fill("#666");
  strokeWeight(1);

  for (let y = 0; y < tileHeight; y++) {
    for (let x = 0; x < tileWidth; x++) {
      const tile = map[y][x];
      if (tile === CellType.Wall) {
        const tx = x * tileSize;
        const ty = y * tileSize;
        rect(tx, ty, tileSize, tileSize);
      }
    }
  }
}

function createWall(x, y) {
  const dirs = shuffle(directions);

  for (const dir of dirs) {
    const tx = x + dir.x;
    const ty = y + dir.y;
    const tx2 = x + dir.x * 2;
    const ty2 = y + dir.y * 2;

    if (0 <= tx2 && tx2 < tileWidth && 0 <= ty2 && ty2 < tileHeight && map[ty][tx] === CellType.Floor && map[ty2][tx2] === CellType.Floor) {
      map[ty][tx] = CellType.Wall;
      map[ty2][tx2] = CellType.Wall;

      positions.unshift({ x: tx2, y: ty2 });
      positions.push({ x, y });
      break;
    }
  }
}