Show HN: Pathfinding Visualizer (honzaap.github.io)

51 points by honzaaap 4y ago ↗ HN

Decided to remake my old pathfinding project to hexagonal tiles. Pretty happy with how it turned out.

Source code: https://github.com/honzaap/Pathfinding

17 comments

[ 3.2 ms ] story [ 49.7 ms ] thread

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

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

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

emilfihlman 4y ago ↗

And depth first seems to behave, strangely.

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

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.

jhomedall 4y ago ↗

Oh you're right. My bad, sorry.

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 (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 4y ago ↗

Looks cool! Thanks for sharing :)