Algorithm-Visualizer | Hacker News Reader

Algorithm-Visualizer

github.com

79 pointswalker_tw20 comments

For anyone wanting to try it directly, here's a quick link:

https://algo-visualiser.herokuapp.com/

From the title I was expecting a more general purpose algorithm visualizer. I think this is more accurately described as "Graph Traversal Algorithm Visualizer".

Even the use of “graph traversal algorithm” is not accurate. Dijkstra and A* aren’t for graph traversal. These are pathfinding algorithms.

You can use Dijkstra as a traversal, since you don’t need and endpoint.

I still agree that comparing a DFS and an A* is a bit strange, they have different use cases.

You might like the Debug Visualizer for VS Code! It's a general purpose visualizer. However it's not as easy to use as this project.

https://github.com/hediet/vscode-debug-visualizer/blob/maste...

The site states that the A* algorithm with the Euclidean heuristic does not always find the shortest path. This appears to be true for the implementation [0], but should not be true in general, as it should be guaranteed that A* will provide a shortest path when used with an admissible heuristic such as the Euclidean distance.

[0] https://imgur.com/a/UCAFHA4

Ah hello thanks for looking at the app. The reason that we state that Euclidean does not always find the shortest path is because the way the distance heuristic is calculated. Euclidean will not work on a quad-directional traversal grid such as this (we cant use diagonals) so instead the Manhattan distance is used to override this issue.

Cool app! However shouldn't using the Euclidean heuristic still result in finding the shortest path, as it will not overestimate the distance to the goal when evaluating a node, even if it is not possible to travel diagonally in the grid?

Also - is the behavior shown in the screenshot working as intended, as the shown path includes a detour?

I don't think this is true. From Wikipedia [1]:

> The heuristic function is problem-specific. If the heuristic function is admissible, meaning that it never overestimates the actual cost to get to the goal, A* is guaranteed to return a least-cost path from start to goal.

In this case the euclidean does not overestimate so I would guess there is a bug in the implementation.

[1] https://en.wikipedia.org/wiki/A*_search_algorithm

Edit:

Having taken a look at the source code I believe the problems mostly stem from the `addNeighboursToOpen` function [2]. It sets the distance and parent of unvisited neighbors of the current node. However this may happen multiple times for a node before it is actually visited. Meaning that the distance and parent is updated multiple times and the value at the end is not the optimal one. A simple fix would be to do a if check to see if the node already has a distance assigned.

[2] https://github.com/Walker-TW/Algorithm-Visualizer/blob/maste...

Thanks for the help. Can you expand on what you mean? The function called on line 35 (heuristicNodeCheck) will compare the heuristic to the new total created every time a node is checked or listed as a neighbour. Therefore the heuristic will always be kept relevant. Are you suggesting that when a node is labelled with a heuristic to keep it as its first value?

I suggest you re-read the parent comment. The issue is not with the heuristic value, it is with the distance and predecessor (parent).

While job searching me and a mate made an interactive app to learn ReactJS and teach graphing algorithms (Dijkstra, A*, BFS etc). Enjoy it (and contact us if you have any exciting jr. dev roles/opportunities !)

While I don't have any roles or opportunities available, when you say things like this:

  contact us if you have any exciting
  jr. dev roles/opportunities

... it would help if you had contact details in your HN profile.

Thanks for the help! I hope that you enjoyed the app. I have updated it (but ill put it just here in case) https://www.linkedin.com/in/thomas-w-walker/

You might want to re-visit this.

Under "Depth First Search" you say:

> Depth first search is the only algorithm listed which will NOT find the shortest path.

That turns out not to be the case. Euclidean will also sometimes not find the shortest path. And indeed, you say so in the section on Euclidean you say:

> *However because our grid is only traversable on horizontal or vertical vertices using this heurtistic will NOT always give the shortest path, ..."

You also mis-spelled "heuristics", but that's easily done, and easily fixed.

The app is nice ... well done.

Thank you very much for the feedback. And for adding the url above.

I am working on a similar project, but for self drawn graphs instead of grid graphs [0]. But it's not finished yet and missing documentation.

[0]: https://algorithms.laszlokorte.de/

Something similar in python to visualize algorithms and generate videos: https://github.com/CCExtractor/vardbg

This would've been very useful in my college days. A 300-person lecture plus a professor with horrible chalk handwriting who didn't host any TA sections was not conducive to learning.

Glad you found it to be informative!

Reply on news.ycombinator.com