【React】壁伸ばし法で迷路を生成する

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

Canvas.tsx

import React, { useEffect } from 'react';
import p5 from 'p5';
import Maze from './maze';

const sketch = (p: p5) => {
  p.setup = () => {
    const maze1 = new Maze(p, 15, 15);
    maze1.set_maze_kabenobashi();
    maze1.print_maze();
  }
}
    
const Canvas = () => {
  useEffect(() => {
    new p5(sketch)
  })
  return (
    <React.Fragment>
    </React.Fragment>
  );
}
    
export default Canvas;

maze.ts

import p5 from 'p5';

class Maze {
  p: p5;
  PATH: number;
  WALL: number;
  width: number;
  height: number;
  maze: number[][] = [];

  constructor(p: p5, width: number, height: number, seed: number = 0) {
    this.p = p;
    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(this.height)].map(() => Array(this.width).fill(0));
    p.randomSeed(seed);
  }

  set_outer_wall(): number[][] {
    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(): number[][] {
    let stack: number[][] = [], point: number[], extending_wall: number[][], directions: number[], direction: number;
    this.set_outer_wall();
    for (let y = 2; y <= this.height-3; y+=2) {
      for (let x = 2; x <= this.width-3; x+=2) {
        stack.push([x,y]);
      }
    }
    while (true) {
      if (stack.length === 0) {
        break;
      }
      stack = this.p.shuffle(stack);
      point = stack.pop()!;
      if (this.maze[point[1]][point[0]] === this.WALL) {
        continue;
      }
      this.maze[point[1]][point[0]] = this.WALL;
      extending_wall = [];
      extending_wall.push(point);
      while (true) {
        directions = [];
        if (this.maze[point[1]-1][point[0]] === this.PATH && !extending_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 && !extending_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 && !extending_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 && !extending_wall.some(e => e[0] === point[0]-2 && e[1] === point[1])) {
          directions.push(3);
        }
        if (directions.length === 0) {
          break;
        }
        direction = directions[this.p.floor(this.p.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;
            extending_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;
            extending_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;
            extending_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;
            extending_wall.push([point[0]-2,point[1]]);
            point = [point[0]-2,point[1]];
          }
        }
      }
    }
    return this.maze;
  }

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

export default Maze;

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

###############
#   #     # # #
### # # # # # #
#     # #     #
##### # # #####
#     # #   # #
# # ####### # #
# # # #     # #
# ### ### # # #
#     # # #   #
# ### # # ### #
#   # # # # # #
# ### # ### ###
#   #         #
###############

参考

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

コメント

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