Last active
June 11, 2018 14:29
-
-
Save avdotion/30b8767be9ae826f1714b3d14d78d392 to your computer and use it in GitHub Desktop.
Maze generation algorithm (Recursive backtracker) (p5.js)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Cell { | |
constructor(i, j) { | |
this.i = i; | |
this.j = j; | |
this.walls = { | |
top: true, | |
right: true, | |
bottom: true, | |
left: true, | |
} | |
} | |
show() { | |
let x = this.i * w; | |
let y = this.j * w; | |
stroke(255); | |
if (this.walls.top) { | |
line(x, y, x + w, y); | |
} | |
if (this.walls.right) { | |
line(x + w, y, x + w, y + w); | |
} | |
if (this.walls.bottom) { | |
line(x + w, y + w, x, y + w); | |
} | |
if (this.walls.left) { | |
line(x, y + w, x, y); | |
} | |
if (this.visited) { | |
noStroke(); | |
fill(255, 0, 255, 100); | |
rect(x, y, w, w); | |
} | |
} | |
index(i, j) { | |
if (i < 0 || j < 0 || i > cols-1 || j > rows-1){ | |
return -1; | |
} | |
return j + i * cols; | |
} | |
checkNeighbors() { | |
const neighbors = { | |
top: grid[this.index(this.i, this.j-1)], | |
right: grid[this.index(this.i+1, this.j)], | |
left: grid[this.index(this.i-1, this.j)], | |
bottom: grid[this.index(this.i, this.j+1)], | |
} | |
let not_visited_neighbors = []; | |
for (let item in neighbors) { | |
if (neighbors[item] && !neighbors[item].visited) { | |
not_visited_neighbors.push(neighbors[item]); | |
} | |
} | |
if (not_visited_neighbors.length > 0) { | |
let r = floor(random(0, not_visited_neighbors.length)); | |
return not_visited_neighbors[r]; | |
} else { | |
return undefined; | |
} | |
} | |
highlight() { | |
let x = this.i*w; | |
let y = this.j*w; | |
noStroke(); | |
fill(0, 0, 255, 100); | |
rect(x, y, w, w); | |
} | |
} |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
const w = 20; | |
let cols, rows; | |
let grid = []; | |
let current; | |
let stack = []; | |
function setup() { | |
createCanvas(600, 600); | |
frameRate(60); | |
cols = floor(width / w); | |
rows = floor(height / w); | |
for (let i = 0; i < cols; i++) { | |
for (let j = 0; j < rows; j++) { | |
grid.push(new Cell(i, j)); | |
} | |
} | |
current = grid[0]; | |
} | |
function draw() { | |
background(51); | |
for (item of grid) { | |
item.show(); | |
} | |
current.visited = true; | |
current.highlight(); | |
let next = current.checkNeighbors(); | |
if (next) { | |
next.visited = true; | |
stack.push(current); | |
removeWalls(current, next); | |
current = next; | |
} else if (stack.length > 0) { | |
current = stack.pop(); | |
} | |
} | |
function removeWalls(a, b) { | |
let x = a.i - b.i; | |
if (x === 1) { | |
a.walls.left = b.walls.right = false; | |
} else if (x === -1) { | |
a.walls.right = b.walls.left = false; | |
} | |
let y = a.j - b.j; | |
if (y === 1) { | |
a.walls.top = b.walls.bottom = false; | |
} else if (y === -1) { | |
a.walls.bottom = b.walls.top = false; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment