Compute a shortest path using the A* search algorithm.

Multiple equivalent nodes (determined by the AStarOptions.key() function) will never be included twice in the path.

The shortest path starting from AStarOptions.start up to a node for which AStarOptions.success() returns true is computed and returned along with its total cost, or undefined is returned if no successful path was found. The returned path comprises both the start and end node.

Example

import { assertEquals } from "https://deno.land/std@0.189.0/testing/asserts.ts";
import { aStar } from "https://deno.land/x/lazy_pathfinding/directed/a_star.ts";

type Pos = [number, number];

function distance(a: Pos, b: Pos): number {
  return Math.abs(a[0] - a[1]) + Math.abs(b[0] - b[1]);
}

const goal: Pos = [4, 6];

const result = aStar<Pos>({
  start: [1, 1],
  successors: ([x, y]) =>
    ([
      [x + 1, y + 2],
      [x + 1, y - 2],
      [x - 1, y + 2],
      [x - 1, y - 2],
      [x + 2, y + 1],
      [x + 2, y - 1],
      [x - 2, y + 1],
      [x - 2, y - 1],
    ] as Pos[])
      .map((p) => [p, 1]),
  heuristic: (node) => distance(node, goal) / 3,
  success: (node) => node[0] === goal[0] && node[1] === goal[1],
  key: (node) => node[0] + "," + node[1],
});

assertEquals(result![1], 4);