2b:null 2c:["$","title",null,{"children":"Fill grid with largest possible squares around obstacles | Grant Custer | Observable"}] 31:Tb4e,draw = () => { regen; ctx.clearRect(0, 0, cwidth, cheight); ctx.fillStyle = "white"; ctx.fillRect(0, 0, cwidth, cheight); let columns = cwidth / cell_size; let rows = cheight / cell_size; let cstep = cell_size; let rstep = cell_size; function getCellIndex(column, row) { return row * columns + column; } function getCellColumnRow(index) { let column = index % columns; let row = Math.floor(index / columns); return [column, row]; } function expandSquare(cells, covered, index) { let start = index; let [scol, srow] = getCellColumnRow(index); let w = 1; let h = 1; function _expand() { if (w === h) { let to_expand = []; let next_column = scol + w; if (next_column === columns) return [w, h]; for (let i = 0; i < h; i++) { let eindex = getCellIndex(next_column, srow + i); let expand_candidate = cells[eindex]; let expand_check = expand_candidate === null && !covered.includes(eindex); if (!expand_check) return [w, h]; } // all expand checks passed w++; return _expand(); } else { let to_expand = []; let next_row = srow + h; if (next_row === rows) return [w - 1, h]; for (let i = 0; i < w; i++) { let eindex = getCellIndex(scol + i, next_row); let expand_candidate = cells[eindex]; to_expand.push(expand_candidate); let expand_check = expand_candidate === null && !covered.includes(eindex); if (!expand_check) return [w - 1, h]; } // all expand checks passed h++; return _expand(); } } return _expand(); } let cells = []; for (let r = 0; r < rows; r++) { for (let c = 0; c < columns; c++) { cells.push(null); } } let randomly_filled_cells = cells.map(c => Math.random() > 0.9 ? "w" : null ); let expanded = []; let covered = []; for (let i = 0; i < cells.length; i++) { let cell = randomly_filled_cells[i]; if (cell === null && !covered.includes(i)) { let [col, row] = getCellColumnRow(i); let [w, h] = expandSquare(randomly_filled_cells, covered, i); expanded.push([col, row, w, h]); // add to covered; for (let r = 0; r < h; r++) { for (let c = 0; c < w; c++) { let cindex = getCellIndex(col + c, row + r); covered.push(cindex); } } } } for (let i = 0; i < cells.length; i++) { let cell = randomly_filled_cells[i]; let [col, row] = getCellColumnRow(i); if (cell === "w") { ctx.fillStyle = "black"; ctx.fillRect(col * cstep, row * rstep, cstep, rstep); } } for (let expand of expanded) { let [col, row, w, h] = expand; ctx.strokeRect(col * cstep, row * rstep, w * cstep, h * rstep); } }32:[] 2f:{"id":"849dae3638b43a02","slug":"fill-grid-with-largest-possible-squares-around-obstacles","title":"Fill grid with largest possible squares around obstacles","thumbnail":"be1a3d309cc46243ed8c44cd7ca1f45b5af425735c66934a8cc0020f6e648352","access_level":"public","create_time":"$D2018-11-28T17:36:16.738Z","update_time":"$D2018-11-29T18:36:14.049Z","view_time":null,"first_public_time":"$D2018-11-29T17:47:30.282Z","has_unpublished_edits":null,"fork":true,"stars":7,"starred":false,"owner":{"type":"team","id":"bf2c1edd2a33aa1b","login":"grantcuster","name":"Grant Custer","avatar_url":"https://avatars-next.observableusercontent.com/10eebb9a620b6b833738fb495f94fb682bcdc3270b247a9a8aef575ed0702c48","tier":"starter_2024"},"version":522,"publish_version":522,"role":null,"authored":false,"authors":[{"type":"individual","id":"a1f8c368ee3d80be","login":"grantcuster","name":"Grant Custer","avatar_url":"https://avatars-next.observableusercontent.com/10eebb9a620b6b833738fb495f94fb682bcdc3270b247a9a8aef575ed0702c48","tier":null}],"members":[{"type":"individual","id":"a1f8c368ee3d80be","login":"grantcuster","name":"Grant Custer","avatar_url":"https://avatars-next.observableusercontent.com/10eebb9a620b6b833738fb495f94fb682bcdc3270b247a9a8aef575ed0702c48","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":4,"collection":{"id":"84831eedf07425ed","slug":"diagrams","title":"Designs and diagrams","owner":{"id":"bf2c1edd2a33aa1b","login":"grantcuster","name":"Grant Custer"}},"type":"notebook","body":{"titling":"auto","title":"Fill grid with largest possible squares around obstacles","cells":[{"id":0,"value":"md`# Fill grid with largest possible squares around obstacles`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2,"value":"canvas = {\n draw();\n yield ctx.canvas;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":242,"value":"viewof regen = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":483,"value":"md`Inspired by [this work](http://feed.grantcuster.com/post/20181016T171452195Z) by Process Studio. This set-up breaks the canvas into a grid, fills in random cells (show in black). then goes back through and fills in the gaps with the largest possible squares. The algorithm iterates through each open cell and tries to expand the square until it runs into a filled square. This was harder than I thought it was going to be and not as clean as I'd hoped. It somebody has tips on how to clean it up I'd love to hear/see them.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":4,"value":"$31","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":49,"value":"ctx = DOM.context2d(cwidth, cheight)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":506,"value":"cwidth = Math.floor(width / cell_size) * cell_size","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":510,"value":"cheight = Math.ceil(cwidth / cell_size / 2) * cell_size","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":504,"value":"cell_size = 20","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W32","stdlib":"1"}} 30:"$2f:body"