36:["$","title",null,{"children":"Best-First Search | pembeci | Observable"}] 3e:Tfa4,{ let k = (cellHeight - 1) * cellWidth, q = 0; const width = cellWidth * (cellSize + cellSpacing) + cellSpacing; const height = cellHeight * (cellSize + cellSpacing) + cellSpacing; const context = DOM.context2d(width, height, 1); context.canvas.style.imageRendering = "pixelated"; context.fillStyle = "#777"; context.fillRect(0, 0, width, height); context.fillStyle = "#fff"; fillCells(context); const maxPaths = 50; obstacles.clear(); const totalCells = cellHeight * cellWidth const obstacleCount = Math.round(totalCells * obstacleRatio); obstacleWeights.clear(); while (obstacles.size < obstacleCount) { const i = Math.floor(Math.random()*totalCells); obstacles.add(i); obstacleWeights.set(i, 1+Math.floor(Math.random()*20)); } // const colors = d3.schemeBuGn[maxPaths] /* Simulating running the algorithm and finding the best paths. For the first n-1 simulations put some obstacles on the path so it is no longer the best path (i.e. lowest cost). This is done hoping to eliminate trivial paths that go from one corner to the other almost in a straight line. The last simulation is used to record the best path cells to show it to the user. */ for (let sim=1; sim<=4; sim++) { const frontier2 = new Queue(); const parent2 = Object.assign(new Array(cellHeight * cellWidth), {[k]: -1}); for (const j of explore(k, parent2, frontier2)) { if (score(j) === 0) { context.fillStyle = "#ddd"; let p = j; while (p>=0 && p != k) { if (sim==4) fillCell(context, p); else if (Math.random() < 0.1 && !obstacles.has(p)) { obstacles.add(p); obstacleWeights.set(p, 4); } p = parent2[p]; } yield context.canvas; break; } } } obstacles.forEach(i => fillCircle(context,i)); const frontier = new Queue(); const parent = Object.assign(new Array(cellHeight * cellWidth), {[k]: -1}); let found = false; let lastPath = null; for (const j of explore(k, parent, frontier)) { const removedNodes = []; const dirty = new Set(); const paths = {}; if (lastPath) paths[0] = lastPath; let rank = 1; while (frontier.length > 0 && rank <= (found ? (maxPaths * 5) : maxPaths)) { const score = frontier.peekValue(); const bestIndex = frontier.pop(); removedNodes.push([bestIndex, score]); if (!paths[rank]) paths[rank] = new Set(); let p = bestIndex; while (p >= 0 && !dirty.has(p)) { paths[rank].add(p); dirty.add(p); p = parent[p]; } if (found && paths[rank].size <= 1) paths[rank] = new Set(); else rank += 1; // rank += 1; } let maxRank = rank-1; removedNodes.forEach(arr => frontier.push(arr[0], arr[1])); Object.keys(paths).forEach(rank => { // context.fillStyle = `rgba(0,0,0,${0.2 + 0.8*(maxPaths+1-rank)/maxPaths}`; // context.fillStyle = colors[rank-1]; // context.fillStyle = d3.interpolateViridis(1 - (0.2 + 0.8*(maxPaths+1-rank)/maxPaths)); // const fillColor = rank == 1 ? "#000" : d3.interpolateViridis(1 - (maxPaths+1-rank)/maxPaths) const fillColor = rank <= 1 ? "#000" : d3.interpolateViridis(1 - (maxRank+1-rank)/maxRank) context.fillStyle = fillColor; paths[rank].forEach(i => { // fillCircle(context, i); fillCell(context, i); if (obstacles.has(i)) { fillCircle(context,i); context.fillStyle = fillColor; } }); }) yield context.canvas; // await sleep(50); if (found) {lastPath = paths[1]; break}; if (score(j) === 0) found=true; context.fillStyle = "#FFF"; // dirty.forEach(i => fillCircle(context,i, true)); dirty.forEach(i => { fillCell(context,i); if (obstacles.has(i)) { fillCircle(context,i); context.fillStyle = "#FFF"; } }) } } 3f:T46a,function* explore(start, parent, frontier) { const cost = new Uint8Array(cellHeight * cellWidth); let i, j; frontier.push(start, score(start)); while ((i = frontier.pop()) !== undefined) { const c = cost[i]; if (cells[i] & E && parent[j = i + 1] === undefined) { parent[j] = i, cost[j] = c + (obstacles.has(j) ? obstacleWeights.get(j)*obstacleCost : 0); frontier.push(j, cost[j] + score(j)); yield j; } if (cells[i] & W && parent[j = i - 1] === undefined) { parent[j] = i, cost[j] = c + (obstacles.has(j) ? obstacleWeights.get(j)*obstacleCost : 0); frontier.push(j, cost[j] + score(j)); yield j; } if (cells[i] & S && parent[j = i + cellWidth] === undefined) { parent[j] = i, cost[j] = c + (obstacles.has(j) ? obstacleWeights.get(j)*obstacleCost : 0); frontier.push(j, cost[j] + score(j)); yield j; } if (cells[i] & N && parent[j = i - cellWidth] === undefined) { parent[j] = i, cost[j] = c + (obstacles.has(j) ? obstacleWeights.get(j)*obstacleCost : 0); frontier.push(j, cost[j] + score(j)); yield j; } } }40:T505,function generate(cellWidth, cellHeight) { const heap = new Queue(); const cells = new Uint8Array(cellWidth * cellHeight); let edge; heap.push({index: 0, direction: N}, Math.random()); heap.push({index: 0, direction: E}, Math.random()); while (edge = heap.pop()) { let i0 = edge.index, i1; let d0 = edge.direction, d1; let x0 = i0 % cellWidth, x1; let y0 = i0 / cellWidth | 0, y1; if (d0 === N) i1 = i0 - cellWidth, x1 = x0, y1 = y0 - 1, d1 = S; else if (d0 === S) i1 = i0 + cellWidth, x1 = x0, y1 = y0 + 1, d1 = N; else if (d0 === W) i1 = i0 - 1, x1 = x0 - 1, y1 = y0, d1 = E; else i1 = i0 + 1, x1 = x0 + 1, y1 = y0, d1 = W; if (cells[i1] === 0 /* || Math.random() < 0.001 */ ) { cells[i0] |= d0, cells[i1] |= d1; if (y1 > 0 && cells[i1 - cellWidth] === 0) { heap.push({index: i1, direction: N}, Math.random()); } if (y1 < cellHeight - 1 && cells[i1 + cellWidth] === 0) { heap.push({index: i1, direction: S}, Math.random()); } if (x1 > 0 && cells[i1 - 1] === 0) { heap.push({index: i1, direction: W}, Math.random()); } if (x1 < cellWidth - 1 && cells[i1 + 1] === 0) { heap.push({index: i1, direction: E}, Math.random()); } } } return cells; }41:[] 3a:{"id":"78fa1dbfcf9420b8","slug":"untitled/2","title":"Best-First Search","thumbnail":"0e8fd5353e337c9b323e173172b771e30127f5be5264120c699c84991adc09f9","access_level":"public","create_time":"$D2018-10-29T18:05:03.652Z","update_time":"$D2021-03-04T20:28:27.596Z","view_time":null,"first_public_time":"$D2018-11-10T10:05:24.497Z","has_unpublished_edits":null,"fork":{"id":"0111a8d2e0bf050b","slug":"best-first-search","title":"Best-First Search","owner":{"id":"8c2e47252fd4995c","login":"mbostock","name":"Mike Bostock"}},"stars":0,"starred":false,"owner":{"type":"team","id":"88abc8fecdeb7811","login":"pembeci","name":"","avatar_url":"https://avatars-next.observableusercontent.com/f1ff548c862bdb114171e430f5632b7bea66b973a6a092c53b86ecf9211ca9a0","tier":"starter_2024","bio":"","followed_by_you":false,"follows_you":false},"version":721,"publish_version":721,"role":null,"authored":false,"authors":[{"type":"individual","id":"d703748563fe201b","login":"pembeci","name":"","avatar_url":"https://avatars-next.observableusercontent.com/f1ff548c862bdb114171e430f5632b7bea66b973a6a092c53b86ecf9211ca9a0","tier":null,"bio":"","followed_by_you":false,"follows_you":false}],"members":[{"type":"individual","id":"d703748563fe201b","login":"pembeci","name":"","avatar_url":"https://avatars-next.observableusercontent.com/f1ff548c862bdb114171e430f5632b7bea66b973a6a092c53b86ecf9211ca9a0","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":2,"collection":null,"type":"notebook","body":{"titling":"auto","title":"Best-First Search","cells":[{"id":0,"value":"md`# Best-First Search\n\nMore specifically, [A* search](https://en.wikipedia.org/wiki/A*_search_algorithm).` ","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":687,"value":"md`**WIP**\n\nShow the best branches instead of visited cells as in the original notebook. By best branches I mean the nodes/cells in the A* tree whose scores are the lowest thus most promising to be part of the correct path. The color of the branch denotes how promising it is (from less promising yellow to most promising dark blue). Colors are based on rank not value of the score. Black cells denote the current expanded path. We can watch how the algorithm switchs between the branches because rank of node scores change as new nodes (and their scores) are added to the tree. Light gray cells are the solution. So you can hit replay several times and try to find a solution which is more fractal edge (Norwegian coastline) like rather than a straight line from one corner to the other. Some obstacles (red dots) are added to the cells to make things harder for the algorithm. Obstacles add to the cost of the path. So the goal is not just the shortest path but a path with less obstacles. \n`\n ","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":122,"value":"viewof replay = html`