2e:null 2f:["$","title",null,{"children":"Mazes: Traversing | Jo Wood | Observable"}] 34:T8c0,What may not be quite so obvious is that this distance grid also gives us the ability to find the _longest_ path in the maze, or in other words, a harder maze to solve if we select appropriate start and end points. In graph terms, this longest path is known as the graph's [diameter](https://mathworld.wolfram.com/GraphDiameter.html), which, because any perfect maze is a tree, can be easily found as follows: - Starting at some arbitrary point _root_, generate the distance grid. - Find the cell with the largest distance, call that _A_. - Starting at _A_, generate another distance grid. - Call the cell with the largest distance in this new distance grid _B_. The longest path in the entire maze will be between _A_ and _B_. It might not be the only longest path, but we can guarantee there will be no longer one. It's worth pausing for a minute to think about why it is that two distance searches starting with _any_ arbitrary root cell will necessarily reveal a longest maze path. Can you intuitively reason why this is so?

Click to show my intuition.

Imagine there was a longer path than that between _A_ and _B_ above. Call the cell endpoints of that longer path _C_ and _D_.
• _C_ and _D_ would have to be different to both _A_ and _B_ because by definition _B_ (not _C_ and not _D_) is the furthest point from _A_.
• It follows that at least one of C or D must have a distance from _root_ that is greater than the distance from _root_ to _A_. If that were not the case the distance from _C_ to _D_ would be less than or equal to the distance from the _root_ to _A_, which by definition of _C_ and _D_ cannot be true.
• But this contradicts the selection of _A_ which was the furthest point from _root_, therefore there cannot be a longer path _C_ to _D_.

If you prefer physical analogies, imagine a series of beads connected together with strings where each bead is a maze cell and the strings are connections between cells. If you pick it up holding any bead, the others will hang downward. If you then pick the lowest bead and hang it from this one, the distance from the bead you are now holding to the new lowest bead will be its diameter.

35:[] 32:{"id":"41573b90d0697093","slug":"mazes-traversing","title":"Mazes: Traversing","thumbnail":"293e894ab72bd118d2c2bbed6876b8c5d403a2e82c58f1ed41fe0a952eb6a2fd","access_level":"public","create_time":"$D2023-05-29T06:21:59.298Z","update_time":"$D2023-12-02T09:22:35.652Z","view_time":null,"first_public_time":"$D2023-05-29T11:32:27.549Z","has_unpublished_edits":null,"fork":false,"stars":6,"starred":false,"owner":{"type":"team","id":"9461f58b209074d5","login":"jwolondon","name":"Jo Wood","avatar_url":"https://avatars-next.observableusercontent.com/27f72cecd1ac20853a533421fab228ce5f611cbc0986c1e420f7d3b1eb49ef50","tier":"starter_2024"},"version":770,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"e2432cc13dc447d3","login":"jwolondon","name":"Jo Wood","avatar_url":"https://avatars-next.observableusercontent.com/27f72cecd1ac20853a533421fab228ce5f611cbc0986c1e420f7d3b1eb49ef50","tier":null}],"members":[{"type":"individual","id":"e2432cc13dc447d3","login":"jwolondon","name":"Jo Wood","avatar_url":"https://avatars-next.observableusercontent.com/27f72cecd1ac20853a533421fab228ce5f611cbc0986c1e420f7d3b1eb49ef50","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":true,"trashed":false,"lapsed":null,"subscribed":null,"forks":1,"collection":{"id":"8012407fcb8b062b","slug":"mazes","title":"mazes","owner":{"id":"9461f58b209074d5","login":"jwolondon","name":"Jo Wood"}},"type":"notebook","body":{"title":"Mazes: Traversing","cells":[{"id":0,"value":"# Mazes: Traversing\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 chapter 3._","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":6,"value":"Because in a perfect maze every cell is connected, however indirectly, to every other, we know they are always solvable. There will be a pathway from a maze's start to its end wherever they may be. The interesting questions become: what is the shortest path (which will be the only path in a perfect maze), and what is an efficient way to find it?\n\nThe fact that a maze can be represented as a graph suggests we can use standard graph traversal algorithms to find the shortest path. And indeed, [Dijkstra's shortest path algorithm](https://en.wikipedia.org/wiki/Dijkstra's_algorithm) provides us with a solution.\n\nThis [graph implementation](https://observablehq.com/@jwolondon/gds-graph), which we can use to represent the maze graph, contains a method `shortestPath()` which will calculate the shortest path between any pair of nodes (i.e. cells in this case) using Dijkstra's algorithm.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":85,"value":"composeShortest(swExample(), {\n title: \"Shortest path (sidewinder)\"\n}).render()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":100,"value":"This works for any fully connected maze (i.e. where every cell is accessible from every other). Because Dijkstra's algorithm works for any graph, it will also solve mazes with loops (i.e. are represented by a cyclic graph, not a tree).","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":270,"value":"composeShortest(braidedExample(), { title: \"A shortest path\" }).render()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":265,"value":"Showing the path is useful in highlighting the bias of the generation process. For example try regenerating the sidewinder maze below and see how the shortest path tends to follow the same type of pattern each time, moving north towards the clear top row, then back down south again.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":87,"value":"{\n regenerate;\n const gSize = 48;\n return composeShortest(\n sidewinder(new Maze(gSize, gSize)).setStartAndEnd(\n [gSize - 1, -1],\n [gSize - 1, gSize]\n ),\n { title: \"Shortest path (sidewinder)\", r: new Renderer(480, 480) }\n ).render();\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":94,"value":"viewof regenerate = Inputs.button(\"Regenerate maze\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":102,"value":"## 2. Digging in to Dijkstra\n\nThe Dijkstra shortest path algorithm comprises two steps. \n\nThe first works by proceeding from the start node (entrance cell) finding the distance of every node (cell) in the graph from the start until the end node (exit cell) is found. This is usually done via a breadth-first search progressing a 'frontier' of cells closest to those for which distances have already been calculated.\n\nThe second then traverses back from the end cell taking the connected node with the lowest distance at each point. The result of that traversal back to the start will be a shortest path.\n\nIn the case of a maze where the 'cost' of each permitted cell-to-cell movement is constant, we can calculate the distances grid simply with a [breadth-first search (BFS)](https://en.wikipedia.org/wiki/Breadth-first_search) of the maze grid:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":114,"value":"function distanceGrid(maze, startPos) {\n let [sRow, sCol] = [0, 0];\n if (startPos !== undefined) {\n [sRow, sCol] = startPos;\n } else if (maze.srt) {\n [sRow, sCol] = [maze.getStart().row, maze.getStart().col];\n }\n\n const distances = maze.grid.map((row) => Array(row.length).fill(Infinity));\n const startRow = maze.getStart(sRow, sCol).row;\n const startCol = maze.getStart(sRow, sCol).col;\n\n // Breadth first search from the startng position\n let queue = [maze.grid[startRow][startCol]];\n distances[startRow][startCol] = 0;\n while (queue.length > 0) {\n const c = queue.shift();\n for (let linked of c.links) {\n if (distances[linked.row]?.[linked.col] === Infinity) {\n distances[linked.row][linked.col] = distances[c.row][c.col] + 1;\n queue.push(linked);\n }\n }\n }\n return distances;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":172,"value":"We can see these calculated distance values by displaying them as cell labels in the maze.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":178,"value":"{\n const r = new Renderer(900, 400);\n const maze = swExample();\n const distances = distanceGrid(maze, [maze.srt.row, maze.srt.col]);\n\n const shortest = toGraph(maze)\n .shortestPath(\"start\", \"end\")\n .map((d) => fromId(d))\n .slice(1, -1)\n .map(([r, c]) => [c + 0.5, r + 0.5]);\n\n const opt = {\n r: r,\n labels: true,\n labelSize: 8,\n labeller: (c) => distances[c.row][c.col]\n };\n\n compose(maze, { ...opt, title: \"Distances from bottom left\" });\n r.translate(450, 0);\n compose(maze, {\n ...opt,\n title: \"Distances with shortest path overlain\"\n })\n .fill()\n .stroke(\"rgba(146,25,32,0.5\")\n .bezierLine(shortest, 0.1);\n return r.render();\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":198,"value":"It should be apparent that counting back from the exit (43 cells away from the start), decreasing the distance on each move, takes us back along the shortest path, because unlike counting forward from 0, there is no ambiguity in which is the next cell in sequence.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":225,"value":"$34","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":227,"value":"function composeLongest(m, opt) {\n const defaults = { r: new Renderer(300, 300), cShortest: composeShortest };\n opt = Object.assign({}, opt, defaults);\n\n const furthest = (ds) => {\n let [maxD, maxPos] = [ds[0][0], [0, 0]];\n for (let row = 0; row < m.nRows; row++) {\n for (let col = 0; col < m.grid[row].length; col++) {\n if (ds[row][col] > maxD) {\n maxD = ds[row][col];\n maxPos = [row, col];\n }\n }\n }\n return maxPos;\n };\n\n // Find the longest distance from some arbitrary start point:\n const cellA = furthest(distanceGrid(m, [0, 0]));\n const cellB = furthest(distanceGrid(m, cellA));\n return opt.cShortest(m, { ...opt, start: cellA, end: cellB });\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":413,"value":"Here's the longest possible path in the sidewinder maze shown towards the start of this page:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":356,"value":"composeLongest(swExample()).render()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":416,"value":"As with the shortest path, the longest path can also reveal biases in the structure of the maze. The path tends to form an 𝝥-shape, reflecting the bias towards north-south paths and the clear top row corridor.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":377,"value":"{\n regenerate2;\n const gSize = 48;\n return composeLongest(sidewinder(new Maze(gSize, gSize)), {\n r: new Renderer(480, 480),\n title: \"Longest path\"\n }).render();\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":408,"value":"viewof regenerate2 = Inputs.button(\"Regenerate maze\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":418,"value":"The distance grid can also be used to reveal bias in the maze if we colour all maze cells according to the distance from some start location.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":526,"value":"In the visualization below the maze is rotated so the starting cell (therefore with the lowest distance) is always in the bottom-left. Mazes generated with no bias should not exhibit any systematic differences with different start corners.\n\nTry selecting different start corners and observing the bias in each. And see how the structure of that bias varies between the two maze generation processes we have considered so far.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":420,"value":"{\n mChoice.regenerate;\n const [gSize, w] = [24, 480];\n const [mazeFn, clr] =\n mChoice.type === \"Sidewinder\"\n ? [sidewinder, d3.interpolateBlues]\n : [binaryTree, d3.interpolateOranges];\n const [start, angle] =\n mChoice.start === \"bottom-left\"\n ? [[gSize, 0], 0]\n : mChoice.start === \"bottom-right\"\n ? [[gSize, gSize], 90]\n : mChoice.start === \"top-right\"\n ? [[0, gSize], 180]\n : [[0, 0], -90];\n\n const maze = mazeFn(new Maze(gSize, gSize));\n const r = new Renderer(w, w);\n r.translate(w / 2, w / 2)\n .rotate(angle)\n .translate(-w / 2, -w / 2);\n composeDistanceByColour(maze, {\n startPos: start,\n clrInterp: clr,\n r: r,\n title: mChoice.type + \" coloured by distance from \" + mChoice.start\n });\n\n return r.render();\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":465,"value":"viewof mChoice = Inputs.form({\n type: Inputs.radio([\"Binary tree\", \"Sidewinder\"], {\n value: \"Binary tree\",\n label: \" Maze type\"\n }),\n start: Inputs.radio(\n [\"bottom-left\", \"bottom-right\", \"top-left\", \"top-right\"],\n {\n value: \"bottom-left\",\n label: \" Start corner\"\n }\n ),\n regenerate: Inputs.button(\"Regenerate maze\")\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":528,"value":"Later we will consider some further maze generation functions that attempt to limit the bias in the structure of the mazes they create. But first, let's take a [small diversion to Hampton Court](https://observablehq.com/@jwolondon/mazes-hampton-court).","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":11,"value":"---\n\n## Appendices","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":53,"value":"import { Renderer } from \"@jwolondon/renderer\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":13,"value":"import {\n Maze,\n sidewinder,\n binaryTree,\n toGraph,\n compose,\n toId,\n fromId,\n simpleExample,\n braidedExample,\n btExample,\n swExample\n} from \"@jwolondon/mazes\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":759,"value":"_Apply Dijsktra's shortest path algorithm to the graph representation of a maze to find the shortest path from start to end and display it as a line over the maze:_","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":18,"value":"function composeShortest(m, opt) {\n const defaults = {\n r: new Renderer(300, 300)\n };\n opt = Object.assign({}, defaults, opt);\n const start = opt.start ? toId(...opt.start) : \"start\";\n const end = opt.end ? toId(...opt.end) : \"end\";\n\n const shortest = toGraph(m)\n .shortestPath(start, end)\n .slice(start === \"start\" ? 1 : 0, end === \"end\" ? -1 : Infinity) // Ignore \"start\" and \"end\" nodes if present.\n .map((d) => fromId(d)) // The id of each cell is its row,column position in the grid.\n .map(([r, c]) => [c + 0.5, r + 0.5]); // Swap row and column order and centre with 0.5 increment\n return compose(m, opt)\n .fill()\n .stroke(\"brown\")\n .strokeWidth(3)\n .bezierLine(shortest, 0.1); // Give route slightly curved path\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":764,"value":"_Draw a maze with coloured cells according to the distance from some start point:_","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":501,"value":"function composeDistanceByColour(maze, opt) {\n const defaults = {\n startPos: [0, 0],\n clrInterp: d3.interpolateOranges\n };\n opt = Object.assign({}, defaults, opt);\n const ds = distanceGrid(maze, opt.startPos);\n const clrFn = d3\n .scaleSequential(opt.clrInterp)\n .domain([0, Math.max(...ds.flat())]);\n return compose(maze, {\n r: opt.r,\n colourer: (c) => clrFn(ds[c.row][c.col]),\n title: opt.title\n });\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W35","stdlib":"1","titling":"auto"}} 33:"$32:body"