5 ms·
Unless the "outline" is like tensing a rubber band around the object. In that case, the collision would happen outside the convex part. Anyway, the details are
by juancn 2y ago
Unless the "outline" is like tensing a rubber band around the object. In that case, the collision would happen outside the convex part.
Anyway, the details are not enough for me to fully grasp the algo described.
- jvanderbot 2y agoYou're referring to the "Convex Hull". And if you are inside a shape, drawing edges to the visibile vertices of the shape (until you're on the boundary of the convex hull) will easily get you a path out, and, bonus, will eventually draw a perfect shortest path to the end. See: https://news.ycombinator.com/item?id=42608107#42626311 https://news.ycombinator.com/item?id=42608107#42626311
- philsnow 2y agoImagine 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.
- juancn 2y agoYeah, thank you! I couldn't find the right term.