Find points with maximum visibility in a room-as-grid

Question

I have a 2D grid of cells, like so:

I want to find the "centroids," or the places in each room that can see the most other cells. For example, "centroid" 1 can see 500 other cells, "centroid" 2 can see 400 other cells (NOT included in the first 500), and so on (if there's a better name for this let me know).

I'm currently doing this with the code below.

    public void SetCentroids(CellWalkableState[,] grid)
    {
        centroids = new List<((int, int), int)>();
        List<(int, int)> cellsCopy = new List<(int, int)>();
        for (int i = 0; i < cells.Count; i++)
        {
            cellsCopy.Add(cells[i]);
        }
        Debug.Log(DateTime.Now.ToString("o") + " - Setting centroids for room with " + cells.Count + " cells");
        var perCellInView = cellsCopy.AsParallel().Select(x => (x, StaticClass.FindInView(x, grid))).ToList();
        var force_start = perCellInView.First();
        Debug.Log(DateTime.Now.ToString("o") + " - got in view");
        var perCellInViewOrdered = perCellInView.AsParallel().OrderByDescending(xxx => xxx.Item2.Count);
        var force_start_1 = perCellInViewOrdered.First();
        Debug.Log(DateTime.Now.ToString("o") + " - sorted");
        List<(int, int)> roomCellsAdded = new List<(int, int)>();
        while(roomCellsAdded.Count < (cells.Count*0.9))
        {
            if(cellsCopy.Count == 0)
            {
                Debug.LogError("something is wrong here.");
            }
            var centroid = perCellInViewOrdered.First().x;
            var centroidCells = perCellInViewOrdered.First().Item2;
            if(centroidCells.Count == 0)
            {
                Debug.Log("this shouldnt be happening");
                break;
            }
            roomCellsAdded.AddRange(centroidCells);
            centroids.Add((centroid, centroidCells.Count));
            Debug.Log(DateTime.Now.ToString("o") + " - added centroids, " + roomCellsAdded.Count + " cells in view");
            var loopPerCellInView = perCellInView.AsParallel().Where(x => centroids.Select(y => y.Item1).Contains(x.x) == false).Select(x => (x.x, x.Item2.Except(roomCellsAdded).ToList())).ToList();
            Debug.Log(DateTime.Now.ToString("o") + " - excluded");
            perCellInViewOrdered = loopPerCellInView.AsParallel().OrderByDescending(xxx => xxx.Item2.Count);
            Debug.Log(DateTime.Now.ToString("o") + " - resorted");
        }
    }

    public static List<(int, int)> FindInView((int,int) start, CellWalkableState[,] grid)
    {
        List<(int, int)> visible = new List<(int, int)>() { start };
        bool alive = true;
        int r = 1;
        var length_x = grid.GetLength(0);
        var length_y = grid.GetLength(1);
        List<(int, int)> searched = new List<(int, int)>();
        List<double> angles = new List<double>();
        while(alive)
        {
            //alive = false;
            int newR = r;
            int count = CountFromR(newR);
            var angleInc = 360.0 / count;
            var rNexts = Enumerable.Repeat(1, count).ToArray();
            for (int i = 0; i < count; i++)
            {
                var angle = angleInc * i;
                if(angles.Contains(angle) == false)
                {
                    angles.Add(angle);
                    float cos = Mathf.Cos((float)(Mathf.Deg2Rad * angle));
                    float sin = Mathf.Sin((float)(Mathf.Deg2Rad * angle));
                    var b = r;
                    var p = i % (r * 2);
                    var d = math.sqrt(math.pow(b, 2) + math.pow(p, 2));
                    var dScaled = d / r;
                    bool keepGoing = true;
                    while(keepGoing)
                    {
                        var rCur = dScaled * (rNexts[i]);
                        var loc = (start.Item1 + Mathf.RoundToInt(rCur * cos), start.Item2 + Mathf.RoundToInt(rCur * sin));
                        if (searched.Contains(loc) == false)
                        {
                            searched.Add(loc);
                            if (loc.Item1 >= 0 && loc.Item1 < length_x && loc.Item2 >= 0 && loc.Item2 < length_y)
                            {
                                if (grid[loc.Item1, loc.Item2] == CellWalkableState.Interactive || grid[loc.Item1, loc.Item2] == CellWalkableState.Walkable)
                                {
                                    visible.Add(loc);
                                }
                                else
                                {
                                    keepGoing = false;
                                }
                            }
                            else
                            {
                                keepGoing = false; // invalid, stop
                            }
                        }
                        else
                        {
                            if (visible.Contains(loc) == false)
                            {
                                keepGoing = false; //  can stop, because we can't see past this place
                            }
                        }
                        if(keepGoing)
                        {
                            rNexts[i]++;
                        }
                    }
                }
            }
            angles = angles.Distinct().ToList();
            searched = searched.Distinct().ToList();
            visible = visible.Distinct().ToList();
            if(rNexts.All(x => x <= r))
            {
                alive = false;
            }
            else
            {
                r = rNexts.Max();
            }
        }
        return visible;
    }

    static int CountFromR(int r)
    {
        return 8 * r;
    }

The "short" summary of the code above is that each location first determines what cells around itself it can see. That becomes a list of tuples, List<((int,int), List<(int,int)>)>, where the first item is the location and the second is all cells it views. That main list is sorted by the count of the sublist, such that the item with the most cells-it-can-vew is first. That's added as a centroid, and all cells it can view are added to a second ("already handled") list. A modified "main list" is formed, with each sublist now excluding anything in the second list. It loops doing this until 90% of the cells have been added.

Some output:

2021-04-27T15:24:39.8678545-04:00 - Setting centroids for room with 7129 cells 2021-04-27T15:45:26.4418515-04:00 - got in view 2021-04-27T15:45:26.4578551-04:00 - sorted 2021-04-27T15:45:27.3168517-04:00 - added centroids, 4756 cells in view 2021-04-27T15:45:27.9868523-04:00 - excluded 2021-04-27T15:45:27.9868523-04:00 - resorted 2021-04-27T15:45:28.1058514-04:00 - added centroids, 6838 cells in view 2021-04-27T15:45:28.2513513-04:00 - excluded 2021-04-27T15:45:28.2513513-04:00 - resorted 2021-04-27T15:45:28.2523509-04:00 - Setting centroids for room with 20671 cells

This is just too slow for my purposes. Can anyone suggest alternate methods of doing this? For all of the cells essentially the only information one has is whether they're "open" or one can see through them or not (vs something like a wall).

Answer 1

An approximate solution with fixed integer slopes

For a big speedup (from quadratic in the number of rooms to linear), you could decide to check just a few integer slopes at each point. These are equivalence classes of visibility, i.e., if cell x can see cell y along such a line, and cell y can see cell z along the same line, then all 3 cells can see each other. Then you only need to compute each "visibility interval" along a particular line once, rather than per-cell.

You would probably want to check at least horizontal, vertical and both 45-degree diagonal slopes. For horizontal, start at cell (1, 1), and move right until you hit a wall, let's say at (5, 1). Then the cells (1, 1), (2, 1), (3, 1) and (4, 1) can all see each other along this slope, so although you started at (1, 1), there's no need to repeat the computation for the other 3 cells -- just add a copy of this list (or even a pointer to it, which is faster) to the visibility lists for all 4 cells. Keep heading right, and repeat the process as soon as you hit a non-wall. Then begin again on the next row.

Visibility checking for 45-degree diagonals is slightly harder, but not much, and checking for other slopes in which we advance 1 horizontally and some k vertically (or vice versa) is about the same. (Checking for for general slopes, like for every 2 steps right go up 3, is perhaps a bit trickier.)

Provided you use pointers rather than list copies, for a given slope, this approach spends amortised constant time per cell: Although finding the k horizontally-visible neighbours of some cell takes O(k) time, it means no further horizontal processing needs to be done for any of them. So if you check a constant number of slopes (e.g., the four I suggested), this is O(n) time overall to process n cells. In contrast, I think your current approach takes at least O(nq) time, where q is the average number of cells visible to a cell.