2a:null 2b:["$","title",null,{"children":"Random Growth 2 | fheyen | Observable"}] 30:T81c,canvas = { const size = Math.round(400/cellSize); const grid = Array.from({ length: size }) .fill(0) .map(() => Array.from({ length: size }).fill(0)); const center = Math.round(size/2); grid[center][center] = 1; const border = new Set([[center, center]]) const context = DOM.context2d(size * cellSize, size * cellSize); context.lineWidth = 0.5; context.strokeStyle = '#333'; context.fillStyle = 'white'; context.fillRect(0, 0, size * cellSize, size * cellSize); context.fillStyle = 'green'; context.fillRect(center * cellSize, center * cellSize, cellSize, cellSize); // Don't yield every frame for more performance let frame = 0; while (true) { if (border.size === 0) { break; } try { const chosenBorderCell = Array.from(border)[randInt(border.size - 1)]; const [x, y] = chosenBorderCell; let foundSpace = false; let xn = x; let yn = y; for (let i = 0; i < tries; ++i) { xn = x; yn = y; const direction = randInt(5); if (direction === 0) { yn--; } else if (direction === 1) { xn++; } else if (direction === 2) { yn++; } else if (direction === 3) { xn--; } else { // Go away from center xn = x>center? x+1 : x-1; yn = y>center? y+1 : y-1; } if (grid[xn][yn] === 0 && nFreeNeighbors(xn, yn, grid) > 5) { foundSpace = true; break; } } if (!foundSpace) { // Remove this as border border.delete(chosenBorderCell); context.fillStyle = 'green'; context.fillRect(x * cellSize, y * cellSize, cellSize, cellSize); } if (foundSpace) { grid[xn][yn] = 1; context.fillStyle = '#27C939'; context.fillRect(xn * cellSize, yn * cellSize, cellSize, cellSize); // New positon is border border.add([xn, yn]); } } catch (e) { // This can happend if no new positon is found, e.g. when the grid is very full } if(++frame >= 100) { yield (frame=0, context.canvas); } } }31:T8e7,canvas2 = { const size = Math.round(400 / cellSize); const grid = Array.from({ length: size }) .fill(0) .map(() => Array.from({ length: size }).fill(0)); const center = Math.round(size / 2); grid[center][center] = 1; const border = new Set([[center, center]]); const context = DOM.context2d(size * cellSize, size * cellSize); context.lineWidth = 0.5; context.strokeStyle = '#333'; context.fillStyle = 'white'; context.fillRect(0, 0, size * cellSize, size * cellSize); context.fillStyle = 'green'; context.fillRect(center * cellSize, center * cellSize, cellSize, cellSize); // Don't yield every frame for more performance let frame = 0; while (true) { if (border.size === 0) { break; } try { const chosenBorderCell = Array.from(border)[randInt(border.size - 1)]; const [x, y] = chosenBorderCell; let foundSpace = false; let xn = x; let yn = y; for (let i = 0; i < tries; ++i) { xn = x; yn = y; const direction = randInt(5); if (direction === 0) { yn--; } else if (direction === 1) { xn++; } else if (direction === 2) { yn++; } else if (direction === 3) { xn--; } else { const xyRatio = Math.abs(x / y); // Go away from center if (xyRatio > 1) { xn = x > center ? x + 1 : x - 1; } else { yn = y > center ? y + 1 : y - 1; } } if (grid[xn][yn] === 0 && nFreeNeighbors(xn, yn, grid) > 5) { foundSpace = true; break; } } if (!foundSpace) { // Remove this as border border.delete(chosenBorderCell); context.fillStyle = 'green'; context.fillRect(x * cellSize, y * cellSize, cellSize, cellSize); } if (foundSpace) { grid[xn][yn] = 1; context.fillStyle = '#27C939'; context.fillRect(xn * cellSize, yn * cellSize, cellSize, cellSize); // New positon is border border.add([xn, yn]); } } catch (e) { // This can happend if no new positon is found, e.g. when the grid is very full } if (++frame >= 100) { yield ((frame = 0), context.canvas); } } }32:T98b,canvas3 = { const size = Math.round(400 / cellSize); const grid = Array.from({ length: size }) .fill(0) .map(() => Array.from({ length: size }).fill(0)); const center = Math.round(size / 2); grid[center][center] = 1; const border = new Set([[center, center]]); const context = DOM.context2d(size * cellSize, size * cellSize); context.lineWidth = 0.5; context.strokeStyle = '#333'; context.fillStyle = 'white'; context.fillRect(0, 0, size * cellSize, size * cellSize); context.fillStyle = 'green'; context.fillRect(center * cellSize, center * cellSize, cellSize, cellSize); // Don't yield every frame for more performance let frame = 0; while (true) { if (border.size === 0) { break; } try { const chosenBorderCell = Array.from(border)[randInt(border.size - 1)]; const [x, y] = chosenBorderCell; let foundSpace = false; let xn = x; let yn = y; for (let i = 0; i < tries; ++i) { xn = x; yn = y; const direction = randInt(5); if (direction === 0) { yn--; } else if (direction === 1) { xn++; } else if (direction === 2) { yn++; } else if (direction === 3) { xn--; } else { const xyRatio = Math.abs((x - center) / (y - center)); // Go away from center if (Math.abs(xyRatio - 1) < 0.5) { xn = x > center ? x + 1 : x - 1; yn = y > center ? y + 1 : y - 1; } else if (xyRatio > 1) { xn = x > center ? x + 1 : x - 1; } else { yn = y > center ? y + 1 : y - 1; } } if (grid[xn][yn] === 0 && nFreeNeighbors(xn, yn, grid) > 5) { foundSpace = true; break; } } if (!foundSpace) { // Remove this as border border.delete(chosenBorderCell); context.fillStyle = 'green'; context.fillRect(x * cellSize, y * cellSize, cellSize, cellSize); } if (foundSpace) { grid[xn][yn] = 1; context.fillStyle = '#27C939'; context.fillRect(xn * cellSize, yn * cellSize, cellSize, cellSize); // New positon is border border.add([xn, yn]); } } catch (e) { // This can happend if no new positon is found, e.g. when the grid is very full } if (++frame >= 100) { yield ((frame = 0), context.canvas); } } }33:T8f2,canvas4 = { const size = Math.round(400 / cellSize); const grid = Array.from({ length: size }) .fill(0) .map(() => Array.from({ length: size }).fill(0)); const center = Math.round(size / 2); grid[center][center] = 1; const border = new Set([[center, center]]); const context = DOM.context2d(size * cellSize, size * cellSize); context.lineWidth = 0.5; context.strokeStyle = '#333'; context.fillStyle = 'white'; context.fillRect(0, 0, size * cellSize, size * cellSize); context.fillStyle = 'green'; context.fillRect(center * cellSize, center * cellSize, cellSize, cellSize); // Don't yield every frame for more performance let frame = 0; let randIndex = 0; while (true) { if (border.size === 0) { break; } try { const chosenBorderCell = Array.from(border)[randInt(border.size - 1)]; const [x, y] = chosenBorderCell; let foundSpace = false; let xn = x; let yn = y; for (let i = 0; i < tries; ++i) { xn = x; yn = y; const direction = randInt(4); if (direction === 0) { yn--; } else if (direction === 1) { xn++; } else if (direction === 2) { yn++; } else if (direction === 3) { xn--; } else { // Go 'to the right' const xyRatio = Math.abs((x - center) / (y - center)); xyRatio > 1 ? (x < center ? y-- : y++) : y < center ? x++ : x--; } if (grid[xn][yn] === 0 && nFreeNeighbors(xn, yn, grid) > 5) { foundSpace = true; break; } } if (!foundSpace) { // Remove this as border border.delete(chosenBorderCell); context.fillStyle = 'green'; context.fillRect(x * cellSize, y * cellSize, cellSize, cellSize); } if (foundSpace) { grid[xn][yn] = 1; context.fillStyle = '#27C939'; context.fillRect(xn * cellSize, yn * cellSize, cellSize, cellSize); // New positon is border if (border.size < 100) { border.add([xn, yn]); } } } catch (e) { // This can happend if no new positon is found, e.g. when the grid is very full } if (++frame >= 200) { yield ((frame = 0), context.canvas); } } }34:T8e2,canvas5 = { const size = Math.round(400 / cellSize); const grid = Array.from({ length: size }) .fill(0) .map(() => Array.from({ length: size }).fill(0)); const center = Math.round(size / 2); grid[center][center] = 1; const border = new Set([[center, center]]); const context = DOM.context2d(size * cellSize, size * cellSize); context.fillStyle = 'white'; context.fillRect(0, 0, size * cellSize, size * cellSize); context.fillStyle = 'green'; context.fillRect(center * cellSize, center * cellSize, cellSize, cellSize); // Don't yield every frame for more performance let frame = 0; let randIndex = 0; while (true) { if (border.size === 0) { break; } try { const chosenBorderCell = Array.from(border)[randInt(border.size - 1)]; const [x, y] = chosenBorderCell; let foundSpace = false; let xn = x; let yn = y; for (let i = 0; i < tries; ++i) { xn = x; yn = y; const direction = randInt(4); if (direction === 0) { yn--; } else if (direction === 1) { xn++; } else if (direction === 2) { yn++; } else if (direction === 3) { xn--; } else { // Go 'to the right' const xyRatio = Math.abs((x - center) / (y - center)); xyRatio > 1 ? (x < center ? y-- : y++) : y < center ? x++ : x--; } if (grid[xn][yn] === 0 && nFreeNeighborsInRange(xn, yn, grid, neighborhood) > requiredFreeNeighbors) { foundSpace = true; break; } } if (!foundSpace) { // Remove this as border border.delete(chosenBorderCell); context.fillStyle = 'green'; context.fillRect(x * cellSize, y * cellSize, cellSize, cellSize); } if (foundSpace) { grid[xn][yn] = 1; context.fillStyle = '#27C939'; context.fillRect(xn * cellSize, yn * cellSize, cellSize, cellSize); // New position is border if (border.size < 100) { border.add([xn, yn]); } } } catch (e) { // This can happend if no new position is found, e.g. when the grid is very full } if (++frame >= 200) { yield ((frame = 0), context.canvas); } } }35:[] 2e:{"id":"baee22b053035508","slug":"random-growth-2","title":"Random Growth 2","thumbnail":"b6782d1f95be030b8e1eab4f7f011c2aa924d37aa90392df9fa1d24b19a479dc","access_level":"public","create_time":"$D2021-04-19T13:32:51.125Z","update_time":"$D2021-10-13T12:11:59.269Z","view_time":null,"first_public_time":"$D2021-04-19T15:12:46.726Z","fork":{"id":"a4db7845b182e628","slug":"random-growth","title":"Random Growth","owner":{"id":"5cbdc37d5634c888","login":"fheyen","name":""}},"stars":0,"starred":false,"owner":{"type":"team","id":"5cbdc37d5634c888","login":"fheyen","name":"","avatar_url":"https://avatars-next.observableusercontent.com/5583b3edc59d97385b9ad17f74c76e9ed15457d372ed96534dbd829f3d95ebd5","tier":"starter_2024"},"version":730,"publish_version":730,"role":null,"authored":false,"authors":[{"type":"individual","id":"ce539535bc3f40fc","login":"fheyen","name":"","avatar_url":"https://avatars-next.observableusercontent.com/5583b3edc59d97385b9ad17f74c76e9ed15457d372ed96534dbd829f3d95ebd5","tier":null}],"members":[{"type":"individual","id":"ce539535bc3f40fc","login":"fheyen","name":"","avatar_url":"https://avatars-next.observableusercontent.com/5583b3edc59d97385b9ad17f74c76e9ed15457d372ed96534dbd829f3d95ebd5","tier":null,"role":"editor"}],"comments":[{"id":"4bf9152dc807a22a","reply_to_id":null,"content":"By yielding on every iteration you're restricting your simulation to at most 60 steps per second, because Observable uses requestAnimationFrame() to produce new values from a generator cell.\n\nI would instead suggest to only yield every nth frame. E.g., this would yield every 100th frame:\n\nlet n = 0;\nwhile(true) {\n // ...\n if(++n >= 100) yield (n=0, context.canvas);\n}","create_time":"$D2021-04-21T14:55:36.617Z","update_time":null,"resolved":true,"user":{"type":"individual","id":"07362516b5994994","login":"mootari","name":"Fabian Iwand","avatar_url":"https://avatars-next.observableusercontent.com/0d7defa821f38094c03bad23b9b360a5364e6e97e21fc238c39ddc48db7994ad","tier":null}},{"id":"b6ed272774a65132","reply_to_id":"4bf9152dc807a22a","content":"Thanks! I was indeed wondering how to speed it up","create_time":"$D2021-04-21T15:43:28.578Z","update_time":null,"resolved":true,"user":{"type":"individual","id":"ce539535bc3f40fc","login":"fheyen","name":"","avatar_url":"https://avatars-next.observableusercontent.com/5583b3edc59d97385b9ad17f74c76e9ed15457d372ed96534dbd829f3d95ebd5","tier":null}},{"id":"63c65cfa095571d2","reply_to_id":"4bf9152dc807a22a","content":"Small correction of my earlier comment (for posterity):\n\"I would instead suggest to only yield every nth iteration. E.g., this would yield every 100th iteration:\"","create_time":"$D2021-04-21T16:19:28.140Z","update_time":null,"resolved":true,"user":{"type":"individual","id":"07362516b5994994","login":"mootari","name":"Fabian Iwand","avatar_url":"https://avatars-next.observableusercontent.com/0d7defa821f38094c03bad23b9b360a5364e6e97e21fc238c39ddc48db7994ad","tier":null}}],"custom_thumbnail":false,"trashed":false,"subscribed":null,"forks":0,"collection":{"id":"8938cec8689df6a8","slug":"art","title":"Art","owner":{"id":"5cbdc37d5634c888","login":"fheyen","name":""}},"type":"notebook","body":{"title":"Random Growth 2","cells":[{"id":0,"value":"md`# Random Growth 2\nStarting from the center, this structure grows further and further into the free space, while avoiding self-collisions.\n\nBased on [an earlier project](https://observablehq.com/@fheyen/random-growth), but exploring different strategies.\n\n~~This may take a while to compute~~ Thanks to [@mootari](https://observablehq.com/@mootari) for performance suggestions!\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":330,"value":"viewof tries = Range([1, 10], {value: 5, step: 1, label: \"'Growthiness'\"})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":373,"value":"md`## Preferring diagonal growth`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":6,"value":"$30","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":394,"value":"md`## Preferring horizontal and vertical growth`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":367,"value":"$31","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":431,"value":"md`## Hybrid of the two above, depending on direction`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":425,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":492,"value":"md`## 'Turn right'`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":443,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":610,"value":"md`## Larger Neighbor Region`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":659,"value":"md`Instead of looking at only the 8 immediately neighboring cells, we can also look at a larger square with some 'radius' (e.g. with a radius \\`r\\`, look in a square of \\`(2*r+1)^2\\` around the selected cell).\nThis can be seen as generalization of the above examples, they just use a radius of 1 (try a radius of 1 with 6 free neighbors below).\n\nLooks a lot more natural!\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":621,"value":"viewof neighborhood = Range([1, 10], {value: 5, step: 1, label: \"Neighborhood 'radius'\"})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":628,"value":"viewof requiredFreeNeighbors = Range([1, (neighborhood*2+1)**2], {value: 75, step: 1, label: \"Free neighbors\"})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":559,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":304,"value":"md`## Further Reading\n- With a [hexagonal grid](https://www.redblobgames.com/grids/hexagons/)\n- [RRT](https://en.wikipedia.org/wiki/Rapidly-exploring_random_tree), e.g. see [here](https://www.jasondavies.com/rrt/)\n- [DLA](https://www.jasondavies.com/dla/) [2](https://bl.ocks.org/xmichaelx/39fa023f9ce1fb82d5c0) [3](https://observablehq.com/@tmcw/diffusion-limited-aggregation)\n- [@techsparx/an-improvement-on-bridsons-algorithm-for-poisson-disc-samp/2](https://observablehq.com/@techsparx/an-improvement-on-bridsons-algorithm-for-poisson-disc-samp/2)\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":136,"value":"cellSize = 2;","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":111,"value":"function nFreeNeighbors(x, y, grid) {\n // Check how many neighbors are free\n let free = 0;\n if (grid[x][y-1] === 0) free++;\n if (grid[x][y+1] === 0) free++;\n if (grid[x-1][y] === 0) free++;\n if (grid[x+1][y] === 0) free++;\n // Diagonal\n if (grid[x-1][y-1] === 0) free++;\n if (grid[x-1][y+1] === 0) free++;\n if (grid[x+1][y-1] === 0) free++;\n if (grid[x+1][y+1] === 0) free++;\n return free;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":593,"value":"function nFreeNeighborsInRange(x, y, grid, range) {\n // Check how many neighbors are free\n let free = 0;\n for (let xOffset = -range; xOffset <= range; ++xOffset) {\n for (let yOffset = -range; yOffset <= range; ++yOffset) {\n if (grid[x + xOffset][y + yOffset] === 0) free++;\n }\n }\n return free;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":16,"value":"function randInt(max) {\n return Math.round(Math.random()*max);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":508,"value":"randomLookup7 = Array.from({length: 10_000}).map(()=>randInt(7))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":325,"value":"import {Range} from \"@observablehq/inputs\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"}],"files":"$W35","stdlib":"1","titling":"auto"}} 2f:"$2e:body"