2d:null 2e:["$","title",null,{"children":"Search algorithm animations | Ayaan Kazerouni | Observable"}] 33:Td07,grid = { const gridSize = 500; const cellSize = gridSize / rowsCols; let clickedType = 'UNVISITED'; function setPointType(target, datum, dragStart) { const { type } = datum; if (['START', 'GOAL'].includes(type)) { return; } if (type === 'UNVISITED') { datum.type = 'OBSTACLE'; target.setAttribute('fill', 'grey'); } else if (type === 'OBSTACLE') { datum.type = 'UNVISITED'; target.setAttribute('fill', 'white'); } } function setNew(datum, type) { // These should update the original points, which will be used by the search algorithm const old = points.flat().find(p => p.type === type); if (old) { old.type = 'UNVISITED'; } const nu = points.flat().find(p => p.x === datum.x && p.y === datum.y); nu.type = type; } const svg = d3.create('svg') .attr('viewBox', [0, 0, gridSize, gridSize]) .style('max-width', `${gridSize}px`); const gridCell = svg.append('g') .attr('stroke', 'black') .attr('stroke-width', 1) .attr('max-width', '70%'); // Grid is drawn based on the searchPoints, which is initially just a copy of the original points list const rects = gridCell .selectAll('rect') .data(searchPoints.flat(), d => `${d.x}, ${d.y} ${d.type}`) .join('rect') .attr('x', d => d.x * cellSize) .attr('y', d => d.y * cellSize) .attr('width', cellSize) .attr('height', cellSize) .attr('fill', d => cellColor[d.type] || 'white') .attr('stroke-width', d => d.selected ? 3 : 1) .on('mouseout', (e, d) => { const { buttons, target } = e; if (buttons === 1) { target.setAttribute('stroke-width', 1); if (['START', 'GOAL'].includes(clickedType)) { // Unset the type target.setAttribute('fill', 'white'); } } }) .on('mouseover', (e, d) => { const { buttons, target } = e; if (buttons === 1) { target.setAttribute('stroke-width', 3); if (['START', 'GOAL'].includes(clickedType)) { target.setAttribute('fill', cellColor[clickedType]); } else { setPointType(target, d); } } }) .on('mousedown', (e, d) => { const { target } = e; target.setAttribute('stroke-width', 3); setPointType(target, d); clickedType = d.type; }) .on('mouseup', (e, d) => { const { target } = e; target.setAttribute('stroke-width', 1); // User interaction is complete. Update the points array if (clickedType === 'START') { setNew(d, 'START'); } else if (clickedType === 'GOAL') { setNew(d, 'GOAL'); } }) const pathLines = gridCell .selectAll('path') .data(searchPoints.flat().filter(p => p.type === 'PATH'), d => `${d.x}, ${d.y} ${d.type}`) .join('path') .attr('stroke', 'yellow') .attr('stroke-width', '2pt') .attr('fill', 'none') .attr('d', d => { const {start, end} = pathLine(d, cellSize); const centre = { x: (d.x * cellSize) + (cellSize / 2), y: (d.y * cellSize) + (cellSize / 2) }; return `M ${start.x} ${start.y} L ${centre.x} ${centre.y} ${end.x} ${end.y}` }) return svg.node(); }34:Ta3d,searchPoints = { const initialPoints = mutable points; while (gridControls) { const flattened = initialPoints.flat() const start = flattened.find(p => p.type === 'START'); start.g = 0; // Only needed for A-star const goal = flattened.find(p => p.type === 'GOAL'); // The structure for the list of neighbours to visit depends on the // search algorithm being used. let toVisit = { 'BFS': new Queue(), 'DFS': new Stack(), 'AStar': new PriorityQueue((a, b) => { const aH = heuristic(a, goal); const bH = heuristic(b, goal); const fComp = (a.g + aH) - (b.g + bH); if (fComp === 0) { return tieBreakStrategy === 'insertionOrder' ? a._insertionOrder - b._insertionOrder : tieBreakStrategy === 'greedy' ? aH - bH : fComp; } return fComp; }) }[searchType]; toVisit.push(start); while (toVisit.length) { // PriorityQueue, Queue, and Stack have the same interface for { includes, remove, push, length } let current = toVisit.remove(); if (adjacent(current, goal)) { while (current.previous !== null) { current.type = 'PATH'; if (current.previous) { current.previous.next = current; // Helps with drawing the path. } current = current.previous; } break; } current.type = ['START', 'GOAL'].includes(current.type) ? current.type : 'VISITED'; neighbours(current, diagonals) .filter(withinBounds) .map(({x, y}) => initialPoints[y][x]) .filter(n => ['UNVISITED', 'QUEUED'].includes(n.type)) .forEach(n => { // Some extra steps needed for A-star if (searchType !== 'AStar' && !toVisit.includes(n)) { n.previous = current; n.type = 'QUEUED'; toVisit.push(n); } else if(searchType === 'AStar') { const newG = current.g + 1; if (!toVisit.includes(n) || toVisit.removeIf(inQueue => inQueue.x === n.x && inQueue.y === n.y && inQueue.g > newG)) { n.previous = current; n.type = 'QUEUED'; n.g = newG; toVisit.push(n); } } }); // if click to search is turned on, make it wait again yield Promises.delay(timeScale(speed), initialPoints) } // Search concluded: simulate a click on the toggle search button viewof gridControls[2].dispatchEvent(new Event("click")); yield initialPoints; } yield initialPoints; // The search was terminated }35:Tc5f,class PriorityQueue { constructor(comp) { this.comp = comp; this.heap = []; this.insertionCounter = 0; // Add this } get length() { return this.heap.length; } push(point) { point._insertionOrder = this.insertionCounter++; this.heap.push(point); this.siftUp(this.heap.length - 1); } includes(point) { return this.heap.find(p => p.x === point.x && p.y === point.y) !== undefined; } removeIf(pred) { const index = this.heap.findIndex(pred); if (index !== -1) { this.remove(index); return true; } return false; } remove(pos=0) { if (this.heap.length === 0) { throw new Error("Can't remove. Heap is empty."); } if (pos === this.heap.length - 1) { // We are removing the last element return this.heap.pop(); } else { this.swap(pos, this.heap.length - 1) const toReturn = this.heap.pop(); this.siftDown(pos); return toReturn; } } siftUp(pos) { if (pos == 0) { return; } if (this.isInvalid(pos)) { throw new Error('Invalid heap position', pos); } const parentIndex = this.getParent(pos); const parent = this.heap[parentIndex] const toSift = this.heap[pos]; // Swap the node and its parent if the node is smaller than the parent if (parent !== undefined && this.comp(toSift, parent) < 0) { this.swap(pos, parentIndex); this.siftUp(parentIndex); } } siftDown(pos) { if (this.heap.length === 0 || this.isLeaf(pos)) { return; } const leftIndex = this.getLeft(pos); const rightIndex = this.getRight(pos); let swapIndex; let toSwap; if (rightIndex >= this.heap.length) { // There is no right child toSwap = this.heap[leftIndex]; swapIndex = leftIndex; } else { const left = this.heap[leftIndex]; const right = this.heap[rightIndex]; // If a swap is to occur, we want to swap with the smallest child node. toSwap = this.comp(left, right) < 0 ? left : right; swapIndex = this.comp(left, right) < 0 ? leftIndex : rightIndex; } const toSift = this.heap[pos]; if (this.comp(toSift, toSwap) > 0) { // The thing being sifted is smaller than its smallest neighbour this.swap(pos, swapIndex); this.siftDown(swapIndex); } } getParent(pos) { return Math.floor((pos - 1) / 2); } getRight(pos) { return 2 * pos + 2; } getLeft(pos) { return 2 * pos + 1; } isLeaf(pos) { if (this.isInvalid(pos)) { const err = new Error('Invalid heap position. ' + pos); throw err; } return pos >= Math.floor(this.heap.length / 2) && pos < this.heap.length; } swap(pos1, pos2) { if (this.isInvalid(pos1) || this.isInvalid(pos2)) { throw new Error('Invalid heap position.'); } const temp = this.heap[pos1]; this.heap[pos1] = this.heap[pos2]; this.heap[pos2] = temp; } isInvalid(pos) { return pos < 0 || pos >= this.heap.length; } toString() { let string = '' for (const p of this.heap) { string = string + `(${p.x},${p.y}) `; } return string; } }36:T6fa,function pathLine(point, cellSize) { const {x, y} = point; const previous = point.previous; const next = point.next; const bottomBorder = { x: (x * cellSize) + (cellSize / 2), y: (y * cellSize) + cellSize }; const topBorder = { x: (x * cellSize) + (cellSize / 2), y: y * cellSize }; const leftBorder = { x: x * cellSize, y: (y * cellSize) + (cellSize / 2) }; const rightBorder = { x: (x * cellSize) + cellSize, y: (y * cellSize) + (cellSize / 2) }; const centre = { x: (x * cellSize) + (cellSize / 2), y: (y * cellSize) + (cellSize / 2) }; const topRight = { x: (x * cellSize) + cellSize, y: (y * cellSize) }; const topLeft = { x: (x * cellSize), y: (y * cellSize) }; const bottomRight = { x: (x * cellSize) + cellSize, y: (y * cellSize) + cellSize }; const bottomLeft = { x: (x * cellSize), y: (y * cellSize) + cellSize }; function getBorderPoint(refPoint) { if (!refPoint) return centre; const dx = refPoint.x - x; const dy = refPoint.y - y; const key = `${dx},${dy}`; const borderMap = { '0,1': bottomBorder, '0,-1': topBorder, '-1,0': leftBorder, '1,0': rightBorder, '1,-1': topRight, '1,1': bottomRight, '-1,-1': topLeft, '-1,1': bottomLeft }; const result = borderMap[key]; if (!result) { throw new Error(`Point (${refPoint.x}, ${refPoint.y}) is not adjacent to (${x}, ${y})`); } return result; } function getHalfPath(usePrevious) { const refPoint = usePrevious ? previous : next; if (!usePrevious && !refPoint) { const goal = searchPoints.flat().find(d => d.type === 'GOAL'); return getBorderPoint(goal); } return getBorderPoint(refPoint); } return { start: getHalfPath(true), end: getHalfPath(false) } }37:[] 31:{"id":"9995f3efa6342e27","slug":"search-algorithm-animations","title":"Search algorithm animations","thumbnail":"855adf06a59cbca1a81a35a2beda10c5bde4b63c8ea7430c07fa413a3870a123","access_level":"public","create_time":"$D2023-12-05T04:27:11.642Z","update_time":"$D2026-02-26T17:23:47.417Z","view_time":null,"first_public_time":"$D2023-12-05T04:27:11.642Z","has_unpublished_edits":null,"fork":false,"stars":0,"starred":false,"owner":{"type":"team","id":"1d83bfce92a9c574","login":"ayaankazerouni","name":"Ayaan Kazerouni","avatar_url":"https://avatars-next.observableusercontent.com/0e57571babb328d16b661fb3c0f94c9629fc275ae03e484ce19dbcf72fa1be0d","tier":"starter_2024"},"version":1936,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"7a2aaf0dcd8f4999","login":"ayaankazerouni","name":"Ayaan Kazerouni","avatar_url":"https://avatars-next.observableusercontent.com/d56bdf990c9be43beacbf55c7ca358b0aa7c36eb9211e9fc23f3b50bc80603bd","tier":null}],"members":[{"type":"individual","id":"7a2aaf0dcd8f4999","login":"ayaankazerouni","name":"Ayaan Kazerouni","avatar_url":"https://avatars-next.observableusercontent.com/d56bdf990c9be43beacbf55c7ca358b0aa7c36eb9211e9fc23f3b50bc80603bd","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"title":"Search algorithm animations","cells":[{"id":0,"value":"# Search algorithm animations \n\nThis notebook is inspired by [pathfinding.js](https://qiao.github.io/PathFinding.js/visual/), which I have often used while teaching. I wanted a version where I can control the animation speed or even step through algorithms manually during explanations—hence this notebook.\n\n(I am also avoiding grading.)","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":788,"value":"viewof searchType = {\n const input = Inputs.radio(new Map([['Breadth-first', 'BFS'], ['Depth-first', 'DFS'], ['A-Star', 'AStar']]),\n {label: 'Search type', value: 'BFS'});\n return input ;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1364,"value":"viewof heuristic = {\n const manhattan = (a, b) => Math.abs(a.x - b.x) + Math.abs(a.y - b.y);\n const euclidean = (a, b) => Math.sqrt(Math.pow(a.x - b.x, 2) + Math.pow(a.y - b.y, 2));\n const input = Inputs.radio(new Map([\n ['Manhattan distance', manhattan],\n ['Euclidean distance', euclidean]\n ]), { label: 'Distance heuristic (A* only)', value: manhattan, disabled: searchType !== 'AStar'});\n\n return input;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1377,"value":"viewof diagonals = Inputs.toggle({ label: 'Allow diagonal neighbours?', value: false })","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":784,"value":"viewof rowsCols = Inputs.range([2, 20], { step: 1, label: 'Grid size', value: 15 } )","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":896,"value":"viewof speed = Inputs.range([0.00, 1], { step: 0.01, label: 'Speed', format: x => x.toFixed(2), value: 1 })","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":978,"value":"viewof gridControls = Inputs.button([\n ['Reset grid', () => mutable points = resetPoints(points)],\n ['Shuffle grid', () => mutable points = generatePoints()],\n ['Toggle search', (v) => {\n return !v;\n }]\n], { label: 'Controls', value: false });","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":826,"value":"instructions = md`_Drag the start square (green) and goal square (red) to try out different scenarios. **Click and drag** to set obstacles (grey). **Click** on obstacles to unset. As the search runs, yellow squares are included in the frontier (to-do list), blue squares are marked as visited. If a path is found, it will appear as a yellow line._`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":6,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":854,"value":"---\n\n### Code for the search","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":654,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":712,"value":"function adjacent(a, b) {\n return heuristic(a, b) === 1;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":535,"value":"function withinBounds({ x, y }) {\n return x >= 0 && x < rowsCols && y >= 0 && y < rowsCols;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":514,"value":"function neighbours({ x, y }, diagonals=false) {\n if (!diagonals) {\n return [\n {x, y: y - 1}, // top\n {x: x + 1, y}, // right\n {x, y: y + 1}, // bottom\n {x: x - 1, y}, // left\n ];\n } else {\n return [\n {x, y: y - 1}, // top\n {x: x + 1, y: y - 1}, // top right\n {x: x + 1, y}, // right\n {x: x + 1, y: y + 1}, // bottom right\n {x, y: y + 1}, // bottom\n {x: x - 1, y: y + 1}, // bottom left\n {x: x - 1, y}, // left\n {x: x - 1, y: y - 1}, // top left\n ]\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":913,"value":"timeScale = d3.scaleLinear([0.001, 1], [1000, 0])","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1624,"value":"class Queue {\n constructor() {\n this.queue = []\n }\n\n get length() {\n return this.queue.length;\n }\n\n includes(item) {\n return this.queue.includes(item)\n }\n\n remove() {\n return this.queue.shift();\n }\n\n push(item) {\n this.queue.push(item)\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1630,"value":"class Stack extends Queue {\n remove() {\n return this.queue.pop();\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1351,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1822,"value":"tieBreakStrategy = 'greedy'; // insertionOrder, greedy, or none","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":857,"value":"---\n\n### Code for the grid","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":196,"value":"cellColor = ({\n START: 'lightgreen',\n GOAL: 'red',\n OBSTACLE: 'grey',\n VISITED: 'lightblue',\n PATH: 'lightblue',\n QUEUED: 'yellow'\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1889,"value":"$36","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":866,"value":"#### Generate the points for the grid","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":25,"value":"mutable points = generatePoints();","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":479,"value":"function generatePoints() {\n const points = [];\n for (let i = 0; i < rowsCols; i++) {\n const row = [];\n for (let j = 0; j < rowsCols; j++) {\n row.push({x: j, y: i, type: 'UNVISITED', previous: null, g: Infinity, h: Infinity});\n }\n points.push(row);\n }\n\n points[randomIndex()][randomIndex()].type = 'START';\n points[randomIndex()][randomIndex()].type = 'GOAL';\n\n return points;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1020,"value":"function resetPoints(points) {\n const reset = points.slice();\n reset.flat()\n .filter(p => !['START', 'GOAL', 'OBSTACLE'].includes(p.type))\n .forEach(p => {\n p.type = 'UNVISITED';\n p.previous = null\n });\n\n return reset;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":507,"value":"function randomIndex() {\n return Math.floor(Math.random() * rowsCols);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1591,"value":"","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"}],"files":"$W37","stdlib":"1","titling":"auto"}} 32:"$31:body"