Quickdocs

cl-astar

2024-10-12

A heavily optimized yet flexible A* pathfinding algorithm implementation

Upstream URL

Author

Andrew Kravchuk <[email protected]>

License

MIT

README

Provided Systems

1cl-astar

https://img.shields.io/gitlab/pipeline-status/lockie/cl-astar?label=tests&style=flat&extension=.png https://img.shields.io/gitlab/last-commit/lockie/cl-astar?ref=develop&style=flat&extension=.png https://img.shields.io/gitlab/v/tag/lockie/cl-astar?label=version&style=flat&extension=.png https://img.shields.io/gitlab/license/lockie/cl-astar?color=blue&style=flat&extension=.png 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.

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 A* algorithm.

See the documentation page for more details.

1.1Installation

For now, you'll have to install LuckyLambda Quicklisp distribution (assumingyou have Quicklisp installed) by executing the following in your Lisp :

  (ql-dist:install-dist "http://dist.luckylambda.technology/releases/lucky-lambda.txt")

Alternatively, just clone this repository to your 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.

1.2Usage

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

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

1.3Benchmark

The following table shows average run time of pathfinding function in secondsfor different random maze sizes (see benchmark.lisp). The benchmark was rununder 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 performancenumbers (1, 2). You can have a look at impressively sleek assembly producedby SBCL for FIND-PATH function 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 biggerthan roughly 100x100 tiles (e.g. 3200 by 3200 pixels considering single tileto be 32x32), consider chunking your world and running pathfinding inseparate chunks rather than in whole game world itself.

1.4Roadmap

See TODO.org.

1.5Games made using cl-astar

1.6Contributing

Merge requests are welcome, just please submit them against the developbranch. For major changes, please open an issue first to discuss what you wouldlike to change.