27:null 28:["$","title",null,{"children":"Pathfinding | Nifley | Observable"}] 2d:Tf23,rendering = { const svg = d3.select(DOM.svg()).attr("viewBox", [0, 0, width, dispWidth]); let tgt = map.start; let origin = map.start; // Viridis colored cells svg.selectAll('.row') .data(map) .enter() .append('g').attr('transform', (_, i) => `translate(0, ${i * cellSize})`) .selectAll('.cell').data((_, i) => map[i]).enter() .append('rect') .attr("width", cellSize) .attr('height', cellSize) .attr('x', (_, i) => i * cellSize) .attr('stroke', 'white') .attr('stroke-width', '2px') .attr('fill', d => color(d)) .attr('rx', "5px") .on('click', function(e, d) { if (e.target.nodeName != 'rect') return; let y = Math.round(e.target.getAttribute('x') / cellSize); let x = Math.round(e.target.parentNode.getAttribute('transform').slice(13, -1) / cellSize); tgt = [ x, y ]; recalcPaths(); }).on('contextmenu', function(e, d) { if (e.target.nodeName != 'rect') return; let y = Math.round(e.target.getAttribute('x') / cellSize); let x = Math.round(e.target.parentNode.getAttribute('transform').slice(13, -1) / cellSize); if (map[x][y] != "#") { origin = [x, y] recalcPaths(); e.preventDefault(); return false; } }); // Text labels for grid cells svg.selectAll('.row') .data(map) .enter() .append('g').attr('transform', (_, i) => `translate(0, ${(i+0.5) * cellSize})`) .selectAll('.cell').data((_, i) => map[i]).enter() .append('text') .attr('x', (_, i) => (i+0.5) * cellSize) .attr('class', 'label') .attr('text-anchor', 'middle') .attr('dominant-baseline', 'middle') .style('pointer-events', 'none') .attr('fill', d => (d > 20) ? "#D0D0D0" : "#202020") .text(d => d) svg.selectAll('.label').style('font-family', 'ui-monospace').style('font-size', `${200/map.height}px`); // Paths let path = dijkstra(origin, tgt, map); svg.append("path") .attr('id', 'dijkstra') .attr('d', d3.line()(path.map(p => [(p[1] + 0.5) * cellSize, (p[0] + 0.5) * cellSize]))) .attr('fill', 'none') .style('stroke-linejoin', 'round') .style('stroke-linecap', 'round') .attr('stroke', 'red') .attr('stroke-width', '5px') .style('pointer-events', 'none') path = Astar(origin, tgt, map); svg.append("path") .attr('id', 'Astar') .attr('d', d3.line()(path.map(p => [(p[1] + 0.5) * cellSize, (p[0] + 0.5) * cellSize]))) .attr('fill', 'none') .style('stroke-linejoin', 'round') .style('stroke-linecap', 'round') .attr('stroke', 'green') .attr('stroke-width', '5px') .style('pointer-events', 'none') svg.append("path") .attr('d', d3.line()(totalPath.map(p => [(p[1] + 0.5) * cellSize, (p[0] + 0.5) * cellSize]))) .attr('fill', 'none') .style('stroke-linejoin', 'round') .style('stroke-linecap', 'round') .attr('stroke', 'orange') .attr('stroke-width', '5px') .style('pointer-events', 'none') svg.append("path") .attr('d', d3.line()(optimizedTreasures.map(p => [(p[1] + 0.5) * cellSize, (p[0] + 0.5) * cellSize]))) .attr('fill', 'none') .style('stroke-linejoin', 'round') .style('stroke-linecap', 'round') .attr('stroke', 'blue') .attr('stroke-width', '3px') .style('pointer-events', 'none') .style("stroke-dasharray","5,10"); function recalcPaths() { // target = [x,y]; path = dijkstra(origin, tgt, map); svg.select('#dijkstra') .attr('d', d3.line()( path.map(p => [(p[1] + 0.5) * cellSize, (p[0] + 0.5) * cellSize])) ); path = Astar(origin, tgt, map); svg.select('#Astar') .attr('d', d3.line()( path.map(p => [(p[1] + 0.5) * cellSize, (p[0] + 0.5) * cellSize])) ); } return svg.node(); }2e:T5c1,function Astar(src, dest, grid) { const Q = new BHeap(({cost}) => cost); const dist = new Map(); const estimatedCost = new Map(); const prev = new Map(); const visited = new Map(); for (let rowi = 0; rowi < grid.length; ++rowi) { for (let celli = 0; celli < grid[rowi].length; ++celli) { dist.set([rowi, celli].toString(), cmpv([rowi, celli], src) ? 0 : Infinity); estimatedCost.set([rowi, celli].toString(), manhattanDistance([rowi, celli], dest)); prev.set([rowi, celli].toString(), undefined); } } Q.push({c: src, cost: 0}); let u; while (Q.size()) { u = Q.pop().c; if (cmpv(u, dest)) break; if (visited.has(u.toString())) continue; visited.set(u.toString(), true); for (let no of nbrs) { let v = [no[0] + u[0], no[1] + u[1]] if ( v[0] >= grid.length || v[1] >= grid[0].length || v[0] < 0 || v[1] < 0) continue; const alt = dist.get(u.toString()) + values[grid[v[0]][v[1]]]; if (alt < dist.get(v.toString())) { dist.set(v.toString(), alt); estimatedCost.set(v.toString(), alt + manhattanDistance(v, dest)); prev.set(v.toString(), u); Q.push({c: v, cost: estimatedCost.get(v.toString())}); } } } let path = [dest]; while (prev.get(path[path.length - 1].toString()) != undefined) path.push(prev.get(path[path.length - 1].toString())) path.reverse() return path; }2f:T509,function dijkstra(src, dest, grid) { const Q = new BHeap(({dist}) => dist); const dist = new Map(); const prev = new Map(); const visited = new Map(); for (let rowi = 0; rowi < grid.length; ++rowi) { for (let celli = 0; celli < grid[rowi].length; ++celli) { dist.set([rowi, celli].toString(), cmpv([rowi, celli], src) ? 0 : Infinity); prev.set([rowi, celli].toString(), undefined); Q.push({c: [rowi, celli], dist: cmpv([rowi, celli], src) ? 0 : Infinity}); } } let u; while (Q.size()) { u = Q.pop().c; if (cmpv(u, dest)) break; if (visited.has(u.toString())) continue; visited.set(u.toString(), true); for (let no of nbrs) { let v = [no[0] + u[0], no[1] + u[1]] if ( v[0] >= grid.length || v[1] >= grid[0].length || v[0] < 0 || v[1] < 0) continue; const alt = dist.get(u.toString()) + values[grid[v[0]][v[1]]]; if (alt < dist.get(v.toString())) { dist.set(v.toString(), alt); prev.set(v.toString(), u); Q.push({c: v, dist: alt}); } } } let path = [u]; while (prev.get(path[path.length - 1].toString()) != undefined) path.push(prev.get(path[path.length - 1].toString())) path.reverse() return path; }30:T665,mapCSVs = { let files = [ FileAttachment("Level_0_0.csv"), FileAttachment("Level_0_1.csv"), FileAttachment("Level_0_2.csv"), FileAttachment("Level_0_3.csv"), FileAttachment("Level_0_4.csv"), FileAttachment("Level_1_0.csv"), FileAttachment("Level_1_1.csv"), FileAttachment("Level_1_2.csv"), FileAttachment("Level_2_0.csv"), FileAttachment("Level_2_1.csv"), FileAttachment("Level_2_2.csv"), FileAttachment("Level_2_3.csv"), FileAttachment("Level_3_0.csv"), FileAttachment("Level_3_1.csv"), FileAttachment("Level_3_2.csv"), FileAttachment("Level_3_3.csv"), FileAttachment("Level_3_4.csv"), FileAttachment("Level_3_5.csv"), FileAttachment("Level_3_6.csv"), FileAttachment("Level_3_7.csv"), FileAttachment("Level_3_8.csv"), FileAttachment("Level_3_9.csv"), FileAttachment("Level_4_0.csv"), FileAttachment("Level_4_1.csv"), FileAttachment("Level_4_2.csv"), FileAttachment("Level_5_0.csv"), FileAttachment("Level_5_1.csv"), FileAttachment("Level_5_2.csv"), FileAttachment("Level_5_3.csv"), FileAttachment("Level_6_0.csv"), FileAttachment("Level_6_1.csv"), FileAttachment("Level_6_2.csv"), FileAttachment("Level_6_3.csv"), FileAttachment("Level_6_4.csv"), FileAttachment("Level_6_5.csv"), FileAttachment("Level_6_6.csv"), FileAttachment("Level_7_0.csv"), FileAttachment("Level_7_1.csv"), FileAttachment("Level_7_2.csv"), FileAttachment("Level_8_0.csv"), FileAttachment("Level_8_1.csv") ] return Promise.all(files.map(f => f.text())) }31:[{"id":"603e676f8b2fc689f130316bbc3dfc8f36b3839e265456288cea7506396f70f9f10bdb3825704e7826da7bcda53ee6b24c0c08a79c59d37fa8246195fe1eccf9","href":"https://static.observableusercontent.com/files/603e676f8b2fc689f130316bbc3dfc8f36b3839e265456288cea7506396f70f9f10bdb3825704e7826da7bcda53ee6b24c0c08a79c59d37fa8246195fe1eccf9","name":"Level_5_2.csv","type":"text/csv","lastModified":1652891644627,"size":291},{"id":"bd6152ed766b8484c1fc2c8e254f0d284e151ee23ceba0aa63f71d8361163b8657c1df7608efec85269f4d822250cd41b78b16cae1dfe7888b708b0cce5288d3","href":"https://static.observableusercontent.com/files/bd6152ed766b8484c1fc2c8e254f0d284e151ee23ceba0aa63f71d8361163b8657c1df7608efec85269f4d822250cd41b78b16cae1dfe7888b708b0cce5288d3","name":"Level_8_0.csv","type":"text/csv","lastModified":1652891646610.054,"size":291},{"id":"3206d04fdc2e80e7127942a98d36b3e2a958a2c01955f77d4711987061407cd83b0366b0d3bf0e8f566349913551a6a9ca427d37d7692cc44c4c44ef7ce51905","href":"https://static.observableusercontent.com/files/3206d04fdc2e80e7127942a98d36b3e2a958a2c01955f77d4711987061407cd83b0366b0d3bf0e8f566349913551a6a9ca427d37d7692cc44c4c44ef7ce51905","name":"Level_8_1.csv","type":"text/csv","lastModified":1652891647989.051,"size":291},{"id":"160caaa64b86c2e3c92af28e606b9a448ba6f4fcfb34dcef67532d1bc8672dc97b9b5240f0e3a8588d5eeb57d8c74537f7691c68421d0cd61be04d6542e38cd1","href":"https://static.observableusercontent.com/files/160caaa64b86c2e3c92af28e606b9a448ba6f4fcfb34dcef67532d1bc8672dc97b9b5240f0e3a8588d5eeb57d8c74537f7691c68421d0cd61be04d6542e38cd1","name":"Level_6_0.csv","type":"text/csv","lastModified":1652891644810.228,"size":5104},{"id":"a6f905752fc94217fffa11e08cc7d47344e2859a31d1303b5eee37fd76595f97254c002a49f26ab38e1796bcdc8506319606c9f186c4257c82ca0afe2599e668","href":"https://static.observableusercontent.com/files/a6f905752fc94217fffa11e08cc7d47344e2859a31d1303b5eee37fd76595f97254c002a49f26ab38e1796bcdc8506319606c9f186c4257c82ca0afe2599e668","name":"Level_5_3.csv","type":"text/csv","lastModified":1652891644831.142,"size":291},{"id":"8a1beb65d0c56f6f4b4b47fee5329a6237de04fc2bac41d7c322988a040d6d91fac12f24c598b12b20f12f07f595777d4f149144c51effe6014b87eb0456e978","href":"https://static.observableusercontent.com/files/8a1beb65d0c56f6f4b4b47fee5329a6237de04fc2bac41d7c322988a040d6d91fac12f24c598b12b20f12f07f595777d4f149144c51effe6014b87eb0456e978","name":"Level_2_3.csv","type":"text/csv","lastModified":1652891642202.681,"size":64},{"id":"f440fb0dc32b53333d10c8548456c2a1a22a3f0619f63376b9cfafc3991723d9025a9d6b82c3ab4aa16429d673ed98b4c24e2c452b408730a1e5cf090212e2b7","href":"https://static.observableusercontent.com/files/f440fb0dc32b53333d10c8548456c2a1a22a3f0619f63376b9cfafc3991723d9025a9d6b82c3ab4aa16429d673ed98b4c24e2c452b408730a1e5cf090212e2b7","name":"Level_1_2.csv","type":"text/csv","lastModified":1652891642003.661,"size":1143},{"id":"c0fc5c902c1fb0899fad085fef5ca17afd59640fbc0ca67a2bfcca913801bb37876f9393e35bd47785f9c0ce4d8ff6b7e50346916622c32d0fe6d0ad099d1402","href":"https://static.observableusercontent.com/files/c0fc5c902c1fb0899fad085fef5ca17afd59640fbc0ca67a2bfcca913801bb37876f9393e35bd47785f9c0ce4d8ff6b7e50346916622c32d0fe6d0ad099d1402","name":"Level_6_4.csv","type":"text/csv","lastModified":1652891647416.512,"size":614},{"id":"6e21eec4e6ee49322135af661bdb8ba137c0deea517ecf16889ee938c0fcb9339387593bf59f9c180fe514fd53be81161dcf036cfc9b7acad3e194e78494cbc1","href":"https://static.observableusercontent.com/files/6e21eec4e6ee49322135af661bdb8ba137c0deea517ecf16889ee938c0fcb9339387593bf59f9c180fe514fd53be81161dcf036cfc9b7acad3e194e78494cbc1","name":"Level_7_2.csv","type":"text/csv","lastModified":1652891646620.39,"size":360},{"id":"ccd1793f2627eff1fdf14ba885bfb66066cdc0c76264a5544bb9d9910d9c47d4e562a953d3b00d5ca0a023996379e01233ec127413fa5692a9c9054f219ded9f","href":"https://static.observableusercontent.com/files/ccd1793f2627eff1fdf14ba885bfb66066cdc0c76264a5544bb9d9910d9c47d4e562a953d3b00d5ca0a023996379e01233ec127413fa5692a9c9054f219ded9f","name":"Level_7_0.csv","type":"text/csv","lastModified":1652891646152.185,"size":291},{"id":"41b70d87a1f4c605a4f3a9c483e80824040f058d85ce0fd37f84a463176eea3d2b48f2cc2b8ebed4cc01231a4f3cfe38cfa0a7ecb3d8f7b050f38500fdb0c7b2","href":"https://static.observableusercontent.com/files/41b70d87a1f4c605a4f3a9c483e80824040f058d85ce0fd37f84a463176eea3d2b48f2cc2b8ebed4cc01231a4f3cfe38cfa0a7ecb3d8f7b050f38500fdb0c7b2","name":"Level_7_1.csv","type":"text/csv","lastModified":1652891646211.39,"size":291},{"id":"2994bd3ae45e2fa80552e9671a7107e30e661612b644ab52ec0a21188abda44c56563aec9bc7b54dfec493ab83214444f819ec15777a6607ad314145b434ee21","href":"https://static.observableusercontent.com/files/2994bd3ae45e2fa80552e9671a7107e30e661612b644ab52ec0a21188abda44c56563aec9bc7b54dfec493ab83214444f819ec15777a6607ad314145b434ee21","name":"Level_6_5.csv","type":"text/csv","lastModified":1652891645843.468,"size":614},{"id":"33afbe70b28e03ace37d1be899446aa1b34ffb8122047e373dbff3cfb5250ea4d750cece3719c39a18f5f143e9b02970cae126c2f7ba18204463b6146d40002b","href":"https://static.observableusercontent.com/files/33afbe70b28e03ace37d1be899446aa1b34ffb8122047e373dbff3cfb5250ea4d750cece3719c39a18f5f143e9b02970cae126c2f7ba18204463b6146d40002b","name":"Level_6_6.csv","type":"text/csv","lastModified":1652891645680.07,"size":1437},{"id":"c5e4b16ffc083a124161d247eb66d3609ebfe5c67360e4b15c8381c8e4471aa28d44acb1f269ac7a521d000ec2b9b8c6e8c10aafc3da5799a65823d22a2bc4aa","href":"https://static.observableusercontent.com/files/c5e4b16ffc083a124161d247eb66d3609ebfe5c67360e4b15c8381c8e4471aa28d44acb1f269ac7a521d000ec2b9b8c6e8c10aafc3da5799a65823d22a2bc4aa","name":"Level_6_3.csv","type":"text/csv","lastModified":1652891645478.7,"size":799},{"id":"8fd3bb98b682c0e821b435a9ed0c9a1664f8660d2fd74eb148c8ef9f46bb736dea5ff088d4bb1c2d6ca14b337f27f35f8d0ae3547e8e076892c202e2ec3f516f","href":"https://static.observableusercontent.com/files/8fd3bb98b682c0e821b435a9ed0c9a1664f8660d2fd74eb148c8ef9f46bb736dea5ff088d4bb1c2d6ca14b337f27f35f8d0ae3547e8e076892c202e2ec3f516f","name":"Level_6_2.csv","type":"text/csv","lastModified":1652891645201.081,"size":1437},{"id":"d3e9b9cb7f9944bd1d4fb25fa815381e09be5eb9af665e70ca288011f4610f141cb8797fb1083fe0a133c60983fa629eec72109012119290d72ee0ba9052d042","href":"https://static.observableusercontent.com/files/d3e9b9cb7f9944bd1d4fb25fa815381e09be5eb9af665e70ca288011f4610f141cb8797fb1083fe0a133c60983fa629eec72109012119290d72ee0ba9052d042","name":"Level_6_1.csv","type":"text/csv","lastModified":1652891645068.991,"size":5104},{"id":"84c528560d6dba29e7e08811d15f4891c705e90f40246a4bfcf7f3972c5d3885a2e9a4ef9e8a66e4916448fb9315f930c1e3dfd5e26d387b6f3f5ac2c9728b80","href":"https://static.observableusercontent.com/files/84c528560d6dba29e7e08811d15f4891c705e90f40246a4bfcf7f3972c5d3885a2e9a4ef9e8a66e4916448fb9315f930c1e3dfd5e26d387b6f3f5ac2c9728b80","name":"Level_5_1.csv","type":"text/csv","lastModified":1652891644425.214,"size":291},{"id":"10612d3ff14ff2797d044053cd467ef75b787cc9365b5dd0db1056af14a21b76b104b86f67ac30e9eeaa7494b38d6fbdef8ea6b64209a541ca0c4a9d290141fe","href":"https://static.observableusercontent.com/files/10612d3ff14ff2797d044053cd467ef75b787cc9365b5dd0db1056af14a21b76b104b86f67ac30e9eeaa7494b38d6fbdef8ea6b64209a541ca0c4a9d290141fe","name":"Level_5_0.csv","type":"text/csv","lastModified":1652891644332.373,"size":291},{"id":"612bb3b2980646b3661ea3c5d231889a2c6826ad1f0b3b971985fee8c27da2750962b1ca1644ce2564f27c4c533fa6b1bc818ec4aff1bce6afe7b40f2919b993","href":"https://static.observableusercontent.com/files/612bb3b2980646b3661ea3c5d231889a2c6826ad1f0b3b971985fee8c27da2750962b1ca1644ce2564f27c4c533fa6b1bc818ec4aff1bce6afe7b40f2919b993","name":"Level_4_2.csv","type":"text/csv","lastModified":1652891644169.877,"size":1143},{"id":"35c7ea2b658add7972fa61e139c2fa6b47bf200118c3a15b7c7796f1f1136d0895a3e7498bda37e9cc3a00f125d39729579d0ffa5f1bfcec28c3d8226ba34ec8","href":"https://static.observableusercontent.com/files/35c7ea2b658add7972fa61e139c2fa6b47bf200118c3a15b7c7796f1f1136d0895a3e7498bda37e9cc3a00f125d39729579d0ffa5f1bfcec28c3d8226ba34ec8","name":"Level_4_0.csv","type":"text/csv","lastModified":1652891643994.729,"size":291},{"id":"31811d8344b423e5d356bdb8b2bd3ccd8e4f3b0e0bab0d1ed5bda11dbfaf0e65951c7376f55090cc4e49e1aacbb0695ed86757ba5a3e72f3fb9caa914d94d81e","href":"https://static.observableusercontent.com/files/31811d8344b423e5d356bdb8b2bd3ccd8e4f3b0e0bab0d1ed5bda11dbfaf0e65951c7376f55090cc4e49e1aacbb0695ed86757ba5a3e72f3fb9caa914d94d81e","name":"Level_4_1.csv","type":"text/csv","lastModified":1652891643910.374,"size":291},{"id":"3b7c31f0ed3becaa551625c3b022f735f01471f0cb44d18aeb21b93965fbfd55d7dfcedf59dad13b563cb2c3abe5f678fcf848ce971361074ae5e1754a3bbb6a","href":"https://static.observableusercontent.com/files/3b7c31f0ed3becaa551625c3b022f735f01471f0cb44d18aeb21b93965fbfd55d7dfcedf59dad13b563cb2c3abe5f678fcf848ce971361074ae5e1754a3bbb6a","name":"Level_3_8.csv","type":"text/csv","lastModified":1652891643674.592,"size":484},{"id":"343465f168a4a0411be4a5b723879622d459efdd9083f377a21e03c81461bf10072cee5514992c3a8ec551aa3d1b8d2159b76658ca8bd34523ae6ad33cf8e95a","href":"https://static.observableusercontent.com/files/343465f168a4a0411be4a5b723879622d459efdd9083f377a21e03c81461bf10072cee5514992c3a8ec551aa3d1b8d2159b76658ca8bd34523ae6ad33cf8e95a","name":"Level_3_9.csv","type":"text/csv","lastModified":1652891643504.007,"size":484},{"id":"1f68c3ef89799e852625f8893c810ec065f41e8f69efe69127dd7d19367844f5a014c6fa3a4b358bd088ab9c17607682a555982cff273017575d27c994464a16","href":"https://static.observableusercontent.com/files/1f68c3ef89799e852625f8893c810ec065f41e8f69efe69127dd7d19367844f5a014c6fa3a4b358bd088ab9c17607682a555982cff273017575d27c994464a16","name":"Level_3_7.csv","type":"text/csv","lastModified":1652891643318.677,"size":484},{"id":"bcd101fa746bb83ef1e391412f8cd9250d8c3dba2720b12957fa33d5a3e8ac40ccdec401e36692aebc9cbde2ac98a84313f8c2f4255e149bda11d2e1f541567f","href":"https://static.observableusercontent.com/files/bcd101fa746bb83ef1e391412f8cd9250d8c3dba2720b12957fa33d5a3e8ac40ccdec401e36692aebc9cbde2ac98a84313f8c2f4255e149bda11d2e1f541567f","name":"Level_3_6.csv","type":"text/csv","lastModified":1652891643140.086,"size":484},{"id":"ebb665e8ddc8013d0fbc5a69ffc83df20409fed1956d6013540ba5990c9ddfdf96854d9bf43b620e7cbdc0e15577dc7f97287060fb04bb4c28862156d05a9b74","href":"https://static.observableusercontent.com/files/ebb665e8ddc8013d0fbc5a69ffc83df20409fed1956d6013540ba5990c9ddfdf96854d9bf43b620e7cbdc0e15577dc7f97287060fb04bb4c28862156d05a9b74","name":"Level_3_2.csv","type":"text/csv","lastModified":1652891642962.801,"size":484},{"id":"82d57386885d1ada96a27e782d332fbe38432435696374249db1bcb06b0abb5e1ee34401d608a13189bbcdb2a6e877d2af64743af6cc0241474cdff4a8d5e0a8","href":"https://static.observableusercontent.com/files/82d57386885d1ada96a27e782d332fbe38432435696374249db1bcb06b0abb5e1ee34401d608a13189bbcdb2a6e877d2af64743af6cc0241474cdff4a8d5e0a8","name":"Level_3_5.csv","type":"text/csv","lastModified":1652891642859.165,"size":577},{"id":"dfb832885444833c255bb6d21a95574b817994d8fa2f8d39693cb945864d7e30f4dd18a45724663f9cd12d1edd7004559394595a6d96940ccd931a02004771bf","href":"https://static.observableusercontent.com/files/dfb832885444833c255bb6d21a95574b817994d8fa2f8d39693cb945864d7e30f4dd18a45724663f9cd12d1edd7004559394595a6d96940ccd931a02004771bf","name":"Level_3_1.csv","type":"text/csv","lastModified":1652891642797.04,"size":484},{"id":"7ac26207aa49218bfd7b6759e34bfe8bacc6c00bc8cc5ba0ea46bac21c82669b3abcd29cf15b6398398d9f0834832d84fbf67805716fa0ae2dcaf46cb324efe8","href":"https://static.observableusercontent.com/files/7ac26207aa49218bfd7b6759e34bfe8bacc6c00bc8cc5ba0ea46bac21c82669b3abcd29cf15b6398398d9f0834832d84fbf67805716fa0ae2dcaf46cb324efe8","name":"Level_3_0.csv","type":"text/csv","lastModified":1652891642553.404,"size":224},{"id":"60b4035d9e1a2858fc6c9674d990a6ae060f5b6ec3327eb260eec362093929e3f950fcb0754819e543ae31e975d65653db338532bb78a569585557420365e92a","href":"https://static.observableusercontent.com/files/60b4035d9e1a2858fc6c9674d990a6ae060f5b6ec3327eb260eec362093929e3f950fcb0754819e543ae31e975d65653db338532bb78a569585557420365e92a","name":"Level_3_3.csv","type":"text/csv","lastModified":1652891642463.189,"size":484},{"id":"1b2ed9607c6b9b063c2c5b87a8f8db265932923b223d9fb0f7b15a1f32b0c7bb680ffc001a493366cc9c7d29bf38aa6d3be8b67ef9ef5b33296b1dc315775c11","href":"https://static.observableusercontent.com/files/1b2ed9607c6b9b063c2c5b87a8f8db265932923b223d9fb0f7b15a1f32b0c7bb680ffc001a493366cc9c7d29bf38aa6d3be8b67ef9ef5b33296b1dc315775c11","name":"Level_3_4.csv","type":"text/csv","lastModified":1652891642390.345,"size":484},{"id":"9b8d2bb810f5863686c5ef51fd1881409a58012a8b2959f41df00b120ee90fc2c83c8aeca488b57555325bc005c18c75c4b27c6004128f87d9d10a4e609f798e","href":"https://static.observableusercontent.com/files/9b8d2bb810f5863686c5ef51fd1881409a58012a8b2959f41df00b120ee90fc2c83c8aeca488b57555325bc005c18c75c4b27c6004128f87d9d10a4e609f798e","name":"Level_2_0.csv","type":"text/csv","lastModified":1652891641987.469,"size":291},{"id":"ef04fbb4088fa488f6ab57b502738828a6c6ce9d4ef690fd813f041e9dcbf7f23968ff2beb95eee5fab7548312ce908aad2a85eff2e73aef84d17c059fdf41be","href":"https://static.observableusercontent.com/files/ef04fbb4088fa488f6ab57b502738828a6c6ce9d4ef690fd813f041e9dcbf7f23968ff2beb95eee5fab7548312ce908aad2a85eff2e73aef84d17c059fdf41be","name":"Level_1_1.csv","type":"text/csv","lastModified":1652891641825.634,"size":291},{"id":"55e3830ea66eb7c60db8c9a11540b1e0a52b7be99aff7b5a6c9909534e9d2b6ffc00557ea0aef24b3dc36a20ebbababfa5ae928825f0b3ead5087944d19e1ed6","href":"https://static.observableusercontent.com/files/55e3830ea66eb7c60db8c9a11540b1e0a52b7be99aff7b5a6c9909534e9d2b6ffc00557ea0aef24b3dc36a20ebbababfa5ae928825f0b3ead5087944d19e1ed6","name":"Level_2_2.csv","type":"text/csv","lastModified":1652891641611.972,"size":291},{"id":"b64f507b61d941fb3119bccaea6ec21b2532149084430156d36f09d07130ecc93daef1c69224633c3861952023567287fd3184eea527cbbdef18102bb2796b65","href":"https://static.observableusercontent.com/files/b64f507b61d941fb3119bccaea6ec21b2532149084430156d36f09d07130ecc93daef1c69224633c3861952023567287fd3184eea527cbbdef18102bb2796b65","name":"Level_2_1.csv","type":"text/csv","lastModified":1652891641671.979,"size":291},{"id":"9bb8d0b3e276d81db41b7845e5b5ed541fb3a6675e4a38cab91c1d7cd849230ece3f3e4fe31cb3a83b270df41fcec72ac4af082f43817b7499b024bc67ca9ca6","href":"https://static.observableusercontent.com/files/9bb8d0b3e276d81db41b7845e5b5ed541fb3a6675e4a38cab91c1d7cd849230ece3f3e4fe31cb3a83b270df41fcec72ac4af082f43817b7499b024bc67ca9ca6","name":"Level_0_4.csv","type":"text/csv","lastModified":1652891641466.022,"size":291},{"id":"2b7bd21a722788dd8bcc7e7018a133d88542a89693f0e036817d161e4144384f52fe6e3112dd6d4203ab3c4eebcc12e9287c4414d00d8e8c792e92391a4b7b06","href":"https://static.observableusercontent.com/files/2b7bd21a722788dd8bcc7e7018a133d88542a89693f0e036817d161e4144384f52fe6e3112dd6d4203ab3c4eebcc12e9287c4414d00d8e8c792e92391a4b7b06","name":"Level_0_2.csv","type":"text/csv","lastModified":1652891641312.277,"size":291},{"id":"fa8d84de0a72257d6f8736b988980e125dba01dab6e5cd88703620073d2ef56258768c7a29b0fe5d32207a4d704ae49d508156c771594efb0e140576afab84a2","href":"https://static.observableusercontent.com/files/fa8d84de0a72257d6f8736b988980e125dba01dab6e5cd88703620073d2ef56258768c7a29b0fe5d32207a4d704ae49d508156c771594efb0e140576afab84a2","name":"Level_0_1.csv","type":"text/csv","lastModified":1652891641271.183,"size":291},{"id":"e0bf8220fea16b937bd05d68b364f1f590258bc4e123d492be337999f5400bdad2eb1aa34a49c598d5186fb109c27ced0b10f534a8fedac2b6f89bcce3d78d6b","href":"https://static.observableusercontent.com/files/e0bf8220fea16b937bd05d68b364f1f590258bc4e123d492be337999f5400bdad2eb1aa34a49c598d5186fb109c27ced0b10f534a8fedac2b6f89bcce3d78d6b","name":"Level_1_0.csv","type":"text/csv","lastModified":1652891641106.806,"size":291},{"id":"80967a2ebcddaae718d41af5b04a7baf129f32ba27870c4ed6d29c8f68854b19dedff31e76f324650317023c509417d33fde84ad07ec8c071bee4fdb9e032af7","href":"https://static.observableusercontent.com/files/80967a2ebcddaae718d41af5b04a7baf129f32ba27870c4ed6d29c8f68854b19dedff31e76f324650317023c509417d33fde84ad07ec8c071bee4fdb9e032af7","name":"Level_0_0.csv","type":"text/csv","lastModified":1652891641060.512,"size":291},{"id":"2174a1655d81c54418bdbc7c18a05947ce3794ca58368080ade21d04539b06a8a3f494cc2e09759eca59e5e33e4a61342c68448953645c9704d9ba485378cdd7","href":"https://static.observableusercontent.com/files/2174a1655d81c54418bdbc7c18a05947ce3794ca58368080ade21d04539b06a8a3f494cc2e09759eca59e5e33e4a61342c68448953645c9704d9ba485378cdd7","name":"Level_0_3.csv","type":"text/csv","lastModified":1652891640797.101,"size":291}] 2b:{"id":"5cdae8bc4d6c5dd8","slug":null,"title":"Pathfinding","thumbnail":"e5a6d5442057ed19bf7c25a0b2f3ab16b44cca37083a0862f60c01e3f823e309","access_level":"public","create_time":"$D2022-05-18T14:18:53.150Z","update_time":"$D2023-09-13T03:20:53.498Z","view_time":null,"first_public_time":"$D2023-09-13T02:54:34.867Z","has_unpublished_edits":null,"fork":false,"stars":1,"starred":false,"owner":{"type":"team","id":"93d474714c1f5db5","login":"nifleysnifley","name":"Nifley","avatar_url":"https://avatars-next.observableusercontent.com/e6a81acf90a6fe8ed27600a821ff2a32d1bc76b5e624de3acac52854d60ab126","tier":"starter_2024"},"version":797,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"219a91dd69caffc4","login":"nifleysnifley","name":"Nifley","avatar_url":"https://avatars-next.observableusercontent.com/e6a81acf90a6fe8ed27600a821ff2a32d1bc76b5e624de3acac52854d60ab126","tier":null}],"members":[{"type":"individual","id":"219a91dd69caffc4","login":"nifleysnifley","name":"Nifley","avatar_url":"https://avatars-next.observableusercontent.com/e6a81acf90a6fe8ed27600a821ff2a32d1bc76b5e624de3acac52854d60ab126","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":1,"collection":{"id":"85f7f3b56216cc78","slug":"advent-of-code-visualizations","title":"Advent of Code Visualizations","owner":{"id":"93d474714c1f5db5","login":"nifleysnifley","name":"Nifley"}},"type":"notebook","body":{"title":"Pathfinding","cells":[{"id":0,"value":"# Pathfinding\nPrototypes and experiments related to a challenge project I was given in CS class.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":8,"value":"$2d","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":366,"value":"viewof target = Inputs.select(map.treasures, { label: \"Destination\" })","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":374,"value":"viewof mapSel = Inputs.select(mapNames, {label: \"Level\"})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":67,"value":"$2e","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":131,"value":"function manhattanDistance(src, dest) {\n return src.map((s, i) => Math.abs(s - dest[i])).reduce((a, b) => a + b);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":80,"value":"$2f","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":436,"value":"treasureDistances = {\n let distances = new Map();\n\n let t = [...map.treasures]\n t.push(map.start);\n\n for (let a of t)\n for (let b of map.treasures) {\n if (cmpv(a, b)) continue;\n distances[`${a.toString()}->${b.toString()}`] = Astar(a, b, map).length;\n }\n \n return distances;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":447,"value":"sortedTreasures = {\n let remainingTreasures = [...map.treasures];\n let currentTreasure = map.start;\n let sorted = [ currentTreasure ];\n \n while (remainingTreasures.length) {\n remainingTreasures.sort((a, b) => treasureDistances[`${currentTreasure}->${b}`] - treasureDistances[`${currentTreasure}->${a}`]);\n currentTreasure = remainingTreasures.pop();\n sorted.push(currentTreasure);\n }\n\n return sorted;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":499,"value":"optimizedTreasures = {\n let t = [...sortedTreasures];\n\n function twoOpt(...i) {\n return t.slice(0, i[0]).concat(t.slice(i[0], i[1]).reverse()).concat(t.slice(i[1]));\n }\n\n let minPathCost = calculateTraversalCost(t);\n for (let i = 0; i < t.length; i++)\n for (let j = 0; j < t.length; j++) {\n if (i > j) break;\n let optPath = twoOpt(i, j);\n let cost = calculateTraversalCost(optPath);\n if (cost < minPathCost) {\n t = optPath;\n minPathCost\n }\n }\n \n return t;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":703,"value":"totalPath = {\n let path = [ map.start ];\n\n for (let i = 0; i < optimizedTreasures.length - 1; i++) {\n path = path.concat(Astar(optimizedTreasures[i], optimizedTreasures[i+1], map).slice(1))\n }\n\n return path;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":547,"value":"calculateTraversalCost = (p) => {\n let acc = 0;\n\n for (let i = 0; i < p.length - 1; i++)\n acc += treasureDistances[`${p[i]}->${p[i+1]}`]\n\n return acc;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":708,"value":"calculatePathCost = (p) => {\n let acc = 0;\n\n for (let i of p)\n acc += values[map[i[0]][i[1]]];\n\n return acc;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":71,"value":"nbrs = [\n [0,-1],\n [0, 1],\n [-1,0],\n [1, 0],\n\n // [-1,-1],\n // [1, 1],\n // [-1,1],\n // [1, -1],\n]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":73,"value":"cmpv = (a,b) => a[0] == b[0] && a[1] == b[1]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":404,"value":"dispWidth = width/2;","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":11,"value":"cellSize = dispWidth / Math.max(map.width, map.height);","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":286,"value":"mutable map = loadMap(mapSel)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":327,"value":"values = ({\n \"P\": 1, // Start\n \"#\": 1024,\n \"T\": 1, // Treasure!\n \" \": 1,\n \"W\": 1024,\n \"w\": 13,\n \"B\": 23,\n \"t\": 37,\n \"M\": 47,\n \"m\": 5,\n \"L\": 61,\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":377,"value":"color = {\n const colors = {\n \"P\": \"red\", // Start\n \"#\": 'brown',\n \"T\": \"yellow\", // Treasure!\n \" \": '#F0F0F0',\n \"W\": 'brown',\n \"w\": 'lightblue',\n \"B\": 'lightgreen',\n \"t\": 'green',\n \"M\": 'lightgray',\n \"m\": 'darkbrown',\n \"L\": 'orange',\n };\n \n let colorFn = value => colors[value];\n \n return colorFn;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":29,"value":"function loadMap(name) {\n let csv = mapCSVs[mapNames.indexOf(name)]\n let m = csv.split('\\r\\n').map(l => l.split(','));\n \n m.start = [ 0, 0 ];\n m.width = m.length-2;\n m.pop();\n m.pop();\n m.height = m[0].length;\n m.treasures = [];\n\n for (let x = 0; x < m.length; ++x) {\n m[x].forEach((e, y) => {\n if (e == \"P\")\n m.start = [ x, y ];\n else if (e == \"T\") \n m.treasures.push([ x, y ]);\n })\n }\n\n m.end = m.treasures[m.treasures.length-1];\n\n return m;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":309,"value":"$30","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":277,"value":"mapNames = [\n \"Level_0_0\",\n \"Level_0_1\",\n \"Level_0_2\",\n \"Level_0_3\",\n \"Level_0_4\",\n \"Level_1_0\",\n \"Level_1_1\",\n \"Level_1_2\",\n \"Level_2_0\",\n \"Level_2_1\",\n \"Level_2_2\",\n \"Level_2_3\",\n \"Level_3_0\",\n \"Level_3_1\",\n \"Level_3_2\",\n \"Level_3_3\",\n \"Level_3_4\",\n \"Level_3_5\",\n \"Level_3_6\",\n \"Level_3_7\",\n \"Level_3_8\",\n \"Level_3_9\",\n \"Level_4_0\",\n \"Level_4_1\",\n \"Level_4_2\",\n \"Level_5_0\",\n \"Level_5_1\",\n \"Level_5_2\",\n \"Level_5_3\",\n \"Level_6_0\",\n \"Level_6_1\",\n \"Level_6_2\",\n \"Level_6_3\",\n \"Level_6_4\",\n \"Level_6_5\",\n \"Level_6_6\",\n \"Level_7_0\",\n \"Level_7_1\",\n \"Level_7_2\",\n \"Level_8_0\",\n \"Level_8_1\",\n]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":3,"value":"import { BHeap } from '@bryangingechen/dijkstras-algorithm-huge-version'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W31","stdlib":"1","titling":"auto"}} 2c:"$2b:body"