A* pathfinding with the LuaJIT FFI

[Steven Johnson <steve@...>]

In addition to simplex noise, I've played around with a 2D, grid-
based A* implementation using the FFI, based on
an adaptation of [1] I inherited a long while back, and replacing its
open list with the skew heap posted in [2] (LuaJIT REALLY seemed to
take to that). This code's a lot cleaner since most of the
experimental fare is gone, aside from the commented-out testing mess
at the end.

Because of its intended use case, it's a two-step process, where you
make a zone and populate it with walls (infrequent), then generate a
path over that (frequent). I tested this embedded, with a homebrew
GUI, so it might be more work to try out, but the code is all there,
anyway.

On a Core i7 2.67 / 2.79 GHz, to go from one corner to another in a 25x25
grid, the first GeneratePath() is 4 or 5 milliseconds. After that it
tends to fall to 2 or 3 or sometimes rise to 8 or 9. Starting in the
same quadrant I see about 2 or 3 milliseconds.

With a full-grid failure (fencing in the exit), I see about 60
milliseconds, then 30-something, then leveling off around 8 or 9.

With a relatively complicated maze I get about 75-80 milliseconds from
one corner to the other, then as it starts "learning" it levels off
around the 20s-30s.

Unfortunately, I have gotten a crash (based on the dumps, some time
after trace #189), which I'll try to narrow down. Anyhow, it's mostly
a toy for now. I may later add 3D (looks straightforward), incremental
path generation, etc. if the need arises.

-------------------------------------------------------------------------------------

I hope these are of interest to somebody. Again, code is submitted to the
public domain: MIT wherever possible, more restrictive license as any
of the sources demands (I didn't see anything). Improvements welcome.

[1] - http://www.koders.com/cpp/fid2FF7A5E2D2687EBB6166A4868357DB339AA6FCB8.aspx
[2] - http://lua-users.org/lists/lua-l/2008-03/msg00674.html

Attachment: Pathing.lua
Description: Binary data