6 ms·

PathFinding.js

muhuk 12y ago
In case you miss the tiny link, here's the source: https://github.com/qiao/PathFinding.js https://github.com/qiao/PathFinding.js
curiousAl 12y ago
Wow, this is a fantastic visualization of algorithms with scary doctoral-thesis-y names. I love visualizations that make scary things simple.
tejon 12y ago
Of course it's a gray link... but wow, major enhancements since ~1 year ago when I was on my pathfinding binge. Good stuff! Never did implement full jump-point optimization, though I got halfway there by manipulating queue priorities.
jMyles 12y ago
In my first bit of play, I just tried to find cases where Manhattan lost to the others. It seems like Manhattan is not as good when faced with a plausible path only to be thwarted at the end - is this right? Can you show a few cases where Manhattan loses by a landslide?
- roryokane 12y ago
  Manhattan is a heuristic for measuring distance, not an algorithm to find a path, so I wouldn’t really say it “loses”, rather it “is less applicable”. Manhattan, Euclidean, and Chebyshev are all just different ways of measuring distance (https://en.wikipedia.org/wiki/Taxicab_geometry https://en.wikipedia.org/wiki/Taxicab_geometry, https://en.wikipedia.org/wiki/Euclidean_distance https://en.wikipedia.org/wiki/Euclidean_distance, https://en.wikipedia.org/wiki/Chebyshev_distance https://en.wikipedia.org/wiki/Chebyshev_distance). Each algorithm uses the heuristic to measure how promising each possible path is (how close each path is to the goal according to that definition of distance, ignoring walls), and prioritizes the most promising paths. Based on those definitions, I would guess that “Chebyshev” distance is almost always the most accurate heuristic to use when you check “Allow Diagonal”, because it will always be perfectly accurate if there are no walls in the way, unlike the others. Similarly, when “Allow Diagonal” is unchecked, “Manhattan” distance is the most accurate. And “Euclidean” distance is always the least accurate in this demo, because in this demo, paths are always constrained to 45° or 90° turns so that they stay on the grid, whereas Euclidean distance assumes that it is possible to move at arbitrary angles like 18.2° right from east.
  - jMyles 12y ago
    I have found one example where Euclidean wins: http://imgur.com/FgQ04k0 http://imgur.com/FgQ04k0
- applekor 12y ago
  Because Manhattan distance isn't an admissible heuristic for an 8-connected grid I think it breaks the A*'s guarantee of optimality. I don't have an example, but it might be a place to start looking.
jwklemm 12y ago
Really useful library and great visualizations. I'm having flashbacks to my CS algorithm analysis class.
newbrict 12y ago
The recursive visualization is really slow on even moderately complex graphs, otherwise it's a really neat tool
- eschutte2 12y ago
  Yes - I found this a couple months ago when I needed to do a pathfinding feature for a client, and I thought the same thing. It turns out browsers can do A* fast enough for live pathfinding on a fairly complex graph during mouse drag, which I wasn't sure about when I started. In any case, playing with this visualization helped me poke holes in some of the simplified approaches I had in mind.
tokenizerrr 12y ago
Very nice. If the author is the submitter or sees this, could you please provide some details on what kind of libraries and techniques have gone into creating this? A blog post or something would be great.
- WestCoastJustin 12y ago
  Not the author, just the submitter, more info can be found @ https://github.com/qiao/PathFinding.js https://github.com/qiao/PathFinding.js BTW, I actually found this when I was looking at his other repo for visualizing midi files @ http://qiao.github.io/euphony/#36 http://qiao.github.io/euphony/#36 code @ https://github.com/qiao/euphony https://github.com/qiao/euphony
reitzensteinm 12y ago
One trick I've used quite a bit in games I've written is to do a breadth-first search of the entire playfield, with no termination, resulting in data for how to get from any tile to the destination. This has a few nice advantages: * Breadth first is trivially broken up to iterate over multiple frames, amortizing the cost of visiting each tile * It reduces the worst case as the number of enemies scales up but the destination counts are low. * The implementation in general is very simple * You can still early terminate if you keep track of the farthest distance a pathfinding layer needs to satisfy. * No pathological, worst case situations where a playfield becomes very expensive to pathfind. An open field is the worst case. I first used this in Robokill, a flash game which often had 20+ enemies on the same screen tracking the player. I estimated at the time that it cost about as much as doing A* on ~5 enemies. In games, the worst (common) case is basically all that matters - a constant 60fps is significantly better than 100fps dropping to 30fps occasionally.
- Kiro 12y ago
  How often did you need to do the pathfinding in Robokill? I've tried making a game where I did pathfinding with A* every few seconds with 20 enemies tracking a player and it locked up the browser for like a second every time.
  - reitzensteinm 12y ago
    Using the technique I outlined, the pathfinding is run continuously, stepping once per frame, processing tiles further and further out. When the player changes tile, it resets. This results in a relatively small per frame cost, with a constant worst case (for a 21x21 tile grid, it would be at most 80 tiles processed in one frame, i.e. 21x4 - 4, the number of tiles in the outside border). As outlined above, this is exactly what you want in a game, because it makes the sharp edge cases you're describing impossible. Throw a hundred enemies in there in a pathological maze environment, moving the player around continuously, breaking walls, and it (the pathfinding aspect) will run just fine. Try to do that with A* in the browser, and my crystal ball predicts the addition of a well worn copy of Web Workers for Dummies on a book shelf near you :) One gotcha is that if you don't stop moving, half of the screen that's too far away from the player will not be updated, but enemies in those squares just use the out of date information. In Robokill, I couldn't even notice the error this causes when I was testing.
diziet 12y ago
For a similar problem, check out http://www.pathery.com/ http://www.pathery.com/ - create the longest possible maze with X blocks.
lilymuki 12y ago
https://uradura.wordpress.com/2014/09/21/43rrr-watch-chicago-vs-jets-live-stream-online-nfl-at-metlife-stadium-nfl-regular-season-5hfhu/ https://uradura.wordpress.com/2014/09/21/43rrr-watch-chicago...
iandanforth 12y ago
None of these appear to work in an intuitive fashion. Are there algorithms that better resemble biological strategies? If I create a large walled area, I expect an entity to explore in one direction with a preference with external walls, miss areas and completely fail sometimes. Here's a cute and furry demonstration of biological pathfinding: https://www.youtube.com/watch?v=HRd5WYrnML4 https://www.youtube.com/watch?v=HRd5WYrnML4
- Tehnix 12y ago
  That sounds like a Depth-First-Search[1] (which wasn't included exactly). In DFS you'll go all the way out one way, until you reach the end, and then go back to when you last had a choice, and go out a new way, etc (a bit like the mouse did). It is worth mentioning though, that this approach probably isn't so good if the map level is very large, since the BFS is way more likely to catch something around the player first. [1] http://en.wikipedia.org/wiki/Depth-first_search http://en.wikipedia.org/wiki/Depth-first_search
jokoon 12y ago
I recently implemented A* with the help of this website, which really explains it well. http://www.redblobgames.com/pathfinding/a-star/introduction.html http://www.redblobgames.com/pathfinding/a-star/introduction.... I also used a method to create discrete path between cells, to straighten the path when possible.
- deleted 12y ago
  [deleted]
poseid 12y ago
I wonder if something like this could be used to automatically place components in an electrical circuit (PCB)
- orbifold 12y ago
  The problem is much harder, in fact NP complete I believe and there are indeed placing tools that do that.
noiv 12y ago
The above pathfinder is much faster with a binary heap, https://github.com/bgrins/javascript-astar https://github.com/bgrins/javascript-astar and can be heavily optimized if you know your engine. With SpiderMonkey I get fixed cost of around 1ms for initialization and it checks nearly 2000 nodes in 1ms on a 3Ghz Core Duo with a relative costly euclidean heuristic. So worst case on a 40x50 map is ~2ms. If worst case can be avoided upfront you'll always get a response within 2ms even with a 2000 nodes long path on most maps. It is amazing what one can do with JS nowadays.

muhuk 12y ago

In case you miss the tiny link, here's the source: https://github.com/qiao/PathFinding.js https://github.com/qiao/PathFinding.js

curiousAl 12y ago

Wow, this is a fantastic visualization of algorithms with scary doctoral-thesis-y names. I love visualizations that make scary things simple.

tejon 12y ago

Of course it's a gray link... but wow, major enhancements since ~1 year ago when I was on my pathfinding binge. Good stuff! Never did implement full jump-point optimization, though I got halfway there by manipulating queue priorities.

jMyles 12y ago

In my first bit of play, I just tried to find cases where Manhattan lost to the others. It seems like Manhattan is not as good when faced with a plausible path only to be thwarted at the end - is this right? Can you show a few cases where Manhattan loses by a landslide?

roryokane 12y ago
Manhattan is a heuristic for measuring distance, not an algorithm to find a path, so I wouldn’t really say it “loses”, rather it “is less applicable”. Manhattan, Euclidean, and Chebyshev are all just different ways of measuring distance (https://en.wikipedia.org/wiki/Taxicab_geometry https://en.wikipedia.org/wiki/Taxicab_geometry, https://en.wikipedia.org/wiki/Euclidean_distance https://en.wikipedia.org/wiki/Euclidean_distance, https://en.wikipedia.org/wiki/Chebyshev_distance https://en.wikipedia.org/wiki/Chebyshev_distance). Each algorithm uses the heuristic to measure how promising each possible path is (how close each path is to the goal according to that definition of distance, ignoring walls), and prioritizes the most promising paths. Based on those definitions, I would guess that “Chebyshev” distance is almost always the most accurate heuristic to use when you check “Allow Diagonal”, because it will always be perfectly accurate if there are no walls in the way, unlike the others. Similarly, when “Allow Diagonal” is unchecked, “Manhattan” distance is the most accurate. And “Euclidean” distance is always the least accurate in this demo, because in this demo, paths are always constrained to 45° or 90° turns so that they stay on the grid, whereas Euclidean distance assumes that it is possible to move at arbitrary angles like 18.2° right from east.
- jMyles 12y ago
  I have found one example where Euclidean wins: http://imgur.com/FgQ04k0 http://imgur.com/FgQ04k0
applekor 12y ago
Because Manhattan distance isn't an admissible heuristic for an 8-connected grid I think it breaks the A*'s guarantee of optimality. I don't have an example, but it might be a place to start looking.

jwklemm 12y ago

Really useful library and great visualizations. I'm having flashbacks to my CS algorithm analysis class.

newbrict 12y ago

The recursive visualization is really slow on even moderately complex graphs, otherwise it's a really neat tool

eschutte2 12y ago
Yes - I found this a couple months ago when I needed to do a pathfinding feature for a client, and I thought the same thing. It turns out browsers can do A* fast enough for live pathfinding on a fairly complex graph during mouse drag, which I wasn't sure about when I started. In any case, playing with this visualization helped me poke holes in some of the simplified approaches I had in mind.

tokenizerrr 12y ago

Very nice. If the author is the submitter or sees this, could you please provide some details on what kind of libraries and techniques have gone into creating this? A blog post or something would be great.

WestCoastJustin 12y ago
Not the author, just the submitter, more info can be found @ https://github.com/qiao/PathFinding.js https://github.com/qiao/PathFinding.js BTW, I actually found this when I was looking at his other repo for visualizing midi files @ http://qiao.github.io/euphony/#36 http://qiao.github.io/euphony/#36 code @ https://github.com/qiao/euphony https://github.com/qiao/euphony

reitzensteinm 12y ago

One trick I've used quite a bit in games I've written is to do a breadth-first search of the entire playfield, with no termination, resulting in data for how to get from any tile to the destination. This has a few nice advantages: * Breadth first is trivially broken up to iterate over multiple frames, amortizing the cost of visiting each tile * It reduces the worst case as the number of enemies scales up but the destination counts are low. * The implementation in general is very simple * You can still early terminate if you keep track of the farthest distance a pathfinding layer needs to satisfy. * No pathological, worst case situations where a playfield becomes very expensive to pathfind. An open field is the worst case. I first used this in Robokill, a flash game which often had 20+ enemies on the same screen tracking the player. I estimated at the time that it cost about as much as doing A* on ~5 enemies. In games, the worst (common) case is basically all that matters - a constant 60fps is significantly better than 100fps dropping to 30fps occasionally.

Kiro 12y ago
How often did you need to do the pathfinding in Robokill? I've tried making a game where I did pathfinding with A* every few seconds with 20 enemies tracking a player and it locked up the browser for like a second every time.
- reitzensteinm 12y ago
  Using the technique I outlined, the pathfinding is run continuously, stepping once per frame, processing tiles further and further out. When the player changes tile, it resets. This results in a relatively small per frame cost, with a constant worst case (for a 21x21 tile grid, it would be at most 80 tiles processed in one frame, i.e. 21x4 - 4, the number of tiles in the outside border). As outlined above, this is exactly what you want in a game, because it makes the sharp edge cases you're describing impossible. Throw a hundred enemies in there in a pathological maze environment, moving the player around continuously, breaking walls, and it (the pathfinding aspect) will run just fine. Try to do that with A* in the browser, and my crystal ball predicts the addition of a well worn copy of Web Workers for Dummies on a book shelf near you :) One gotcha is that if you don't stop moving, half of the screen that's too far away from the player will not be updated, but enemies in those squares just use the out of date information. In Robokill, I couldn't even notice the error this causes when I was testing.

diziet 12y ago

For a similar problem, check out http://www.pathery.com/ http://www.pathery.com/ - create the longest possible maze with X blocks.

lilymuki 12y ago

https://uradura.wordpress.com/2014/09/21/43rrr-watch-chicago-vs-jets-live-stream-online-nfl-at-metlife-stadium-nfl-regular-season-5hfhu/ https://uradura.wordpress.com/2014/09/21/43rrr-watch-chicago...

iandanforth 12y ago

None of these appear to work in an intuitive fashion. Are there algorithms that better resemble biological strategies? If I create a large walled area, I expect an entity to explore in one direction with a preference with external walls, miss areas and completely fail sometimes. Here's a cute and furry demonstration of biological pathfinding: https://www.youtube.com/watch?v=HRd5WYrnML4 https://www.youtube.com/watch?v=HRd5WYrnML4

Tehnix 12y ago
That sounds like a Depth-First-Search[1] (which wasn't included exactly). In DFS you'll go all the way out one way, until you reach the end, and then go back to when you last had a choice, and go out a new way, etc (a bit like the mouse did). It is worth mentioning though, that this approach probably isn't so good if the map level is very large, since the BFS is way more likely to catch something around the player first. [1] http://en.wikipedia.org/wiki/Depth-first_search http://en.wikipedia.org/wiki/Depth-first_search

jokoon 12y ago

I recently implemented A* with the help of this website, which really explains it well. http://www.redblobgames.com/pathfinding/a-star/introduction.html http://www.redblobgames.com/pathfinding/a-star/introduction.... I also used a method to create discrete path between cells, to straighten the path when possible.

deleted 12y ago
[deleted]

poseid 12y ago

I wonder if something like this could be used to automatically place components in an electrical circuit (PCB)

orbifold 12y ago
The problem is much harder, in fact NP complete I believe and there are indeed placing tools that do that.

noiv 12y ago

The above pathfinder is much faster with a binary heap, https://github.com/bgrins/javascript-astar https://github.com/bgrins/javascript-astar and can be heavily optimized if you know your engine. With SpiderMonkey I get fixed cost of around 1ms for initialization and it checks nearly 2000 nodes in 1ms on a 3Ghz Core Duo with a relative costly euclidean heuristic. So worst case on a 40x50 map is ~2ms. If worst case can be avoided upfront you'll always get a response within 2ms even with a 2000 nodes long path on most maps. It is amazing what one can do with JS nowadays.