2d:null 2e:["$","title",null,{"children":"Wave Function Collapse | Michael Cooper | Observable"}] 33:T520,map = { reset; let start = new Date(); let map = []; while (map.length < mapSize.h) { let row = []; while (row.length < mapSize.w) { row.push({ x: row.length, y: map.length, options: Array.from(Object.keys(tileTypes)) }); } map.push(row); } if (incremental) yield map; let stepsRemaining = mapSize.w * mapSize.h * 10; let step = 0; while (_.flatten(map).some((cell) => cell.options.length > 1)) { if (stepsRemaining-- <= 0) { break; } let previousMap = JSON.parse(JSON.stringify(map)); let uncollapsedCells = _.flatten(map).filter( (cell) => cell.options.length > 1 ); if (!uncollapsedCells.length) { break; } const cellToCollapse = d3.sort( _.shuffle(uncollapsedCells), (d) => d.options.length )[0]; cellToCollapse.options = [chooseRandom(cellToCollapse.options)]; collapseMap(cellToCollapse, map); if (_.flatten(map).some((cell) => cell.options.length === 0)) { map = previousMap; } else { step += 1; } if (incremental && step % incrementalStepSize === 0) { mutable debug = { timeTaken: new Date() - start, steps: step }; yield map; } } mutable debug = { timeTaken: new Date() - start, steps: step }; yield map; }34:[] 31:{"id":"dbaeb246a89104ab","slug":"wave-function-collapse-tiles","title":"Wave Function Collapse","thumbnail":"10a3121967e225f572b0afb0e4a689b0afb2435e77773ed0cac46af123b898ae","access_level":"unlisted","create_time":"$D2022-05-18T21:45:10.241Z","update_time":"$D2022-05-26T05:54:06.398Z","view_time":null,"first_public_time":null,"has_unpublished_edits":null,"fork":false,"stars":3,"starred":false,"owner":{"type":"team","id":"3a9cb3bb8fb63f67","login":"mythmon","name":"Michael Cooper","avatar_url":"https://avatars-next.observableusercontent.com/60cdc428c59f56064db989dbde23b5af37103628a470beeebd56d0c18c206120","tier":"starter_2024"},"version":448,"publish_version":448,"role":null,"authored":false,"authors":[{"type":"individual","id":"b2ae65df1901fe65","login":"mythmon","name":"Michael Cooper","avatar_url":"https://avatars-next.observableusercontent.com/60cdc428c59f56064db989dbde23b5af37103628a470beeebd56d0c18c206120","tier":null}],"members":[{"type":"individual","id":"b2ae65df1901fe65","login":"mythmon","name":"Michael Cooper","avatar_url":"https://avatars-next.observableusercontent.com/60cdc428c59f56064db989dbde23b5af37103628a470beeebd56d0c18c206120","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"title":"Wave Function Collapse","cells":[{"id":0,"value":"# Wave Function Collapse\n\nGenerates a grid of tiles semi-randomly based on adjanency rules. Inspired by many sources, including [Gridbugs](https://www.gridbugs.org/wave-function-collapse/).","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":277,"value":"tileField(map)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":133,"value":"viewof reset = Inputs.button(\"Reroll\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":279,"value":"viewof incremental = Inputs.toggle({ label: \"Animate progress\", value: true })","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":297,"value":"viewof incrementalStepSize = Inputs.range([1, 1000], {\n label: \"Steps per update\",\n step: 1,\n value: 50\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":345,"value":"---\n\n## Why is this so slow when animate progress is checked?\n### Total runtime","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":321,"value":"Plot.plot({\n marks: [\n Plot.barY(\n runtimes,\n Plot.groupX(\n { y: \"mean\" },\n {\n x: \"stepSize\",\n y: \"timeTaken\",\n fill: (d) => (d.incremental ? \"Animated\" : \"One-shot\"),\n sort: { x: \"y\", reverse: true },\n z: \"stepSize\"\n }\n )\n ),\n Plot.ruleY([0])\n ],\n x: { tickFormat: (d) => d ?? \"One-shot\", label: \"Steps per update\" },\n y: {\n label: \"Total time (sec )\",\n tickFormat: (d) => d3.format(\".2s\")(d / 1000)\n },\n color: { scheme: \"set1\", legend: true }\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":424,"value":"### Steps per run","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":416,"value":"Plot.plot({\n marks: [\n Plot.rectY(\n runtimes,\n Plot.binX(\n { y: \"count\" },\n { x: \"steps\", fill: (d) => (d.incremental ? \"Animated\" : \"One-shot\") }\n )\n ),\n Plot.ruleY([0])\n ],\n color: { scheme: \"set1\", legend: true }\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":282,"value":"mutable debug = null","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":301,"value":"runtimes = d3\n .csvParse(\n `timeTaken,steps,stepSize,incremental,width,height\n14403,1607,30,true,58,29\n14107,1579,30,true,58,29\n14093,1564,30,true,58,29\n20327,1607,20,true,58,29\n20346,1612,20,true,58,29\n19840,1562,20,true,58,29\n40839,1592,10,true,58,29\n40067,1571,10,true,58,29\n39875,1570,10,true,58,29\n5745,1585,100,true,58,29\n5613,1542,100,true,58,29\n5625,1574,100,true,58,29\n2025,1559,,false,58,29\n2026,1525,,false,58,29\n2018,1546,,false,58,29\n2856,1569,1000,true,58,29\n2765,1586,1000,true,58,29\n2758,1603,1000,true,58,29\n2101,1591,,null,58,29\n2238,1613,,null,58,29\n`\n )\n .map((d) => ({\n ...d,\n timeTaken: +d.timeTaken,\n steps: +d.steps,\n stepSize: d.stepSize ? +d.stepSize : null,\n incremental: d.incremental === \"true\",\n width: +d.width,\n height: +d.height\n }))","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":381,"value":"## Wave Collapse Algorithm","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":54,"value":"$33","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":250,"value":"collapseMap = (cellToCollapse, map) => {\n let queue = [cellToCollapse];\n while (queue.length) {\n let targetCell = queue.shift();\n for (let [dx, dy] of [\n [-1, 0],\n [1, 0],\n [0, -1],\n [0, 1]\n ]) {\n let allNeighborOptions = new Set();\n for (const option of targetCell.options) {\n let tileType = tileTypes[option];\n for (let n of tileType.neighbors) {\n allNeighborOptions.add(n);\n }\n }\n\n let x = targetCell.x + dx;\n let y = targetCell.y + dy;\n let neighbor = map[y]?.[x];\n if (!neighbor) continue;\n let newOptions = neighbor.options.filter((optName) =>\n allNeighborOptions.has(optName)\n );\n if (newOptions.length < neighbor.options.length) {\n neighbor.options = newOptions;\n queue.push(neighbor);\n }\n }\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":383,"value":"## Constants","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":151,"value":"mapSize = ({ w: 58, h: 29 })","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":27,"value":"tileSize = Math.floor(Math.min(width / mapSize.w, 500 / mapSize.h))","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":94,"value":"numTileTypes = Array.from(Object.keys(tileTypes)).length","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":6,"value":"tileTypes = Object.fromEntries(\n [\n {\n id: \"grass\",\n color: \"lime\",\n neighbors: [\"grass\", \"forest\", \"sand\"]\n },\n {\n id: \"forest\",\n color: \"green\",\n neighbors: [\"forest\", \"grass\"]\n },\n {\n id: \"sand\",\n color: \"yellow\",\n neighbors: [\"sand\", \"grass\", \"water\"]\n },\n {\n id: \"water\",\n color: \"blue\",\n neighbors: [\"water\", \"sand\", \"deepwater\"]\n },\n {\n id: \"deepwater\",\n color: \"rgb(0, 0, 80)\",\n neighbors: [\"water\", \"deepwater\"]\n }\n ].map((tile) => [tile.id, tile])\n)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":385,"value":"## Renderers","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":13,"value":"tileField = (map) =>\n html`\n \n ${map.flatMap((row) => row.map((cell) => tileComp(cell)))}\n \n `","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":46,"value":"tileComp = ({ options, x, y }) => {\n if (options.length === 1)\n return html``;\n\n return null;\n\n // the below is too dom-heavy\n\n // return html`\n // ${options.map((tn) => html`

`)}\n // `;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":18,"value":"\n\n${Array.from(Object.values(tileTypes)).map(tile => \n htl.html``\n)}","pinned":true,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":394,"value":"## Helpers","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":91,"value":"chooseRandom = (vals, weight = () => 1) => {\n let weights = vals.map((val) => weight(val));\n let totalWeight = d3.sum(weights);\n let r = Math.random() * totalWeight;\n for (let i = 0; i < vals.length; i++) {\n r -= weights[i];\n if (r <= 0) return vals[i];\n }\n throw new Error(\"no value chosen\");\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":15,"value":"html = htl.html","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W34","stdlib":"1","titling":"auto"}} 32:"$31:body"