## pulsar.lua - another pathfinding lib

kikito
Inner party member
Posts: 3142
Joined: Sat Oct 03, 2009 5:22 pm
Contact:

### pulsar.lua - another pathfinding lib

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 (12.87 KiB) Viewed 3541 times
It also has got a demo! Here it is:
pulsar-demo.love
demo for v0.5
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

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.

Robin
The Omniscient
Posts: 6506
Joined: Fri Feb 20, 2009 4:29 pm
Location: The Netherlands
Contact:

### Re: pulsar.lua - another pathfinding lib

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.

kikito
Inner party member
Posts: 3142
Joined: Sat Oct 03, 2009 5:22 pm
Contact:

### Re: pulsar.lua - another pathfinding lib

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

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.

MarekkPie
Inner party member
Posts: 587
Joined: Wed Dec 28, 2011 4:48 pm
Contact:

### Re: pulsar.lua - another pathfinding lib

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.

kikito
Inner party member
Posts: 3142
Joined: Sat Oct 03, 2009 5:22 pm
Contact:

### Re: pulsar.lua - another pathfinding lib

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.

hryx
Party member
Posts: 110
Joined: Mon Mar 29, 2010 2:28 am
Location: SF<CA<USA

### Re: pulsar.lua - another pathfinding lib

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.

MarekkPie
Inner party member
Posts: 587
Joined: Wed Dec 28, 2011 4:48 pm
Contact:

### Re: pulsar.lua - another pathfinding lib

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,
}

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*).

Jasoco
Inner party member
Posts: 3619
Joined: Mon Jun 22, 2009 9:35 am
Location: Pennsylvania, USA
Contact:

### Re: pulsar.lua - another pathfinding lib

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?

### Who is online

Users browsing this forum: No registered users and 5 guests