4 ms·
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 almos
by eknkc 4y ago
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 https://link.ekin.dev/OTW2xy
- _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; });
- squeaky-clean 4y agoThe 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 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.
- phire 4y agoIt'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)
- squeaky-clean 4y agoIt 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.
- Karliss 4y ago"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.
- deleted 4y ago[deleted]
- marginalia_nu 4y agoManhattan metric maybe? In that case a diagonal line isn't shorter than an L-shaped route.
- kentonv 4y agoYeah 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 https://github.com/eoin-barr/pathfinding-visualizer/pull/1
- StoicMonkey 4y agoNice fix! Now if only someone could answer this Cloudflare Workers question... https://stackoverflow.com/questions/74331904/racing-javascript-promises-while-ensuring-all-promises-complete https://stackoverflow.com/questions/74331904/racing-javascri...