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