cl-astar

0.0.4

A heavily optimized yet flexible A* pathfinding algorithm implementation

System Information

Version: 0.0.4

Dependencies:

Author: Andrew Kravchuk

License: MIT

Homepage: https://gitlab.com/lockie/cl-astar

Definition Index

CL-ASTAR
- A*
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＊ 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 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:
```
(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.
- EXTERNAL TYPE-DEFINITION
  FLOAT-COORDINATE
  
  Source
  A floating-point coordinate type suitable for use with ENCODE-FLOAT-COORDINATES and DECODE-FLOAT-COORDINATES.
- EXTERNAL TYPE-DEFINITION
  INTEGER-COORDINATE
  
  Source
  An integer coordinate type suitable for use with ENCODE-INTEGER-COORDINATES and DECODE-INTEGER-COORDINATES.
- EXTERNAL FUNCTION
  DECODE-FLOAT-COORDINATES
  
  VALUE
  
  Source
  An implementation of decoder that unpacks floating-point coordinates from single FIXNUM using dirty bit tricks.
  
  See FLOAT-COORDINATE
- EXTERNAL FUNCTION
  DECODE-INTEGER-COORDINATES
  
  VALUE
  
  Source
  An implementation of decoder that unpacks integer coordinates from single FIXNUM using dirty bit tricks.
  
  See INTEGER-COORDINATE
- EXTERNAL FUNCTION
  ENCODE-FLOAT-COORDINATES
  
  X
  
  Y
  
  Source
  An implemetation of encoder that fits given floating-point coordinates into single FIXNUM using dirty bit tricks.
  
  See FLOAT-COORDINATE
- EXTERNAL FUNCTION
  ENCODE-INTEGER-COORDINATES
  
  X
  
  Y
  
  Source
  An implemetation of encoder that fits given integer coordinates into single FIXNUM using dirty bit tricks.
  
  See INTEGER-COORDINATE
- EXTERNAL FUNCTION
  GOAL-REACHED-EXACT-P
  
  X
  
  Y
  
  GOAL-X
  
  GOAL-Y
  
  Source
  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.
- EXTERNAL MACRO
  DEFINE-PATH-FINDER
  
  NAME
  
  &REST
  
  PARAMETERS
  
  &KEY
  
  WORLD-SIZE
  
  FRONTIER-SIZE
  
  COORDINATE-TYPE
  
  COORDINATE-ENCODER
  
  COORDINATE-DECODER
  
  INDEXER
  
  GOAL-REACHED-P
  
  NEIGHBOUR-ENUMERATOR
  
  EXACT-COST
  
  HEURISTIC-COST
  
  MAX-MOVEMENT-COST
  
  PATH-INITIATOR
  
  PATH-PROCESSOR
  
  PATH-FINALIZER
  
  VARIABLES
  
  &BODY
  
  DECLARATIONS-AND-DOCSTRING
  
  Source
  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). 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 (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 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.
  
  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 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).
- EXTERNAL MACRO
  MAKE-4-DIRECTIONS-ENUMERATOR
  
  &KEY
  
  NODE-WIDTH
  
  NODE-HEIGHT
  
  MIN-X
  
  MIN-Y
  
  MAX-X
  
  MAX-Y
  
  Source
  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.
- EXTERNAL MACRO
  MAKE-8-DIRECTIONS-ENUMERATOR
  
  &KEY
  
  NODE-WIDTH
  
  NODE-HEIGHT
  
  MIN-X
  
  MIN-Y
  
  MAX-X
  
  MAX-Y
  
  Source
  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.
- EXTERNAL MACRO
  MAKE-COLUMN-MAJOR-INDEXER
  
  HEIGHT
  
  &KEY
  
  NODE-WIDTH
  
  NODE-HEIGHT
  
  Source
  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).
- EXTERNAL MACRO
  MAKE-EUCLIDEAN-DISTANCE-HEURISTIC
  
  &OPTIONAL
  
  SCALE-FACTOR
  
  Source
  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.
- EXTERNAL MACRO
  MAKE-MANHATTAN-DISTANCE-HEURISTIC
  
  &OPTIONAL
  
  SCALE-FACTOR
  
  Source
  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
- EXTERNAL MACRO
  MAKE-OCTILE-DISTANCE-HEURISTIC
  
  &OPTIONAL
  
  SCALE-FACTOR
  
  Source
  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
- EXTERNAL MACRO
  MAKE-ROW-MAJOR-INDEXER
  
  WIDTH
  
  &KEY
  
  NODE-WIDTH
  
  NODE-HEIGHT
  
  Source
  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).