Getting Started

Requirements

• SBCL. cl-astar is plain Common Lisp: it needs no foreign library and no other Lisp library.
• For the tests: stift, which fetches Parachute, pinned by commit in the stiftfile.

A game made with Pyssel that finds paths lists cl-astar in its own stiftfile, beside Pyssel, and in its system's :depends-on.

Loading

(asdf:load-system :cl-astar)

(defpackage #:example
  (:use #:cl)
  (:local-nicknames (#:astar #:cl-astar)))
(in-package #:example)

The examples in this wiki use the nickname astar for cl-astar.

A first path

(let ((grid (astar:make-grid :region '(0 0 5 4) :diagonal-mode :never)))
  (astar:fill-solid-region grid '(2 0 1 3))      ; a wall, open at the bottom
  (list (astar:cell-path grid 0 0 4 0)
        (astar:cell-path grid 0 0 2 1)
        (astar:cell-path grid 0 0 2 1 :allow-partial-path t)))
;; => (#2A((0 0) (1 0) (1 1) (1 2) (1 3) (2 3) (3 3) (3 2) (3 1) (3 0) (4 0))
;;     #2A()
;;     #2A((0 0) (1 0) (1 1)))

1. make-grid makes a grid of the cells of a region, a list (X Y WIDTH HEIGHT): here 5 columns and 4 rows from 0, 0. Its cells are made at once, none solid. :diagonal-mode :never keeps paths to rows and columns.
2. fill-solid-region makes the cells of a rectangle solid: a wall down column 2, three cells high.
3. cell-path returns the cells of the cheapest path, as an array of a row of X and Y for each, from the first cell to the last: around the wall's end.
4. No path ends at a solid cell, so the path to the wall's cell 2, 1 is empty, an array of no rows...
5. ...unless :allow-partial-path asks for the path to the reachable cell nearest it.

cell-point-path returns the cells' positions instead, as the grid's cell size and offset place them. For points of your own instead of cells, see Graphs.

Running the tests

stift test

CI runs the suite on SBCL, on Linux. It compares cl-astar's answers to random graphs and grids with Godot 4.7.2's, which tests/godot-answers.txt holds; see Coming from Godot.