在作为网格的房间中查找具有最大可见性的点
Find points with maximum visibility in a room-as-grid
我有一个二维单元格网格，如下所示：
我想找到“质心”，或者每个房间中可以看到最多其他单元格的地方。例如，“centroid”1 可以看到 500 个其他单元格，“centroid”2 可以看到 400 个其他单元格（不包括在前 500 个单元格中），依此类推（如果有更好的名称请告诉我）。
我目前正在使用以下代码执行此操作。
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;
}
上面代码的“简短”摘要是每个位置首先确定它可以看到其周围的哪些单元格。这变成了一个元组列表，List<((int,int), List<(int,int)>)>，其中第一项是位置，第二项是它查看的所有单元格。该主列表按子列表的计数排序，因此具有最多 cells-it-can-vew 的项目排在第一位。这是作为质心添加的，它可以查看的所有单元格都添加到第二个（“已处理”）列表中。形成了修改后的“主列表”，每个子列表现在不包括第二个列表中的任何内容。它循环执行此操作，直到添加了 90% 的单元格。
一些输出：
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
这对我来说太慢了。任何人都可以建议这样做的替代方法吗？对于所有细胞，基本上唯一的信息是它们是否“打开”或是否可以透过它们（相对于墙壁之类的东西）。
具有固定整数斜率的近似解
要获得较大的加速（从房间数量的二次方到线性），您可以决定在每个点只检查几个整数斜率。这些是可见性的等价 类，即，如果单元格 x 可以沿着这条线看到单元格 y，并且单元格 y 可以沿着同一条线看到单元格 z，那么所有 3 个单元格都可以看到彼此。然后你只需要计算一次沿特定线的每个“可见性间隔”，而不是每个单元格。
您可能希望至少检查水平坡度、垂直坡度和两个 45 度对角线坡度。对于水平方向，从单元格 (1, 1) 开始，向右移动直到碰到墙，比方说在 (5, 1) 处。然后单元格 (1, 1), (2, 1), (3, 1) 和 (4, 1) 都可以沿着这个斜率看到彼此，所以虽然你从 (1, 1) 开始，但没有必要对其他 3 个单元格重复计算——只需将此列表的副本（或者甚至是指向它的指针，这样速度更快）添加到所有 4 个单元格的可见性列表中。保持向右行驶，并在撞到非墙壁后立即重复该过程。然后在下一行重新开始。
45 度对角线的可见性检查稍微困难一些，但并不多，检查我们水平前进 1 和垂直前进一些 k（或反之亦然）的其他斜坡大致相同。 （检查一般坡度，比如每 2 步向右上升 3 步，可能有点棘手。）
如果您使用指针而不是列表副本，对于给定的斜率，此方法会在每个单元格上花费固定的摊销时间：虽然找到某个单元格的 k 个水平可见邻居需要 O(k) 时间，但这意味着不再需要需要对其中任何一个进行水平处理。因此，如果您检查恒定数量的斜率（例如，我建议的四个斜率），则这是处理 n 个单元格的总时间 O(n)。相比之下，我认为您当前的方法至少需要 O(nq) 时间，其中 q 是一个单元格可见的单元格的平均数量。
我有一个二维单元格网格，如下所示：
我想找到“质心”，或者每个房间中可以看到最多其他单元格的地方。例如，“centroid”1 可以看到 500 个其他单元格，“centroid”2 可以看到 400 个其他单元格（不包括在前 500 个单元格中），依此类推（如果有更好的名称请告诉我）。
我目前正在使用以下代码执行此操作。
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;
}
上面代码的“简短”摘要是每个位置首先确定它可以看到其周围的哪些单元格。这变成了一个元组列表，List<((int,int), List<(int,int)>)>，其中第一项是位置，第二项是它查看的所有单元格。该主列表按子列表的计数排序，因此具有最多 cells-it-can-vew 的项目排在第一位。这是作为质心添加的，它可以查看的所有单元格都添加到第二个（“已处理”）列表中。形成了修改后的“主列表”，每个子列表现在不包括第二个列表中的任何内容。它循环执行此操作，直到添加了 90% 的单元格。
一些输出：
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
这对我来说太慢了。任何人都可以建议这样做的替代方法吗？对于所有细胞，基本上唯一的信息是它们是否“打开”或是否可以透过它们（相对于墙壁之类的东西）。
具有固定整数斜率的近似解
要获得较大的加速（从房间数量的二次方到线性），您可以决定在每个点只检查几个整数斜率。这些是可见性的等价 类，即，如果单元格 x 可以沿着这条线看到单元格 y，并且单元格 y 可以沿着同一条线看到单元格 z，那么所有 3 个单元格都可以看到彼此。然后你只需要计算一次沿特定线的每个“可见性间隔”，而不是每个单元格。
您可能希望至少检查水平坡度、垂直坡度和两个 45 度对角线坡度。对于水平方向，从单元格 (1, 1) 开始，向右移动直到碰到墙，比方说在 (5, 1) 处。然后单元格 (1, 1), (2, 1), (3, 1) 和 (4, 1) 都可以沿着这个斜率看到彼此，所以虽然你从 (1, 1) 开始，但没有必要对其他 3 个单元格重复计算——只需将此列表的副本（或者甚至是指向它的指针，这样速度更快）添加到所有 4 个单元格的可见性列表中。保持向右行驶，并在撞到非墙壁后立即重复该过程。然后在下一行重新开始。
45 度对角线的可见性检查稍微困难一些，但并不多，检查我们水平前进 1 和垂直前进一些 k（或反之亦然）的其他斜坡大致相同。 （检查一般坡度，比如每 2 步向右上升 3 步，可能有点棘手。）
如果您使用指针而不是列表副本，对于给定的斜率，此方法会在每个单元格上花费固定的摊销时间：虽然找到某个单元格的 k 个水平可见邻居需要 O(k) 时间，但这意味着不再需要需要对其中任何一个进行水平处理。因此，如果您检查恒定数量的斜率（例如，我建议的四个斜率），则这是处理 n 个单元格的总时间 O(n)。相比之下，我认为您当前的方法至少需要 O(nq) 时间，其中 q 是一个单元格可见的单元格的平均数量。