astar-core

Description

A-Star algorithm

Installation

npm install astar-core --save

or

yarn add astar-core

Usage

import AStarCore from "astar-core";

const { AStar, Graph } = AStarCore;

// map size equals 【gridSize x gridSize】
const gridSize = 10;

// decide how many walls in map
const wallFrequency = 0.1;

// wall flag
const WALL = 0;

// road flag
const ROAD = 1;

// 2 D arrays to store all nodes
const nodes = [];

// generate all nodes in map
for (let x = 0; x < gridSize; x++) {
  const nodeRow = [];
  for (let y = 0; y < gridSize; y++) {
    const isWall = Math.floor(Math.random() * (1 / wallFrequency));
    if (isWall === WALL) {
      nodeRow.push(WALL);
    } else {
      nodeRow.push(ROAD);
    }
  }
  nodes.push(nodeRow);
}

// start node
const start = nodes[0][0];

// end node
const end = nodes[gridSize - 1][gridSize - 1];
// graph options
// diagonal: specifies whether diagonal moves are allowed.
const graphOptions = { diagonal: false };

// create a map data
const graph = new Graph(nodes, graphOptions);

// a-star options
// closest: specifies whether to return the path to the closest node if the target is unreachable.
// heuristic: Heuristic function (see AStarCore.Heuristics).
const astarOptions = { closest: false, heuristic: null }; 

// use a-star algorithm to search the shortest path.
// it will return the path from start to end.
const path = AStar.search(graph, start, end, astarOptions);