cl-astar

• Graphs
• Grids
• Costs of your own
• Numbers
• Godot's names
• Threads
• Errors
• Tests
• Licence

A* pathfinding for Common Lisp, as Godot's AStar2D and AStarGrid2D: graphs of points of one's own and the connections between them, and grids of cells, some of them solid, with weight scales, diagonal modes, heuristics and jump point search. Of equally cheap paths, a search finds the one Godot 4.7 finds. cl-astar knows nothing of a game engine.

(asdf:load-system :cl-astar)

;; A grid of 8 by 5 cells, each 16 units square, with a wall down the
;; middle that leaves a gap at the bottom.
(defvar *grid* (cl-astar:make-grid :region '(0 0 8 5) :cell-size '(16 16)))
(cl-astar:fill-solid-region *grid* '(4 0 1 4))

(cl-astar:cell-path *grid* 1 1 6 1)
;; => #2A((1 1) (2 2) (3 3) (4 4) (5 3) (6 2) (6 1))
(cl-astar:cell-point-path *grid* 1 1 6 1)
;; => #2A((16.0 16.0) (32.0 32.0) (48.0 48.0) (64.0 64.0) (80.0 48.0) (96.0 32.0)
;;        (96.0 16.0))

;; Points of one's own: a straight way through a point that costs three
;; times as much to enter, and a way round.
(defvar *graph* (cl-astar:make-graph))
(cl-astar:add-point *graph* 1 0 0)
(cl-astar:add-point *graph* 2 10 0 :weight-scale 3)
(cl-astar:add-point *graph* 3 20 0)
(cl-astar:add-point *graph* 4 10 10)
(cl-astar:connect-points *graph* 1 2)
(cl-astar:connect-points *graph* 2 3)
(cl-astar:connect-points *graph* 1 4)
(cl-astar:connect-points *graph* 4 3)
(cl-astar:id-path *graph* 1 3)
;; => #(1 4 3)

Graphs

A graph, as Godot's AStar2D, holds points in the plane. make-graph makes an empty one.

• add-point adds a point with an id of your choosing, an integer from 0, at X, Y, with a :weight-scale, 1 by default, by which the cost of moving to it is multiplied, and returns the id. Adding a point the graph has moves it and sets its weight scale. next-point-id returns an id no point has; remove-point removes a point with its connections.
• connect-points connects one point to another, both ways unless :bidirectional nil; disconnect-points takes a connection away, both ways or one. points-connected-p asks, in either direction or, without :bidirectional, from the first point to the second; point-connections lists the points a point connects to.
• (setf point-disabled) disables a point, as a temporary obstacle: no path passes through it, starts at it or ends at it.
• point-position, point-weight-scale, point-ids, point-count and has-point-p read the points; point-position and point-weight-scale also setf. reserve-points makes room for many points at once, as point-capacity tells; clear-graph empties the graph.
• closest-point returns the id of the enabled point nearest a position, the lowest id of those as near; closest-position-in-segment returns the position nearest it on a connection between enabled points.

id-path returns the ids of the points on the cheapest path between two points, and point-path their positions. Where there is no path, both are empty, unless :allow-partial-path asks for the path to the reachable point closest to the end.

Grids

A grid, as Godot's AStarGrid2D, is a rectangle of cells, each connected to its neighbours. make-grid takes its :region, a list (X Y WIDTH HEIGHT), whose corner may be below 0; :cell-size and :offset, which, with :cell-shape, :square or a diamond's :isometric-right or :isometric-down, place its cells for cell-position and cell-point-path.

• (setf cell-solid) makes a cell an obstacle, and fill-solid-region a rectangle of them; (setf cell-weight-scale) and fill-weight-scale-region make cells dearer to enter.
• :diagonal-mode says when a path may move diagonally: :always, :never, :at-least-one-walkable, past one solid cell but not between two, or :only-if-no-obstacles.
• :default-compute-heuristic measures the cost of a move and :default-estimate-heuristic estimates the cost to the end: :euclidean, :manhattan, for paths that never move diagonally, :octile or :chebyshev.
• :jumping-enabled jumps along lines of free cells, as jump point search does: faster across open ground, but weight scales count for nothing then, as in Godot, and a path lists only the cells where it turns.

cell-path returns the cells on the cheapest path between two cells, as a row of X and Y each, and cell-point-path their positions. A grid's settings have readers and writers of the same names, such as grid-region and grid-diagonal-mode. A new region, offset, cell size or cell shape leaves the grid dirty, as grid-dirty-p tells, until update-grid makes its cells anew, none solid; until then, only its settings and cell-in-bounds-p can be read. cell-data-in-region lists the cells of a region, each with its position, solidity and weight scale.

Costs of your own

A subclass of graph measures costs its own way with methods on compute-cost, the cost of a move between connected points, and estimate-cost, the estimated cost from a point to the end; both are the distance by default, which call-next-method gives. With graph-neighbor-filter-enabled true, a method on filter-neighbor rules moves out. A subclass of grid has compute-cell-cost and estimate-cell-cost. Make an instance of the subclass with make-instance, which takes the arguments of make-graph or make-grid as initargs.

;; A grid whose row 1 is a road, along which moves cost a tenth.
(defclass road-grid (cl-astar:grid) ())

(defmethod cl-astar:compute-cell-cost ((grid road-grid) from-x from-y to-x to-y)
  (let ((cost (call-next-method)))
    (if (= from-y to-y 1) (/ cost 10) cost)))

;; Never estimate more than a path can cost, or the path found may not be
;; the cheapest.
(defmethod cl-astar:estimate-cell-cost ((grid road-grid) from-x from-y end-x end-y)
  (/ (call-next-method) 10))

(cl-astar:cell-path (make-instance 'road-grid :region '(0 0 7 3) :diagonal-mode :never)
                    0 0 6 0)
;; => #2A((0 0) (0 1) (1 1) (2 1) (3 1) (4 1) (5 1) (6 1) (6 0))

A cost is a real of 0 or more, and an estimate any real. A method that returns a single float or an integer allocates nothing; a double float is boxed.

Numbers

Positions, costs and weight scales are single floats, as in Godot, and a search adds costs up in the order Godot does, which is how it finds Godot's path of several equally cheap ones. A position comes back as a specialised array of two single floats, as cl-gmath's vec2: point-position and cell-position write into an array you give them, and allocate nothing. Paths are new specialised arrays; a search allocates nothing else.

Godot's names

Godot	cl-astar
AStar2D.new()	make-graph
get_available_point_id	next-point-id
add_point, remove_point, has_point	add-point, remove-point, has-point-p
set_point_position, get_point_position	point-position
set_point_disabled, is_point_disabled	point-disabled
are_points_connected	points-connected-p
reserve_space, get_point_capacity	reserve-points, point-capacity
get_id_path, get_point_path	id-path, point-path
neighbor_filter_enabled, _filter_neighbor	graph-neighbor-filter-enabled, filter-neighbor
_compute_cost, _estimate_cost	compute-cost, estimate-cost
AStarGrid2D.new(), then update()	make-grid
update, is_dirty, clear	update-grid, grid-dirty-p, clear-grid
is_in_bounds	cell-in-bounds-p
set_point_solid, is_point_solid	cell-solid
set_point_weight_scale	cell-weight-scale
get_point_position, get_point_data_in_region	cell-position, cell-data-in-region
get_id_path, get_point_path	cell-path, cell-point-path
_compute_cost, _estimate_cost	compute-cell-cost, estimate-cell-cost

Where Godot logs an error and goes on, cl-astar signals one. Godot gives the origin as the nearest position on a segment of a graph with none, and leaves out points and segments further than 10^10 from the position it is given; cl-astar gives NIL, and leaves nothing out. A grid made with make-grid is up to date, its cells made.

Threads

A graph or a grid is used from one thread at a time, finding paths included, since a search keeps its state in the graph or grid it searches. Different graphs and grids may be used from different threads at once.

Errors

Errors are astar-error conditions, such as a path asked for from a point a graph lacks, a cell outside a grid's region, a dirty grid's cells, or a negative cost from a method. Arguments of the wrong type are type-error conditions.

Tests

stift test

tests/godot-answers.txt holds Godot 4.7.2's answers to the random cases tests/godot-test.lisp makes, which the suite compares with cl-astar's. To ask a Godot of another version, write the cases and run tools/godot-answers.gd:

(asdf:load-system "cl-astar/test")
(cl-astar/test:write-godot-cases "cases.txt")

godot --headless --script tools/godot-answers.gd -- cases.txt tests/godot-answers.txt

Licence

MIT. See LICENSE.