4 ms·

Show HN: Pathfinding Visualizer

51 points by honzaaap 4y ago

Decided to remake my old pathfinding project to hexagonal tiles. Pretty happy with how it turned out. Source code: https://github.com/honzaap/Pathfinding https://github.com/honzaap/Pathfinding

tonetheman 4y ago
Needs instructions
mxmlnkn 4y ago
Interesting to watch but some explanations on the website might be useful. Choosing "Prim's Algorithm" uses up 20GB in a few seconds before it gets killed.
BatFastard 4y ago
Makes me wonder why anyone would use anything but A* or greedy algorithm. Fun to play with and watch!
- littlestymaar 4y ago
  Factorio had a blog post a while ago explaining why basic A* didn't work for them. On my phone right now so I can't find it easily but I'm pretty sure it was posted in HN. Edit: found it. https://news.ycombinator.com/item?id=21294354 https://news.ycombinator.com/item?id=21294354
mef 4y ago
very cool! tiny nit: solid grey blocks are paths and gradient tiles are walls, but my expectation is reversed
- omoikane 4y ago
  I wish the gradient walls were replaced by solid color tiles instead. Currently the top part of the grid seems lacking in contrast between paths and walls.
phailhaus 4y ago
This is great! Very juicy visualization. One bit of feedback though: some of the algorithms take a while to complete, and it doesn't seem like I can "stop" or "reset" while it's running?
emilfihlman 4y ago
I think there's a "bug" (a bad heuristic?) in the A* code, since it produces easy suboptimal "solutions". https://emil.fi/m/astarsuboptimal.png https://emil.fi/m/astarsuboptimal.png
- emilfihlman 4y ago
  Also seems to produce suboptimal solutions with Dijkstra's algorithm, which shouldn't be the case, right? https://emil.fi/m/dijkstrasuboptimal.png https://emil.fi/m/dijkstrasuboptimal.png
  - emilfihlman 4y ago
    And depth first seems to behave, strangely. https://emil.fi/m/depthsuboptimal.png https://emil.fi/m/depthsuboptimal.png
    - honzaaap 4y ago
      That's weird, I am unable to recreate these bugs but it could be something with screen size, since I generate tiles according to window size. I'll look into it. Thanks!
      - emilfihlman 4y ago
        Here's one a friend generated on his machine with Dijkstra. https://emil.fi/m/dijkstrasuboptimalfriend.png https://emil.fi/m/dijkstrasuboptimalfriend.png Seems like there's a bug or more.
- jhomedall 4y ago
  The top (selected) path is 23 hexes from start to finish, but the winding closer path is 24 hexes.
  - emilfihlman 4y ago
    Not the issue here, look at the end of the selected path, where the cursor is. If you go down where the cursor is instead of right the path is 1 step shorter.
karussell 4y ago
I did a similar visualization but for road network paths: uni-directional A* https://karussell.files.wordpress.com/2012/07/astar.gif https://karussell.files.wordpress.com/2012/07/astar.gif (New version: https://www.graphhopper.com/wp-content/uploads/2017/07/astar-1.gif https://www.graphhopper.com/wp-content/uploads/2017/07/astar...) bi-directional Dijkstra https://karussell.files.wordpress.com/2012/06/bidijkstra.gif https://karussell.files.wordpress.com/2012/06/bidijkstra.gif This uses a primitive Swing UI https://github.com/graphhopper/graphhopper/blob/master/tools/src/main/java/com/graphhopper/ui/MiniGraphUI.java https://github.com/graphhopper/graphhopper/blob/master/tools... And it can be color encoded too https://www.graphhopper.com/blog/2016/01/19/alternative-roads-to-rome/ https://www.graphhopper.com/blog/2016/01/19/alternative-road... which is inspired from others: https://www.graphhopper.com/blog/2015/12/14/roads-to-rome-from-moovel-lab/ https://www.graphhopper.com/blog/2015/12/14/roads-to-rome-fr... Or here I used Deck.gl with time-dependent data: https://www.graphhopper.com/blog/2018/07/04/high-precision-reachability/ https://www.graphhopper.com/blog/2018/07/04/high-precision-r...
- honzaaap 4y ago
  Looks cool! Thanks for sharing :)

51 points by honzaaap 4y ago

Decided to remake my old pathfinding project to hexagonal tiles. Pretty happy with how it turned out. Source code: https://github.com/honzaap/Pathfinding https://github.com/honzaap/Pathfinding

tonetheman 4y ago

Needs instructions

mxmlnkn 4y ago

Interesting to watch but some explanations on the website might be useful. Choosing "Prim's Algorithm" uses up 20GB in a few seconds before it gets killed.

BatFastard 4y ago

Makes me wonder why anyone would use anything but A* or greedy algorithm. Fun to play with and watch!

littlestymaar 4y ago
Factorio had a blog post a while ago explaining why basic A* didn't work for them. On my phone right now so I can't find it easily but I'm pretty sure it was posted in HN. Edit: found it. https://news.ycombinator.com/item?id=21294354 https://news.ycombinator.com/item?id=21294354

mef 4y ago

very cool! tiny nit: solid grey blocks are paths and gradient tiles are walls, but my expectation is reversed

omoikane 4y ago
I wish the gradient walls were replaced by solid color tiles instead. Currently the top part of the grid seems lacking in contrast between paths and walls.

phailhaus 4y ago

This is great! Very juicy visualization. One bit of feedback though: some of the algorithms take a while to complete, and it doesn't seem like I can "stop" or "reset" while it's running?

emilfihlman 4y ago

I think there's a "bug" (a bad heuristic?) in the A* code, since it produces easy suboptimal "solutions". https://emil.fi/m/astarsuboptimal.png https://emil.fi/m/astarsuboptimal.png

emilfihlman 4y ago
Also seems to produce suboptimal solutions with Dijkstra's algorithm, which shouldn't be the case, right? https://emil.fi/m/dijkstrasuboptimal.png https://emil.fi/m/dijkstrasuboptimal.png
- emilfihlman 4y ago
  And depth first seems to behave, strangely. https://emil.fi/m/depthsuboptimal.png https://emil.fi/m/depthsuboptimal.png
  - honzaaap 4y ago
    That's weird, I am unable to recreate these bugs but it could be something with screen size, since I generate tiles according to window size. I'll look into it. Thanks!
    - emilfihlman 4y ago
      Here's one a friend generated on his machine with Dijkstra. https://emil.fi/m/dijkstrasuboptimalfriend.png https://emil.fi/m/dijkstrasuboptimalfriend.png Seems like there's a bug or more.
jhomedall 4y ago
The top (selected) path is 23 hexes from start to finish, but the winding closer path is 24 hexes.
- emilfihlman 4y ago
  Not the issue here, look at the end of the selected path, where the cursor is. If you go down where the cursor is instead of right the path is 1 step shorter.

karussell 4y ago

I did a similar visualization but for road network paths: uni-directional A* https://karussell.files.wordpress.com/2012/07/astar.gif https://karussell.files.wordpress.com/2012/07/astar.gif (New version: https://www.graphhopper.com/wp-content/uploads/2017/07/astar-1.gif https://www.graphhopper.com/wp-content/uploads/2017/07/astar...) bi-directional Dijkstra https://karussell.files.wordpress.com/2012/06/bidijkstra.gif https://karussell.files.wordpress.com/2012/06/bidijkstra.gif This uses a primitive Swing UI https://github.com/graphhopper/graphhopper/blob/master/tools/src/main/java/com/graphhopper/ui/MiniGraphUI.java https://github.com/graphhopper/graphhopper/blob/master/tools... And it can be color encoded too https://www.graphhopper.com/blog/2016/01/19/alternative-roads-to-rome/ https://www.graphhopper.com/blog/2016/01/19/alternative-road... which is inspired from others: https://www.graphhopper.com/blog/2015/12/14/roads-to-rome-from-moovel-lab/ https://www.graphhopper.com/blog/2015/12/14/roads-to-rome-fr... Or here I used Deck.gl with time-dependent data: https://www.graphhopper.com/blog/2018/07/04/high-precision-reachability/ https://www.graphhopper.com/blog/2018/07/04/high-precision-r...

honzaaap 4y ago
Looks cool! Thanks for sharing :)