[HN Gopher] Show HN: Pathfinding Visualizer
___________________________________________________________________
Show HN: Pathfinding Visualizer
Decided to remake my old pathfinding project to hexagonal tiles.
Pretty happy with how it turned out. Source code:
https://github.com/honzaap/Pathfinding
Author : honzaaap
Score : 34 points
Date : 2022-06-25 14:30 UTC (8 hours ago)
(HTM) web link (honzaap.github.io)
(TXT) w3m dump (honzaap.github.io)
| phailhaus wrote:
| 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?
| tonetheman wrote:
| Needs instructions
| BatFastard wrote:
| Makes me wonder why anyone would use anything but A* or greedy
| algorithm. Fun to play with and watch!
| littlestymaar wrote:
| 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
| karussell wrote:
| I did a similar visualization but for road network paths:
|
| uni-directional A*
| https://karussell.files.wordpress.com/2012/07/astar.gif (New
| version: https://www.graphhopper.com/wp-
| content/uploads/2017/07/astar...)
|
| bi-directional Dijkstra
| https://karussell.files.wordpress.com/2012/06/bidijkstra.gif
|
| This uses a primitive Swing UI
| https://github.com/graphhopper/graphhopper/blob/master/tools...
|
| And it can be color encoded too
| 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-fr...
|
| Or here I used Deck.gl with time-dependent data:
| https://www.graphhopper.com/blog/2018/07/04/high-precision-r...
| honzaaap wrote:
| Looks cool! Thanks for sharing :)
| mxmlnkn wrote:
| 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.
| emilfihlman wrote:
| 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
| jhomedall wrote:
| The top (selected) path is 23 hexes from start to finish, but
| the winding closer path is 24 hexes.
| emilfihlman wrote:
| 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.
| emilfihlman wrote:
| Also seems to produce suboptimal solutions with Dijkstra's
| algorithm, which shouldn't be the case, right?
|
| https://emil.fi/m/dijkstrasuboptimal.png
| emilfihlman wrote:
| And depth first seems to behave, strangely.
|
| https://emil.fi/m/depthsuboptimal.png
| honzaaap wrote:
| 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 wrote:
| Here's one a friend generated on his machine with
| Dijkstra.
|
| https://emil.fi/m/dijkstrasuboptimalfriend.png
|
| Seems like there's a bug or more.
| mef wrote:
| very cool!
|
| tiny nit: solid grey blocks are paths and gradient tiles are
| walls, but my expectation is reversed
| omoikane wrote:
| 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.
___________________________________________________________________
(page generated 2022-06-25 23:01 UTC)