class Cell {
constructor(row, col, id) {
this.row = row;
this.col = col;
this.adjacent = [];
this.links = [];
this.id = id || toId(row, col);
}
// Link this cell with another either bi-directionally or unidirectionally.
link(c, bidi = true) {
if (c) {
this.links.push(c);
if (bidi) {
c.link(this, false);
}
}
return this;
}
// Break the link between this cell and another.
unlink(c, bidi = true) {
if (c) {
this.links = this.links.filter((linkedC) => linkedC !== c);
if (bidi) {
c.unlink(this, false);
}
}
return this;
}
// Is this cell linked to the given one?
isLinked(c) {
return this.links.includes(c);
}
}
class Maze {
constructor(nRows, nCols) {
this.nRows = nRows;
this.nCols = nCols || nRows;
this.nCells = this.nRows * this.nCols;
this.init();
}
// Initialise grid of unconnected cells.
init() {
this.grid = Array.from({ length: this.nRows }, (_, row) =>
Array.from({ length: this.nCols }, (_, col) => new Cell(row, col))
);
for (const c of this.eachCell()) {
c.adjacent.push(this.grid[c.row - 1]?.[c.col]);
c.adjacent.push(this.grid[c.row][c.col + 1]);
c.adjacent.push(this.grid[c.row + 1]?.[c.col]);
c.adjacent.push(this.grid[c.row][c.col - 1]);
}
}
// Iterate over each row in this maze.
*eachRow() {
for (const row of this.grid) {
yield row;
}
}
// Iterate over each cell in this maze.
*eachCell() {
for (const row of this.eachRow()) {
for (const cell of row) {
yield cell;
}
}
}
// Choose a random cell from this maze. Optionally via a seeded random number generator
randomCell(rGen) {
const row = randInt(this.nRows, rGen);
const col = randInt(this.grid[row].length, rGen);
return this.grid[row][col];
}
// Link together the two cells at the given pair of locations.
link([r1, c1], [r2, c2], bidi = true) {
this.grid[r1][c1].link(this.grid[r2][c2], bidi);
return this;
}
// Add a start and end to the maze at the given coordinate pairs.
setStartAndEnd([r1, c1], [r2, c2]) {
// Break old links to start and end if they exist.
this.start?.links[0].unlink(this.start);
this.end?.links[0].unlink(this.end);
if (r1 >= 0 || r1 < this.nRows || c1 >= 0 || c1 < this.nCols) {
this.srt = new Cell(r1, c1, "start");
this.srt.link(this.grid[this.clampR(r1)][this.clampC(c1)]);
}
if (r2 >= 0 || r2 < this.nRows || c2 >= 0 || c2 < this.nCols) {
this.end = new Cell(r2, c2, "end");
// this.end.link(this.grid[this.clampR(r2)][this.clampC(c2)]);
this.grid[this.clampR(r2)][this.clampC(c2)].link(this.end);
}
return this;
}
// Provide a starting cell for maze navigation.
getStart(row, col) {
if (row != undefined && col != undefined) {
return this.grid[this.clampR(row)][this.clampC(col)]; // Explict start location provided.
}
return this.srt?.links[0] ? this.srt.links[0] : this.grid[0][0]; // Cell linked to start with default [0,0]
}
clampR(row) {
return Math.max(0, Math.min(row, this.nRows - 1));
}
clampC(col) {
return Math.max(0, Math.min(col, this.nCols - 1));
}
}
function binaryTree(grid, rGen) {
for (const c of grid.eachCell()) {
c.link(randSample(c.adjacent.slice(0, 2).filter(Boolean), rGen));
}
return grid;
}
function sidewinder(grid, rGen) {
for (const row of grid.eachRow()) {
const run = [];
for (const c of row) {
run.push(c);
if (!c.adjacent[1] || (c.adjacent[0] && randInt(2, rGen) === 0)) {
const c2 = randSample(run, rGen);
if (c2.adjacent[0]) {
c2.link(c2.adjacent[0]);
run.length = 0;
}
} else {
c.link(c.adjacent[1]);
}
}
}
return grid;
}
One platform to build and deploy the best data apps
Experiment and prototype by building visualizations in live JavaScript notebooks. Collaborate with your team and decide which concepts to build out.
Use Observable Framework to build data apps locally. Use data loaders to build in any language or library, including Python, SQL, and R.
Seamlessly deploy to Observable. Test before you ship, use automatic deploy-on-commit, and ensure your projects are always up-to-date.