xxxxxxxxxx
180
// Maze generation using Depth First Search (DST) approach
// 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
}
}