News for hackers. Stuff that matters.
Re:Show HN: BFS, Dijkstra and A* interactive demo made in React by mysterydip on Monday January 18, 2021 @10:31AM (#25822666)
No discussion of A* etc is complete without a link to red blob games' interactive pages: https://www.redblobgames.com/pathfinding/a-star/introduction...
Re:Show HN: BFS, Dijkstra and A* interactive demo made in React by psyc on Monday January 18, 2021 @11:27AM (#25823333)
That was also my introduction to A*. Say, does anyone have insights into optimizing path finding for speed, as the map gets larger and number of entities increases?
Re:Show HN: BFS, Dijkstra and A* interactive demo made in React by Vvector on Monday January 18, 2021 @11:59AM (#25823748)
One method is to preprocess the map, which then can greatly increase the accuracy of the A* heuristic.

https://www.redblobgames.com/pathfinding/l1-clarkson/

Re:Show HN: BFS, Dijkstra and A* interactive demo made in React by mysterydip on Monday January 18, 2021 @12:04PM (#25823810)
I would think you could do a scaling of sorts, like if your map was 100x100 you could reduce it to 10x10 with "clear", "fully blocked", and "partially blocked" based on the contents, and work a general path at that meta level first, then focus on each grid map at the full scale to navigate around local obstacles. You could do multiple scales depending on your needs and where the terrain makes sense to categorize most into clear or blocked.
Re:Show HN: BFS, Dijkstra and A* interactive demo made in React by jaydenmilne on Monday January 18, 2021 @12:21PM (#25824046)
Same story, made something similar in straight JavaScript while I was at school and never showed it to anyone:

https://jayd.ml/algorithms/search/ (source https://github.com/jaydenmilne/jaydenmilne.github.io/tree/ma...)

Features:

- Draw your own maze!

- Several different algorithms!

- Adjust solving speed / step algorithm!

- Bugs!

- Share your mazes in the URL (abuse link shorteners to store your data! shorturl.at/ioyT9)

I'm quite proud of how I (ab)used async/await to increase the stack size and be able to easily step and delay the algorithms without having to rewrite them to be re-entrant.

(in case you're wondering, left click to draw walls, right click to place start then end node, left click and drag on walls to go into erase mode)

Re:Show HN: BFS, Dijkstra and A* interactive demo made in React by npretto on Sunday January 17, 2021 @07:59AM (#25810326)
Two years ago I had to make a project about pathfinding for a university project, and I just realised I never showed it anywhere.

I made this little interactive playground for various pathfinding algorithms showing how they can be seen as a general algorithm with different a different queue and different heuristic in use.

The readme has some theory but the cool thing is the link to the app on netlify where you can experiment moving the positions of start, goal and of the obstacles.

If you're interested I'd suggest you keep the readme open while toying with the app, as the readme has more theory.

Re:Show HN: BFS, Dijkstra and A* interactive demo made in React by tpoacher on Monday January 18, 2021 @01:22PM (#25824787)
I think you have a typo in the first introduction popup. It says BSD instead of BFS
Re:Show HN: BFS, Dijkstra and A* interactive demo made in React by djxfade on Monday January 18, 2021 @08:34AM (#25821591)
Do I have to build it myself, or do you have it hosted somewhere?
Re:Show HN: BFS, Dijkstra and A* interactive demo made in React by npretto on Monday January 18, 2021 @10:12AM (#25822504)
Thanks for pointing that out, the link is actually kinda hidden. I added it to the readme
Re:Show HN: BFS, Dijkstra and A* interactive demo made in React by almata on Monday January 18, 2021 @08:39AM (#25821645)
There is a link on the About section: https://interactive-pathfinding.netlify.com
Re:Show HN: BFS, Dijkstra and A* interactive demo made in React by _the_inflator on Monday January 18, 2021 @08:45AM (#25821688)
I love pathfinding visualizations. Every time. Good job!
Re:Show HN: BFS, Dijkstra and A* interactive demo made in React by ggambetta on Monday January 18, 2021 @09:01AM (#25821851)
Nice work :) There's never going to bee too many learning materials with good visualizations.

For pathfinding, I've made one myself [0], and the Red Blob Games [1] one is also very popular.

[0] https://gabrielgambetta.com/generic-search.html

[1] https://www.redblobgames.com/pathfinding/a-star/introduction...

Re:Show HN: BFS, Dijkstra and A* interactive demo made in React by armytricks on Monday January 18, 2021 @09:00AM (#25821837)
For your non-admissible heuristic demo, it might also be interesting to look at squaring the euclidian distance and the affect of biasing the algorithm in this way.
Re:Show HN: BFS, Dijkstra and A* interactive demo made in React by mcv on Monday January 18, 2021 @10:55AM (#25822967)
I think the short summary is: Dijkstra is best when you don't know or care where you're going (there's no heuristic to tell you how close you are, or you want to know distances to all locations), but if that heuristic exists, A* is better.

I once used A* in a coding challenge for a job. Create a grid (in React) where you can place obstacles, wormholes, a start and a finish, and find the shortest route through it. The wormholes normally break A*, but I'd figured out a way to take them into account. Was a fun challenge. (Didn't take the job.)

Re:Show HN: BFS, Dijkstra and A* interactive demo made in React by maeln on Monday January 18, 2021 @12:14PM (#25823928)
Yes, I would like to see more pathfinding demo talking about 0 weight link, or even negative weight (although I don't know of any pathfinding problem that would use negative weight). Floyd–Warshall is always ignored although I think it is cool. Now you can pathfind with portal :)
Re:Show HN: BFS, Dijkstra and A* interactive demo made in React by vladimirralev on Monday January 18, 2021 @01:37PM (#25824950)
I think your priority queue is doing O(nlogn) sort for every insert https://github.com/npretto/pathfinding/blob/master/src/algo/...

This should be a heap with O(logn) insert instead to be truly Dijsktra/A*

Re:Show HN: BFS, Dijkstra and A* interactive demo made in React by jschulenklopper on Monday January 18, 2021 @03:17PM (#25826097)
Dijkstra / A* search algorithm do not prescribe which algorithm to use to add/insert items to the queue, or which algorithm to use to maintain a priority queue. So, your optimization might be an improvement, but it doesn't make the process "more or less" truly Dijkstra or A*.
Re:Show HN: BFS, Dijkstra and A* interactive demo made in React by oplav on Monday January 18, 2021 @11:27AM (#25823339)
Nice job!

For others who want to play with visualizing different search algorithms, this is another cool tool:

https://qiao.github.io/PathFinding.js/visual/

Re:Show HN: BFS, Dijkstra and A* interactive demo made in React by jschulenklopper on Monday January 18, 2021 @12:38PM (#25824255)
Also interesting: https://observablehq.com/@mbostock/best-first-search, a visual display of A*
Re:Show HN: BFS, Dijkstra and A* interactive demo made in React by chrisweekly on Monday January 18, 2021 @09:26AM (#25822073)
Very cool, thanks for sharing! Bonus points for non-gratuitous use of currying and generators in the implementation, not to mention clear and concise documentation. A+! :)
Re:Show HN: BFS, Dijkstra and A* interactive demo made in React by d33lio on Monday January 18, 2021 @07:31PM (#25828516)
Thanks for posting this! Your repo is a fantastic bit of reading for people who are curious how to make a non-standard visualization with React JS.
Re:Show HN: BFS, Dijkstra and A* interactive demo made in React by jokethrowaway on Monday January 18, 2021 @11:25AM (#25823313)
Very cool, well done!

It seems to crash (white page) if you cover the destination point with the constraint box.

You may want to look into (lazy) Theta* next