AI Maze Generator - Recursive Backtracking Puzzle Navigate procedurally generated mazes! Adjust maz

function setup() {
  createCanvas(windowWidth, windowHeight);
  pixelDensity(1); // Ensure consistent rendering across screens

  // Create UI elements
  createUI();

  // Initial maze generation
  generateMaze();
}

function createUI() {
  let uiDiv = createDiv();
  uiDiv.style('position', 'absolute');
  uiDiv.style('top', '10px');
  uiDiv.style('left', '10px');
  uiDiv.style('background', 'rgba(255, 255, 255, 0.8)');
  uiDiv.style('padding', '10px');
  uiDiv.style('border-radius', '5px');
  uiDiv.style('font-family', 'sans-serif');
  uiDiv.style('color', '#333');

  infoText = createP('Maze Size: 20x20');
  infoText.parent(uiDiv);
  infoText.style('margin', '0 0 10px 0');

  sizeSlider = createSlider(10, 50, 20, 1); // Min, Max, Default, Step
  sizeSlider.parent(uiDiv);
  sizeSlider.style('width', '200px');
  sizeSlider.input(() => {
    infoText.html(`Maze Size: ${sizeSlider.value()}x${sizeSlider.value()}`);
  });

  generateButton = createButton('Generate New Maze');
  generateButton.parent(uiDiv);
  generateButton.style('margin-top', '10px');
  generateButton.mousePressed(generateMaze);

  solveButton = createButton('Solve Maze');
  solveButton.parent(uiDiv);
  solveButton.style('margin-left', '10px');
  solveButton.style('margin-top', '10px');
  solveButton.mousePressed(solveMaze);
}

function draw() {
  background(0); // Dark background

  // Draw all cells
  for (let j = 0; j < rows; j++) {
    for (let i = 0; i < cols; i++) {
      grid[i][j].show();
    }
  }

  // Draw current cell during generation
  if (!mazeGenerated && current) {
    current.highlight();
  }

  // Draw solution path if solving
  if (solvingMaze && solutionPath.length > 0) {
    drawSolution();
  }

  // Draw player
  drawPlayer();

  // Draw goal
  drawGoal();

  // Continue maze generation step by step if not yet complete
  if (!mazeGenerated) {
    recursiveBacktrackingStep();
  }
}

function generateMaze() {
  cols = sizeSlider.value();
  rows = sizeSlider.value();
  cellWidth = min(width, height) / cols; // Make it square based on smaller dimension

  grid = [];
  stack = [];
  mazeGenerated = false;
  solvingMaze = false;
  solutionPath = [];

  // Initialize grid
  for (let i = 0; i < cols; i++) {
    grid[i] = [];
    for (let j = 0; j < rows; j++) {
      grid[i][j] = new Cell(i, j);
    }
  }

  // Set starting cell for generation
  current = grid[0][0];
  current.visited = true;
  stack.push(current);

  // Set player and goal
  player = { i: 0, j: 0 }; // Start at top-left
  goal = grid[cols - 1][rows - 1]; // Goal at bottom-right
  
  // Set goal cell's parent to null for BFS
  goal.parent = null;
}

function recursiveBacktrackingStep() {
  if (stack.length === 0) {
    mazeGenerated = true;
    console.log("Maze Generated!");
    return;
  }

  current = stack[stack.length - 1]; // Look at the top of the stack (don't pop yet)

  let neighbors = current.checkNeighbors();

  if (neighbors.length > 0) {
    let next = random(neighbors);

    // Remove walls
    removeWalls(current, next);

    next.visited = true;
    stack.push(next); // Push the new cell onto the stack
  } else {
    stack.pop(); // Backtrack
  }
}

function removeWalls(a, b) {
  let x = a.i - b.i;
  if (x === 1) { // b is to the left of a
    a.walls[3] = false; // a's left wall
    b.walls[1] = false; // b's right wall
  } else if (x === -1) { // b is to the right of a
    a.walls[1] = false; // a's right wall
    b.walls[3] = false; // b's left wall
  }

  let y = a.j - b.j;
  if (y === 1) { // b is above a
    a.walls[0] = false; // a's top wall
    b.walls[2] = false; // b's bottom wall
  } else if (y === -1) { // b is below a
    a.walls[2] = false; // a's bottom wall
    b.walls[0] = false; // b's top wall
  }
}

function solveMaze() {
  if (!mazeGenerated) {
    console.log("Maze not yet generated. Please wait.");
    return;
  }
  if (solvingMaze) {
    console.log("Maze already being solved or solution shown.");
    return;
  }

  solvingMaze = true;
  solutionPath = [];

  // Reset visited status for pathfinding and parent references
  for (let j = 0; j < rows; j++) {
    for (let i = 0; i < cols; i++) {
      grid[i][j].pathVisited = false;
      grid[i][j].parent = null;
    }
  }

  let startCell = grid[player.i][player.j];
  let queue = [];

  queue.push(startCell);
  startCell.pathVisited = true;

  while (queue.length > 0) {
    let currentCell = queue.shift();

    if (currentCell === goal) {
      // Goal reached, reconstruct path
      let pathCell = goal;
      while (pathCell !== null) {
        solutionPath.unshift(pathCell); // Add to the beginning of the array
        pathCell = pathCell.parent;
      }
      console.log("Solution found!");
      return;
    }

    // Check neighbors (top, right, bottom, left)
    let neighbors = [];
    if (!currentCell.walls[0] && currentCell.j > 0) neighbors.push(grid[currentCell.i][currentCell.j - 1]); // Top
    if (!currentCell.walls[1] && currentCell.i < cols - 1) neighbors.push(grid[currentCell.i + 1][currentCell.j]); // Right
    if (!currentCell.walls[2] && currentCell.j < rows - 1) neighbors.push(grid[currentCell.i][currentCell.j + 1]); // Bottom
    if (!currentCell.walls[3] && currentCell.i > 0) neighbors.push(grid[currentCell.i - 1][currentCell.j]); // Left

    for (let neighbor of neighbors) {
      if (!neighbor.pathVisited) {
        neighbor.pathVisited = true;
        neighbor.parent = currentCell;
        queue.push(neighbor);
      }
    }
  }

  console.log("No solution found (this should not happen in a generated maze).");
}

function drawSolution() {
  // Draw path as a series of connected circles
  noFill();
  stroke(0, 0, 255, 150); // Blue for solution path
  strokeWeight(cellWidth / 4);

  beginShape();
  for (let cell of solutionPath) {
    let x = cell.i * cellWidth + cellWidth / 2;
    let y = cell.j * cellWidth + cellWidth / 2;
    vertex(x, y);
  }
  endShape();
}

function drawPlayer() {
  fill(0, 255, 0); // Green for player
  noStroke();
  let x = player.i * cellWidth + cellWidth / 2;
  let y = player.j * cellWidth + cellWidth / 2;
  circle(x, y, cellWidth * 0.6);
}

function drawGoal() {
  fill(255, 0, 0); // Red for goal
  noStroke();
  let x = goal.i * cellWidth + cellWidth / 2;
  let y = goal.j * cellWidth + cellWidth / 2;
  circle(x, y, cellWidth * 0.7);
}

function keyPressed() {
  if (!mazeGenerated) return; // Don't move player while maze is generating

  let currentCell = grid[player.i][player.j];
  let nextI = player.i;
  let nextJ = player.j;

  if (keyCode === LEFT_ARROW) {
    if (!currentCell.walls[3]) { // Check left wall
      nextI--;
    }
  } else if (keyCode === RIGHT_ARROW) {
    if (!currentCell.walls[1]) { // Check right wall
      nextI++;
    }
  } else if (keyCode === UP_ARROW) {
    if (!currentCell.walls[0]) { // Check top wall
      nextJ--;
    }
  } else if (keyCode === DOWN_ARROW) {
    if (!currentCell.walls[2]) { // Check bottom wall
      nextJ++;
    }
  }

  // Ensure player stays within bounds
  nextI = constrain(nextI, 0, cols - 1);
  nextJ = constrain(nextJ, 0, rows - 1);

  // Update player position
  player.i = nextI;
  player.j = nextJ;

  // If player moves, hide solution if it was active
  if (solvingMaze) {
    solvingMaze = false;
    solutionPath = [];
  }
}

class Cell {
  constructor(i, j) {
    this.i = i;
    this.j = j;
    this.walls = [true, true, true, true]; // [top, right, bottom, left]
    this.visited = false; // For maze generation
    this.pathVisited = false; // For pathfinding
    this.parent = null; // For pathfinding to reconstruct the path
  }

  show() {
    let x = this.i * cellWidth;
    let y = this.j * cellWidth;

    stroke(255); // White walls
    strokeWeight(2);

    // Draw walls if they exist
    if (this.walls[0]) line(x, y, x + cellWidth, y);           // Top
    if (this.walls[1]) line(x + cellWidth, y, x + cellWidth, y + cellWidth); // Right
    if (this.walls[2]) line(x + cellWidth, y + cellWidth, x, y + cellWidth); // Bottom
    if (this.walls[3]) line(x, y + cellWidth, x, y);           // Left

    // Highlight visited cells during generation (optional, can be removed once generated)
    if (this.visited && !mazeGenerated) {
      noStroke();
      fill(255, 0, 255, 50); // Pink highlight
      rect(x, y, cellWidth, cellWidth);
    }
  }

  highlight() {
    let x = this.i * cellWidth;
    let y = this.j * cellWidth;
    noStroke();
    fill(0, 255, 255, 100); // Cyan highlight for current cell
    rect(x, y, cellWidth, cellWidth);
  }

  checkNeighbors() {
    let neighbors = [];

    // Check neighbors (top, right, bottom, left)
    let top    = this.j > 0 ? grid[this.i][this.j - 1] : undefined;
    let right  = this.i < cols - 1 ? grid[this.i + 1][this.j] : undefined;
    let bottom = this.j < rows - 1 ? grid[this.i][this.j + 1] : undefined;
    let left   = this.i > 0 ? grid[this.i - 1][this.j] : undefined;

    if (top && !top.visited) neighbors.push(top);
    if (right && !right.visited) neighbors.push(right);
    if (bottom && !bottom.visited) neighbors.push(bottom);
    if (left && !left.visited) neighbors.push(left);

    return neighbors;
  }
}

function windowResized() {
  resizeCanvas(windowWidth, windowHeight);
  // Recalculate cell width and redraw maze
  cellWidth = min(width, height) / cols;
  redraw(); // Redraw the maze based on new canvas size
}