function aStar(origin, target, barriers) {
if (!target || barriers.has(target)) return [];
// Init the priority queue
const frontier = new Heapify(256, [], [], Array);
frontier.push(origin, 0);
// Init path graph and cost tracker
const cameFrom = {[origin]: null};
const costSoFar = {[origin]: 0};
// Main algo loop
let current;
while (frontier.length > 0) {
current = frontier.pop();
if (current === target) break;
// Find neighbors, removing barriers
const neighbors = h3.kRing(current, 1)
.filter(h3Index => h3Index !== current && !barriers.has(h3Index));
// Traverse all neighbors
for (const neighbor of neighbors) {
const cost = costSoFar[current] + 1;
if (!costSoFar[neighbor] || cost < costSoFar[neighbor]) {
costSoFar[neighbor] = cost;
// Add to the queue
const priority = cost + h3.h3Distance(neighbor, target);
// .push will throw if we exceed queue size. This either indicates
// that the target is unreachable, or that it is too far to reach
// through this traversal method.
try {
frontier.push(neighbor, priority);
} catch (e) {
return [];
}
// Add path
cameFrom[neighbor] = current;
}
}
}
// Walk the traversal graph backwards from the target
const path = [];
current = target;
while (current !== origin) {
path.push(current);
current = cameFrom[current];
}
path.reverse();
return path;
}
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
