How to maximize enclosed area and minimize perimeter on a grid with obstacles?

Question

Developing an RTS game, I have a tile-based terrain (grid) filled with obstacles. It looks like this (red shapes are obstacles):

Now I need to plan an enclosed area on the terrain with some restrictions:

• tile marked with a "star" must be included (it is a seed)
• area needs to be at least 20 tiles (for this example)
• farthest area tile from the seed needs to be no more than 7 steps away (for this example)
• area needs to traversable by moving in 4 directions
• area should be bound by existing obstacles and by new fences
• new fences building takes time and resources, it is beneficial to use existing obstacles as much as possible and have the smallest number of fences placed.
• there are cases where terrain could be free of any obstacles, or contrary to that - be a maze-like labyrinth)
• it is okay to fail (e.g. there's not enough walkable tiles around the seed), or the area/fences ratio is too low.
• processing is done on CPU (if that matters)

So, here are some "manual" attempts at outlining an area of required size using the least fences:

As you can see, there are 3 enclosed areas (green, blue, orange) with very similar perimeters, yet different areas. Best one in this case would be "green" one - it has the least fences added (just 10) and has the sufficient area (21).

What is the algorithm to allow to plan area of given size (~20) while minimizing the amount of additional fences required?

---

So far I have tried to take the larger area and try to clip it - using BFS to get the area within possible reach (7 steps), clipped the last step (since it is touching the unexplored and has no neighbor info) and clipped the obvious protruding buds - leaves plenty of tiles to work with. I'm out of good ideas on how to improve from that:

• yellow tile is the seed
• red tiles are walkable (saturation shows distance from the seed)
• dark grey tiles are obstacles
• light grey tiles are obstacles that also need fences
• purple tiles got clipped by existing incomplete algo
• black tiles are unexplored
• yellow dashes are required fences

As you can see, it looks quite sub-optimal, but I'm at loss as to how to proceed.

Answer 1

An idea that came to me while typing the question and preparing the pictures:

1. Take existing results (BFS to get the area within reach (7+1 steps)/

2. Clip the last step (since it is touching the unexplored and has no neighbor info)

3. Clip the obvious protruding buds (3 fences around 1 tile)

4. We could "blow up" all the corners - if 2 fences are to be placed in a zig-zag pattern, we can always flip them to include one more tile while keeping the perimeter the same.

   

   however I'm leaving this step for later evaluation, since that would include the yet unexplored tiles into the mix.

5. Now we can repeatedly scan the resulting area across (horizontal and vertical) and evaluate the side edges to see how many fences would get removed or added if that line was to be clipped:

   

   • white dashes show the sorted candidates for clipping (the more fences we remove and the less area we remove is better).

This gives a quite good result, with a typical 2/1 factor of area/fences.