pulsar.lua - another pathfinding lib

Showcase your libraries, tools and other projects that help your fellow love users.
User avatar
kikito
Inner party member
Posts: 3153
Joined: Sat Oct 03, 2009 5:22 pm
Location: Madrid, Spain
Contact:

pulsar.lua - another pathfinding lib

Post by kikito »

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
pulsar.lua.png
pulsar.lua.png (12.87 KiB) Viewed 7921 times
It also has got a demo! Here it is:
pulsar-demo.love
demo for v0.5
(12.9 KiB) Downloaded 660 times
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.
When I write def I mean function.
coffee
Party member
Posts: 1206
Joined: Wed Nov 02, 2011 9:07 pm

Re: pulsar.lua - another pathfinding lib

Post by coffee »

Hi kikito, even that is in early stage, is looking very good, congratulations for this new approach. I liked very much to see here the search working "realtime". A slower draw option to watch better the algorithms working would be awesome.
Last edited by coffee on Sun Feb 12, 2012 6:40 pm, edited 2 times in total.
User avatar
Robin
The Omniscient
Posts: 6506
Joined: Fri Feb 20, 2009 4:29 pm
Location: The Netherlands
Contact:

Re: pulsar.lua - another pathfinding lib

Post by Robin »

Neato!

Would it be possible to adapt the algorithm so that it wouldn't recalculate anything if unnecessary. For example, when adding an obstacle that isn't in the shortest path can't change what the shortest path is. And when you place an obstacle on the path, it wouldn't need to start all over, I think.
Help us help you: attach a .love.
User avatar
kikito
Inner party member
Posts: 3153
Joined: Sat Oct 03, 2009 5:22 pm
Location: Madrid, Spain
Contact:

Re: pulsar.lua - another pathfinding lib

Post by kikito »

coffee wrote:A slower draw option to watch better the algorithms working would be awesome
Actually, with cron.lua, doing an algorithm that does the resolution slowly would be quite easy, as there is a method called finder:step(). The difficult part would be drawing the interface for controlling that. I might need to include a more sophisticated ui lib, like quickie, to control the speed, etc. For now, try changing the line in game.lua to "finder:searchPath(1)" to get the slowest version.
coffee wrote:I think that either a animal, human or machine wouldn't behave like that.
Actually, a robot might move precisely like that. The path you are seeing is actually optimal - if you only can move up,down, left or right, that path gives you the smallest number of steps possible - count them!. It is however not the only optimal path; just one of them. Other paths are also optimal, and more "human-like". That is what I meant when I said that I wanted to investicate "path beautifiers"; making them a bit more "human". Paradoxically, making such paths actually takes longer than this approach.
Robin wrote:Would it be possible to adapt the algorithm so that it wouldn't recalculate anything if unnecessary. For example, when adding an obstacle that isn't in the shortest path can't change what the shortest path is. And when you place an obstacle on the path, it wouldn't need to start all over, I think.
That part should not be too difficult to do - the finder has a table called "nodes" holding the information it has on each of the studied cells - that's what's used to color the "yellow-blueish" cells. Any change on the rest of the cells (the ones that are "black" after the path has been calculated) would not affect the path. But any change on the "colored" cells would require recalculations. Right now, the closest they are to the destination, the less recalculations one has to do, since the finder goes "from the origin to the destination" - most of the path is unaltered that way. I want to investigate wether "searching from both ways at the same time" can help here. It might not help.

Another interesting question is - what happens if you move the origin or destination just one cell? Right now it means recalculating everything. Could the finder detect that, too? This would be very useful for moving entities.
When I write def I mean function.
coffee
Party member
Posts: 1206
Joined: Wed Nov 02, 2011 9:07 pm

Re: pulsar.lua - another pathfinding lib

Post by coffee »

kikito wrote:
Actually, a robot might move precisely like that. The path you are seeing is actually optimal - if you only can move up,down, left or right, that path gives you the smallest number of steps possible - count them!. It is however not the only optimal path; just one of them. Other paths are also optimal, and more "human-like". That is what I meant when I said that I wanted to investicate "path beautifiers"; making them a bit more "human". Paradoxically, making such paths actually takes longer than this approach.
Yes kikito. I regreted say that (so I edited and deleted my screenshot before your response) because my orange alternative wasn't following "your" L moves. So my orange diagonal was "cheating". After some counts I notice that your path won 1 move ahead, so robots probably would do this path. Sorry for taking early conclusions.
User avatar
MarekkPie
Inner party member
Posts: 587
Joined: Wed Dec 28, 2011 4:48 pm
Contact:

Re: pulsar.lua - another pathfinding lib

Post by MarekkPie »

Looks cool.

I am a bit confused with your claim on finding the "best path, so far" if you decide to interrupt the pathfinding. Do you mean that it will find the best path to the furthest searched node? Will it then branch from there to simply use the heuristic score to follow?

I did a paper on Jump Point Search (and by paper, I mean I read about it on the guy's website and wrote some BS on it.) If you stuck to orthogonal movement, it seems like it would be extremely easy to implement; it's the diagonal movement that starts confusing me.
User avatar
kikito
Inner party member
Posts: 3153
Joined: Sat Oct 03, 2009 5:22 pm
Location: Madrid, Spain
Contact:

Re: pulsar.lua - another pathfinding lib

Post by kikito »

MarekkPie wrote:Do you mean that it will find the best path to the furthest searched node? Will it then branch from there to simply use the heuristic score to follow?
Oh, it is nothing sophisticated. You already know that A* works by creating "nodes", one for each location(or cell) in the map. Each node has a "parent", which is the node from which it is "cheaper" to reach to the node. There is also a variable called "best node". Initially, the best node is close to the origin, and it gradually approaches the destination. When it reaches the destination, the "path" is built by parsing the "parents" successively, until you get back to the origin.

The "red paths" or "partial paths" are for those occasions on which the process took too long, and the best node didn't get to the destination; and yet you need a path. You can tell the finder "Ok. You are a failure and didn't get to the destination. Give me whatever you have, because I need to move". Then the finder will take its current best node, and create a partial path from there to the origin. It is not guaranteed that it's the best path; in fact, it almost probably isn't. But it's better than nothing! (sometimes)
MarekkPie wrote:I did a paper on Jump Point Search (and by paper, I mean I read about it on the guy's website and wrote some BS on it.) If you stuck to orthogonal movement, it seems like it would be extremely easy to implement; it's the diagonal movement that starts confusing me.
I haven't wrapped my head around that yet. I don't know how to prune nodes when restricted to cardinal movement only. If you can write a small pseudo-algorithm about how that would work, I'd be grateful
When I write def I mean function.
User avatar
hryx
Party member
Posts: 110
Joined: Mon Mar 29, 2010 2:28 am
Location: SF<CA<USA

Re: pulsar.lua - another pathfinding lib

Post by hryx »

Brilliant, Kikito. I can see this interruptible search being potentially very useful.

Some ideas for what you could add to the demo:
  • User input to change max number of steps per frame
  • User input to step through search iterations
  • When a path is found, show total time needed to discover path
These are a bit superfluous but they might help a potential user understand the library and its features better.
User avatar
MarekkPie
Inner party member
Posts: 587
Joined: Wed Dec 28, 2011 4:48 pm
Contact:

Re: pulsar.lua - another pathfinding lib

Post by MarekkPie »

This is pseudocode, but from my understanding, cardinal JPS goes like this:

Code: Select all

function prune(grid, node, prev)
        -- Check to see if we have reached a "jump point"; in this case,
        -- a jump point is simply when we are near a wall, since walls
        -- modify the number of "good neighbors" that an individual node
        -- has.
        for r = node.row - 1, node.row + 1 do
                for c = node.col - 1, node.col + 1 do
                        -- If we see a wall in our vicinity, do a regular
                        -- A* search around that point, to give a new jump
                        -- direction.
                        if grid[r][c].wall then
                                return normalAStar()
                        end     
                end     
        end

        -- Since we haven't found a wall, we don't need to add anything to our
        -- openlist, because we know that the best path is opposite our previous
        -- node.

        -- Get the direction between the previous node and the current node
        local dir = {
                x = node.col - prev.col,
                y = node.row - prev.row,
        }
        
        addToClosedList(node)
        return prune(grid, grid[node.row + (dir.y * -1)][node.col + (dir.x * -1)], node)
end     
There might be a little more to it, but from my understanding, it is pretty simple for cardinal directions. Diagonal, it seems you need to extend cardinally in the same general direction as diagonally (i.e. if you are going NW then you need to look north and west), but I can't get my head around that part.

This way assumes you haven't found your neighbors beforehand, or at least haven't pruned the walls beforehand. I don't quite know how I would do this if you did (like I do in my A*).
User avatar
Jasoco
Inner party member
Posts: 3725
Joined: Mon Jun 22, 2009 9:35 am
Location: Pennsylvania, USA
Contact:

Re: pulsar.lua - another pathfinding lib

Post by Jasoco »

Really nice. I like how it does diagonal paths at angles other than 45º and treats catty-corner tiles the way I want them to. Interesting though, I drew a line all the way along the map vertically and instead of failing with an error or message it draws a path to the last spot it looked in. Will it at least return a "failed" message if it can't find a path?
Post Reply

Who is online

Users browsing this forum: Google [Bot] and 50 guests