4 ms·

Off-topic a bit, but I've been curious about a 2D pathfinding problem for a while that this site doesn't seem to tackle despite having lots of articles on the s

Off-topic a bit, but I've been curious about a 2D pathfinding problem for a while that this site doesn't seem to tackle despite having lots of articles on the subject. Is there an algorithm out there for finding "enclaves" (i.e. places where you might want to place rewards, spawn the player) within a large 2D terrain grid? Not super precise, but given a 2D boolean array of pathable/unpathable cells, say generated by Perlin noise, find locations that are only accessible via a relatively narrow "choke point". Example: https://imgur.com/a/jFPXlS5 https://imgur.com/a/jFPXlS5 Standard pathfinding algorithms don't provide enough information to do this, but maybe there's some kind of heuristic approach that could work well.

stefan_ 3y ago
Lots of pathfinding solutions prefer to work with connected convex polygons (since inside the polygon, you can always go straight to every other point inside). You could merge your cells into these polygons and then filter for small ones by area, I guess.
Marazan 3y ago
Brute force and ignorance approach: Choose random starting point and compute distance to all other points on the map. Repeat for multiple random starting points. Average the distance. Points with high average distance are difficult to reach.
otikik 3y ago
You are not trying to find a "path" since you don't have a starting point - you only have end points. Your enclaves are more defined by the shape of the walls (roughly x cells in radius) than with the fact that you reach them through chokepoints. After all, a chokepoint can be just a small door in an otherwise big corridor, separating two big areas. And by concentrating on chokepoints you will lose all the "isolated islands". You might be luckier treating this as a "map treatment" problem. An algorithm that does things to the whole map, and then reads the result. For example: 1. Start assigning a score of 0 to all map cells. 2. For every cell in the map, set to 1 if it's in contact with any walls 3. Then add 1 to every cell of the map if it contacts a cell with a non-zero value 4. Repeat the above step n times, where n is the average "radius" of you enclave rooms. 5. Every cell with a score of n or higher is a "candidate". For every candidate: 5.a Check that none of the cells around have a bigger score. If so, move on to the next candidate 5.b Check that there's no "treasure" around it in a circle of radius n 5.c You have found the center of an enclave. Mark it with "treasure" and move on to the next cell.
gabereiser 3y ago
Find starting point in dungeon. A* to every room. Rooms with a large distance (iter count) and with only one or two paths out (choke points, use graph to see edges) become potentials, every potential that is _far & narrow_ is flagged “enclave” with rewards increasing by distance to start. This is one way to approach the problem. The other way is to do prefab rooms and when generating your dungeons, randomly select one or two prefab enclave rooms to throw into the shuffle. Shuffle the rooms and spread them out then connect hallways and such. This is the approach that Enter the Gungeon took. Another approach is what @otikik describes. Tracing the walls buy assigning a value to the cells that can then be scored. Minesweeper style.
amitp 3y ago
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/

stefan_ 3y ago

Lots of pathfinding solutions prefer to work with connected convex polygons (since inside the polygon, you can always go straight to every other point inside). You could merge your cells into these polygons and then filter for small ones by area, I guess.

Marazan 3y ago

Brute force and ignorance approach: Choose random starting point and compute distance to all other points on the map. Repeat for multiple random starting points. Average the distance. Points with high average distance are difficult to reach.

otikik 3y ago

You are not trying to find a "path" since you don't have a starting point - you only have end points. Your enclaves are more defined by the shape of the walls (roughly x cells in radius) than with the fact that you reach them through chokepoints. After all, a chokepoint can be just a small door in an otherwise big corridor, separating two big areas. And by concentrating on chokepoints you will lose all the "isolated islands". You might be luckier treating this as a "map treatment" problem. An algorithm that does things to the whole map, and then reads the result. For example: 1. Start assigning a score of 0 to all map cells. 2. For every cell in the map, set to 1 if it's in contact with any walls 3. Then add 1 to every cell of the map if it contacts a cell with a non-zero value 4. Repeat the above step n times, where n is the average "radius" of you enclave rooms. 5. Every cell with a score of n or higher is a "candidate". For every candidate: 5.a Check that none of the cells around have a bigger score. If so, move on to the next candidate 5.b Check that there's no "treasure" around it in a circle of radius n 5.c You have found the center of an enclave. Mark it with "treasure" and move on to the next cell.

gabereiser 3y ago

Find starting point in dungeon. A* to every room. Rooms with a large distance (iter count) and with only one or two paths out (choke points, use graph to see edges) become potentials, every potential that is _far & narrow_ is flagged “enclave” with rewards increasing by distance to start. This is one way to approach the problem. The other way is to do prefab rooms and when generating your dungeons, randomly select one or two prefab enclave rooms to throw into the shuffle. Shuffle the rooms and spread them out then connect hallways and such. This is the approach that Enter the Gungeon took. Another approach is what @otikik describes. Tracing the walls buy assigning a value to the cells that can then be scored. Minesweeper style.

amitp 3y ago

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/