Draggable objects

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.

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.

[dead]

Amit is a treasure. I referenced his articles many times when making my own games. We could really use more thoughtful and friendly visual learning resources like this for other subject matter.

I love how half the comments on here are about what a nice person the author of the site is. I, too, have had only positive interactions with Amit!