30:T53b,class Cell { constructor(row, column) { this.row = row; this.column = column; this.links = new Map(); // neighbour cells linked (joined by a passage) this.north = null; this.south = null; this.east = null; this.west = null; } link(cell, bidi = true) { this.links.set(cell, true); if (bidi) cell.link(this, false); return this; } unlink(cell, bidi = true) { this.links.delete(cell); if (bidi) cell.unlink(this, false); return this; } getLinks() { return this.links.keys(); // iterator } isLinkedTo(cell) { return this.links.has(cell); } neighbors() { const list = []; if (self.north) list.push(self.north); if (self.south) list.push(self.south); if (self.east) list.push(self.east); if (self.west) list.push(self.west); } getDistances() { const distances = new Distances(this); let frontier = [this]; while (frontier.length > 0) { const newFrontier = []; frontier.forEach((cell) => { for (const linked of cell.getLinks()) { const visited = distances.has(linked); if (!visited) { distances.set(linked, distances.get(cell) + 1); newFrontier.push(linked); } } }); frontier = newFrontier; } return distances; } }31:T60e,class Grid { constructor(rows, columns) { this.rows = rows; this.columns = columns; this.grid = this.prepareGrid(); this.configureCells(); } // Create the grid: an array of arrays where each value is a cell prepareGrid() { const g = new Array(this.rows); for (let r = 0; r < this.rows; r++) { g[r] = new Array(this.columns); for (let c = 0; c < this.columns; c++) { g[r][c] = new Cell(r, c); } } return g; } // Set the proper properties on all cells in the grid configureCells() { const g = this.grid; for (let r = 0; r < this.rows; r++) { for (let c = 0; c < this.columns; c++) { const cc = g[r][c]; // current cell if (r - 1 >= 0) cc.north = g[r - 1][c]; if (r + 1 < this.rows) cc.south = g[r + 1][c]; if (c - 1 >= 0) cc.west = g[r][c - 1]; if (c + 1 < this.columns) cc.east = g[r][c + 1]; } } } getCell(row, column) { if (row < 0 || row >= this.rows) return null; if (column < 0 || column >= this.columns) return null; return this.grid[row][column]; } getRandomCell() { const ri = randomInt([0, this.rows]); const ci = randomInt([0, this.columns]); return this.grid[ri][ci]; } size() { return this.rows * this.columns; } getRows() { return this.grid; } getCells() { const cells = []; for (let r = 0; r < this.rows; r++) { for (let c = 0; c < this.columns; c++) { cells.push(this.grid[r][c]); } } return cells; } }32:T4c0,function drawMaze({ grid, cellSize, distances = false }) { const width = [cellSize * grid.columns]; const height = [cellSize * grid.rows]; const background = "white"; const wall = "black"; const ctx = DOM.context2d(width, height); ctx.canvas.style.background = background; ctx.strokeStyle = "black"; ctx.lineWidth = 3; function drawLine(fx, fy, tx, ty) { ctx.moveTo(fx, fy); ctx.lineTo(tx, ty); ctx.stroke(); } ctx.beginPath(); //ctx.font = "30px Arial"; ctx.textAlign = "center"; ctx.fillStyle = "deeppink"; grid.getCells().forEach((cell) => { const x1 = cell.column * cellSize; const y1 = cell.row * cellSize; const x2 = (cell.column + 1) * cellSize; const y2 = (cell.row + 1) * cellSize; if (distances) { const d = distances.get(cell); if (d || d === 0) ctx.fillText( distances.get(cell), x1 + cellSize / 2, y1 + cellSize / 1.5 ); } if (!cell.north) drawLine(x1, y1, x2, y1); if (!cell.west) drawLine(x1, y1, x1, y2); if (!cell.isLinkedTo(cell.east)) drawLine(x2, y1, x2, y2); if (!cell.isLinkedTo(cell.south)) drawLine(x1, y2, x2, y2); }); return ctx.canvas; }33:[] 2e:{"title":"Mazes","cells":[{"id":0,"value":"# Mazes","pinned":false,"hidden":false,"mode":"md"},{"id":471,"value":"md`A js port of the code that appears in the book [mazes for programmers](http://www.mazesforprogrammers.com/). Part of the [maze series](https://observablehq.com/collection/@drio/mazes).\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":271,"value":"{\n const start = g.getCell(0, 0);\n // Compute distances to all cells in grid\n const distances = { nothing: false };\n if (whatToShow !== \"nothing\") {\n const start = g.getCell(0, 0);\n distances.all = start.getDistances(); // compute distances from start\n\n // path from Northwest corner to southwest corner\n if (whatToShow === \"best\") {\n const SWCell = g.getCell(g.rows - 1, 0);\n distances.best = distances.all.pathTo(SWCell);\n }\n }\n console.log(distances);\n return drawMaze({ grid: g, cellSize, distances: distances[whatToShow] });\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":430,"value":"viewof newMaze = Inputs.button(\"new maze ✨\", { label: \"\" })","pinned":false,"hidden":false,"mode":"ojs"},{"id":693,"value":"viewof cellSize = Inputs.range([20, 50], {\n step: 1,\n label: \"Cell size\",\n value: 20\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":436,"value":"viewof numberOfCells = Inputs.range([5, 30], {\n step: 1,\n label: \"Number of Cells\",\n value: 15\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":648,"value":"viewof whatToShow = Inputs.select([\"all\", \"best\", \"nothing\"], {\n value: \"best\",\n label: \"Distances to show:\"\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":675,"value":"viewof algorithm = Inputs.select([\"binary tree\", \"sidewinder\"], {\n value: \"binary tree\",\n label: \"Algorithm:\"\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":660,"value":"g = {\n newMaze;\n const algs = {\n \"binary tree\": binaryTree,\n sidewinder: sideWinder\n };\n\n let g = new Grid(numberOfCells, numberOfCells);\n g = algs[algorithm](g);\n return g;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":91,"value":"$30","pinned":false,"hidden":false,"mode":"ojs"},{"id":131,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":491,"value":"/*\n We will use this class to keep track of how far each cells is from the \n reference cell.\n */\nclass Distances {\n constructor(root) {\n this.root = root;\n this.cells = new Map();\n this.cells.set(this.root, 0);\n }\n\n getDistance(cell) {\n this.cells.get(cell);\n }\n\n set(cell, distance) {\n this.cells.set(cell, distance);\n }\n\n getCells() {\n this.cells.keys();\n }\n\n has(cell) {\n return this.cells.has(cell);\n }\n\n get(cell) {\n return this.cells.get(cell);\n }\n\n pathTo(goal) {\n // goal: cell\n let current = goal;\n\n const breadcrumbs = new Distances(this.root);\n breadcrumbs.set(current, this.cells.get(current));\n\n while (current !== this.root) {\n for (const neighbor of current.getLinks()) {\n if (this.cells.get(neighbor) < this.cells.get(current)) {\n breadcrumbs.set(neighbor, this.cells.get(neighbor));\n current = neighbor;\n break;\n }\n }\n }\n return breadcrumbs;\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":164,"value":"/* Create a maze using the binary tree algorithm */\nfunction binaryTree(grid) {\n grid.getCells().forEach((cell) => {\n const neighbors = [];\n if (cell.north) neighbors.push(cell.north);\n if (cell.east) neighbors.push(cell.east);\n\n const index = randomInt([0, neighbors.length]);\n const neighbor = neighbors[index];\n\n if (neighbor) cell.link(neighbor);\n });\n return grid;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":681,"value":"/* Create a maze using the sidewinder algorithm */\nfunction sideWinder(grid) {\n grid.getRows().forEach((row) => {\n let run = [];\n row.forEach((cell) => {\n run.push(cell);\n\n const atEasternBoundary = !cell.east;\n const atNorthenBoundary = !cell.north;\n // Close the run if: we are at the eastern boundary or\n // randomly if we are somewhere in the middle\n const shouldCloseOut =\n atEasternBoundary || (!atNorthenBoundary && randomInt([0, 2]));\n\n if (shouldCloseOut) {\n // pick a random cell from the run\n const member = run[Math.floor(Math.random() * run.length)];\n if (member.north) member.link(member.north);\n run = [];\n } else {\n cell.link(cell.east);\n }\n });\n });\n return grid;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":292,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":237,"value":"/* Generates a random number between range [x, y) */\nrandomInt = (range) =>\n parseInt(Math.random() * (range[1] - range[0]), 10) + range[0]","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W33","stdlib":"1","titling":"auto"}