Maze algorithms in JavaScript

backtracking.js

class Backtracking {
  constructor(height, width) {
    if (width % 2 === 0) {
      width += 1;
    }
    if (height % 2 === 0) {
      height += 1;
    }

    this.width = width;
    this.height = height;
    this.grid = Array(height)
      .fill(null)
      .map(() => Array(width).fill(true));
  }

  createMaze() {
    this.carve(1, 1);
    this.grid[1][0] = false;
    this.grid[this.height - 2][this.width - 1] = false;
    return this.grid;
  }

  carve(x, y) {
    this.grid[y][x] = false;

    const directions = [Directions.UP, Directions.DOWN, Directions.LEFT, Directions.RIGHT];

    for (let i = directions.length - 1; i >= 0; i--) {
      const randomIndex = Math.floor(Math.random() * (i + 1));
      const direction = directions[randomIndex];
      directions[randomIndex] = directions[i];

      let nx = x;
      let ny = y;

      if (direction === Directions.UP) {
        ny -= 2;
      } else if (direction === Directions.DOWN) {
        ny += 2;
      } else if (direction === Directions.LEFT) {
        nx -= 2;
      } else {
        nx += 2;
      }

      if (ny < 0 || ny >= this.height || nx < 0 || nx >= this.width || !this.grid[ny][nx]) {
        continue;
      }

      this.grid[(y + ny) >> 1][(x + nx) >> 1] = false;
      this.carve(nx, ny);
    }
  }
}