Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Pathfinding Visualizer

pathfinding-visualizer-nu.vercel.app

Post reply on HN
Print view View original

31–40 of 55 posts

Re: Pathfinding Visualizer

#31

Post by StoicMonkey »

kentonv wrote: post #26
eknkc wrote: post #6

Am I missing something that this is doing something other than finding shortest paths? For example A* on an empty map should generate a diagonal path with almost no checks outside the paths immediate neighbors. But I get this: https://link.ekin.dev/OTW2xy

Yeah the A* search had a bug. It "bugged" me enough that I made a PR to fix it... https://github.com/eoin-barr/pathfinding-visualizer/pull/1

Nice fix! Now if only someone could answer this Cloudflare Workers question...

https://stackoverflow.com/questions/74331904/racing-javascri...

Re: Pathfinding Visualizer

#32

Post by Karliss »

squeaky-clean wrote: post #23
phire wrote: post #21

Earlier quoted context omitted.

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)

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 t…

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

Re: Pathfinding Visualizer

#33

Post by Karliss »

drewtato wrote: post #22

My feedback: Building the maze takes too long. Maybe turn the play button into a fast-forward button when the maze is being built and solved. The dark mode colors are pretty bad. When you click and hold, it should turn every square the same color until you let go again. Right now it toggles every square you pass over, which is confusing. When you move the start and end, it removes walls from the board. Isn't Dijkstra…

> Isn't Dijkstra the same as BFS?

That's because demonstrating Dijkstra on a grid is as useful as demonstrating air resistance in vacuum. In a grid with only horizontal and vertical Dijkstra will produce same order as BFS (but more slowly). You could see some difference if you treated diagonal moves as having sqrt(2) length, but such distance metric is rarely useful. Either you simplify things by having grid and not allowing diagonal movement or treating them like like them length 1, or you allow free 2D movement at arbitrary angles with proper euclidean geometry and distances. Treating diagonal distances as sqrt(2) is worst of both approaches. You loose most of the simplification provided by grid and can't evaluate it in head or on a paper, but it still doesn't produce geometrically accurate results.

One case where Dijkstra on a grid would make sense if you treated entering and exiting certain cells as slower=longer distance. Might be useful if you modeled a game where certain cells contain difficult to traverse terrain like mountains or swamp.

Re: Pathfinding Visualizer

#37

Post by linhns »

Nice stuff! However, when I try to drag the start/end points around the map it has an 'eraser' effect, deleting walls as it goes. Also you can try using black or darker gray for walls.
Post reply on HN