pulsar.lua - another pathfinding lib
Posted: Sun Feb 12, 2012 5:26 pm
Hello ladies, and gentlemen (mostly gentlemen)!
I've been working on a pathfinding lib for AGES now. And it is still not finished!
But it's got a name. It's called
It also has got a demo! Here it is:
Some notes:
I have stolen lots of stuff from Amit's A* pages. Incredibly good resource!
The idea behind pulsar.lua was having something "interruptible". I wanted to be able to create a path finder, start it, and if it was taking too much time in the frame, stop it, and continue on the next frame. I've managed to create that so far - search is done "by steps". By default, the demo runs 10 steps per frame, which isn't much. But you can see how the frames are calculated (at least in my computer).
If you want to see it going as fast as it can, just remove the 10 from the finder:searchPath(10) line in game.lua ; it'll skip to the chase and show the complete path; it'll take much less time than before because drawing the grid is actually quite intensive. I think it is reasonably fast but the intent was not making it the fastest A* possible - other libs might be better suited to that task.
A nice byproduct of the "imperceptibility" is that you can always ask a finder for the best path he's found so far. It will probably not be the best path, but it can give you a good approximation in some cases. In the demo, these paths appear briefly in red. You can see them more clearly by making the destination inaccessible; a red path (going nowhere) will appear.
I also wanted to make the lib flexible, not tied to square grids only. I think so far, I have succeeded on that front, too. The lib has a section for square grids, since they are the most usual ones, but one could use it for other kinds of grids.
Another objective I have is being able to recalculate parts of the node set without having to re-create the whole thing from scratch - for example, to handle an open/closed door better. I still haven't done this, but I have a pretty clear idea about how to do it.
I want to explore the possibility of moving "backwards" from the destination in addition to "forward" from the origin. This can potentially make the "open/closed door recalculation" even more useful.
I also want to implement Jump Point Search, simply because it is very cool.
I'd like to include some "path beautifier" function(s), too, so that the resulting paths look a bit more "natural".
Finally, I have to include tests for lots of stuff. For this lib, I decided to go "cowboy style" after not being able to advance much using TDD. But I plan to include tests "backwards", now that I understand the algorithm better, and have understood how to "split it into parts".
So, as you can see, there is a long road ahead until I reach 1.0; so for now it's on 0.5. But the demo works very well; please do try it.
PD: By default, the movement is only up-down-left-right, and the heuristic used is the manhattan distance. It's very simple to change that to "eight-directions" movement, and the diagonal heuristic. I'll leave that as an exercise for the reader.
I've been working on a pathfinding lib for AGES now. And it is still not finished!
But it's got a name. It's called
It also has got a demo! Here it is:
Some notes:
I have stolen lots of stuff from Amit's A* pages. Incredibly good resource!
The idea behind pulsar.lua was having something "interruptible". I wanted to be able to create a path finder, start it, and if it was taking too much time in the frame, stop it, and continue on the next frame. I've managed to create that so far - search is done "by steps". By default, the demo runs 10 steps per frame, which isn't much. But you can see how the frames are calculated (at least in my computer).
If you want to see it going as fast as it can, just remove the 10 from the finder:searchPath(10) line in game.lua ; it'll skip to the chase and show the complete path; it'll take much less time than before because drawing the grid is actually quite intensive. I think it is reasonably fast but the intent was not making it the fastest A* possible - other libs might be better suited to that task.
A nice byproduct of the "imperceptibility" is that you can always ask a finder for the best path he's found so far. It will probably not be the best path, but it can give you a good approximation in some cases. In the demo, these paths appear briefly in red. You can see them more clearly by making the destination inaccessible; a red path (going nowhere) will appear.
I also wanted to make the lib flexible, not tied to square grids only. I think so far, I have succeeded on that front, too. The lib has a section for square grids, since they are the most usual ones, but one could use it for other kinds of grids.
Another objective I have is being able to recalculate parts of the node set without having to re-create the whole thing from scratch - for example, to handle an open/closed door better. I still haven't done this, but I have a pretty clear idea about how to do it.
I want to explore the possibility of moving "backwards" from the destination in addition to "forward" from the origin. This can potentially make the "open/closed door recalculation" even more useful.
I also want to implement Jump Point Search, simply because it is very cool.
I'd like to include some "path beautifier" function(s), too, so that the resulting paths look a bit more "natural".
Finally, I have to include tests for lots of stuff. For this lib, I decided to go "cowboy style" after not being able to advance much using TDD. But I plan to include tests "backwards", now that I understand the algorithm better, and have understood how to "split it into parts".
So, as you can see, there is a long road ahead until I reach 1.0; so for now it's on 0.5. But the demo works very well; please do try it.
PD: By default, the movement is only up-down-left-right, and the heuristic used is the manhattan distance. It's very simple to change that to "eight-directions" movement, and the diagonal heuristic. I'll leave that as an exercise for the reader.