astar-stepper

AStar Stepper

A little A* path-finding library written in TypeScript. Still a work in progress.

Basic Usage

import { solve, stepper } from "astar-stepper";

// Creates a node, which can be any object
const node = (x, y, neighbours = []) => {
    return {x, y, neighbours};
};

// Makes two nodes neighbours of each other
const linkNodes = (a, b) => {
    a.neighbours.push(b);
    b.neighbours.push(a);
};

// Calculates the 'cost' to travel between two nodes, asynchronously
const costBetweenNodes = async (a, b) => {
    // In this case the distance of a straight line between their X/Y points.
    return Math.sqrt(Math.pow(a.x - b.x, 2) + Math.pow(a.y - b.y, 2));
};

// Gets the immediate neighbours of a node, asynchronously
const getNeighbours = async (node) => {
    // Might return a property on the node, or calculate neighbours dynamically, or anything else!
    return node.neighbours;
};

// Sample nodes
const nodes = [];
nodes.push(node(0, 0));
nodes.push(node(1, 6));
nodes.push(node(2, 0));
nodes.push(node(3, 5));
nodes.push(node(4, 2));

// Link nodes in chain 0->1->2->etc
linkNodes(nodes[0], nodes[1]);
linkNodes(nodes[1], nodes[2]);
linkNodes(nodes[2], nodes[3]);
linkNodes(nodes[3], nodes[4]);

// Calculate the most cost effective path asynchronously
const solveAllAtOnce = async () => {
    const result = await solve(nodes[0], nodes[4], getNeighbours, costBetweenNodes, costBetweenNodes);
    
    console.log(result.status); // 1 if solved, -1 if not.
    console.log(result.cost); // Total cost of path
    console.log(result.path); // The array of nodes to travel from startNode to goalNode inclusive
};

solveAllAtOnce();

// Watch the progress step by step
const solveInSteps = async () => {
    const step = await stepper(nodes[0], nodes[4], getNeighbours, costBetweenNodes, costBetweenNodes);
    let stepResult;
    do {
        stepResult = await step();
        console.log(stepResult.result); // The result at this step
        console.log(stepResult.state); // The current state of the solver, with access to the open and closed Sets.
    } while (stepResult.result.status === 0);
};

solveInSteps();

solve(startNode, goalNode, neighbourGetter, heuristicCostEstimator, costBetweenCalculator)

For calculating the optimal path all in one go asynchronously.

startNode: The node to be begin the path from.

goalNode: The node to end at.

neighbourGetter: A function that takes a node, and returns a Promise containing an array of neighbouring nodes.

heuristicCostEstimator: A function that takes a start and end node, and returns a Promise containing a number representing the approximate cost of traveling between the two nodes.

costBetweenCalculator: A function that takes two neighbouring nodes, and returns a Promise containing a number representing the cost of traveling from the first node to the second.

Returns a Promise resolving to a PathAndCost object (see below).

synchronousSolve(startNode, goalNode, neighbourGetter, heuristicCostEstimator, costBetweenCalculator)

For calculating the optimal path all in one go synchronously.

startNode: The node to be begin the path from.

goalNode: The node to end at.

neighbourGetter: A function that takes a node, and returns an array of neighbouring nodes.

heuristicCostEstimator: A function that takes a start and end node, and returns a number representing the approximate cost of traveling between the two nodes.

costBetweenCalculator: A function that takes two neighbouring nodes, and returns a number representing the cost of traveling from the first node to the second.

Returns a PathAndCost object (see below).

stepper(startNode, goalNode, neighbourGetter, heuristicCostEstimator, costBetweenCalculator)

For calculating a step at a time asynchronously.

Parameters are the same as for solve()

Returns a function that can be called repeatedly, each time returning a Promise resolving to a Step object (see below) describing the current state.

synchronousStepper(startNode, goalNode, neighbourGetter, heuristicCostEstimator, costBetweenCalculator)

For calculating a step at a time synchronously.

Parameters are the same as for synchronousSolve()

Returns a function that can be called repeatedly, each time returning a Step object (see below) describing the current state.

Step

Returned by invoking the function that stepper/synchronousStepper generates.

Contains:

result: A PathAndCost object (see below)

state: An object representing the current state, which contains:

state.open: A Strong Set (like) object containing the current open nodes.

state.closed: A Strong Set (like) object containing the closed nodes.

PathAndCost

solve() and each call to stepper.step() return a Promise resolving to a PathAndCost object, which contains:

status: 1 if successfully solved, 0 if currently solving, -1 if no solution was found.

cost: The total cost of travelling the shortest path between the start and goal nodes. 0 if no solution has been found (yet).

path: An array of nodes, from the start to the goal inclusive. Empty if no solution has been found (yet).

Requirements

Requires a global Promise object, or a polyfill.

By default it expects global Set and WeakMap, however these can be substituted:

import { AStarMapSet } from "astar-stepper";

AStarMapSet.weakMap = () => {
    return new WeakMapSubstitute(); // An object with set, get, and has methods.
};

AStarMapSet.strongSet = () => {
    return new StrongSetSubstitute(); // An object with add, has, delete, forEach and size methods.
}