API Reference

Everything cl-astar exports. Every function's docstring says the same: (describe 'cl-astar:id-path).

Thread rules for all of it: a graph or a grid is used from one thread at a time, finding paths included. See Threads.

Types

Type	Values
point-id	the id of a graph's point: an integer from 0 to most-positive-fixnum
cell-coordinate	a cell's column or row: an integer of 32 bits
region	a list (X Y WIDTH HEIGHT) of cells, X and Y cell coordinates, WIDTH and HEIGHT from 0
diagonal-mode	:always, :never, :at-least-one-walkable or :only-if-no-obstacles
heuristic	:euclidean, :manhattan, :octile or :chebyshev
cell-shape	:square, :isometric-right or :isometric-down

A position returned is a (simple-array single-float (2)), as cl-gmath's vec2; one given to a writer, or a grid's offset or cell size, is any sequence of two reals. Coordinates given to add-point, closest-point and closest-position-in-segment are any reals.

Graphs

graph (class)

Points in the plane and the connections between them, as Godot's AStar2D. Subclass it for costs of your own; make-instance takes :neighbor-filter-enabled.

make-graph

(make-graph &key neighbor-filter-enabled) => graph

Returns an empty graph. With neighbor-filter-enabled, its searches ask filter-neighbor before each move.

graph-neighbor-filter-enabled

(graph-neighbor-filter-enabled graph) => boolean
(setf (graph-neighbor-filter-enabled graph) boolean)

Whether searches ask filter-neighbor, as Godot's neighbor_filter_enabled.

add-point

(add-point graph id x y &key (weight-scale 1)) => id

Adds a point with id at x, y, with weight-scale, a real of 0 or more, by which the cost of moving to it is multiplied, and returns id. If the graph has a point with id, moves it and sets its weight scale; its connections and whether it is disabled stay.

next-point-id

(next-point-id graph) => point-id

Returns an id no point has: the one it returned before, or that of the point removed since, if no point has it, else the first free id above it. 0 in a new or cleared graph. Godot's get_available_point_id.

remove-point

(remove-point graph id) => nil

Removes the point and its connections, both ways.

has-point-p, point-count, point-ids

(has-point-p graph id) => boolean
(point-count graph) => integer
(point-ids graph) => (simple-array fixnum (*))

Whether the graph has a point with id; how many points it has; their ids, in Godot's order: as added, each removed point's place taken by the last.

point-position

(point-position graph id &optional result) => position
(setf (point-position graph id) position)

The point's position, written into result, a (simple-array single-float (2)), if given, which allocates nothing. The writer takes a sequence of two reals.

point-weight-scale

(point-weight-scale graph id) => single-float
(setf (point-weight-scale graph id) weight-scale)

The factor of the cost of a move to the point; the writer takes a real of 0 or more.

point-disabled

(point-disabled graph id) => boolean
(setf (point-disabled graph id) boolean)

Whether the point is disabled: no path passes through it, starts at it or ends at it.

connect-points, disconnect-points

(connect-points graph id to-id &key (bidirectional t)) => nil
(disconnect-points graph id to-id &key (bidirectional t)) => nil

Connect id to to-id, and back if bidirectional; connecting connected points adds the direction asked for. Disconnect them both ways, or without bidirectional, only from id to to-id. Connecting a point to itself is an error.

points-connected-p

(points-connected-p graph id to-id &key (bidirectional t)) => boolean

Whether the points are connected in either direction, or without bidirectional, so that a path may move from id to to-id. False if either is missing.

point-connections

(point-connections graph id) => (simple-array fixnum (*))

The ids of the points id connects to, in Godot's order: as connected, each disconnected point's place taken by the last.

reserve-points, point-capacity, clear-graph

(reserve-points graph count) => graph
(point-capacity graph) => integer
(clear-graph graph) => graph

Make room for count points, at least as many as the graph has, so that adding that many grows no array; how many points fit before the arrays grow; remove every point and connection, keeping the room.

closest-point

(closest-point graph x y &key include-disabled) => point-id or nil

The enabled point nearest x, y, or with include-disabled any point; of points as near, the lowest id. NIL for a graph without points.

closest-position-in-segment

(closest-position-in-segment graph x y &optional result) => position or nil

The position nearest x, y on a connection between two enabled points, written into result if given; NIL if no two enabled points are connected.

id-path, point-path

(id-path graph from-id to-id &key allow-partial-path) => (simple-array fixnum (*))
(point-path graph from-id to-id &key allow-partial-path) => (simple-array single-float (* 2))

The ids, or the positions, a row of X and Y each, of the points on the cheapest path from from-id to to-id, from-id first. Empty if there is no path, unless allow-partial-path, which leads the path to the reachable point closest to to-id instead. No path passes through, starts at or ends at a disabled point. See Graphs.

compute-cost, estimate-cost, filter-neighbor (generic functions)

(compute-cost graph from to) => real
(estimate-cost graph from end) => real
(filter-neighbor graph from neighbor) => generalized boolean

The cost of a move between connected points, the distance by default; an estimate of the cost from a point to the end, the distance by default; true to refuse a move, false by default, asked only while graph-neighbor-filter-enabled. See Costs of Your Own.

Grids

grid (class)

A rectangle of cells, as Godot's AStarGrid2D. Subclass it for costs of your own; make-instance takes make-grid's arguments as initargs.

make-grid

(make-grid &key (region '(0 0 0 0)) (offset '(0 0)) (cell-size '(1 1))
                (cell-shape :square) (diagonal-mode :always)
                (default-compute-heuristic :euclidean)
                (default-estimate-heuristic :euclidean) jumping-enabled)
  => grid

Returns a grid of the cells of region, none solid, each of weight scale 1, up to date. See Grids.

Settings

Reader, and setf writer	Value
(grid-region grid)	the region, a new list (X Y WIDTH HEIGHT)
(grid-offset grid)	the offset added to the cells' positions, a new position
(grid-cell-size grid)	a cell's width and height, a new position
(grid-cell-shape grid)	a cell-shape
(grid-diagonal-mode grid)	a diagonal-mode
(grid-default-compute-heuristic grid)	the heuristic that measures a move's cost
(grid-default-estimate-heuristic grid)	the heuristic that estimates the cost to the end
(grid-jumping-enabled grid)	true if searches jump along lines of free cells

A new region, offset, cell size or cell shape leaves the grid dirty; the others take effect at once.

grid-dirty-p, update-grid, clear-grid

(grid-dirty-p grid) => boolean
(update-grid grid) => grid
(clear-grid grid) => grid

Whether the region, offset, cell size or cell shape changed since the cells were made; if so, make them anew, none solid; give the grid the empty region (0 0 0 0). See Grids.

cell-in-bounds-p

(cell-in-bounds-p grid x y) => boolean

Whether the cell is in the grid's region, dirty or not.

cell-solid, fill-solid-region

(cell-solid grid x y) => boolean
(setf (cell-solid grid x y) boolean)
(fill-solid-region grid region &optional (solid t)) => nil

Whether the cell is solid: no path passes through it, starts at it or ends at it. Make every cell of region the grid has solid, or free.

cell-weight-scale, fill-weight-scale-region

(cell-weight-scale grid x y) => single-float
(setf (cell-weight-scale grid x y) weight-scale)
(fill-weight-scale-region grid region weight-scale) => nil

The factor of the cost of a move to the cell, unless the grid jumps; set it for every cell of region the grid has. A weight scale is a real of 0 or more.

cell-position

(cell-position grid x y &optional result) => position

Where the grid's offset, cell size and cell shape place the cell, written into result if given, which allocates nothing.

cell-data-in-region

(cell-data-in-region grid region) => list

A property list of :x, :y, :position, :solid and :weight-scale for each cell of region the grid has, row by row.

cell-path, cell-point-path

(cell-path grid from-x from-y to-x to-y &key allow-partial-path)
  => (simple-array fixnum (* 2))
(cell-point-path grid from-x from-y to-x to-y &key allow-partial-path)
  => (simple-array single-float (* 2))

The cells, or their positions, a row of X and Y each, on the cheapest path between the cells, the first cell first. No rows if there is no path, unless allow-partial-path. When the grid jumps, only the cells where the path turns. See Grids.

compute-cell-cost, estimate-cell-cost (generic functions)

(compute-cell-cost grid from-x from-y to-x to-y) => real
(estimate-cell-cost grid from-x from-y end-x end-y) => real

The cost of a move, by grid-default-compute-heuristic by default; an estimate of the cost to the end, by grid-default-estimate-heuristic by default. See Costs of Your Own.

Conditions

astar-error (condition)

What cl-astar signals for a point a graph lacks, a cell outside a grid's region, a dirty grid's cells, a position that is not two reals, or a cost a method returned that a search cannot use. astar-error-message returns what went wrong and what to do about it. See Errors.