如何在bool[,]中快速查找离指定Vector2最近的True值索引？

嘿，针对你要优化二维bool数组中查找最近True坐标的需求，我给你几个性能优先的方案，完全甩开暴力遍历O(L×W)的低效问题：

核心前提：预处理所有True坐标 #

首先必须做一次性预处理：把数组中所有True的坐标提取出来，存入合适的数据结构。这个步骤只需要在数组初始化或更新时执行一次，后续所有查询都基于这个预存集合操作——这是性能提升的关键，毕竟重复查询时，预处理的成本可以忽略不计。

性能优先的数据结构与实现思路 #

1. 分层扩展查找 + HashSet（推荐，平均性能最优） #

这种思路是从目标点向外逐层扩展检查，一旦找到存在于HashSet中的坐标就立即返回，不需要遍历所有True点：

• 先检查目标点本身是否为True，是的话直接返回
• 然后从距离1开始，逐层检查所有曼哈顿距离为当前值的点，直到找到第一个在HashSet中的坐标
• 曼哈顿距离计算比欧氏距离快，能快速缩小候选范围，若需要精确直线距离，找到候选后再做验证即可

具体实现（C# 风格，性能优先）：

private HashSet<Vector2> _truePositions;
private int _gridRows;
private int _gridCols;

// 预处理：提取所有True坐标
public void Preprocess(bool[,] grid)
{
    _truePositions = new HashSet<Vector2>();
    _gridRows = grid.GetLength(0);
    _gridCols = grid.GetLength(1);
    
    // 一次性遍历数组存入HashSet，O(L×W)仅执行一次
    for (int y = 0; y < _gridRows; y++)
    {
        for (int x = 0; x < _gridCols; x++)
        {
            if (grid[y, x])
            {
                _truePositions.Add(new Vector2(x, y));
            }
        }
    }
}

public Vector2 GetNearestTrue(Vector2 target)
{
    // 先检查目标点本身
    if (_truePositions.Contains(target))
        return target;

    // 最大可能距离设为数组对角线长度的上限
    int maxDistance = Math.Max(_gridRows, _gridCols);
    
    // 逐层扩展查找
    for (int d = 1; d <= maxDistance; d++)
    {
        // 遍历所有曼哈顿距离为d的点
        for (int dx = -d; dx <= d; dx++)
        {
            int dyOffset = d - Math.Abs(dx);
            // 检查正dy方向的点
            Vector2 candidate1 = new Vector2(target.X + dx, target.Y + dyOffset);
            if (IsInGrid(candidate1) && _truePositions.Contains(candidate1))
                return candidate1;
            
            // 检查负dy方向的点（避免重复检查dy=0的情况）
            if (dyOffset != 0)
            {
                Vector2 candidate2 = new Vector2(target.X + dx, target.Y - dyOffset);
                if (IsInGrid(candidate2) && _truePositions.Contains(candidate2))
                    return candidate2;
            }
        }
    }

    throw new InvalidOperationException("数组中不存在True值");
}

// 辅助方法：判断坐标是否在数组范围内
private bool IsInGrid(Vector2 pos)
{
    return pos.X >= 0 && pos.X < _gridCols && pos.Y >= 0 && pos.Y < _gridRows;
}

这个实现的优势非常明显：如果目标点附近有True，几乎瞬间就能找到结果；只有当目标点离所有True都很远时，才会遍历较多点，但整体性能远优于暴力遍历。

2. 排序坐标列表 + 二分筛选（适合大规模数据） #

如果True的数量极大，分层查找的最坏情况可能不够理想，可以用排序+二分的思路：

• 预处理时把所有True坐标按X轴（或Y轴）排序，存入List<Vector2>
• 查询时，先用二分法找到X值接近目标点的坐标区间，只在这个区间内计算距离找最近的点
• 这种方法的时间复杂度是O(logN + K)，其中K是筛选出的候选坐标数量，远小于总True数N

示例验证 #

针对你给出的示例数组[[T,T,F],[T,F,T],[T,T,T]]：

• 调用GetNearestTrue(new Vector2(2,3))：目标点超出数组范围，分层查找时会快速定位到距离最近的(1,2)（假设数组是0-based索引，若为1-based则对应(2,3)附近的(1,2)）
• 调用GetNearestTrue(new Vector2(1,1))：距离1的候选点中包含(0,1)和(1,0)，会返回第一个找到的符合条件的坐标，满足需求

内容的提问来源于stack exchange，提问作者Tim