Pasta: a pluggable A* implementation

Wikipedia article about A*

Usage

BYOC -- Bring Your Own Context. The algorithm is decoupled from the underlying (graph? grid?) pathfindable data structure. You need to provide:

• a cost function that computes the cost of traveling from one node to another
• a heuristic function that estimates the cost of traveling from one node to the target ()
• a neighbors function that returns a set of neighbor nodes reachable from a given node

Individual nodes can be identified by any value -- just make sure that your neighbors implementation generates comparable identifiers.

This algorithm is using an h-based tie breaking to reduce the number of visited nodes for same-cost paths. According to Amit-the-A*-guru, this is an idea by Steven van Dijk.

import { pasta } from "https://cdn.jsdelivr.net/gh/ondras/pasta@main/pasta.ts";

const N = 5; // our graph is a 5x5 grid

function taxicab(x1, y1, x2, y2) { return Math.abs(x1-x2) + Math.abs(y1-y2); }

function cost(from, to) {
  let [x1, y1] = from.split(",").map(Number);
  let [x2, y2] = to.split(",").map(Number);
  return taxicab(x1, y1, x2, y2);
}

function heuristic(from, to) {
  return cost(from, to); // often, we can re-use the cost function as heuristic
}

function neighbors(node) {
  let [x, y] = node.split(",").map(Number);
  return [[-1,0],[1,0],[0,-1],[0,1]]
    .map(([dx, dy]) => [x+dx, y+dy])
    .filter(([x, y]) => x>=0 && y>=0 && x<N && y<N)
    .map(xy => xy.join(","));
}

let options = { cost, neighbors, heuristic };
let path = pasta("0,0", "4,4", options);
console.log(path); // 0,0 -> 1,0 -> ... -> 4,0 -> 4,1 -> ... -> 4,4