Skip to content(if available)orjump to list(if available)

Keep 'em (not) separated: detecting discontinuities in grid graphs

seveibar

This is a very nice writeup, in game engines, they often cache a “nav mesh” that indicates how one point can go to basically any other point. As the author, mentioned, finding a path to a known outer point validates that the point has not been enclosed, so it seems like this could be solved efficiently with a cached pathfinding algorithm I’d also consider forming a graph from the grid cells and using a max flow algorithm, these are very fast! No affiliation but I love this paper on cached pathfinding algorithms for games https://www.gameaipro.com/GameAIPro/GameAIPro_Chapter17_Path...