cl-astar

cl-astar finds the cheapest path between two places with A*, as Godot's AStar2D and AStarGrid2D do: across a graph of points of your own and the connections between them, or across a grid of cells, some of them solid. Of several equally cheap paths, it finds the one Godot 4.7 finds. It knows nothing of a game engine, and depends on nothing.

(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)

What it gives you

• Graphs. Points with ids of your choosing, positions and weight scales, connected both ways or one, some disabled as obstacles; the cheapest path between two points, or a partial path to the reachable point nearest an unreachable one; the nearest point or position on a connection to a place.
• Grids. A region of cells, square or diamond, some solid and some dearer to enter; paths that move diagonally as one of four modes allows, measured by one of four heuristics, and jump point search for open ground.
• Costs of your own. A subclass measures the cost of a move and the estimate to the end its own way, with methods, and can rule moves out.
• Godot's paths. Costs are added up in single floats in Godot's order, and the open list breaks ties as Godot's does, so a game ported from Godot finds the same paths; the suite checks its answers against Godot 4.7.2's.
• No garbage. A search allocates nothing but the path it returns.

Pages

Page	What it covers
Getting Started	Requirements, loading, a first path, running the tests
Graphs	Points, connections, disabled points, nearest points, paths and partial paths
Grids	Regions, solid cells, weight scales, diagonal modes, heuristics, jumping, positions, updating
Costs of Your Own	Subclasses that compute costs and estimates, and filter moves
Coming from Godot	Godot's names, and where cl-astar differs
Threads	What may be shared between threads
Errors	astar-error, and what each message means
API Reference	Every exported symbol

Used by

Games made with Pyssel, which list cl-astar in their own stiftfile. Pyssel itself does not depend on it.

Status

Built in step 26 of the engine's build order (part 26h), for games such as a tower defence's enemies finding their way. Godot's AStar3D is not here yet.

Licence

MIT. See LICENSE in the repository.