Skip to content

Instantly share code, notes, and snippets.

@SiddharthShyniben
Created April 15, 2023 06:07
Show Gist options
  • Save SiddharthShyniben/e2abcb2d36d2f3d619c5c1ec7cb1a658 to your computer and use it in GitHub Desktop.
Save SiddharthShyniben/e2abcb2d36d2f3d619c5c1ec7cb1a658 to your computer and use it in GitHub Desktop.
Maze algorithms in JavaScript
class Backtracking {
constructor(height, width) {
if (width % 2 === 0) {
width += 1;
}
if (height % 2 === 0) {
height += 1;
}
this.width = width;
this.height = height;
this.grid = Array(height)
.fill(null)
.map(() => Array(width).fill(true));
}
createMaze() {
this.carve(1, 1);
this.grid[1][0] = false;
this.grid[this.height - 2][this.width - 1] = false;
return this.grid;
}
carve(x, y) {
this.grid[y][x] = false;
const directions = [Directions.UP, Directions.DOWN, Directions.LEFT, Directions.RIGHT];
for (let i = directions.length - 1; i >= 0; i--) {
const randomIndex = Math.floor(Math.random() * (i + 1));
const direction = directions[randomIndex];
directions[randomIndex] = directions[i];
let nx = x;
let ny = y;
if (direction === Directions.UP) {
ny -= 2;
} else if (direction === Directions.DOWN) {
ny += 2;
} else if (direction === Directions.LEFT) {
nx -= 2;
} else {
nx += 2;
}
if (ny < 0 || ny >= this.height || nx < 0 || nx >= this.width || !this.grid[ny][nx]) {
continue;
}
this.grid[(y + ny) >> 1][(x + nx) >> 1] = false;
this.carve(nx, ny);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment