2a:null 2b:["$","title",null,{"children":"Labyrinth | Forrest O. | Observable"}] 30:T526,md`## Fun with space-filling curves > "Then it seemed like falling into a labyrinth: we thought we were at the finish, but our way bent round and we found ourselves as it were back at the beginning, and just as far from that which we were seeking at first." ... Thus the present-day notion of a labyrinth as a place where one can lose [his] way must be set aside. It is a confusing path, hard to follow without a thread, but, provided [the traverser] is not devoured at the midpoint, it leads surely, despite twists and turns, back to the beginning. – Socrates describing the labyrinthine line of a logical argument in Plato's dialogue Euthydemus I've been doing a [few versions](https://twitter.com/forresto/status/879959151727837184) of this generative Labyrinth in the past few years. Each time I learn something new. I'm going to attempt to make a growing animated version, as a way to try _Observable_ & literate programming. ![photo cut labyrinth experiment](https://pbs.twimg.com/media/DDY-JqvXUAAKaS6.jpg:large) Finger labyrinth, carved into poplar wood (June 2018): [![finger labyrinth](https://c2.staticflickr.com/2/1773/42300190154_601ef7fa7d_b.jpg)](https://www.flickr.com/photos/forresto/42300190154/) (☝️ [html video experiment](https://twitter.com/forresto/status/1137385929646194690)) `31:T4f4,md` ## How should we represent the data Instead of starting with svg or canvas, I'm going to start by building up data that describes the labyrinth. I can then translate that same data to canvas, svg, or a string to visualize the process. The last time that I made code to draw a labyrinth, the data for the intial board and path looked something like this: \`\`\` →→↓ ↑ ↓ ↑←← \`\`\` Each space in the path (or board) points to the next. To decide if the labyrinth can grow in a particular direction, a segment in the path has to check its surroundings. \`\`\` →→↓ →↑ ↓ ↑←←← \`\`\` Each mutation to the path is optionally symmetrical. \`\`\` →↓ →→→↓ →→→↓ →↑→↓ →↑ ↓← →↑ ↓← →↑ ↓← ↑←←← ↑←↓← ↑←↓← ↑← ↑← \`\`\` I want to do things a little differently this time, though. I'm wondering if I could make something that could be more general than just 90° turns filling a square. Or maybe, instead of the "linked-loop" data that I've been working with, I can try thinking in terms of [tiles](https://trasevol.dog/2017/09/01/di19/). \`\`\` ╔╗ ╔╬╝ ╚╝ \`\`\` `32:T42d,TILES = [ ['EMPTY', SPACE], // key, char, turns to if expand up, right, down, left, rotated 180° ['O', '◽︎', 'T', 'R', 'B', 'L', 'O'], ['T', '╨', null, 'TR', 'TB', 'TL', 'B'], ['R', '╞', 'TR', null, 'RB', 'RL', 'L'], ['B', '╥', 'TB', 'RB', null, 'BL', 'T'], ['L', '╡', 'TL', 'RL', 'BL', null, 'R'], ['RB', '╔', 'TRB', null, null, 'RBL', 'TL'], ['BL', '╗', 'TBL', 'RBL', null, null, 'TR'], ['TR', '╚', null, null, 'TRB', 'TRL', 'BL'], ['TL', '╝', null, 'TRL', 'TBL', null, 'RB'], ['TB', '║', null, 'TRB', null, 'TBL', 'TB'], ['RL', '═', 'TRL', null, 'RBL', null, 'RL'], ['TRB', '╠', null, null, null, 'TRBL', 'TBL'], ['TBL', '╣', null, 'TRBL', null, null, 'TRB'], ['TRL', '╩', null, null, 'TRBL', null, 'RBL'], ['RBL', '╦', 'TRBL', null, null, null, 'TRL'], ['TRBL', '╬', null, null, null, null, 'TRBL'], ['NEG', SPACE], ]33:T578,function findMutations (board, w = boardSize, h = w) { const potentials = [] for (let index = 0, len = board.length; index < len; index++) { const tile = board[index]; if (tile !== TILE_INDEX.EMPTY) { continue; } const row = Math.floor(index / w) const col = index % w // Can this tile connect with the one under it? if (row < h - 1) { const underIndex = index + w const under = TILES[board[underIndex]] if (under[OVER]) { // A mutation is represented as [this index, this tile, that index, that change tile] potentials.push([index, UNDER, underIndex, TILE_INDEX[under[OVER]]]) } } // Over if (row > 0) { const overIndex = index - w const over = TILES[board[overIndex]] if (over[UNDER]) { potentials.push([index, OVER, overIndex, TILE_INDEX[over[UNDER]]]) } } // Right if (col < w - 1) { const rightIndex = index + 1 const rightward = TILES[board[rightIndex]] if (rightward[LEFT]){ potentials.push([index, RIGHT, rightIndex, TILE_INDEX[rightward[LEFT]]]) } } // Left if (col > 0) { const leftIndex = index - 1 const leftward = TILES[board[leftIndex]] if (leftward[RIGHT]){ potentials.push([index, LEFT, leftIndex, TILE_INDEX[leftward[RIGHT]]]) } } }; return potentials; }34:T6db,viewof negSpace = { const board = Array(negDemoWidth * negDemoHeight).fill(TILE_INDEX.EMPTY) board[0] = TILE_INDEX.O const middle = Math.floor(board.length / 2) board[middle] = TILE_INDEX.NEG board[middle - 1] = TILE_INDEX.NEG board[middle + 1] = TILE_INDEX.NEG board[middle - negDemoWidth] = TILE_INDEX.NEG board[middle + negDemoWidth] = TILE_INDEX.NEG function toString (board, width) { return board.map((t, i) => { let char = '' switch (t) { case TILE_INDEX.O: char = '🔘' break case TILE_INDEX.NEG: char = '⬛️' break default: char = '⬜️' } if (i > 0 && ((i + 1) % width) === 0) char += "\n" return char }).join('') } const el = html`

${toString(board, negDemoWidth)}

` el.onclick = (event) => { const {layerX, layerY, shiftKey} = event; const {width, height} = el.getBoundingClientRect(); const row = Math.floor(layerY / height * negDemoHeight) const col = Math.floor((layerX - 10) / width * negDemoWidth) const index = row * negDemoWidth + col if (board[index] === undefined) return if (shiftKey) { board[index] = board[index] === TILE_INDEX.O ? TILE_INDEX.EMPTY : TILE_INDEX.O } else { board[index] = board[index] === TILE_INDEX.NEG ? TILE_INDEX.EMPTY : TILE_INDEX.NEG } el.textContent = toString(board, negDemoWidth) // make it viewof-able? el.value = board el.dispatchEvent(new CustomEvent('input')) } // make it viewof-able? el.value = board el.dispatchEvent(new CustomEvent('input')) return el; }35:T552,function solveSymmetrical (seed, board, w, h = w) { // if (w % 2 === 0) { // throw "w should be odd" // } // if (h % 2 === 0) { // throw "h should be odd" // } const random = makeRandomGenerator(seed) const len = board.length let mutations = findMutations(board, w) let i = 0 while (mutations.length) { const mutation = mutations[random(mutations.length)] const [thisIndex, thisTile, thatIndex, thatTile] = mutation; board[thisIndex] = thisTile board[thatIndex] = thatTile // Symmetry if (board[len - 1 - thisIndex] === TILE_INDEX.EMPTY) { const addTileIndex = TILE_INDEX[TILES[thisTile][ROTATED]] board[len - 1 - thisIndex] = addTileIndex const extendTile = TILES[board[len - 1 - thatIndex]] switch (addTileIndex) { case TILE_INDEX.T: board[len - 1 - thatIndex] = TILE_INDEX[extendTile[UNDER]] break case TILE_INDEX.R: board[len - 1 - thatIndex] = TILE_INDEX[extendTile[LEFT]] break case TILE_INDEX.B: board[len - 1 - thatIndex] = TILE_INDEX[extendTile[OVER]] break case TILE_INDEX.L: board[len - 1 - thatIndex] = TILE_INDEX[extendTile[RIGHT]] break default: break } } mutations = findMutations(board, w) i++ } return board }36:[] 2e:{"id":"6b688f41041a357a","slug":"labyrinth","title":"Labyrinth","thumbnail":"ed3c88916fd37defb2b2bc8edcfc6c79225b78a0e5a459a22a1c272d6d635407","access_level":"public","create_time":"$D2018-02-07T14:17:35.149Z","update_time":"$D2019-08-31T06:53:09.278Z","view_time":null,"first_public_time":"$D2018-02-12T02:46:19.093Z","has_unpublished_edits":null,"fork":false,"stars":15,"starred":false,"owner":{"type":"team","id":"f9abb147dc0e6dcd","login":"forresto","name":"Forrest O.","avatar_url":"https://avatars-next.observableusercontent.com/c22671040121cb9b9d22913e2eb0ffc4d65d3e535cda1133d6655f1d63b32e3f","tier":"starter_2024"},"version":1839,"publish_version":1839,"role":null,"authored":false,"authors":[{"type":"individual","id":"b16dd1586d4d1422","login":"forresto","name":"Forrest O.","avatar_url":"https://avatars-next.observableusercontent.com/c22671040121cb9b9d22913e2eb0ffc4d65d3e535cda1133d6655f1d63b32e3f","tier":null}],"members":[{"type":"individual","id":"b16dd1586d4d1422","login":"forresto","name":"Forrest O.","avatar_url":"https://avatars-next.observableusercontent.com/c22671040121cb9b9d22913e2eb0ffc4d65d3e535cda1133d6655f1d63b32e3f","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":5,"collection":{"id":"6775b0fa0cb0d1a3","slug":"labyrinth","title":"labyrinth","owner":{"id":"f9abb147dc0e6dcd","login":"forresto","name":"Forrest O."}},"type":"notebook","body":{"titling":"auto","title":"Labyrinth","cells":[{"id":914,"value":"md`# Labyrinth\n\ntldr:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":952,"value":"tldr = boardToPathEl(tldrBoard, tldrCols, 9)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1121,"value":"tldrCols = Math.floor(width / 28 / 2) * 2 + 1","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":976,"value":"tldrBoard = solveAsync('hello', makeInitialBoard(tldrCols, 9), tldrCols, 9)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":0,"value":"$30","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":130,"value":"$31","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":741,"value":"md`# Initial setup\n## Index constants\nKinda wierd but...`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":396,"value":"KEY = 0","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":398,"value":"CHAR = 1","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":400,"value":"OVER = 2","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":402,"value":"RIGHT = 3","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":404,"value":"UNDER = 4","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":406,"value":"LEFT = 5","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1273,"value":"ROTATED = 6","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":687,"value":"md`## TILES\n\nI think this is like a simple [Tracery](http://www.tracery.io/) grammer or _Wave Form Collapse_ dictionary. Each tile decribes _what it will change to_ if the path is extended from it. For example, \"right bottom (\\`╔\\`)\" extended to the left will become \"right bottom left (\\`<╦\\`)\". \n`//SPACE = navigator.userAgent.toLowerCase().indexOf('android') > -1 ? '─' : ' '","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":392,"value":"$32","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":748,"value":"md`The index constants above and the \\`TILE_INDEX\\` below make it easier to answer questions like \"if I extend the path to the left here, what does the tile to the right turn to?\"\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":271,"value":"TILE_INDEX = {\n const tileIndexes = {}\n TILES.forEach((tile, index) => {\n tileIndexes[tile[KEY]] = index\n })\n return tileIndexes;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":863,"value":"viewof boardSize = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":531,"value":"makeInitialBoard = function (w, h = w) {\n const length = w * h\n const board = Array(length)\n .fill(TILE_INDEX.EMPTY)\n // Start loop in middle of board\n board[Math.floor(length / 2)] = TILE_INDEX.O\n return board\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":236,"value":"initialBoard = makeInitialBoard(boardSize)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":295,"value":"md`## Logging\nFor quick visual debugging`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":246,"value":"function boardToString (board, w = boardSize) {\n let str = \"\"\n if (!board || !board.forEach) return str\n board.forEach((tile, index) => {\n str += TILES[tile][CHAR]\n if ((index+1) % w === 0) {\n str += \"\\n\"\n }\n })\n return str\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":431,"value":"boardToEl = function (board, w = boardSize, h = w) {\n return html`

${boardToString(board, w)}

`\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1028,"value":"demoBoard = [\n 6, 5, 6, 15, 7, 3, 7,\n 8, 11, 9, 10, 8, 11, 9,\n 3, 11, 7, 10, 6, 11, 5,\n 4, 3, 16, 16, 16, 5, 4,\n 12, 5, 2, 10, 2, 3, 13,\n 8, 15, 5, 10, 3, 15, 9,\n 0, 8, 11, 14, 11, 9, 0\n]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":251,"value":"boardToElDemo = boardToEl(demoBoard, 7)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":732,"value":"md`### 🤔 Second order?\n\nThe \"walls\" in that string are actually the path... maybe expanding it would give a sense of the path better.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1020,"value":"boardToPathString = {\n\nconst fourChars =[\n [SPACE+SPACE\n ,SPACE+SPACE], // Space\n ['╔╗'\n ,'╚╝'], // O\n ['║║'\n ,'╚╝'], // T\n ['╔═'\n ,'╚═'], // R\n ['╔╗'\n ,'║║'], // B\n ['═╗'\n ,'═╝'], // L\n ['╔═'\n ,'║╔'], // RB\n ['═╗'\n ,'╗║'], // BL\n ['║╚'\n ,'╚═'], // TR\n ['╝║'\n ,'═╝'], // TL\n ['║║'\n ,'║║'], // TB\n ['══'\n ,'══'], // RL\n ['║╚'\n ,'║╔'], // TRB\n ['╝║'\n ,'╗║'], // TBL\n ['╝╚'\n ,'══'], // TRL\n ['══'\n ,'╗╔'], // RBL\n ['╝╚'\n ,'╗╔'], // TRBL\n [SPACE+SPACE\n ,SPACE+SPACE], // NEG\n];\n \nreturn function (board, w = boardSize) {\n let arr = [];\n let str = \"\"\n for (let i = 0, len = board.length; i < len; i++) {\n const tile = board[i];\n const row = Math.floor(i / w)\n for (let r = 0; r < 2; r++) {\n const strIndex = row * 2 + r\n if (!arr[strIndex]) {\n arr[strIndex] = \"\"\n }\n arr[strIndex] += fourChars[tile][r]\n }\n }\n return arr.join(\"\\n\")\n}\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1040,"value":"boardToPathEl = function (board, w = boardSize, h = w) {\n return html`

${boardToPathString(board, w)}

`\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1038,"value":"boardToPathEl(demoBoard, 7)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1200,"value":"md`### Monospace hack\nSome systems don't size the box-drawing chararcters at the same width as other characters in a monospace element (ಠ_ಠ). Measure these to check, and decide if \\`SPACE\\` needs to be another box-drawing character:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1203,"value":"spaceEl = html`_`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1208,"value":"boxEl = html`╬`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1213,"value":"SPACE = spaceEl.getBoundingClientRect().width === boxEl.getBoundingClientRect().width ? ' ' : '─'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":343,"value":"md`## Find possible directions to grow\n\nWe want all possibilities for a given board step before choosing one with the seeded random number generator. I'm ending up with something like a limited version of the Wave Form Collapse method:\n\n> The neighboring tiles’ possibilities are reduced, according to their compatibility with their newly set neighbor, and then their neighbors’ tiles possibilities are reduced, etc until no more possibilities can be reduced.\n\n– [Rémy 'Trasevol_Dog' Devaux](https://trasevol.dog/2017/09/01/di19/)\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":345,"value":"$33","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":830,"value":"md`## Test it, step by step`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":356,"value":"initialMutations = findMutations(initialBoard)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":457,"value":"stepCloneBoard = function (board, randomGen) {\n const mutations = findMutations(board)\n const mutation = mutations[randomGen(mutations.length)]\n const out = board.slice()\n out[mutation[0]] = mutation[1]\n out[mutation[2]] = mutation[3]\n return out;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":963,"value":"md`Change seed to change the demos:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":499,"value":"viewof demoStepSeed = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":468,"value":"demoStepGen = makeRandomGenerator(demoStepSeed)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":464,"value":"firstStep = stepCloneBoard(initialBoard, demoStepGen)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":459,"value":"firstStepEl = boardToEl(firstStep)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":365,"value":"secondStep = stepCloneBoard(firstStep, demoStepGen)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":484,"value":"secondStepEl = boardToEl(secondStep)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":804,"value":"twelveSteps = {\n const stepGen = makeRandomGenerator(demoStepSeed)\n let board = initialBoard\n const boardEls = [boardToEl(board)]\n for (let i=0; i < 11; i++) {\n board = stepCloneBoard(board, stepGen)\n boardEls.push(boardToEl(board))\n }\n return html`

${boardEls}

`\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":488,"value":"md`# Solve a board with a seed\n\nSeems like that works 😄 ... let's try to fill a whole board. When you change the seed the board should change.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":491,"value":"viewof boardDemoSeed = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":522,"value":"viewof boardDemoSize = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":503,"value":"function solveSync (seed, board, w, h = w) {\n const random = makeRandomGenerator(seed)\n let mutations = findMutations(board, w, h)\n while (mutations.length) {\n const mutation = mutations[random(mutations.length)]\n board[mutation[0]] = mutation[1]\n board[mutation[2]] = mutation[3]\n mutations = findMutations(board, w, h)\n }\n return board\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":512,"value":"solvedEl = boardToPathEl(solveSync(boardDemoSeed, makeInitialBoard(boardDemoSize), boardDemoSize), boardDemoSize)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":981,"value":"md`Import \\`makeRandomGenerator\\`: a seeded random number generator ([random-seed](https://www.npmjs.com/package/random-seed) on npm, [demos and viz on Observable](https://beta.observablehq.com/@forresto/random-seed)):`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2,"value":"import {makeRandomGenerator} from '@forresto/random-seed'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":35,"value":"viewof inputSeed = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":561,"value":"md`# Asynchronous generation and animation\n\nPart of the inspiration to do another version of this generative thing was [Mike Bostock's Introduction to Asynchronous Iteration](https://beta.observablehq.com/@mbostock/introduction-to-asynchronous-iteration) article. I haven't gotten a chance to use these concepts in my everyday programming so far.\n\nAlso, it's fun to watch a labyrinth grow from the initial seed. Solving the labyrinth gets noticeably slow at sizes >30, so we might as well animate the solving instead of freezing the browser.\n\nChange the seed to see it animate:\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":592,"value":"viewof asyncDemoSeed = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":594,"value":"viewof asyncDemoSize = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":580,"value":"async function* solveAsync (seed, board, w, h = w) {\n const random = makeRandomGenerator(seed)\n let mutations = findMutations(board, w, h)\n while (mutations.length) {\n const mutation = mutations[random(mutations.length)]\n board[mutation[0]] = mutation[1]\n board[mutation[2]] = mutation[3]\n mutations = findMutations(board, w, h)\n // This is optional... Observable already throttles to rAF\n // await Promises.delay(1000/60)\n yield board\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":604,"value":"{\n let board = makeInitialBoard(asyncDemoSize)\n yield* pauser(boardToPathEl(board, asyncDemoSize));\n const boardGen = solveAsync(asyncDemoSeed, board, asyncDemoSize)\n while (true) {\n const {done, value} = await boardGen.next();\n if (done) return;\n yield boardToPathEl(value, asyncDemoSize);\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":613,"value":"md`## Hey\n\nIt works 🎉\n\nFuture ideas: \n* [x] symmetry\n* [ ] nice rendering\n * isometric three.js https://observablehq.com/@tmcw/notebooks-featured-logo\n * zdog pseudo 3d https://codepen.io/forresto/pen/YbMQXj?editors=0010\n* [ ] speed\n * don't find all mutations for each step, rather start on a random tile?\n * or a generator for mutations to only need to calculate the one we want?\n * more than 1 step per animation frame? 👈 would be easy but make it harder to see the growth.\n* [ ] non-square tiles\n* [ ] non-planar board\n* [x] https://beta.observablehq.com/@tmcw/pauser to start animations once cell is in view\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1142,"value":"function* pauser(element) {\n // From https://beta.observablehq.com/@tmcw/pauser to make the animations below start on scroll\n yield element;\n // Just in case the element is too tall\n element.parentNode.style.maxHeight = '5vh'\n element.parentNode.style.overflow = 'auto'\n // Some browsers (Safari) don't support this feature yet, so fall back\n // to how this notebook would work without pauser doing its thing.\n if (!window.IntersectionObserver) return;\n yield new Promise(resolve => {\n let observer = (new window.IntersectionObserver(([entry]) => {\n entry.isIntersecting && (observer.disconnect(), resolve(element))\n }, { threshold: 0.9 }));\n observer.observe(element.parentNode)\n });\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":758,"value":"md`# Multiple paths in one board\nThis would not work with my last labyrith drawing code, which was built around one \"linked-loop\" path. Starting from tiles in this version, it's free.\n\nChange the seed:\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":764,"value":"viewof multipleDemoSeed = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":777,"value":"viewof multipleDemoW = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":882,"value":"viewof multipleDemoH = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":760,"value":"makeMultipleStartBoard = function (w, h) {\n const b = makeInitialBoard(w, h)\n b[0] = 1\n b[w - 1] = 1\n b[b.length - 1] = 1\n b[b.length - w] = 1\n return b;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":774,"value":"{\n let board = makeMultipleStartBoard(multipleDemoW, multipleDemoH)\n yield* pauser(boardToEl(board, multipleDemoW, multipleDemoH));\n const boardGen = solveAsync(multipleDemoSeed, board, multipleDemoW, multipleDemoH)\n while (true) {\n const {done, value} = await boardGen.next();\n if (done) return;\n yield boardToEl(value, multipleDemoW, multipleDemoH);\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1396,"value":"md`# Outside in\n\nInstead of a seed in the middle, start with a (double) path around the outside.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1400,"value":"function makeInitialBoardPathAround (w, h = w) {\n const length = w * h\n const board = [];\n for (let i = 0; i < length; i++) {\n if (i === 0) {\n board[i] = TILE_INDEX.RB\n } else if (i === w - 1) {\n board[i] = TILE_INDEX.BL\n } else if (i === length - w) {\n board[i] = TILE_INDEX.TR\n } else if (i === length - 1) {\n board[i] = TILE_INDEX.TL\n } else if (i < w || i > length - w) {\n board[i] = TILE_INDEX.RL\n } else if (i % w === 0 || (i + 1) % w === 0){\n board[i] = TILE_INDEX.TB\n } else {\n\t board[i] = 0\n }\n }\n return board\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1423,"value":"viewof outDemoSeed = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1425,"value":"viewof outDemoSize = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1398,"value":"{\n let board = makeInitialBoardPathAround(outDemoSize)\n yield* pauser(boardToPathEl(board, outDemoSize));\n const boardGen = solveAsync(outDemoSeed, board, outDemoSize)\n while (true) {\n const {done, value} = await boardGen.next();\n if (done) return;\n yield boardToPathEl(value, outDemoSize);\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1452,"value":"md`# Negative space\n\nBy adding a tile type that isn't considered empty, the labyrinth will fill in around it.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1456,"value":"viewof negDemoWidth = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1459,"value":"viewof negDemoHeight = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1552,"value":"md`\n* Click to toggle negative space\n* Shift-click to toggle path starts\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1461,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1600,"value":"viewof negDemoSeed = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1557,"value":"boardToPathEl(solveSync(negDemoSeed, negSpace.slice(), negDemoWidth, negDemoHeight), negDemoWidth, negDemoHeight)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1254,"value":"md`# Rotational symmetry\n\nIt should be pretty easy to add symmetry to each step. I'll add a column to the \\`TILES\\` dictionary to define each tile rotated 180°. (I thought about extending \\`TILES\\` at this point in the doc, which would feel better in the literary flow, but I think it would be harder to write. Tradeoffs.)\n\nWidth should be odd for these.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1263,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1278,"value":"viewof symDemoSeed = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1280,"value":"viewof symDemoSize = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1289,"value":"symmetricalEl = boardToPathEl(solveSymmetrical(symDemoSeed, makeInitialBoard(symDemoSize), symDemoSize), symDemoSize)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1332,"value":"md`# WIP... Moving through dimensions\n\nI think there is something to find exploring the WaveFormCollapse into other dimensions, for different kinds of animation other than just growing. Each step in the animation is choosing one of the possibilities, collapsing potential realities down to one.\n\nLet's look at a solved labyrinth. If we make the \"other\" choice in the last collapse, one of the \"end bends\" will blip out and be replaced with one from another direction.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1385,"value":"boardToPathEl(solveSyncStep(wfcDemoSeed, makeInitialBoard(3), 9, 3), 3)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1390,"value":" boardToPathEl(solveSyncStep(wfcDemoSeed, makeInitialBoard(3), 9 - 2, 3), 3)\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1338,"value":"function solveSyncStep (seed, board, entropyStep, w, h = w) {\n const random = makeRandomGenerator(seed)\n let mutations = findMutations(board, w)\n let i = 0\n while (mutations.length) {\n let mutationIndex = random(mutations.length)\n if (i === entropyStep) {\n mutationIndex = (mutationIndex + Math.floor(mutations.length / 2)) % mutations.length\n }\n const mutation = mutations[mutationIndex]\n board[mutation[0]] = mutation[1]\n board[mutation[2]] = mutation[3]\n mutations = findMutations(board, w)\n i++\n }\n return board\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1342,"value":"viewof wfcDemoSeed = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1344,"value":"viewof wfcDemoSize = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1369,"value":"wfcSteps = wfcDemoSize * wfcDemoSize","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1346,"value":"viewof wfcEntropyStep = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1349,"value":"boardToPathEl(solveSyncStep(wfcDemoSeed, makeInitialBoard(wfcDemoSize), wfcEntropyStep, wfcDemoSize), wfcDemoSize)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1378,"value":"md`But then going back from there, chosing different ones... how will that shift the form? Can we find a path through that space back to the original form to find an interesting loop?`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1820,"value":"md`# Later... SVG paths...\n\nhttps://observablehq.com/@forresto/labyrinth-to-svg`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1833,"value":"demo","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1825,"value":"import {demo} from '@forresto/labyrinth-to-svg'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W36","stdlib":"1"}} 2f:"$2e:body"