4 ms·
Imagine a maze or labyrinth, with the agent and the destination both inside of it. Is it useful to try to figure out the convex hull of the walls, even if it i
by philsnow 2y ago
Imagine a maze or labyrinth, with the agent and the destination both inside of it. Is it useful to try to figure out the convex hull of the walls, even if it is effectively "the entire maze"?
The agents in the article seem to mostly be finding their way around sparsely-distributed, discrete obstacles, so I can see how the "raycasting" approach described would work well, but in a sufficiently obstructed environment like a maze, something like (double-ended) A* is going to both be simpler and likely perform better.
- jvanderbot 2y agoYou can path-find using only vertices and a can-see function to generate a-star successors. The convex hull is just where the paths will go if it has to go around an obstacle. So if your maze is specified as obstacles take the vertices. If your maze is specified some other way it depends how expensive it is to translate it. What you're suggesting is fine and well and good, but it will in an asymptotic analysis do more work than double ended a* that only expands successors for intersections. Think about all the iterations where the expanded state is just one more grid cell closer to the end of the hall, vs just jumping to the end of the hall. If you limit to counting only iterations, a geometric approach is faster (vs grid). That may not be the best way to do it in practice. It's also way harder to implement because let's face it everything is a grid.