Skip to content

Instantly share code, notes, and snippets.

@avdotion
Last active June 11, 2018 14:29
Show Gist options
  • Save avdotion/30b8767be9ae826f1714b3d14d78d392 to your computer and use it in GitHub Desktop.
Save avdotion/30b8767be9ae826f1714b3d14d78d392 to your computer and use it in GitHub Desktop.
Maze generation algorithm (Recursive backtracker) (p5.js)
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);
}
}
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