迷路の幅と高さをそれぞれ width, height として設定し、
その数値にしたがって壁伸ばし法で迷路を生成する。
※迷路の幅と高さは5以上の奇数とする。
let maze1;
function setup() {
maze1 = new Maze(15, 15);
maze1.set_maze_kabenobashi();
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));
randomSeed(seed);
}
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_kabenobashi() {
this.set_outer_wall();
let stack = [];
for (let y = 2; y < this.height-1; y+=2) {
for (let x = 2; x < this.width-1; x+=2) {
stack.push([x,y]);
}
}
while (true) {
if (stack.length == 0) {
break;
}
stack = shuffle(stack);
let _point = stack.pop();
if (this.maze[_point[1]][_point[0]] == this.WALL) {
continue;
}
this.maze[_point[1]][_point[0]] = this.WALL;
let extend_wall = []
extend_wall.push([_point[0],_point[1]]);
while (true) {
let directions = [];
if (this.maze[_point[1]-1][_point[0]] == this.PATH && !extend_wall.some(e => e[0] == _point[0] && e[1] == _point[1]-2)) {
directions.push(0);
}
if (this.maze[_point[1]][_point[0]+1] == this.PATH && !extend_wall.some(e => e[0] == _point[0]+2 && e[1] == _point[1])) {
directions.push(1);
}
if (this.maze[_point[1]+1][_point[0]] == this.PATH && !extend_wall.some(e => e[0] == _point[0] && e[1] == _point[1]+2)) {
directions.push(2);
}
if (this.maze[_point[1]][_point[0]-1] == this.PATH && !extend_wall.some(e => e[0] == _point[0]-2 && e[1] == _point[1])) {
directions.push(3);
}
if (directions.length == 0) {
break;
}
let direction = directions[floor(random(directions.length))];
if (direction == 0) {
if (this.maze[_point[1]-2][_point[0]] == this.WALL) {
this.maze[_point[1]-1][_point[0]] = this.WALL;
break;
} else {
this.maze[_point[1]-1][_point[0]] = this.WALL;
this.maze[_point[1]-2][_point[0]] = this.WALL;
extend_wall.push([_point[0],_point[1]-2]);
_point = [_point[0],_point[1]-2];
}
} else if (direction == 1) {
if (this.maze[_point[1]][_point[0]+2] == this.WALL) {
this.maze[_point[1]][_point[0]+1] = this.WALL;
break;
} else {
this.maze[_point[1]][_point[0]+1] = this.WALL;
this.maze[_point[1]][_point[0]+2] = this.WALL;
extend_wall.push([_point[0]+2,_point[1]]);
_point = [_point[0]+2,_point[1]];
}
} else if (direction == 2) {
if (this.maze[_point[1]+2][_point[0]] == this.WALL) {
this.maze[_point[1]+1][_point[0]] = this.WALL;
break;
} else {
this.maze[_point[1]+1][_point[0]] = this.WALL;
this.maze[_point[1]+2][_point[0]] = this.WALL;
extend_wall.push([_point[0],_point[1]+2]);
_point = [_point[0],_point[1]+2];
}
} else if (direction == 3) {
if (this.maze[_point[1]][_point[0]-2] == this.WALL) {
this.maze[_point[1]][_point[0]-1] = this.WALL;
break;
} else {
this.maze[_point[1]][_point[0]-1] = this.WALL;
this.maze[_point[1]][_point[0]-2] = this.WALL;
extend_wall.push([_point[0]-2,_point[1]]);
_point = [_point[0]-2,_point[1]];
}
}
}
}
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);
}
}
}
今回は、以下のように出力される。
###############
# # # # #
### # # # # # #
# # # #
##### # # #####
# # # # #
# # ####### # #
# # # # # #
# ### ### # # #
# # # # #
# ### # # ### #
# # # # # # #
# ### # ### ###
# # #
###############
set-maze-kabenobashi-js by inoha_naito -p5.js Web Editor
A web editor for p5.js, a JavaScript library with the goal of making coding accessible to artists, designers, educators,...
参考
迷路生成(壁伸ばし法) - Algoful
壁伸ばし法は迷路生成アルゴリズムの一種です。何もない状態から壁を生成することで迷路を作り上げます。シミュレーション機能で生成される過程を確認できます。C#の実装サンプルを用意しているのでUnityでのゲーム開発の参考にどうぞ。
[Python] 壁伸ばし法による迷路生成
迷路生成のアルゴリズム 迷路生成のアルゴリズムは数多くあります。 Maze Classification -M…
自動生成迷路