<story><title>A* search: optimized implementation in Lisp</title><url>https://gitlab.com/lockie/cl-astar</url></story><parent_chain></parent_chain><comment><author>Jach</author><text>I like this author&amp;#x27;s work on fast game structures for Lisp, shows what you can do if you&amp;#x27;re willing to do a bit of work on explicit types and so on. It&amp;#x27;s not obvious from the readme but the trivial-benchmark code includes details like time spent in the garbage collector (0 for this) and memory allocated, not just wall clock time. If he wants to do more interesting benchmarks, a standard set to use includes &lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;movingai.com&amp;#x2F;benchmarks&amp;#x2F;grids.html&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;movingai.com&amp;#x2F;benchmarks&amp;#x2F;grids.html&lt;/a&gt; which includes some maps from real games.&lt;p&gt;It&amp;#x27;s quite a bit faster than my Lisp version, at least, though mine&amp;#x27;s an unoptimized (lots of lists) incompletely ported C++ version. Tempted to dig out the C++ version and compare since it was pretty fast... I originally ported it to make a joke about a vtuber&amp;#x27;s long neck: &lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;pbs.twimg.com&amp;#x2F;media&amp;#x2F;FAJQkskVQAoiGlT?format=png&amp;amp;name=orig&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;pbs.twimg.com&amp;#x2F;media&amp;#x2F;FAJQkskVQAoiGlT?format=png&amp;amp;name=...&lt;/a&gt; (Edit: screenshot from C++ version: &lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;www.thejach.com&amp;#x2F;imgs&amp;#x2F;visibility_with_astar.png&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;www.thejach.com&amp;#x2F;imgs&amp;#x2F;visibility_with_astar.png&lt;/a&gt; Note how the shorter path would be going through the central chamber, but visibility is high there, so it goes down the corridors. Original had lots of extra features like fog of war, visibility tests&amp;#x2F;terrain analysis, smoothing and rubber-banding, a Floyd-Warshall implementation...)</text></comment>
<story><title>A* search: optimized implementation in Lisp</title><url>https://gitlab.com/lockie/cl-astar</url></story><parent_chain></parent_chain><comment><author>mark_l_watson</author><text>I love seeing highly optimized Common Lisp code like this.&lt;p&gt;I implemented A* in Common Lisp for my Springer Verlag AI book (1998), so a bit of nostalgia for me.&lt;p&gt;SBCL is really an amazing ecosystem and I argue that it is a great example of the power of open source.</text></comment>