【p5.js】穴掘り法で迷路を生成する

迷路の幅と高さをそれぞれ width, height として設定し、
その数値にしたがって穴掘り法で迷路を生成する。
※迷路の幅と高さは5以上の奇数とする。

let maze1;

function setup() {
  maze1 = new Maze(15, 15);
  maze1.set_maze_anahori();
  maze1.print_maze();
}

class Maze {
  constructor(width, height, seed=0) {
    this.PATH = 0;
    this.WALL = 1;
    this.width = width;
    this.height = height;
    if (this.width < 5 || this.height < 5) {
      return;
    }
    if (this.width%2 == 0) {
      this.width++;
    }
    if (this.height%2 == 0) {
      this.height++;
    }
    this.maze = Array.from(new Array(this.height), () => new Array(this.width).fill(this.PATH));
    this.start = [1, 1];
    randomSeed(seed);
  }

  set_all_wall() {
    for (let y = 0; y < this.height; ++y) {
      for (let x = 0; x < this.width; ++x) {
        this.maze[y][x] = this.WALL;
      }
    }
    return this.maze;
  }

  set_outer_path() {
    for (let y = 0; y < this.height; ++y) {
      for (let x = 0; x < this.width; ++x) {
        if (x == 0 || y == 0 || x == this.width-1 || y == this.height-1) {
          this.maze[y][x] = this.PATH;
        }
      }
    }
    return this.maze;
  }

  set_outer_wall() {
    for (let y = 0; y < this.height; ++y) {
      for (let x = 0; x < this.width; ++x) {
        if (x == 0 || y == 0 || x == this.width-1 || y == this.height-1) {
          this.maze[y][x] = this.WALL;
        }
      }
    }
    return this.maze;
  }

  set_maze_anahori() {
    this.set_all_wall();
    this.set_outer_path();
    let stack = [];
    let point = this.start;
    stack.push(point);
    this.maze[point[1]][point[0]] = this.PATH;
    while (true) {
      if (stack.length == 0) {
        break;
      }
      stack = shuffle(stack);
      point = stack.pop();
      while (true) {
        let directions = [];
        if (this.maze[point[1]-1][point[0]] == this.WALL && this.maze[point[1]-2][point[0]] == this.WALL) {
          directions.push(0);
        }
        if (this.maze[point[1]][point[0]+1] == this.WALL && this.maze[point[1]][point[0]+2] == this.WALL) {
          directions.push(1);
        }
        if (this.maze[point[1]+1][point[0]] == this.WALL && this.maze[point[1]+2][point[0]] == this.WALL) {
          directions.push(2);
        }
        if (this.maze[point[1]][point[0]-1] == this.WALL && this.maze[point[1]][point[0]-2] == this.WALL) {
          directions.push(3);
        }
        if (directions.length == 0) {
          break;
        }
        let direction = directions[floor(random(directions.length))];
        if (direction == 0) {
          this.maze[point[1]-1][point[0]] = this.PATH;
          this.maze[point[1]-2][point[0]] = this.PATH;
          stack.push([point[0],point[1]]);
          point = [point[0],point[1]-2];
        } else if (direction == 1) {
          this.maze[point[1]][point[0]+1] = this.PATH;
          this.maze[point[1]][point[0]+2] = this.PATH;
          stack.push([point[0],point[1]]);
          point = [point[0]+2,point[1]];
        } else if (direction == 2) {
          this.maze[point[1]+1][point[0]] = this.PATH;
          this.maze[point[1]+2][point[0]] = this.PATH;
          stack.push([point[0],point[1]]);
          point = [point[0],point[1]+2];
        } else if (direction == 3) {
          this.maze[point[1]][point[0]-1] = this.PATH;
          this.maze[point[1]][point[0]-2] = this.PATH;
          stack.push([point[0],point[1]]);
          point = [point[0]-2,point[1]];
        }
      }
    }
    this.set_outer_wall();
    return this.maze;
  }

  print_maze() {
    for (let col of this.maze) {
      let arr = '';
      for(let cell of col) {
        if (cell == this.WALL) {
          arr += '#';
        } else if (cell == this.PATH) {
          arr += ' ';
        }
      }
      console.log(arr);
    }
  }
}

今回は、以下のように出力される。

###############
#     # #     #
##### # # ### #
# #   # # #   #
# # ### # #####
# # #   #     #
# # # ####### #
# #   #     # #
# # ### ### # #
# #     #   # #
# # ##### # # #
# # #   # # # #
# # # # # # # #
#   # #   #   #
###############
p5.js Web Editor
A web editor for p5.js, a JavaScript library with the goal of making coding accessible to artists, designers, educators, and beginners.

参考

迷路生成(穴掘り法) - Algoful
穴掘り法は迷路生成アルゴリズムの一種です...
[Python] 穴掘り法による迷路生成
迷路生成のアルゴリズム 迷路生成のアルゴリズムは数多くあります。 Maze Classification -M…
自動生成迷路

コメント

タイトルとURLをコピーしました