Hacker News new | ask | show | jobs
by squeaky-clean 1316 days ago
The algorithms do seem wrong. I get this for a DFS on an empty map [0]. And the A star doesn't appear to follow any heuristic during the search.

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

edit: Just wanted to add in case this is more of a frontend demo than a pathfinder demo, it does look beautiful and the search animation is more intuitive than similar demos I've seen. And runs fine on my phone.
1 comments
phire 1316 days ago
It's not really a bug.

It's just that (unlike the other 3 algorithms) DFS doesn't guarantee to find the shortest path, just a path.

Not a problem on mazes with only one solution, but problematic when there are multiple solutions (or near-infinite solutions on an empty map)

link
squeaky-clean 1316 days ago
It still doesn't feel like a DFS though. It's not picking the next node in a consistent order. I wouldn't expect gaps between the search.

This nerd-sniped me so I dug into the code, it's because it uses the non-recursive approach but it has an extra step of not adding neighbors to the stack if they've already been added previously. So you get this staggered line search because it avoids searching any tiles adjacent to a previously searched tile unless there are no other options. Decent optimization and still technically a DFS, it's just not the textbook example.

link
Karliss 1315 days ago
"Still technically a DFS" - No! The traditional textbook DFS visiting order has certain important properties. It's not just a "BFS" which uses stack and doesn't produce shortest path. There are more complex graph processing for finding strongly connected components, searching cutpoints and others which rely on proper DFS. Replacing DFS with this thing will result in completely wrong result. It is possible to implement a proper DFS non recursively, but it's a bit more trickier than just replacing queue with a stack in BFS.
link
gugagore 1315 days ago
What important property of DFS is missing if you just replace a stack with a queue?
link
Karliss 1315 days ago
If you form a spanning tree by noting which edges where used during DFS traversal of undirected graph, then all of the edges not used will connect a node with it's ancestor and there will be no cross edges. It doesn't matter if all you care is traversing the graph in any order and maybe checking which parts are connected, but it is important for some of the more complex graph algorithms built on top of DFS.
link