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 the A* to get the area within reach (7 steps), clipped the last step (since it is unexplored and has no neighbor info) and clipped the obvious protruding buds, but 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.