Find a encircliement in Hexagonal grid (optimization issue)

Question

I have a hex grid of 10000 cells (100x100). The player can grab a cell next to one of his cells (borders). If the player has formed a ring after placing a cell, I want to get a list of cells that ended up in the encircliment. This is what it looks like before creating the enсircliment

The player clicked, and got the cells that were in the ring

It could also look something like this:

var visited = new HashSet<int>();
    var queue = new Queue<int>();
    //6 Starting squares (the player clicks on a cell, we get the neighbors of that cell and count them as starting cell)
    foreach (var tile in startingTiles)
    {
        //If we found the end of the grid, we did not find the encircliment
        if (tgs.CellIsBorder(tile))
        {
            continue;
        }

        visited.Clear();
        queue.Clear();

        visited.Add(tile);
        queue.Enqueue(tile);
        bool failed = false;

        while (queue.Count > 0)
        {
            var currentTile = queue.Dequeue();

            if (tgs.CellIsBorder(currentTile))
            {
                failed = true;
                break;
            }
            
            //List of cells that the player owns + visited cells
            var skipCells = player.myCells.Select(x => x.Index).Concat(visited);
            
            //We get a list of cells to go through further in the search
            var iterate = tgs.CellGetNeighbours(currentTile).Select(x => x.index)
                .Except(skipCells);

            //add cells to check further
            foreach (var neighbor in iterate)
            {
                visited.Add(neighbor);
                queue.Enqueue(neighbor);

            }
        }
        
        //WE FOUND A ENCIRCLEMENT!
        if (failed == false)
        {
            result = GetCellModelFromIndexes(visited);
        }

Of course I have code that works, but only on small grids. If the grid is 10,000, there is already a noticeable delay. Can anyone suggest a more suitable algorithm, or a code fix?

Answer 1

1. Optimize Needlessly Slow Operations

Your basic approach should work well on small to medium maps, it's just that the way you've chosen to implement it is unnecessarily slow:

• You search the same regions multiple times. If neighbour #1, 2 and 3 are all connected to the outside, you search the outside of the map three times when you already knew the right answer from neighbour 1's visited set.

  Start at an adjacent tile of your own territory, then walk the neighbours in order until you come to another player's territory. Search there. Then walk until you find the next tile of your own territory, skipping any others (since you know they border the same set). Check if the next other-player tile after that is already in the visited set before starting a new search. This simple optimization should cut the search time down by half or better.

• You're using LINQ expressions like player.myCells.Select(x => x.Index).Concat(visited). This is great for compact, expressive, readable code, but you pay a cost in performance.

  Consider having a read-only array of tile offsets. Then this code could look something like:

  for (int i = 0; i < 6; i++) {
      int neighbourIndex = currentTile + NeighbourOffests[i];
      if (playerOwner[neighbourIndex] != thisPlayer 
          && !visited.Contains(neighbourIndex)) {
  
          queue.Add(neighbourIndex);
          visited.Add(neighbourIndex);
      }
  }
  

  It's a little more verbose, but it's dead simple to execute.

• You're re-creating your data structures every time you call this function. Since this is something your game needs to do frequently, create your data structures once, and re-use them.

  C#'s System.Collections types get created with a small capacity at first, and gradually re-allocate to larger and larger sizes as you fill them up. If you're creating new ones all the time, you're paying that memory re-allocation cost on every tile placement. But if you re-use them, you pay the "warm-up" cost once, and then continue benefitting from it for free.

  This is also why, if you have a good idea of how many items you'll need to store in the collection (and that number is big), it's a good idea to pass in that initial capacity to their constructor so they can pre-size themselves appropriately, rather than working up to it over several re-allocations as the collection grows.

• You're using a HashSet for what could be a visited flag on each cell in an array. Yes, they're both \$O(1)\$, but looking up this information in a HashSet requires hashing the key and pseudo-random memory access, so it will be noticeably slower. HashSet structures are good for when the space of all possible set members is too big to reasonably allocate memory for all of them in an array, but here it's just your map size, so simpler options are available.

  In particular, iterating the keys of a hashmap is slow, which is what Concat(visited) has to do.

• You're using breadth-first search. This explores cells in order of their distance from the starting point, meaning if your new tile is in the middle of the map, you'll explore an expanding ring out to 50 tiles in all directions (about 7 850 tiles), instead of walking the 50 tiles to the nearest edge. This could be a good use case for depth-first search, or possibly even A* with a heuristic to seek toward the closest edge of the map.

  A quick hacky version of that would be to use depth-first search with an array of neighbour offsets as suggested above, but select which neighbour offset array to use based on the position of your starting tile. You can have 6 different orderings of the neighbours, one trying each cardinal direction first. So choosing the down-prioritized neighbour set when your starting tile is close to the bottom of the map might get you similar behaviour to A*'s heuristic-seeking, but with lower code complexity.

---

2. Algorithmic Efficiencies

I'd recommend trying the simple fixes in suggestion 1. first, and profiling to see if that's enough to make the cases you care about fast. But if you need to scale up to truly massive (or even infinite) maps, a flood fill looking for the edge won't suffice and we'll need a strategy that keeps the iteration more tightly bounded. Here's a sketch of one such strategy...

You can recognize whether a move closes a ring by looking at the pattern of 6 neighbours immediately surrounding the clicked tile:

1. It must have at least two neighbours that are the player's own territory.

2. It must have at least two neighbours of other players' territory.

3. These territory bands must alternate: reading around the hex, it has to go mine -> other -> mine - other or mine -> other -> mine -> other -> mine -> other (counting contiguous runs of neighbours of the same territory as just one word in the sequence).

4. Two of these "mine" territories on either side of an "other" must be from the same connected shape. If so, the ring has successfully cut off this "other" from the rest.

You can determine 4 very quickly (amortized to nearly-constant time) using a disjoint set data structure, as I explain here in the context of determining connectivity in road networks.

Once you know that a ring has been closed, you need to access all the cells inside the ring to change their colours. The trouble is, the method above doesn't tell us which side is "inside".

Instead of doing a flood fill to check (taking time proportional to the area - \$O(n^2)\$), we can walk the border of the shape (proportional to the perimeter - \$O(n)\$). I explain a method here to walk along territory borders of a hex grid. For each other in the list above, start a perimeter walk from an edge between that other and the newly-placed tile, with your "right hand" in your territory and your feet in the other.

Do a little book-keeping: each time your hand moves from one column to another, append its y position to a list for that column. Add +60 to an angle counter whenever you move your hand, and subtract 60 whenever you move your feet.

When you return to your starting point, check the winding of the path by looking at the sign of the total angle accumulated. Negative means the border you walked was the "outside", while positive means you walked the "inside" of the loop.

Either way, your list of y-coordinates where you entered and exited each column now give you a collection of contiguous spans of mine territory. You can iterate over them in a tight loop updating their ownership (and disjoint set) data. You can either do this once for the "outside" border, at the cost of redundantly re-visiting parts of your territory far from the new loop, or for each "inside" border (of which there could be up to two, if the new tile pinched was placed at the junction of a Y shape of other territory, breaking it into three disconnected branches, only one of which still connects to the outside).

This is algorithmically a bit more complicated, but saves you from ever flood-filling the whole map, so it can scale to arbitrarily large maps with cost that stays bounded to the perimeter of the largest/most convoluted contiguous shapes.