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

21–30 of 55 posts

Re: Pathfinding Visualizer

#21

Post by phire »

squeaky-clean wrote: post #8
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

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.

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)

Re: Pathfinding Visualizer

#22

Post by drewtato »

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 the same as BFS?

Fast is not fast.

I think an inverted binary tree maze would be nice.

Re: Pathfinding Visualizer

#23

Post by squeaky-clean »

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

Earlier quoted context omitted.

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.

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

Re: Pathfinding Visualizer

#24

Post by squeaky-clean »

_0ffh wrote: post #13
squeaky-clean wrote: post #9

Earlier quoted context omitted.

The blue squares show the nodes it checked, and with A star the entire map shouldn't be blue on an empty maze.

Yeah right, in that case there's something wrong there! Maybe in the way it queues up the options.

Think I found it, if you change the sort in astar.ts to just return 1 or -1 based on the comparison it behaves like A-star.

   untraversedTiles.sort((a, b) => {
      if (heuristicCost[a.row][a.col]

Re: Pathfinding Visualizer

#25

Post by squeaky-clean »

RomanPushkin wrote: post #18

It would be nice to see and edit the code. Probably something for the future

There's a github icon in the modal that pops up when you first use it. You can click the (?) button to see it again. Or here's the direct link https://github.com/eoin-barr/pathfinding-visualizer

(I'm not the author/OP but the code is pretty readable and it was really easy to get running with just `yarn; yarn dev`)

Re: Pathfinding Visualizer

#26

Post by kentonv »

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

Re: Pathfinding Visualizer

#28

Post by alexcnwy »

ubj wrote: post #4

Very nice! My only suggestion would be to include Jump Point Search (JPS) [1], which can be an order of magnitude faster than A* search in grid map settings. JPS has also been extended to 3D grids for quadrotor path planning [2]. [1]: https://ojs.aaai.org/index.php/AAAI/article/view/7994 [2]: https://ieeexplore.ieee.org/abstract/document/7839930

Wow I didn’t think about this for 3D space, thanks for the links!

Re: Pathfinding Visualizer

#30

Post by lake_vincent »

pydave wrote: post #17

Looks nice, but too bad you can't run different pathfinders on the same maze. Running on an empty grid is default but it's less interesting to me.

+1 for this. Would love to compare all the algos on the same maze, so you can visualize the differences in their pathfinding approach.
Post reply on HN