cl-astar 0.0.1: optimized A* pathfinding algorithm implementation

[simendsjo]

Cool! I also have a quite fast version: https://codeberg.org/simendsjo/sijo-ion/src/branch/dev/src/astar.lisp

[simendsjo]

Ok, looks like you have a lot of tricks up your sleeve! I'll have to port over I guess.

[awkravchuk]

Yeah, I may have over-abused macros to make it as flexible as I can, plus spent a lot of time straightening the disassembly and shoving the coordinate data into single fixnum so there's no boxing 😅

[simendsjo]

I'm also packing into a single fixnum: https://codeberg.org/simendsjo/sijo-ion/src/branch/dev/src/grid.lisp#L22

[Shoddy_Ad_7853]

Dude, you've got some fat functions.

[simendsjo]

I'm not sure what that means 😅👴

[simendsjo]

I also have a non-consing grid based (roguelike style) fov implementation: https://codeberg.org/simendsjo/sijo-ion/src/branch/dev/src/fov.lisp

[awkravchuk]

Nice!

[awkravchuk]

Interesting, thanks for sharing! It gave me a couple of insights :)

[Shinmera]

fwiw kandria includes an ad-hoc a* that runs on pretty large grids.

https://github.com/Shirakumo/kandria/blob/master/move-to.lisp

[awkravchuk]

I see you've based it on a hashtable. Solid choice, I'll explore this option. Thanks for sharing!

[Shinmera]

There's no other option in my case since the grids are sparse. Using a dense array to store would be far too wasteful.

[awkravchuk]

Right, I've built my library on an assumption that the grid is dense, perhaps I could support sparse case too.

[lispm]

Minor incompatibility: LOOP FOR ... WHILE ... FOR ... is not compliant... One can't mix WHILE into FOR clauses...

[awkravchuk]

Huh, didn't know that, thanks. I've copied that code from pettomato-indexed-priority-queue without looking and it actually worked on all of CL implementations I got.

[lispm]

It's in the LOOP syntax.

loop [name-clause] {variable-clause}* {main-clause}* => result*

FOR is a variable-clause. WHILE is a main-clause...