This is something I already have a working solution for, but it takes forever (sometimes >5 hours, and I’ve done this half a dozen times in the last week fixing minor details) so I’m curious if there are suggestions for improvement.
I have a grid of cells, like the image below:
That’s 180 x 270, or 48600 total cells, and the colors have the following meaning:
Grey - walkable
Yellow - walkable and interactive
Black - wall or an interactive object (so unwalkable)
One can see that there are regions of the grey cells enclosed by walls. These are “Rooms.” For various reasons I’m interested in getting what I’m calling (for lack of a better word) the “centroids” of each room: the minimum number (and location) of points in the room required to see every point in the room. Imagine a patrolling robot for example, who wants to check every point.
My current code to do this is 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]);
}
var perCellInView = cellsCopy.AsParallel().Select(x => (x, StaticClass.FindInView(x, grid)));
var perCellInViewOrdered = perCellInView.AsParallel().OrderByDescending(xxx => xxx.Item2.Count).ToList();
//Debug.Log("counts: " + perCellInViewOrdered[0].Item2.Count + "," + perCellInViewOrdered[1].Item2.Count);
List<(int, int)> roomCellsAdded = new List<(int, int)>();
while(roomCellsAdded.Count < cells.Count)
{
if(cellsCopy.Count == 0)
{
Debug.LogError("something is wrong here.");
}
var centroid = perCellInViewOrdered[0].x;
var centroidCells = perCellInViewOrdered[0].Item2;
if(centroidCells.Count == 0)
{
Debug.Log("this shouldnt be happening");
break;
}
cellsCopy.Remove(centroid);
roomCellsAdded.AddRange(centroidCells);
centroids.Add((centroid, centroidCells.Count));
var loopPerCellInView = perCellInView.AsParallel().Where(x => centroids.Select(y => y.Item1).Contains(x.x) == false).Select(x => (x.x, x.Item2.Except(roomCellsAdded).ToList()));
perCellInViewOrdered = loopPerCellInView.AsParallel().OrderByDescending(xxx => xxx.Item2.Count()).ToList();
//Debug.Log("counts: " + perCellInViewOrdered[0].Item2.Count + "," + perCellInViewOrdered[1].Item2.Count);
}
}
“cells” is just a List<(int,int)> in the Room class which contains all of the grey squares for a given room. The “StaticClass.FindInView” method finds every location that a given point can see (I can provide that method if desired). The general flow is:
–For each point in a room, find what other points it can view (this will be a list/IEnumerable of “((int,int),List<(int,int)>)” structs)
–Sort the list by the count of the second item, such that the location with the most points-it-can-view is first
-Loop through the following:
–Store the first location as a centroid, as well as the points it can view
–get a “derivation” of the original list that does not include already-stored centroids, and does not include already-in-view locations in the sub-list for each centroid
–sort the “derived” list by the count of the second item
As I mentioned before, this is taking literally hours every time. Makes some sense since I’m iterating through groups of sometimes 10,000+ entries in a room, modifying them and sorting them each loop, but it still seems too long.
In addition, the number of “centroids” I’m seeing seems high - for one room on that grid it was 37 in total. It should be, like, 4 or 5 for most of those rooms.
Does anyone see anything I might be doing wrong or inefficiently?