3
\$\begingroup\$

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

enter image description here

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:

enter image description here

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:

enter image description here

  • 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.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Breadth-first search will get you the set of candidate tiles within 7 hops of the start more simply than A*, since you're not plotting a path to a specific destination with varying move costs. This looks like a classic optimization problem that the Computer Science StackExchange might be able to weigh in on. \$\endgroup\$
    – DMGregory
    May 24 '21 at 11:05
  • 1
    \$\begingroup\$ @DMGregory thank for comment! You are right, I'm actually using BFS in my attempt (cos there's no destination). Will correct the question now. \$\endgroup\$
    – Kromster
    May 24 '21 at 12:48
  • 1
    \$\begingroup\$ This looks like a graph partition problem. You have a set of nodes that are reachable from your source node in at most 7 hops, connected to each other by edges, and also with edges connecting to an external "sink" node wherever they neighbour a non-reachable, non-obstacle cell. You seek the minimum cut (the smallest number of edges we need to sever by building fences) that separates the source from the sink that keeps at least 20 nodes on the "source" side of the partition. \$\endgroup\$
    – DMGregory
    May 24 '21 at 13:22
0
\$\begingroup\$

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.

    enter image description here

    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:

    enter image description here enter image description here

    • 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.

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .