Tarjan's Algorithm can be used to find choke points, although I haven't tried it myself [1]. I think what I would try is Breadth First Search with multiple star

Tarjan's Algorithm can be used to find choke points, although I haven't tried it myself [1]. I think what I would try is Breadth First Search with multiple start points to calculate various metrics for the map [2] and maybe All-Pairs if you need more [3]. For example, you might use Tarjan's or All-Pairs to find the most commonly used corridors, and then use Breadth First Search from those "central" points to find the "farthest from central corridor" points. [1] https://old.reddit.com/r/roguelikedev/comments/dc4orn/identifying_choke_points_in_maps/ https://old.reddit.com/r/roguelikedev/comments/dc4orn/identi... [2] https://www.redblobgames.com/pathfinding/distance-to-any/ https://www.redblobgames.com/pathfinding/distance-to-any/ [3] https://www.redblobgames.com/pathfinding/all-pairs/ https://www.redblobgames.com/pathfinding/all-pairs/