3f:null 40:["$","title",null,{"children":"A* Search Algorithm | Ross Mills | Observable"}] 46:T51f,{ let pathPositions = path.map(item => item.pos) function isInPath(x, y) { return pathPositions.find(item => item.x == x && item.y == y); } function leftPad(num) { return ('0' + num).slice(-2); } function getHslColor(cost) { const h = 135 + cost; const s = 50 + (Math.min(100, cost * cost/2)) + '%'; const l = 50 - (Math.min(100, cost * cost/4)) + '%'; return `hsl(${h}, ${s}, ${l})`; } let container = html`

`; for (let i = 0; i < grid.length; i++) { let rowContainer = html`

`; for (let j = 0; j < grid[i].length; j++) { const node = grid[i][j]; let itemContainer = html`

${showCosts ? leftPad(node.data.cost): ' '}

`; if (start[0] == i && start[1] == j) { itemContainer.classList.add('start'); } if (end[0] == i && end[1] == j) { itemContainer.classList.add('end'); } if (isInPath(i, j)) { itemContainer.classList.add('path'); itemContainer.innerText = '*'; } itemContainer.style['background-color'] = getHslColor(node.data.cost); itemContainer.classList.add(node.data.category); rowContainer.appendChild(itemContainer); } container.appendChild(rowContainer); } return container; }47:Td24,// Adapted from https://briangrinstead.com/blog/astar-search-algorithm-in-javascript/ class AStar { costFunction (node) { return node.data.cost; } isBlockedNode (node) { return node.data.cost > 10; } heuristic (pos0, pos1) { // This is the Manhattan distance const d1 = Math.abs(pos1.x - pos0.x); const d2 = Math.abs(pos1.y - pos0.y); return d1 + d2; } search (grid, start, end) { const openList = [start]; const closedList = []; while (openList.length > 0) { // Grab the lowest f(x) to process next var lowInd = 0; for (let i = 0; i < openList.length; i++) { if (openList[i].f < openList[lowInd].f) { lowInd = i; } } let currentNode = openList[lowInd]; // End case -- result has been found, return the traced path if (currentNode.pos == end.pos) { let curr = currentNode; let ret = []; while (curr.parent) { ret.push(curr); curr = curr.parent; } return ret.reverse(); } // Normal case -- move currentNode from open to closed, process each of its neighbors openList.splice(openList.indexOf(currentNode), 1); closedList.push(currentNode); const neighbors = this.neighbors(grid, currentNode); for (let i = 0; i < neighbors.length; i++) { let neighbor = neighbors[i]; if (closedList.indexOf(neighbor) !== -1 || this.isBlockedNode(neighbor)) { // not a valid node to process, skip to next neighbor continue; } // g score is the shortest distance from start to current node, we need to check if // the path we have arrived at this neighbor is the shortest one we have seen yet const gScore = currentNode.g + this.costFunction(neighbor); // neighbor cost let gScoreIsBest = false; if (openList.indexOf(neighbor) === -1) { // This the the first time we have arrived at this node, it must be the best // Also, we need to take the h (heuristic) score since we haven't done so yet gScoreIsBest = true; neighbor.h = this.heuristic(neighbor.pos, end.pos); openList.push(neighbor); } else if (gScore < neighbor.g) { // We have already seen the node, but last time it had a worse g (distance from start) gScoreIsBest = true; } if (gScoreIsBest) { // Found an optimal (so far) path to this node. Store info on how we got here and // just how good it really is... neighbor.parent = currentNode; neighbor.g = gScore; neighbor.f = neighbor.g + neighbor.h; neighbor.debug = "F: " + neighbor.f + ", G: " + neighbor.g + ", H: " + neighbor.h; } } } // No result was found -- empty array signifies failure to find path return []; } neighbors (grid, node) { const ret = []; const x = node.pos.x; const y = node.pos.y; if (grid[x-1] && grid[x-1][y]) { ret.push(grid[x-1][y]); } if (grid[x+1] && grid[x+1][y]) { ret.push(grid[x+1][y]); } if (grid[x][y-1] && grid[x][y-1]) { ret.push(grid[x][y-1]); } if (grid[x][y+1] && grid[x][y+1]) { ret.push(grid[x][y+1]); } return ret; } }48:[] 44:{"id":"ddc17522c27ce80f","slug":"a-search-algorithm","title":"A* Search Algorithm","thumbnail":"569aa5b3efefe4f0f2be3c19e72e47b3fefeaf812f589a3e904dd852bdc9a852","access_level":"public","create_time":"$D2020-05-15T19:32:29.344Z","update_time":"$D2021-01-26T23:52:07.135Z","view_time":null,"first_public_time":"$D2021-01-26T23:52:37.442Z","has_unpublished_edits":null,"fork":false,"stars":2,"starred":false,"owner":{"type":"team","id":"55e9268ccca383a5","login":"rossmills99","name":"Ross Mills","avatar_url":"https://avatars-next.observableusercontent.com/edf6d8f13cc81ae6ed5c2a7f7911f9b522006a0413d822217f3666daf05d1366","tier":"starter_2024","bio":"Software engineer and hands-on tech leader. Creating and collaborating on interesting software projects gets me out of bed in the morning.","following":false},"version":452,"publish_version":452,"role":null,"authored":false,"authors":[{"type":"individual","id":"3d55deecec17df75","login":"rossmills99","name":"Ross Mills","avatar_url":"https://avatars-next.observableusercontent.com/edf6d8f13cc81ae6ed5c2a7f7911f9b522006a0413d822217f3666daf05d1366","tier":null,"bio":"Software engineer and hands-on tech leader.\n","following":false}],"members":[{"type":"individual","id":"3d55deecec17df75","login":"rossmills99","name":"Ross Mills","avatar_url":"https://avatars-next.observableusercontent.com/edf6d8f13cc81ae6ed5c2a7f7911f9b522006a0413d822217f3666daf05d1366","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"titling":"auto","title":"A* Search Algorithm","cells":[{"id":0,"value":"md`# A* Search Algorithm`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":406,"value":"md`The tile grid below represents a jungle where the difficulty to cross each tile is represented by a number, \\`cost\\`. The tiles are darker where the \\`cost\\` is higher and some tiles are impassable (where \\`cost\\ > 10\\`). The A* Search algorithm can be used to find the easiest crossing from one point in the grid to another.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":418,"value":"md`### \\# columns`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":353,"value":"viewof y1 = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":421,"value":"md`#### \\# rows`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":350,"value":"viewof x1 = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":425,"value":"md`#### Show cost on map`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":322,"value":"viewof showCosts = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":428,"value":"md`## Map`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":131,"value":"$46","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":411,"value":"md`${x1 * y1} tiles`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":433,"value":"md`## Points to search for path from/to`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":160,"value":"start = ([0, 0])","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":164,"value":"end = [x1-1, y1-1]","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":81,"value":"path = {\n const astar = new AStar();\n return astar.search(grid, grid[start[0]][start[1]], grid[end[0]][end[1]]);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":187,"value":"pathPositions = path.map(item => item.pos);","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":35,"value":"grid = {\n const grid = [];\n for(let x = 0; x < x1; x++) {\n grid[x] = [];\n for(let y = 0; y < y1; y++) {\n grid[x][y] = { f: 0, g: 0, h: 0, debug: '', parent: null, pos: { x, y } };\n const randomArea = parsedAreaTypes[Math.floor(Math.random() * parsedAreaTypes.length)];\n const areaType = randomArea;\n grid[x][y].data = areaType;\n } \n }\n return grid;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":107,"value":"function clone(item) {\n return JSON.parse(JSON.stringify(item));\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":440,"value":"md`## A* Search Algorithm`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":42,"value":"$47","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":437,"value":"md`## Map Data`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":31,"value":"parsedAreaTypes = parseAreaTypes(areaTypes)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":26,"value":"function parseAreaTypes(areaTypes) {\n const fieldKeys = ['category', 'type', 'cost'];\n const lines = areaTypes.trim().split('\\n');\n return lines.map( line => {\n const fields = line.trim().split(',');\n return {\n category: fields[0].trim(),\n type: fields[1].trim(),\n cost: parseInt(fields[2].trim())\n };\n })\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2,"value":"areaTypes = `\nJungle,Overgrown,10\nJungle,Path,5\nJungle,Clearing,2\nVillage,Shop,3\nVillage,WaterPump,5\nVillage,House,3\nFarm,House,5\nFarm,Shed,6\nFarm,Barn,4\nOpen,Road,1\nHill,UnpassableCliffs,11\nHill,Path,8\nRiver,Crossable,10\nRiver,Uncrossable,11\nCapital,Street,1\nCapital,GovernersMansion,7\n`\n","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":136,"value":"html`\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W48","stdlib":"1"}} 45:"$44:body"