lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]

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,

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] -
[2] -

Attachment: Pathing.lua
Description: Binary data