This is the cl-astar Reference Manual, version 0.0.2, generated automatically by Declt version 4.0 beta 2 "William Riker" on Sun Dec 15 04:40:11 2024 GMT+0.
The main system appears first, followed by any subsystem dependency.
cl-astarA heavily optimized yet flexible A* pathfinding algorithm implementation
Andrew Kravchuk <awkravchuk@gmail.com>
MIT
0.0.2
let-plus (system).
alexandria (system).
float-features (system).
trivial-adjust-simple-array (system).
src (module).
Modules are listed depth-first from the system components tree.
cl-astar/srccl-astar (system).
package.lisp (file).
priority-queue.lisp (file).
main.lisp (file).
Files are sorted by type and then listed depth-first from the systems components trees.
cl-astar/cl-astar.asdcl-astar/src/package.lispcl-astar/src/priority-queue.lispcl-astar/src/main.lispcl-astar/src/priority-queue.lispsrc (module).
copy-q (function).
heapify (function).
improve-key (function).
left (function).
make-q (function).
make-queue (function).
new-capacity (function).
parent (function).
q (structure).
q-items (reader).
(setf q-items) (writer).
q-p (function).
q-priorities (reader).
(setf q-priorities) (writer).
q-size (reader).
(setf q-size) (writer).
queue-empty-p (function).
queue-insert (function).
queue-pop (function).
right (function).
cl-astar/src/main.lispsrc (module).
decode-float-coordinates (function).
decode-integer-coordinates (function).
define-path-finder (macro).
encode-float-coordinates (function).
encode-integer-coordinates (function).
float-coordinate (type).
goal-reached-exact-p (function).
integer-coordinate (type).
make-4-directions-enumerator (macro).
make-8-directions-enumerator (macro).
make-column-major-indexer (macro).
make-euclidean-distance-heuristic (macro).
make-manhattan-distance-heuristic (macro).
make-octile-distance-heuristic (macro).
make-row-major-indexer (macro).
%lambda-expr-p (function).
%parse-body (function).
%required-argument (macro).
&stack (macro).
&wrapper (macro).
*coordinate-type* (special variable).
+bits-per-coordinate+ (constant).
+bits-per-float-exponent+ (constant).
+bits-per-float-significand+ (constant).
+least-float-coordinate+ (constant).
+most-float-coordinate+ (constant).
Packages are listed by definition order.
cl-astar**NOTE: this software is of alpha quality, and the API is
subject to change.**
‘cl-astar‘ is a Common Lisp library providing heavily optimized yet flexible
A* pathfinding algorithm implementation for 2-dimensional spaces.
[A＊](https://en.wikipedia.org/wiki/A%2A_search_algorithm) is the most popular
algorithm choice for pathfinding in video games and other applications,
because it’s fairly flexible and can be used in a wide range of
contexts. For more information, refer to
[Amit’s A* Pages](https://theory.stanford.edu/~amitp/GameProgramming) which is
amazing resource on this algorithm.
Despite being quite flexible, this library does some assumptions about the path
finding task, namely:
- the world to navigate in could be represented as a graph of discrete *nodes*
having some positions, some of which are neighbours to other nodes (think
rectangular map tiles);
- node position within the world is represented by 2D coordinates
(think pixel ‘X‘ & ‘Y‘ coordinates);
- this pair of coordinates can fit into single ‘FIXNUM‘ (that is, about 60
bits on most modern CL implementations, so about 30 bits of information, or
on the order of 10⁹ different states per values of ‘X‘ and ‘Y‘);
- there is cost of moving from one node to another, quantified by a
non-negative floating-point number;
- the cost of moving from given node to its neighbouring node could always be
exactly determined;
- the cost of moving from one arbitrary node to another could be at least
heuristically determined (by e.g. measuring distance between them).
A heart of this library is ‘DEFINE-PATH-FINDER‘ macro which defines (in terms
of ‘DEFUN‘) the function to find the path given your constraints, goal
reaching conditions and cost functions, and to process found path the way you
need. Hence one might even call this library a *microframework*.
Here’s its usage example that finds path in 10×10 maze which is
represented by 2D array with obstacles denoted by star character and empty
cells by space character:
“‘language-lisp
(ql:quickload :cl-astar)
(defconstant maze (make-array ’(10 10)
:element-type ’character
:initial-contents ’(" * * "
"* * * * * "
"* * * * * "
"* * * * * "
"* * * * * "
"* * * * * "
"* * * * * "
"* * * * * "
"* * * * * "
"* * * ")))
(defconstant width (second (array-dimensions maze)))
(defconstant height (first (array-dimensions maze)))
(a*:define-path-finder find-path ()
(:variables ((result (alexandria:copy-array maze)))
:world-size (* width height)
:coordinate-type a*:integer-coordinate
:coordinate-encoder a*:encode-integer-coordinates
:coordinate-decoder a*:decode-integer-coordinates
:indexer (a*:make-row-major-indexer width)
:goal-reached-p a*:goal-reached-exact-p
:neighbour-enumerator (a*:make-4-directions-enumerator
:max-x width :max-y height)
:exact-cost (lambda (x1 y1 x2 y2)
(declare (ignorable x1 y1))
(if (eql (aref maze y2 x2) #\Space)
0.0
most-positive-single-float))
:heuristic-cost (a*:make-manhattan-distance-heuristic)
:path-processor (lambda (x y) (setf (aref result y x) #\x))
:path-finalizer (lambda () result)))
(print (find-path 0 0 9 9))
“‘
The documentation for the symbols exported from the ‘CL-ASTAR‘ package can be found below.
a*
common-lisp.
let-plus.
trivial-adjust-simple-array.
decode-float-coordinates (function).
decode-integer-coordinates (function).
define-path-finder (macro).
encode-float-coordinates (function).
encode-integer-coordinates (function).
float-coordinate (type).
goal-reached-exact-p (function).
integer-coordinate (type).
make-4-directions-enumerator (macro).
make-8-directions-enumerator (macro).
make-column-major-indexer (macro).
make-euclidean-distance-heuristic (macro).
make-manhattan-distance-heuristic (macro).
make-octile-distance-heuristic (macro).
make-row-major-indexer (macro).
%lambda-expr-p (function).
%parse-body (function).
%required-argument (macro).
&stack (macro).
&wrapper (macro).
*coordinate-type* (special variable).
+bits-per-coordinate+ (constant).
+bits-per-float-exponent+ (constant).
+bits-per-float-significand+ (constant).
+least-float-coordinate+ (constant).
+most-float-coordinate+ (constant).
copy-q (function).
heapify (function).
improve-key (function).
left (function).
make-q (function).
make-queue (function).
new-capacity (function).
parent (function).
q (structure).
q-items (reader).
(setf q-items) (writer).
q-p (function).
q-priorities (reader).
(setf q-priorities) (writer).
q-size (reader).
(setf q-size) (writer).
queue-empty-p (function).
queue-insert (function).
queue-pop (function).
right (function).
Definitions are sorted by export status, category, package, and then by lexicographic order.
Defines a function with ‘NAME‘ that takes four values of
‘COORDINATE-TYPE‘ (coordinates of start and goal nodes) and arbitrary number of
keyword parameters specified in ‘PARAMETERS‘ list. The function would return
the value returned by ‘PATH-FINALIZER‘ function (‘T‘ by default, see below) or
‘NIL‘ if a path from start to goal node could not be found. One can also supply
local declarations and docstring for the function being defined using the
‘DECLARATIONS-AND-DOCSTRING‘ argument.
To adjust the resulting function to your needs, you should specify the
following arguments to the macro:
- ‘WORLD-SIZE‘: expression for node count in the world, could be variable;
calculated only once per function invocation.
- ‘FRONTIER-SIZE‘: initial A* frontier size (see
[here](https://redblobgames.com/pathfinding/a-star/introduction.html#breadth-first-search)).
Default value of 500 is more than enough for sane cases and makes it fit
into single memory page, which might or might not improve performance.
- ‘COORDINATE-TYPE‘: type of coordinate that meets the aforementioned
assumptions. There are predefined integer and floating-point types
‘INTEGER-COORDINATE‘ and ‘FLOAT-COORDINATE‘ that can be used
here. Floating-point coordinate type makes sense for use with
e.g. [liballegro](https://github.com/resttime/cl-liballegro) (where pixels do
in fact have floating-point coordinates), integer type makes sense for other
graphic backends and simple cases where the nodes are just stored in an
array. Defaults to ‘FLOAT-COORDINATE‘.
- ‘COORDINATE-ENCODER‘: expression evaluating to lambda expression, or unquoted
symbol denoting (preferably inline) function that takes two coordinates of
‘COORDINATE-TYPE‘ and returns single ‘FIXNUM‘ representing those
coordinates. Defaults to ‘ENCODE-FLOAT-COORDINATES‘.
- ‘COORDINATE-DECODER‘: expression evaluating to lambda expression, or unquoted
symbol denoting (preferably inline) function that takes single ‘FIXNUM‘ value
and unpacks it by returning two coordinates of ‘COORDINATE-TYPE‘ as multiple
‘VALUES‘. Defaults to ‘DECODE-FLOAT-COORDINATES‘.
- ‘INDEXER‘: expression evaluating to lambda expression, or unquoted symbol
denoting (preferably inline) function that takes two coordinates of
‘COORDINATE-TYPE‘ and returns index in some 1-dimensional array; the index
must be unique for the node containing those coordinates. The calls to
‘MAKE-ROW-MAJOR-INDEXER‘ or ‘MAKE-COLUMN-MAJOR-INDEXER‘ macros might be
suitable values of this argument for cases when nodes are uniform in size.
- ‘GOAL-REACHED-P‘: expression evaluating to lambda expression, or unquoted
symbol denoting (preferably inline) function that takes four values of
‘COORDINATE-TYPE‘ (coordinates of current and goal nodes) and returns boolean
indicating whether the goal node is reached by being in that current
node. ‘GOAL-REACHED-EXACT-P‘ could be used here.
- ‘NEIGHBOUR-ENUMERATOR‘: expression evaluating to lambda expression, or
unquoted symbol denoting (preferably inline) function that takes a current
coordinate (two values of ‘COORDINATE-TYPE‘) and a function of two arguments
of ‘COORDINATE-TYPE‘. ‘NEIGHBOUR-ENUMERATOR‘ should call given function with
coordinates of all neighbours of a node occupying given position. The call to
‘MAKE-4-DIRECTIONS-ENUMERATOR‘ or ‘MAKE-8-DIRECTIONS-ENUMERATOR‘ macros might
be suitable value of this argument for corresponding cases.
- ‘EXACT-COST‘: expression evaluating to lambda expression, or unquoted symbol
denoting (preferably inline) function that takes four values of
‘COORDINATE-TYPE‘ (coordinates of two neighbouring nodes) and returns
non-negative ‘SINGLE-FLOAT‘ corresponding to exact cost to move from one
given neighbouring node to another. Note that it should be at the same scale
as ‘HEURISTIC-COST‘. See
[here](http://theory.stanford.edu/~amitp/GameProgramming/MovementCosts.html)
for a discussion of movement cost functions.
- ‘HEURISTIC-COST‘: expression evaluating to lambda expression, or unquoted
symbol denoting (preferably inline) function that takes four values of
‘COORDINATE-TYPE‘ (coordinates of two arbitrary nodes) and returns
non-negative ‘SINGLE-FLOAT‘ corresponding to heuristic cost to move from one
given arbitrary node to another. Note that it should be at the same scale as
‘EXACT-COST‘. Setting this to ‘(CONSTANTLY 0.0)‘ turns A* into Dijkstra’s
algorithm. The call to one of ‘MAKE-MANHATTAN-DISTANCE-HEURISTIC‘,
‘MAKE-OCTILE-DISTANCE-HEURISTIC‘ or ‘MAKE-EUCLIDEAN-DISTANCE-HEURISTIC‘
macros might be suitable value of this argument. A good survey on different
heuristics could be found
[here](http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html).
- ‘MAX-MOVEMENT-COST‘: when any of two cost functions above return value
greater or equal to this, it means that the movement is impossible. Defaults
to ‘MOST-POSITIVE-SINGLE-FLOAT‘.
- ‘PATH-INITIATOR‘: expression evaluating to lambda expression, or unquoted
symbol denoting (preferably inline) function that is called once the path
was successfully found. It takes a single argument which is the count of
nodes along the found path, including start node and goal node. Note that
when the path is not found, this function isn’t called at all. Defaults to
‘IDENTITY‘.
- ‘PATH-PROCESSOR‘: expression evaluating to lambda expression, or unquoted
symbol denoting (preferably inline) function of two arguments of
‘COORDINATE-TYPE‘ that is successively called with coordinates of every node
along the path, including start node and goal node. Note that when the path
is not found, this function isn’t called at all.
- ‘PATH-FINALIZER‘: expression evaluating to lambda expression, or unquoted
symbol denoting (preferably inline) function of no arguments that is called
once after ‘PATH-PROCESSOR‘ has been called with all points in found
path. The return value of this function becomes the return value of path
finder function being defined. Note that when the path is not found, this
function isn’t called at all and defined path finder function returns
‘NIL‘. Defaults to ‘(CONSTANTLY T)‘.
‘VARIABLES‘ is a list of variable specifiers with optional initializers that
is put after
[‘＆AUX‘](https://lispworks.com/documentation/HyperSpec/Body/03_dae.htm)
keyword in parameter list of defined function. Those variables are available
to all lambda expressions listed above. Note that those lambda expressions can
also freely refer to variables ‘START-X‘, ‘START-Y‘, ‘GOAL-X‘, ‘GOAL-Y‘ passed
to the function being defined, as well as to all keyword parameters specified
in ‘PARAMETERS‘.
In terms of memory consumption, the defined function uses 12בFRONTIER-SIZE‘
bytes of stack memory every time it is called (note that frontier may grow for
big worlds and long paths) and 20בWORLD-SIZE‘ bytes of heap memory, but only
the first time, and every time ‘WORLD-SIZE‘ grows bigger (the storage arrays
are closed over the function and reused).
Constructs neighbour enumerator function suitable for use as ‘NEIGHBOUR-ENUMERATOR‘ argument to ‘DEFINE-PATH-FINDER‘ for the uniform node grid allowing movement in 4 directions (left, right, down, up). ‘NODE-WIDTH‘ and ‘NODE-HEIGHT‘ are constant values or constant expressions specifying the node size within the grid, both default to 1. ‘MIN-X‘, ‘MIN-Y‘, ‘MAX-X‘ and ‘MAX-Y‘ are values or expressions specifying the constraints for possible node coordinate values.
Constructs neighbour enumerator function suitable for use as
‘NEIGHBOUR-ENUMERATOR‘ argument to ‘DEFINE-PATH-FINDER‘ for the uniform node
grid allowing movement in 8 directions (two vertical, two horizontal and four
diagonal). ‘NODE-WIDTH‘ and ‘NODE-HEIGHT‘ are constant values or constant
expressions specifying the node size within the grid, both default to
1. ‘MIN-X‘, ‘MIN-Y‘, ‘MAX-X‘ and ‘MAX-Y‘ are values or expressions specifying
the constraints for possible node coordinate values.
Constructs indexer function suitable for use as ‘INDEXER‘ argument to ‘DEFINE-PATH-FINDER‘. The resulting function returns index according to world ‘WIDTH‘ (in nodes) and ‘NODE-WIDTH‘ and ‘NODE-HEIGHT‘ dimensions (both 1 by default).
Constructs heuristic cost function suitable for use as ‘HEURISTIC-COST‘ argument to ‘DEFINE-PATH-FINDER‘ based on Euclidean distance between two nodes. ‘SCALE-FACTOR‘ is constant expression to multiply the calculated distance by, defaulting to 1. Note that this kind of heuristic is best suited for grids allowing any direction of movement.
Constructs heuristic cost function suitable for use as ‘HEURISTIC-COST‘
argument to ‘DEFINE-PATH-FINDER‘ based on Manhattan distance between two
nodes. ‘SCALE-FACTOR‘ is constant expression to multiply the calculated
distance by, defaulting to 1. Note that this kind of heuristic is best suited
for grids allowing 4 directions of movement.
See ‘MAKE-4-DIRECTIONS-ENUMERATOR‘
Constructs heuristic cost function suitable for use as ‘HEURISTIC-COST‘
argument to ‘DEFINE-PATH-FINDER‘ based on octile distance between two
nodes. ‘SCALE-FACTOR‘ is constant expression to multiply the calculated
distance by, defaulting to 1. Note that this kind of heuristic is best suited
for grids allowing 8 directions of movement.
See ‘MAKE-8-DIRECTIONS-ENUMERATOR‘
Constructs indexer function suitable for use as ‘INDEXER‘ argument to ‘DEFINE-PATH-FINDER‘. The resulting function returns index according to world ‘WIDTH‘ (in nodes) and ‘NODE-WIDTH‘ and ‘NODE-HEIGHT‘ dimensions (both 1 by default).
An implementation of decoder that unpacks floating-point coordinates from
single ‘FIXNUM‘ using dirty bit tricks.
See ‘FLOAT-COORDINATE‘
An implementation of decoder that unpacks integer coordinates from single
‘FIXNUM‘ using dirty bit tricks.
See ‘INTEGER-COORDINATE‘
An implemetation of encoder that fits given floating-point coordinates into
single ‘FIXNUM‘ using dirty bit tricks.
See ‘FLOAT-COORDINATE‘
An implemetation of encoder that fits given integer coordinates into single
‘FIXNUM‘ using dirty bit tricks.
See ‘INTEGER-COORDINATE‘
An implementation of goal reached predicate that checks whether given
position is identical to the goal postion.
**NOTE**: this is most likely to work when goal coordinate is multiple of node (e.g. map tile) size.
Number of bits in ‘INTEGER-COORDINATE‘.
A minimum value ‘FLOAT-COORDINATE‘ can take. Values smaller than this (except zero) would lead to underflows.
A maximum value ‘FLOAT-COORDINATE‘ can take. Values greater than this would lead to overflows.
Assume that the children of i are heaps, but that heap[i] may be worse than its children. If it is, move heap[i] down where it belongs. [Page 130 CL&R 2nd ed.].
The item at i may be better than its parent. Promote the item until it is in the correct position.
Are there no items in the queue?
Insert the item by priority according to the compare function. Returns the queue. [Page 140 CL&R 2nd ed.].
Remove the element from the front of the queue and return it. Returns NIL if the queue is empty. [Page 139 CL&R 2nd ed.].
| Jump to: | %
&
(
C D E F G H I L M N P Q R |
|---|
| Jump to: | %
&
(
C D E F G H I L M N P Q R |
|---|
| Jump to: | *
+
C I P S |
|---|
| Jump to: | *
+
C I P S |
|---|
| Jump to: | C F I M P Q S T |
|---|
| Jump to: | C F I M P Q S T |
|---|