30:T9e9,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)); } }31:T77f,function stringify(m) { const joinSym = (c) => c.row === m.nRows - 1 ? c.col === m.nCols - 1 ? "╝" : "╩" : c.col === m.nCols - 1 ? "╣" : "╬"; const vWallSym = (d) => { if (typeof d === "number") { if (m.srt?.row === d && m.srt.col < 0) { return "▶"; } if (m.end?.row === d && m.end.col < 0) { return "◀"; } } if (m.srt?.row === d.row && d.col === m.nCols - 1 && m.srt.col >= m.nCols) { return "◀"; } if (m.end?.row === d.row && d.col === m.nCols - 1 && m.end.col >= m.nCols) { return "▶"; } return "║"; }; const hWallSym = (d) => { if (typeof d === "number") { if (m.srt?.row < 0 && m.srt.col === d) { return " ▼ "; } if (m.end?.row < 0 && m.end.col === d) { return " ▲ "; } } if (m.srt?.row >= m.nRows && d.row === m.nRows - 1 && m.srt.col === d.col) { return " ▲ "; } if (m.end?.row >= m.nRows && d.row === m.nRows - 1 && m.end.col === d.col) { return " ▼ "; } return "═══"; }; const cellSym = (c) => m.srt?.row === c.row && m.srt.col === c.col ? " ⊕ " : m.end?.row === c.row && m.end.col === c.col ? " ⏺ " : " "; let output = "\n╔"; for (let col = 0; col < m.nCols - 1; col++) { output += hWallSym(col) + "╦"; } output += hWallSym(m.nCols - 1) + "╗\n"; for (const row of m.eachRow()) { let [top, bottom] = [ vWallSym(row[0].row), row[0].row === m.nRows - 1 ? "╚" : "╠" ]; for (const c of row) { const rightBorder = c.isLinked(c.E) ? " " : vWallSym(c); top += `${cellSym(c)}${rightBorder}`; const bottomBorder = c.isLinked(c.S) ? " " : hWallSym(c); bottom += `${bottomBorder}${joinSym(c)}`; } output += `${top}\n${bottom}\n`; } return output; }32:Tf57,function compose(m, opt) { const defaults = { cellSize: 16, labels: false, labeller: (c) => c.id, labelSize: undefined, colourer: (c) => "rgb(254,234,217)", dimUnconnected: true }; opt = Object.assign({}, defaults, opt); const r = opt.r ? opt.r : new Renderer(opt.cellSize * m.nCols, opt.cellSize * m.nRows); r.fit( [ [0, 0], [m.nCols, m.nRows] ], 18 ) .textAlign("middle") .textBaseline("middle") .textSize(opt.labelSize ? opt.labelSize : opt.cellSize / 5); // Draw coloured background cells first for (const c of m.eachCell()) { const [x1, y1, x2, y2] = [c.col, c.row, c.col + 1, c.row + 1]; r.stroke(opt.colourer(c)) .fill(opt.colourer(c)) .polygon([ [x1, y1], [x2, y1], [x2, y2], [x1, y2] ]); if (opt.dimUnconnected && c.links.length === 0) { r.stroke("rgba(0,0,0,0.05)") .fill("rgba(0,0,0,0.05)") .polygon([ [x1, y1], [x2, y1], [x2, y2], [x1, y2] ]); } } // Outer boundary r.stroke("black") .strokeWidth(2) .fill() .polygon([ [0, 0], [m.nCols, 0], [m.nCols, m.nRows], [0, m.nRows], [0, 0] ]); // Draw cell boundaries and labels r.strokeWidth(1); for (const c of m.eachCell()) { const [x1, y1, x2, y2] = [c.col, c.row, c.col + 1, c.row + 1]; r.stroke("black"); for (const c1 of c.adjacent.filter(Boolean)) { if (c1.col > c.col && !c.isLinked(c1)) { // Consider cell to east r.line([ [x2, y1], [x2, y2] ]); } else if (c1.row > c.row && !c.isLinked(c1)) { // Consider cell to south r.line([ [x1, y2], [x2, y2] ]); } } if (opt.labels && (!opt.dimUnconnected || c.links.length > 0)) { r.fill(c.links.length === 0 ? "red" : "black") .stroke() .text(opt.labeller(c), (x1 + x2) / 2, (y1 + y2) / 2); } } // Draw entrance and exit markers if they exist const externalTerminus = (row, col, isHorizontal, invert) => { const [xOff, yOff] = [col < 0 ? 0.2 : -0.2, row < 0 ? 0.2 : -0.2]; const dir = invert ? -1 : 1; r.strokeWidth(3).stroke(opt.colourer(m.grid[m.clampR(row)][m.clampC(col)])); if (isHorizontal) { r.line([ [col >= 0 ? m.nCols : 0, row + 0.1], [col >= 0 ? m.nCols : 0, row + 0.9] ]) .fill("black") .stroke() .polygon([ [(col >= 0 ? m.nCols : 0) + xOff * dir, row + 0.3], [(col >= 0 ? m.nCols : 0) + xOff * dir, row + 0.7], [(col >= 0 ? m.nCols : 0) - xOff * dir, row + 0.5] ]); } else { r.line([ [col + 0.1, row >= 0 ? m.nRows : 0], [col + 0.9, row >= 0 ? m.nRows : 0] ]) .fill("black") .stroke() .polygon([ [col + 0.3, (row >= 0 ? m.nRows : 0) + yOff * dir], [col + 0.7, (row >= 0 ? m.nRows : 0) + yOff * dir], [col + 0.5, (row >= 0 ? m.nRows : 0) - yOff * dir] ]); } }; const markTermini = (c, isStart) => { if (c?.col >= 0 && c.col < m.nCols && c.row >= 0 && c.row < m.nRows) { r.fill(isStart ? "" : "black") .stroke(isStart ? "black" : "") .ellipse(c.col + 0.5, c.row + 0.5, 0.25); } else { if (c?.col < 0 || c?.col >= m.nCols) { externalTerminus(c.row, c.col, true, isStart); } else if (c?.row < 0 || c?.row >= m.nRows) { externalTerminus(c.row, c.col, false, isStart); } } }; markTermini(m.srt, true); markTermini(m.end, false); if (opt.title) { r.push() .translate(0, -4) .stroke() .fill("rgb(32,32,32)") .font("italic") .textAlign("left") .textSize(10) .textBaseline("bottom") .text(opt.title, 0, 0) .pop(); } return r; }33:[] 2e:{"title":"Mazes: The Basics","cells":[{"id":0,"value":"# Mazes: The Basics\n\n_Exploring mazes with [Mazes for Programmers](https://pragprog.com/titles/jbmaze/mazes-for-programmers/) by Jamis Buck. If you like coding and mazes, I highly recommend this book. This page is based largely on content in chapters 1 and 2._","pinned":false,"hidden":false,"mode":"md"},{"id":482,"value":"This page explores the creation of _perfect mazes_, that is, mazes where each location has exactly one non-repeating path to the maze's exit. These can be distinguished from _braided mazes_ that offer multiple pathways between pairs of locations. \n\nTo start with, the mazes will be based on a rectangular grid of _cells_:","pinned":false,"hidden":false,"mode":"md"},{"id":484,"value":"compose(new Maze(4, 4), { cellSize: 40 }).render()","pinned":false,"hidden":false,"mode":"ojs"},{"id":491,"value":"from which we can remove selected boundaries connecting adjacent cells. When sufficient boundaries are removed, we have a path from entrance to exit:","pinned":false,"hidden":false,"mode":"md"},{"id":548,"value":"compose(simpleExample(), { cellSize: 40 }).render()","pinned":false,"hidden":false,"mode":"ojs"},{"id":1201,"value":"We could choose to represent the maze as a _graph_, and because every cell is connected to every other via paths that don't double back on themselves, more specifically a _tree_. For example, this 4x4 maze with cell location labels could be represented as:","pinned":false,"hidden":false,"mode":"md"},{"id":1210,"value":"compose(simpleExample(), {\n cellSize: 40,\n labels: true\n}).render()","pinned":false,"hidden":false,"mode":"ojs"},{"id":1203,"value":"toGraph(simpleExample()).toDot({\n rankDir: \"LR\",\n showTree: true,\n compact: true,\n scale: 0.6\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":1231,"value":"Notice how the points where the tree bifurcates (at positions `[1·1]` and `[0·2]`) are the decision points in the maze where there is a choice of routes. _Leaf nodes_ represent dead ends in the maze (`[0·1]`, `[2·0]` and `end`). We can make the decision point locations more obvious by removing the corridor locations from the graph representation (_contracting_ the graph):","pinned":false,"hidden":false,"mode":"md"},{"id":2538,"value":"toGraph(simpleExample()).contract().toDot({ showTree: true, rankDir: \"LR\" })","pinned":false,"hidden":false,"mode":"ojs"},{"id":1233,"value":"## 2. Setting up the maze infrastructure","pinned":false,"hidden":false,"mode":"md"},{"id":1260,"value":"To store the maze we can create two classes - one to represent each cell and another to represent the arrangement of cells that will form the maze. \n\nEach `Cell` contains a reference to its location, its adjacent cells (whether connected or not), links to the cells it is directly connected to and an ID for labelling purposes. To keep things flexible we will allow links to be either bidirectional (default) or unidirectional.","pinned":false,"hidden":false,"mode":"md"},{"id":12,"value":"class Cell {\n constructor(row, col, id) {\n this.row = row;\n this.col = col;\n this.adjacent = [];\n this.links = [];\n this.id = id || toId(row, col);\n }\n\n // Link this cell with another either bi-directionally or unidirectionally.\n link(c, bidi = true) {\n if (c) {\n this.links.push(c);\n if (bidi) {\n c.link(this, false);\n }\n }\n return this;\n }\n\n // Break the link between this cell and another.\n unlink(c, bidi = true) {\n if (c) {\n this.links = this.links.filter((linkedC) => linkedC !== c);\n if (bidi) {\n c.unlink(this, false);\n }\n }\n return this;\n }\n\n // Is this cell linked to the given one?\n isLinked(c) {\n return this.links.includes(c);\n }\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":1265,"value":"The `Maze` class comprises a 2d array of `Cell` objects, which initially are unlinked to one another. It includes methods for linking and unlinking cells so that we can apply a variety of maze generation algorithms. And for convenience a couple of iterating generator functions for processing maze rows and maze cells. Finally, there is a method for adding the start and end cells for traversing the maze.","pinned":false,"hidden":false,"mode":"md"},{"id":28,"value":"$30","pinned":true,"hidden":false,"mode":"ojs"},{"id":1269,"value":"The appendix of this page includes some additional helper functions for representing the maze graphically, as text and converting to and from a [graph](https://observablehq.com/@jwolondon/gds-graph).\n\nWith this basic infrastructure in place, we can consider some algorithms for creating mazes themselves.","pinned":false,"hidden":false,"mode":"md"},{"id":1236,"value":"## 3. Maze generation","pinned":false,"hidden":false,"mode":"md"},{"id":1271,"value":"Remember this approach to maze design erases boundaries between cells such that we are left with a _perfect maze_ or tree-structure that connects all cells to all others via single pathways. There are many ways to achieve this, but here are a couple of simple ones.","pinned":false,"hidden":false,"mode":"md"},{"id":1273,"value":"### 3.1 The binary tree algorithm\n\nThis algorithm keeps things simple because each cell can be considered independently of all others. For each cell, remove either its eastern or northern boundary (for the top row or right column, just remove the only available boundary). This guarantees a pathway because every cell will be directly connected to at least one other.","pinned":false,"hidden":false,"mode":"md"},{"id":65,"value":"function binaryTree(grid, rGen) {\n for (const c of grid.eachCell()) {\n c.link(randSample(c.adjacent.slice(0, 2).filter(Boolean), rGen));\n }\n return grid;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":135,"value":"compose(btExample(), { title: \"Binary tree\" }).render()","pinned":false,"hidden":false,"mode":"ojs"},{"id":2267,"value":"The 'binary' here refers to the fact that any node in the tree representing the maze can have at most two branches. That is, as you navigate the maze and arrive at a junction, there will always be two paths to choose from. This can be seen in the tree representation of the maze above:","pinned":false,"hidden":false,"mode":"md"},{"id":2262,"value":"toGraph(btExample()).toDot({\n rankDir: \"LR\",\n compact: true,\n showTree: true\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":2358,"value":"The binary tree structure is perhaps more obvious if we simplify the graph such that we only include junction nodes. That is, we remove the nodes representing corridors along the maze where there is only one way to go.","pinned":false,"hidden":false,"mode":"md"},{"id":2361,"value":"(\"start\", toTree(toGraph(btExample())).contract()).toDot({\n rankDir: \"LR\",\n showTree: true\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":1284,"value":"The obvious problem is that the top row and right column will have no walls, and the path from any other cell to these two free corridors can always be found by travelling north or east. This N-E tendency for paths along with the northern and eastern corridors is known as the maze's _bias_. Despite the bias, it does generate a guaranteed perfect maze with _O(n)_ efficiency.","pinned":false,"hidden":false,"mode":"md"},{"id":1275,"value":"### 3.2 The sidewinder algorithm\n\nAnother simple algorithm that processes each cell one at a time, but one that removes some (but not all) of the bias of the binary tree algorithm. As with the binary tree, for every cell we randomly choose between an eastern or northern boundary. If eastern, we remove the eastern boundary and move to that cell, storing the cells in a _run_. We continue randomly choosing, adding to the run if east. On the first occurrence of a northern boundary we randomly choose one of the cells in the current run and erase its northern boundary. We then reset the run and move to the next unvisited cell.","pinned":false,"hidden":false,"mode":"md"},{"id":328,"value":"function sidewinder(grid, rGen) {\n for (const row of grid.eachRow()) {\n const run = [];\n for (const c of row) {\n run.push(c);\n if (!c.adjacent[1] || (c.adjacent[0] && randInt(2, rGen) === 0)) {\n const c2 = randSample(run, rGen);\n if (c2.adjacent[0]) {\n c2.link(c2.adjacent[0]);\n run.length = 0;\n }\n } else {\n c.link(c.adjacent[1]);\n }\n }\n }\n return grid;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":426,"value":"compose(swExample(), { title: \"Sidewinder\" }).render()","pinned":false,"hidden":false,"mode":"ojs"},{"id":2272,"value":"Unlike the binary tree, the sidewinder can sometimes yield junctions with three choices as well as those with two. Below is the graph representation of the maze with 'corridor cells' removed. Note the junction at `5-4` with three possible exits.","pinned":false,"hidden":false,"mode":"md"},{"id":2479,"value":"(\"start\", toTree(toGraph(swExample())).contract()).toDot({\n rankDir: \"LR\",\n showTree: true\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":1297,"value":"The bias is less strong than the binary tree, but it still results in a clear top corridor, and travelling north to that corridor is usually quite simple.\n\nYou can compare the biases in both maze generation algorithms by changing the maze size below.","pinned":false,"hidden":false,"mode":"md"},{"id":1332,"value":"{\n const r = new Renderer(900, 450);\n\n compose(\n binaryTree(new Maze(mSize, mSize)).setStartAndEnd(\n [mSize - 1, -1],\n [mSize - 1, mSize]\n ),\n { r: r, title: \"Binary tree\" }\n );\n\n r.translate(450, 0);\n\n compose(\n sidewinder(new Maze(mSize, mSize)).setStartAndEnd(\n [mSize - 1, -1],\n [mSize - 1, mSize]\n ),\n { r: r, title: \"Sidewinder\" }\n );\n\n return r.render();\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1337,"value":"viewof mSize = Inputs.range([12, 80], {\n value: 32,\n step: 1,\n label: \"Maze size\"\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":1330,"value":"The [next page](https://observablehq.com/@jwolondon/mazes-traversing) will look at how to solve mazes and in so doing consider how we can visualize the bias in a maze's structure.","pinned":false,"hidden":false,"mode":"md"},{"id":7,"value":"---\n\n## Appendices","pinned":false,"hidden":false,"mode":"md"},{"id":2020,"value":"### A.1 Maze output","pinned":false,"hidden":false,"mode":"md"},{"id":9,"value":"import { Renderer } from \"@jwolondon/renderer\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":349,"value":"import { Graph } from \"@jwolondon/gds-graph\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":1194,"value":"_Provide a string representation of the maze, useful for terminal output:_","pinned":false,"hidden":false,"mode":"md"},{"id":764,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":1358,"value":"_Compose a renderable graphic of the maze (call its `render()` function to actually draw to screen). Options include providing the rendering context, setting the cell size, whether cell labels are shown, contents and colour of the label (as a function of the cell):_","pinned":false,"hidden":false,"mode":"md"},{"id":537,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":1365,"value":"_Convert between a maze and a [graph representation](https://observablehq.com/@jwolondon/gds-graph):_","pinned":false,"hidden":false,"mode":"md"},{"id":543,"value":"function toGraph(m) {\n const graph = Graph();\n if (m.srt) {\n graph.addEdge(\"start\", m.srt.links[0].id);\n }\n if (m.end) {\n graph.addEdge(\"end\", m.end.links[0].id);\n }\n for (const c of m.eachCell()) {\n for (const link of c.links) {\n graph.addEdge(c.id, link.id);\n }\n }\n return graph;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2300,"value":"function fromGraph(g, grid = Maze) {\n const serialized = g.serialize();\n const [nodes, edges] = [\n serialized.nodes.map((d) => fromId(d.id)).filter(Array.isArray),\n serialized.links.filter((d) => d.source !== \"start\" && d.target !== \"end\")\n ];\n // Find the maze dimensions from the largest node row and column labels\n const nRows = Math.max(...nodes.map(([r, c]) => r)) + 1;\n const nCols = Math.max(...nodes.map(([r, c]) => c)) + 1;\n\n // Join maze cells for every edge in the graph.\n const maze = new grid(nRows, nCols);\n for (const e of edges) {\n maze.link(fromId(e.source), fromId(e.target));\n }\n return maze;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2497,"value":"_Given a graph representing a maze with bi-directional links between cells, generate a tree instead with unidirectional movement from the a root cell. This captures the topology of the maze if it is 'perfect' (i.e. all cells visitable from all others without visiting any cell more than once)._","pinned":false,"hidden":false,"mode":"md"},{"id":2476,"value":"function toTree(g) {\n const tree = new Graph();\n const ns = new Set();\n for (const n of g.breadthFirstSearch([\"start\"])) {\n for (const n2 of g.adjacent(n)) {\n if (!ns.has(n2)) {\n tree.addEdge(n, n2);\n }\n ns.add(n2);\n }\n }\n return tree;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":93,"value":"### A.2 Random numbers and samples","pinned":false,"hidden":false,"mode":"md"},{"id":376,"value":"import { randGenerator } from \"@jwolondon/seeded-random-numbers\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":2015,"value":"_Generate a random integer between 0 and < n. Can optionally use a seeded random number generator (`rGen`) for creating the same sequence of random numbers:_","pinned":false,"hidden":false,"mode":"md"},{"id":90,"value":"function randInt(n, rGen) {\n return rGen ? Math.floor(rGen() * n) : Math.floor(Math.random() * n);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":113,"value":"_Given an array of items, select a random element from it; can be seeded to generate same sequence if `rGen` provided:_","pinned":false,"hidden":false,"mode":"md"},{"id":115,"value":"function randSample(arr, rGen) {\n return arr[randInt(arr.length, rGen)];\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2002,"value":"_Generate a random move (dx,dy) of a given step size in one of four orthogonal directions can be seeded to generate same sequence if `rGen` provided:_","pinned":false,"hidden":false,"mode":"md"},{"id":1999,"value":"function randMove(rGen) {\n const moves = [\n [-1, 0],\n [0, -1],\n [0, 1],\n [1, 0]\n ];\n return randSample(moves, rGen);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1196,"value":"### A.3 Example mazes\n\n_All are functions so that independent instances of the same mazes can be created._","pinned":false,"hidden":false,"mode":"md"},{"id":2025,"value":"_Simple 4x4 perfect maze for illustrative example:_","pinned":false,"hidden":false,"mode":"md"},{"id":519,"value":"function simpleExample() {\n return new Maze(4, 4)\n .link([0, 0], [1, 0])\n .link([0, 1], [0, 2])\n .link([0, 2], [0, 3])\n .link([0, 2], [1, 2])\n .link([0, 3], [1, 3])\n\n .link([1, 0], [1, 1])\n .link([1, 1], [1, 2])\n .link([1, 1], [2, 1])\n .link([1, 3], [2, 3])\n\n .link([2, 0], [3, 0])\n .link([2, 1], [3, 1])\n .link([2, 2], [3, 2])\n .link([2, 2], [2, 3])\n\n .link([3, 0], [3, 1])\n .link([3, 2], [3, 3])\n\n .setStartAndEnd([-1, 0], [3, 4]);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2029,"value":"_12x12 binary tree maze:_","pinned":false,"hidden":false,"mode":"md"},{"id":1309,"value":"function btExample() {\n return binaryTree(new Maze(12, 12), randGenerator(\"apples\")).setStartAndEnd(\n [11, -1],\n [11, 12]\n );\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2031,"value":"_12x12 sidewinder maze:_","pinned":false,"hidden":false,"mode":"md"},{"id":1321,"value":"function swExample() {\n return sidewinder(new Maze(12, 12), randGenerator(\"kiwi\")).setStartAndEnd(\n [11, -1],\n [11, 12]\n );\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2033,"value":"_Braided example with regular chessboard configuration of walls; defaults to 16x16 but can be configured to any size:_","pinned":false,"hidden":false,"mode":"md"},{"id":1651,"value":"function braidedExample(nRows = 16, nCols = 16) {\n const m = new Maze(nRows, nCols);\n for (let i = 0; i < nRows; i++) {\n for (let j = 0; j < nCols; j++) {\n if (i < nRows - 1 && (i + j) % 3 !== 0) {\n m.link([i, j], [i + 1, j]);\n }\n if (j < nCols - 1 && (i + j) % 3 !== 1) {\n m.link([i, j], [i, j + 1]);\n }\n }\n }\n return m.setStartAndEnd([-1, 0], [nRows - 1, nCols]);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2036,"value":"_Given a maze grid create a lattice maze from it (each cell connected to all of its neighbours):_","pinned":false,"hidden":false,"mode":"md"},{"id":1883,"value":"function lattice(grid = new Maze(4, 4)) {\n for (const c of grid.eachCell()) {\n for (const nbr of c.adjacent.filter(Boolean)) {\n c.unlink(nbr);\n c.link(nbr);\n }\n }\n return grid;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2040,"value":"### A.4 Miscellaneous functions","pinned":false,"hidden":false,"mode":"md"},{"id":1542,"value":"_Useful for data structures that need to reference maze cells as primitives. Converts between a cell position to and string label:_","pinned":false,"hidden":false,"mode":"md"},{"id":1525,"value":"function toId(row, col) {\n return `${row}·${col}`;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1533,"value":"function fromId(id) {\n const parsed = id.match(/-?\\d+/g);\n if (parsed) {\n return parsed.map(Number);\n }\n return id;\n}","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W33","stdlib":"1","titling":"auto"}