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

Looks cool! Thanks for sharing :)

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.

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

Also seems to produce suboptimal solutions with Dijkstra's algorithm, which shouldn't be the case, right?

https://emil.fi/m/dijkstrasuboptimal.png

And depth first seems to behave, strangely.

https://emil.fi/m/depthsuboptimal.png

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!

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.

The top (selected) path is 23 hexes from start to finish, but the winding closer path is 24 hexes.

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.

Oh you're right. My bad, sorry.

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?

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

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

very cool!

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

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.

Needs instructions