// https://en.wikipedia.org/wiki/Maze_generation_algorithm#Recursive_implementation

// https://www.youtube.com/watch?v=_p5IH0L63wo

​

// const canvasWidth = 400

// const canvasHeight = 400

// const cellWidth = 20

// const nRows = 20

// const nCols = 20

​

const canvasWidth = 400

const canvasHeight = 400

const cellWidth = 20

// const nRows = floor(canvasWidth/cellWidth) (uses floor(), therefore has to be inside setUp function)

const nRows = 20

//const nCols = floor(canvasHeight/cellWidth)

const nCols = 20

​

​

const grid = []

const visitedCells = new Set()

const backtrackStack = []

​

let currentCell

​

​

class Walls {

  constructor(){

    this.top = true

    this.bottom = true

    this.right = true

    this.left = true

  }

  removeTop() {

    this.top = false

  }

  removeBottom() {

    this.bottom = false

  }

  removeLeft() {

    this.left = false

  }

  removeRight() {

    this.right = false

  }

​

}

​

const arrayIndex = (row, col) => (row * nRows) + col

​

const isValid = (row, col) => row >= 0 && row < nRows && col >= 0 && col < nCols

​

const removeCommonWall = (cell1, cell2) => {

  if (cell1.col - cell2.col < 0) {

    cell1.walls.right = false

    cell2.walls.left = false

  }

  else if (cell1.col - cell2.col > 0){

    cell1.walls.left = false

    cell2.walls.right = false

  }

  else if (cell1.row - cell2.row > 0){

    cell1.walls.top = false

    cell2.walls.bottom = false

  }

  else if (cell1.row - cell2.row < 0){

    cell1.walls.bottom = false

    cell2.walls.top = false

  }

}

​

const Cell = (rowNumber, colNumber) => {

  const row = rowNumber

  const col = colNumber

  const walls = new Walls()

  const show = () => {

    const x = row * cellWidth

    const y = col * cellWidth

    stroke(255)

    if (walls.top) line(x, y, x, y + cellWidth)

    if (walls.bottom) line(x + cellWidth, y, x + cellWidth, y + cellWidth)

    if (walls.right) line(x, y + cellWidth, x + cellWidth, y + cellWidth)

    if (walls.left) line(x, y, x + cellWidth, y) 

    if (visitedCells.has(arrayIndex(row, col)))

      {

        noStroke()

        fill(255, 0, 255, 100)

        rect(row * cellWidth, col * cellWidth, cellWidth, cellWidth)

      }

  }

  const highlight = () => 

    {

      noStroke()

      fill(0, 255, 0)

      rect(row * cellWidth, col * cellWidth, cellWidth, cellWidth)

    }

  const unvisitedNeighbors = () => {

    const neighbors = []

    if (isValid(row - 1, col) && !visitedCells.has(arrayIndex(row - 1, col))) neighbors.push(arrayIndex(row - 1, col))

    if (isValid(row + 1, col) && !visitedCells.has(arrayIndex(row + 1, col))) neighbors.push(arrayIndex(row + 1, col))

    if (isValid(row, col - 1) && !visitedCells.has(arrayIndex(row, col - 1))) neighbors.push(arrayIndex(row, col - 1))

    if (isValid(row, col + 1) && !visitedCells.has(arrayIndex(row, col + 1))) neighbors.push(arrayIndex(row, col + 1))

    return neighbors

  }

  return {

    row, 

    col,

    walls,

    show,

    unvisitedNeighbors,

    highlight

  }

}

​

function setup() {

​

  createCanvas(canvasWidth, canvasHeight);

  // Slows down the draw loop

  //frameRate(3);

  for (let i = 0; i < nRows; i++)

  {

      for (let j = 0; j < nCols; j++)

        {

          grid.push(Cell(i, j))

        }

    }

  // Como se colocasse o primeiro elemento da stack e para iniciar o algoritmo

  currentCell = grid[0]

}

​

// o loop draw é como o while de um algoritmo DST, difere que a condição de parada está dentro no primeiro if

function draw() {

  background(200);

  if (currentCell || backtrackStack.length > 0){

    if (currentCell == null) currentCell = backtrackStack.pop()

    for (let i = 0; i < grid.length; i++)

      {

        grid[i].show()

      }

​

    visitedCells.add(arrayIndex(currentCell.row, currentCell.col))

    currentCell.highlight()

    let unvisitedNeighbors = currentCell.unvisitedNeighbors()

​

    if (unvisitedNeighbors.length > 0)

      {

        backtrackStack.push(currentCell)

        const nextIndex = floor(random(0, unvisitedNeighbors.length))

        const next = grid[unvisitedNeighbors[nextIndex]]

        removeCommonWall(currentCell, next)

        currentCell = next

      }

    else currentCell = null

  }

}