A* algorithm implemented in Typst

astar.typ

#let astar(edges, start: "S", heur: auto, target: none) = {
  if heur == auto {
    heur = _ => 0;
  } else {
    assert.ne(target, none, message: "A* requires a target node to be set");
  }
  if type(heur) == dictionary {
    heur = x => heur.at(x);
  }
  if type(edges) == dictionary {
    edges = x => edges.at(x, default: ());
  }
  let log = ();
  let visited = ();
  let queue = (start,);
  let known = (:);
  known.insert(start, (parent: none, dist: 0));
  while queue != () {
    queue = queue.sorted(key: x => -(known.at(x).dist + heur(x)));
    let cur = queue.pop();
    visited.push(cur);
    for (node, len) in edges(cur) {
      if node in visited { continue; }
      
      let dist = known.at(cur).dist + len;
      if node not in known or known.at(node).dist > dist {
        known.insert(node, (parent: cur, dist: dist));
      }
      if node not in queue { queue.push(node) };
    }
    log.push((
      queue: queue,
      visited: visited,
      known: known,
    ));
    if cur == target {
      break;
    }
  }
  log
}