[HN Gopher] Show HN: BFS, Dijkstra and A* interactive demo made ...
___________________________________________________________________
Show HN: BFS, Dijkstra and A* interactive demo made in React
Author : npretto
Score : 87 points
Date : 2021-01-17 12:54 UTC (1 days ago)
(HTM) web link (github.com)
(TXT) w3m dump (github.com)
| jaydenmilne wrote:
| 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)
| jokethrowaway wrote:
| 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
| oplav wrote:
| 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/
| chrisweekly wrote:
| 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+! :)
| armytricks wrote:
| 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.
| npretto wrote:
| 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.
| tpoacher wrote:
| I think you have a typo in the first introduction popup. It
| says BSD instead of BFS
| djxfade wrote:
| Do I have to build it myself, or do you have it hosted
| somewhere?
| npretto wrote:
| Thanks for pointing that out, the link is actually kinda
| hidden. I added it to the readme
| almata wrote:
| There is a link on the About section: https://interactive-
| pathfinding.netlify.com
| _the_inflator wrote:
| I love pathfinding visualizations. Every time. Good job!
| ggambetta wrote:
| 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...
| vladimirralev wrote:
| 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*
| jschulenklopper wrote:
| 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*.
| mysterydip wrote:
| No discussion of A* etc is complete without a link to red blob
| games' interactive pages:
| https://www.redblobgames.com/pathfinding/a-star/introduction...
| psyc wrote:
| 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?
| Vvector wrote:
| 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/
| mysterydip wrote:
| 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.
| mcv wrote:
| 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.)
| maeln wrote:
| 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 :)
| jschulenklopper wrote:
| Also interesting: https://observablehq.com/@mbostock/best-first-
| search, a visual display of A*
___________________________________________________________________
(page generated 2021-01-18 23:02 UTC)