Skip to main content

AStar

import { Map2D, Node2D, Vector2D } from "@arclockproject/common/library/AStar";

For examples and live demos, see the AStar guide.

Map2D​

Class

class Map2D<CustomNode2D extends Node2D = Node2D>

A grid of Node2Ds that can find paths between them. Movement is up, down, left and right only.

Constructor

new Map2D(nodes: CustomNode2D[][])

Creates a map from a node matrix, usually made with Map2D.generateNodeMatrix.

Parameters

  • nodes (CustomNode2D[][]) — Rows of nodes, [y][x]. All rows should be the same length. Each node's mapRef is set to this map.

Properties

  • nodes (CustomNode2D[][]) — Rows of nodes, [y][x]. All rows should be the same length. Each node's mapRef is set to this map.
  • width (number, default 0) — Number of columns.
  • height (number, default 0) — Number of rows.

Example

const map = new Map2D(
  Map2D.generateNodeMatrix((pos) => new Node2D(pos, 1), 10),
);
map.getNode({ x: 5, y: 5 })!.traversable = false;
const path = map.calculatePath(
  map.getNode({ x: 0, y: 0 }),
  map.getNode({ x: 9, y: 9 })
);

Map2D.getNode()​

Map2D.getNode(pos: Vector2D): CustomNode2D | null
Map2D.getNode(pos: { x: number; y: number }): CustomNode2D | null

Looks up the node at a position.

Parameters

  • pos (Vector2D) — A Vector2D or a plain { x, y }.

Returns CustomNode2D | null — The node at pos, or null if it is outside the map.

Example

map.getNode({ x: 0, y: 0 }); // top-left node
map.getNode({ x: -1, y: 0 }); // null

Map2D.getNodeArea()​

Map2D.getNodeArea(posA: Vector2D, posB: Vector2D): CustomNode2D[][]
Map2D.getNodeArea(posA: { x: number; y: number }, posB: { x: number; y: number }): CustomNode2D[][]

Returns the rectangle of nodes between two corners, as rows. The rectangle starts at the smaller x and y and stops before the larger ones, and is clipped to the map.

Parameters

  • posA (Vector2D) — One corner.
  • posB (Vector2D) — The opposite corner.

Returns CustomNode2D[][] — Rows of nodes, top to bottom.

Example

map.getNodeArea({ x: 0, y: 0 }, { x: 2, y: 2 }); // 2×2 nodes: (0,0) to (1,1)

Map2D.getNodeAreaFlat()​

Map2D.getNodeAreaFlat(posA: Vector2D, posB: Vector2D): CustomNode2D[]
Map2D.getNodeAreaFlat(posA: { x: number; y: number }, posB: { x: number; y: number }): CustomNode2D[]

Same as getNodeArea, but as one flat list, row by row.

Parameters

  • posA (Vector2D) — One corner.
  • posB (Vector2D) — The opposite corner.

Returns CustomNode2D[]

Map2D.forEachNode()​

Map2D.forEachNode(forEach: (node: CustomNode2D) => void): void

Calls forEach for every node, row by row.

Parameters

  • forEach ((node: CustomNode2D) => void) — Called with each node. Changing the node in place is fine.

Map2D.generateNodeMatrix()​

static Map2D.generateNodeMatrix<CustomNode2D extends Node2D = Node2D>(generator: (vector: Vector2D) => CustomNode2D, width: number, height?: number): CustomNode2D[][]

Builds a node matrix to pass to the Map2D constructor, with each node at the right position.

Parameters

  • generator ((vector: Vector2D) => CustomNode2D) — Called once per cell with its position. Returns the node for that cell.
  • width (number) — Number of columns.
  • height? (number) — Number of rows. Defaults to width.

Returns CustomNode2D[][] — Rows of nodes, [y][x].

Example

Map2D.generateNodeMatrix((pos) => new Node2D(pos, 1), 20, 10); // 20 wide, 10 tall

Map2D.calculatePath()​

Map2D.calculatePath(start: CustomNode2D | null, end: CustomNode2D | null): CustomNode2D[] | null

Finds a path from start to end that avoids walls and prefers low-cost nodes. Overwrites the cameFrom, g and f of the nodes it visits.

Parameters

  • start (CustomNode2D | null) — Node to start from. Usually from getNode.
  • end (CustomNode2D | null) — Node to reach.

Returns CustomNode2D[] | null — The path from end back to start, both included. null if either node is null or no path exists.

See also https://en.wikipedia.org/wiki/A*_search_algorithm

Node2D​

Class

class Node2D

One cell of a Map2D. Extend it to store your own data per cell, and pass the subclass as Map2D's type parameter.

Constructor

new Node2D(pos: Vector2D, cost: number, traversable: boolean = true)

Creates a node. Usually made in the generator of Map2D.generateNodeMatrix, which passes the right pos.

Parameters

  • pos (Vector2D) — Position on the map. Must match the node's place in the matrix.
  • cost (number) — How expensive it is to step onto this node. Paths prefer lower costs.
  • traversable? (boolean, default true) — false makes this node a wall.

Properties

  • pos (Vector2D) — Position on the map. Must match the node's place in the matrix.
  • cost (number) — How expensive it is to step onto this node. Paths prefer lower costs.
  • traversable (boolean) — false makes this node a wall.
  • cameFrom (this | null, default null) — The node before this one on the last calculated path. Set by Map2D.calculatePath.
  • g (number, default Infinity) — Path cost from the start. Set by Map2D.calculatePath.
  • f (number, default Infinity) — Search score. Set by Map2D.calculatePath.
  • mapRef (Map2D<this> | null, default null) — The map this node belongs to. Set by the Map2D constructor.

Node2D.distance()​

Node2D.distance(other: this): number

Measures the straight-line distance between the two nodes' positions.

Parameters

  • other (this) — The node to measure to.

Returns number — Straight-line distance to other.

Node2D.getTraversableNeighbors()​

Node2D.getTraversableNeighbors(): this[]

Lists the neighbors a path can step onto. Used by Map2D.calculatePath.

Returns this[] — The nodes up, down, left and right of this one that exist and are traversable.

Node2D.getNeighbors()​

Node2D.getNeighbors(): this[]

Lists every neighbor, including walls. Nodes outside the map are left out.

Returns this[] — The nodes up, down, left and right of this one that exist, including walls.

Node2D.traversePathTill()​

Node2D.traversePathTill(end: this): this[]

Follows cameFrom back from this node until it reaches end. Used by Map2D.calculatePath. Logs an error and returns what it has if the chain breaks.

Parameters

  • end (this) — The node to stop at, usually the start of the path.

Returns this[] — Nodes from this node to end, both included.

Node2D.toString()​

Node2D.toString(): string

Returns string

Vector2D​

Class

class Vector2D

A 2D point or offset on the grid. x is the column and y is the row.

Constructor

new Vector2D(x: number, y: number)

Creates a vector. getNode and the other Map2D methods also take a plain { x, y }.

Parameters

  • x (number) — Column, counted from 0 on the left.
  • y (number) — Row, counted from 0 at the top.

Properties

  • x (number) — Column, counted from 0 on the left.
  • y (number) — Row, counted from 0 at the top.

Vector2D.distance()​

Vector2D.distance(other: Vector2D): number

Measures the straight-line distance, not the number of steps on the grid.

Parameters

  • other (Vector2D) — The point to measure to.

Returns number — Straight-line distance to other.

Example

new Vector2D(0, 0).distance(new Vector2D(3, 4)); // 5

Vector2D.copy()​

Vector2D.copy(): Vector2D

Copies the vector, so it can be changed without changing the original.

Returns Vector2D — A new vector with the same x and y.

Vector2D.add()​

Vector2D.add(vector: Vector2D): this

Adds vector to this vector in place. Use copy() first to keep the original.

Parameters

  • vector (Vector2D) — The offset to add. It is not changed.

Returns this — This vector, for chaining.

Example

new Vector2D(1, 1).add(new Vector2D(2, 0)); // Vector(x=3,y=1)

Vector2D.toString()​

Vector2D.toString(): string

Returns string