🔄 Recursive Backtracking Algorithm in JavaScript

class MazeGenerator {
  constructor(width, height) {
    this.width = width;
    this.height = height;
    this.maze = this.initializeMaze();
    this.visited = new Set();
  }

  initializeMaze() {
    // Create maze with all walls
    return Array(this.height).fill().map(() => 
      Array(this.width).fill().map(() => ({
        top: true, right: true, bottom: true, left: true
      }))
    );
  }

  generateMaze(startX = 0, startY = 0) {
    const stack = [[startX, startY]];
    this.visited.add(`${startX},${startY}`);

    while (stack.length > 0) {
      const [currentX, currentY] = stack[stack.length - 1];
      const neighbors = this.getUnvisitedNeighbors(currentX, currentY);

      if (neighbors.length > 0) {
        // Choose random neighbor
        const [nextX, nextY] = neighbors[Math.floor(Math.random() * neighbors.length)];
        
        // Remove wall between current and next cell
        this.removeWall(currentX, currentY, nextX, nextY);
        
        // Mark as visited and add to stack
        this.visited.add(`${nextX},${nextY}`);
        stack.push([nextX, nextY]);
      } else {
        // Backtrack
        stack.pop();
      }
    }

    return this.maze;
  }

  getUnvisitedNeighbors(x, y) {
    const neighbors = [];
    const directions = [[0, -1], [1, 0], [0, 1], [-1, 0]]; // Up, Right, Down, Left

    for (const [dx, dy] of directions) {
      const newX = x + dx;
      const newY = y + dy;
      
      if (this.isValidCell(newX, newY) && !this.visited.has(`${newX},${newY}`)) {
        neighbors.push([newX, newY]);
      }
    }

    return neighbors;
  }

  removeWall(x1, y1, x2, y2) {
    const dx = x2 - x1;
    const dy = y2 - y1;

    if (dx === 1) { // Moving right
      this.maze[y1][x1].right = false;
      this.maze[y2][x2].left = false;
    } else if (dx === -1) { // Moving left
      this.maze[y1][x1].left = false;
      this.maze[y2][x2].right = false;
    } else if (dy === 1) { // Moving down
      this.maze[y1][x1].bottom = false;
      this.maze[y2][x2].top = false;
    } else if (dy === -1) { // Moving up
      this.maze[y1][x1].top = false;
      this.maze[y2][x2].bottom = false;
    }
  }

  isValidCell(x, y) {
    return x >= 0 && x < this.width && y >= 0 && y < this.height;
  }
}