6 ms·
Pathfinding Visualizer
- RomanPushkin 4y agoIt would be nice to see and edit the code. Probably something for the future
- eoinbarr 4y agoJust added a Github link to the navbar. If you have any ideas or see some here that you like that haven't been implemented go for it !
- squeaky-clean 4y agoThere'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 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`)
- SCLeo 4y agoShameless self-promotion: A non-grid-based path finder I made with Rust and compiled to WASM: https://scleox.github.io/non-grid-path-finder/ https://scleox.github.io/non-grid-path-finder/ (I made it a long time ago and I think the CI is broken...)
- gus_massa 4y agoNice! Some feature requests: The contrast between the walls and the blue (explored) areas is too low. When I press the round button to retry, the maze disappears. I'd like to see the same maze solved with different algorithm, or even see the same algorithm a few times. So my recommendation is to not errase the map, until the user press the button to make another map.
- sahkopoyta 4y ago+1 for maze not disappearing. Comparing the different algorithms is the actually pleasing thing to watch.
- smcl 4y ago+1 also for being a persistent maze when switching search algos. Lovely visualisation though!
- eoinbarr 4y agoYe great idea ! Will definitely look into updating the logic to implement this
- eknkc 4y agoAm 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 https://link.ekin.dev/OTW2xy
- deleted 4y ago[deleted]
- _0ffh 4y agoMaybe it does only horizontal and vertical steps. In that case it makes no difference, because the heuristic should always give you the Manhattan distance, which is equal for all options that don't overshoot the goal.
- squeaky-clean 4y agoThe blue squares show the nodes it checked, and with A star the entire map shouldn't be blue on an empty maze.
- eknkc 4y agoYeah _0ffh's point makes sense on the path found. But even if it finds a path that is basically one horizontal one vertical line, it should still check the immediate neighbors only.
- _0ffh 4y agoYeah right, in that case there's something wrong there! Maybe in the way it queues up the options.
- squeaky-clean 4y agoThink 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] < heuristicCost[b.row][b.col]) { return-1; } return 1; });
- ubj 4y agoVery 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 https://ojs.aaai.org/index.php/AAAI/article/view/7994 [2]: https://ieeexplore.ieee.org/abstract/document/7839930 https://ieeexplore.ieee.org/abstract/document/7839930
- atum47 4y agoLove the visuals, looks kinda slow on a mobile
- bitcharmer 4y agoJust checked and the maze generation part is also disappointingly slow on a powerful PC.
- eoinbarr 4y agoThanks ! Ye I need to reduce the number of of rows and columns on mobile to improve the UX
- sedatk 4y agoBreadth-first search with a binary tree maze resembles how a lightning finds its way to the ground.
- pydave 4y agoLooks 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.
- lake_vincent 4y ago+1 for this. Would love to compare all the algos on the same maze, so you can visualize the differences in their pathfinding approach.
- eoinbarr 4y agoYep great idea will try and update the logic to implement this !
- 51Cards 4y agoVery nice! This brings back memories. In the 90's sometime I found a GIF of a huge maze and I wanted to find the solution. Young coder me decided to write a program in VB to find the solution. Just went and grabbed a screen shot of it here: https://i.imgur.com/gRz5b01.png https://i.imgur.com/gRz5b01.png I can't remember how long it took it to solve it back then but it solves it now on modern hardware in about 3 seconds. Likely much better ways to do it now, I know nothing about path finding theory. This was just a simple recursive search. I need to do more of these fun side projects like this just for the pure joy of it.
- radiojasper 4y agoNice! Would be amazing if every maze gets its own URL so it's shareable.
- eoinbarr 4y agoThanks ! I hadn't thought of that will definitely add this in
- radiojasper 4y agoOh! Awesome, thanks!
- eoinbarr 4y agoYou can now login with Github and create maze URLs which you can share. Lmk if you have any other ideas !
- radiojasper 4y agoohh that's so cool, thank you for that!
- joshwcomeau 4y agoThis is so cool! well done.
- eoinbarr 4y agoThanks !
- drewtato 4y agoMy 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.
- Karliss 4y ago> 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.
- eoinbarr 4y agoYe the colours aren't great - design skills have a long way to go ! Fixed the start and end nodes bug and will look into adding the fast forward button and inverted binary tree maze. Thanks for the ideas !
- balaji1 4y agoThe animation is beautiful. This is art. Thank you artist.
- eoinbarr 4y agoWow, much appreciated :)
- forgotpwd16 4y agoNice explanations of pathfinding algorithms at https://emmilco.github.io/path_finder/ https://emmilco.github.io/path_finder/.
- linhns 4y agoNice 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.
- eoinbarr 4y agoThanks for highlighting that the start and end nodes aren't meant to be moved but I fixed it so that they can't be overridden by a wall. I also made the walls darker for the light theme so hopefully its a bit better !
- ggt31 4y agoWorth to mention https://clementmihailescu.github.io/Pathfinding-Visualizer/# https://clementmihailescu.github.io/Pathfinding-Visualizer/#. I see some inspiration.
- pjmlp 4y agoThis looks great, nice way to teach it. Love the animations.
- eoinbarr 4y agoThanks :)
- yellowapple 4y agoTwo observations: 1. Depth-first pathfinding in an empty grid is delightfully pathological. 2. A* seems like it was born to solve binary-tree mazes, since it always seems to find a way through it on the first try.