3 ms·
It would do just fine - but that's because OP is essentially grabbing on the intuition behind Visibility Graph search, which is (or was) a very common path plan
by jvanderbot 2y ago
It would do just fine - but that's because OP is essentially grabbing on the intuition behind Visibility Graph search, which is (or was) a very common path planning algorithm using just obstacle boundaries.
The algorithm in a maze would just use "intersections" as successors, rather than "Next next step down the hall".
This is, in fact, an optimal search algorithm for this problem, and scales much better than any grid search in this case.
- Farer 2y agoI also hope it works as well as you’re thinking.
- jvanderbot 2y agoIt's not my idea. There's a bunch of video tutorials on it if you want to google around. And I actually have implemented this for some problems and it actually is as good as the theory says. The hard part is transforming from "Grid with 0/1 obstacles" to "sparse set of visible nodes". That's not trivial and can put the whole thing out of reach.