A heavily optimized yet flexible A* pathfinding algorithm implementation

cl-astar

#+HTML: <p align="center"><img src="https://gitlab.com/lockie/cl-astar/-/raw/main/docs/logo.svg" width="64px" /></p>

* cl-astar
[[https://gitlab.com/lockie/cl-astar/-/pipelines/main/latest][https://img.shields.io/gitlab/pipeline-status/lockie/cl-astar?label=tests&style=flat&extension=.png]] [[https://gitlab.com/lockie/cl-astar/-/commits/develop][https://img.shields.io/gitlab/last-commit/lockie/cl-astar?ref=develop&style=flat&extension=.png]] [[https://gitlab.com/lockie/cl-astar/-/tags][https://img.shields.io/gitlab/v/tag/lockie/cl-astar?label=version&style=flat&extension=.png]] [[https://gitlab.com/lockie/cl-astar/-/blob/main/LICENSE][https://img.shields.io/gitlab/license/lockie/cl-astar?color=blue&style=flat&extension=.png]] [[https://functional.cafe/@awkravchuk][https://img.shields.io/mastodon/follow/109994839335624904?color=858AFA&domain=https%3A%2F%2Ffunctional.cafe&label=follow%20on%20mastodon&logo=mastodon&style=flat&extension=.png]]

*NOTE: this software is of alpha quiality, 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.

[[https://en.wikipedia.org/wiki/A%2A_search_algorithm][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 [[https://theory.stanford.edu/~amitp/GameProgramming][Amit's A* Pages]] which is
amazing resource on A* algorithm.

See the [[https://lockie.gitlab.io/cl-astar][documentation page]] for more details.

** Installation
For now, you'll have to install [[http://dist.luckylambda.technology/releases/lucky-lambda/][LuckyLambda]] Quicklisp distribution (assuming
you have [[https://quicklisp.org][Quicklisp]] installed) by executing the following in your Lisp :
#+begin_src lisp
  (ql-dist:install-dist "http://dist.luckylambda.technology/releases/lucky-lambda.txt")
#+end_src

Alternatively, just clone this repository to your [[http://blog.quicklisp.org/2018/01/the-quicklisp-local-projects-mechanism.html][Quicklisp's local-projects]]
directory.

Finally, execute ~(ql:quickload :cl-astar)~ in your Lisp.

The library is optimized for SBCL, and currently the test suite succeeds only
with SBCL under Linux and Windows. However, the library is likely to properly
function with other CL implementations. Note that supplied floating point
coordinate mechanisms will work corretly only on implementations having at
least 60 bit wide =FIXNUM= (those unfortunately do not include ABCL and
CLISP). Integer coordinates should work everywhere though.

** Usage
#+begin_src 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))
#+end_src

Also have a look at =tests/paths.lisp= for more usage examples.

** Benchmark
The following table shows average run time of pathfinding function in seconds
for different random maze sizes (see =benchmark.lisp=). The benchmark was run
under Linux on AMD Ryzen 5 3600X.

| Compiler          |    10x10 |    20x20 |   50x50 | 100x100 | 200x200 | 500x500 | 1000x1000 |
|-------------------+----------+----------+---------+---------+---------+---------+-----------|
| SBCL 2.4.6        | 0.000006 | 0.000013 | 0.00022 | 0.00091 |  0.0041 |   0.013 |     0.034 |
| Clozure CL 1.12.2 | 0.000048 | 0.000115 | 0.00192 | 0.00809 |  0.0337 |   0.104 |   crashed |
| ABCL 1.9.2        | 0.000326 | 0.000753 | 0.01304 | 0.05491 |  0.2355 |   0.739 |     1.787 |
| Allegro CL 10.1   | 0.000118 | 0.000249 | 0.00444 | 0.01853 |  0.0759 |   0.235 |     0.551 |

A few takeaways:
+ This implementation of A* running on SBCL outperforms even C++
  implementations, at least the ones for which I was able to find performance
  numbers ([[https://stackoverflow.com/a/23779490/1336774][1]], [[https://stackoverflow.com/a/17438557/1336774][2]]). You can have a look at impressively sleek assembly produced
  by SBCL for ~FIND-PATH~ function [[https://gitlab.com/lockie/cl-astar/-/snippets/3734066][here]].
+ Allegro CL is surprisingly bad at optimizing nested inline closures.
+ When using A* for a videogame and you want to find paths in game world bigger
  than roughly 100x100 tiles (e.g. 3200 by 3200 pixels considering single tile
  to be 32x32), consider chunking your world and running pathfinding in
  separate chunks rather than in whole game world itself.

** Roadmap
See [[https://gitlab.com/lockie/cl-astar/-/blob/develop/TODO.org][TODO.org]].

** Games made using cl-astar
+ [[https://awkravchuk.itch.io/cycle-of-evil][Cycle of Evil]]
+ [[https://gitlab.com/lockie/cl-astar/-/issues/new][add your own game to this list!]]

** Contributing
Merge requests are welcome, just please submit them against the =develop=
branch. For major changes, please [[https://gitlab.com/lockie/cl-astar/-/issues/new][open an issue]] first to discuss what you would
like to change.

** Copyright
Copyright (C) 2024 Andrew Kravchuk <awkravchuk@gmail.com>

Priority queue implementation included with this library:
+ [[https://github.com/austinhaas/pettomato-indexed-priority-queue][Copyright (C) 2012 Austin Haas <austin@pettomato.com>]]
+ [[https://github.com/aimacode/aima-lisp][Copyright (C) 1998–2002 Peter Norvig <peter@norvig.com>]]

** License
[[https://choosealicense.com/licenses/mit][MIT]]


cl-astar

Upstream URL

Author

License

cl-astar

Version:

License:

Authors:

Dependencies:

cl-astar/tests

License:

Authors:

Dependencies:

Dependencies (5)

Dependents (0)