寻找2D网格中指定Tile所有8方向邻居的高效查找算法

问题背景 #

你在C#开发中使用自定义Tile对象的锯齿数组，需要实现GetNeighbors方法返回指定索引Tile的8方向邻居队列，且已知输入索引合法。当前实现通过多层分支判断来减少检查次数，但平均仍需5-6次条件检查，希望获得更高效的实现。

原方法定义 #

private Tile[][] tileGrid;
private Queue<Tile> GetNeighbors(int r, int c) { ...}

原实现代码 #

Queue<Tile> neighbors = new Queue<Tile>(8);
if (r != 0 && r != tileGrid.Length) //If not on first or last row
{
    neighbors.Enqueue(tileGrid[r+1][c]); 
    neighbors.Enqueue(tileGrid[r-1][c]);
    if (c != tileGrid[r].Length) //If not on last column
    {
        neighbors.Enqueue(tileGrid[r+1][c+1]); 
        neighbors.Enqueue(tileGrid[r][c+1]);
        neighbors.Enqueue(tileGrid[r-1][c+1]);
    }
    if (c != 0) //If not on first column
    {
        neighbors.Enqueue(tileGrid[r-1][c-1]); 
        neighbors.Enqueue(tileGrid[r][c - 1]);
        neighbors.Enqueue(tileGrid[r+1][c-1]);
    }
}
else if (c != 0 && c != tileGrid[r].Length) //Confirms if the tile is on 1st or last row but isn't a corner tile
{
    neighbors.Enqueue(tileGrid[r][c-1]); neighbors.Enqueue(tileGrid[r][c+1]);
    if (r == 0) //if on first row but not corner
    {
        neighbors.Enqueue(tileGrid[r+1][c]); 
        neighbors.Enqueue(tileGrid[r+1][c+1]);
        neighbors.Enqueue(tileGrid[r+1][c-1]);
    }
    else //For last row but not corner
    {
        neighbors.Enqueue(tileGrid[r-1][c]); 
        neighbors.Enqueue(tileGrid[r-1][c+1]);
        neighbors.Enqueue(tileGrid[r-1][c-1]);
    }
}
else
{
    if(r == 0) //if upper corner
    {
        neighbors.Enqueue(tileGrid[r+1][c+1]);
        if(c == 0) 
        { 
           neighbors.Enqueue(tileGrid[r+1][c+1]); 
           neighbors.Enqueue(tileGrid[r][c+1]); 
        }
        else 
        { 
          neighbors.Enqueue(tileGrid[r+1][c-1]); 
          neighbors.Enqueue(tileGrid[r][c-1]); 
        }
    } else //if lower corner
    {
        neighbors.Enqueue(tileGrid[r-1][c]);
        if(c==0) 
        { 
           neighbors.Enqueue(tileGrid[r-1][c+1]); 
           neighbors.Enqueue(tileGrid[r][c+1]); 
        }
        else 
        { 
           neighbors.Enqueue(tileGrid[r-1][c-1]); 
           neighbors.Enqueue(tileGrid[r][c-1]); 
        }
    }
}
return neighbors;

优化方案：预定义方向偏移量+线性遍历 #

核心思路

放弃复杂的分支判断，转而预定义8个方向的行列偏移量数组，遍历每个偏移量计算邻居索引，仅在索引合法时将对应Tile加入队列。这种方式的优势在于：

• 逻辑统一，代码简洁易维护；
• 避免复杂分支带来的CPU分支预测失败开销；
• 简单的范围判断能被编译器充分优化，实际执行效率更稳定。

通用伪代码

// 预定义8个方向的行列偏移量（顺序可按需调整）
directionOffsets = [(-1,0), (1,0), (0,-1), (0,1), (-1,-1), (-1,1), (1,-1), (1,1)]

function GetNeighbors(r, c):
    neighbors = new Queue(8)
    totalRows = length(tileGrid)
    for each (dr, dc) in directionOffsets:
        neighborRow = r + dr
        neighborCol = c + dc
        // 检查行索引合法，且列索引在当前行的有效范围内
        if neighborRow >= 0 and neighborRow < totalRows and neighborCol >= 0 and neighborCol < length(tileGrid[neighborRow]):
            neighbors.enqueue(tileGrid[neighborRow][neighborCol])
    return neighbors

C# 实现代码

// 将偏移量定义为类的静态常量，避免每次方法调用重复创建数组
private static readonly (int dr, int dc)[] _directionOffsets = 
{
    (-1, 0), (1, 0), (0, -1), (0, 1),
    (-1, -1), (-1, 1), (1, -1), (1, 1)
};

private Queue<Tile> GetNeighbors(int r, int c)
{
    var neighbors = new Queue<Tile>(8);
    int totalRows = tileGrid.Length;
    
    foreach (var (dr, dc) in _directionOffsets)
    {
        int nr = r + dr;
        int nc = c + dc;
        
        // 验证邻居索引的合法性：行在范围内，且列在该行的有效范围内
        if (nr >= 0 && nr < totalRows && nc >= 0 && nc < tileGrid[nr].Length)
        {
            neighbors.Enqueue(tileGrid[nr][nc]);
        }
    }
    
    return neighbors;
}

效率说明 #

• 原实现的多层分支看似减少了检查次数，但复杂的分支结构容易触发CPU分支预测失败，反而增加执行开销；
• 优化后的实现采用线性遍历，每个循环的条件检查都是简单的数值比较，CPU能高效流水线执行，实际性能更优；
• 由于输入索引合法，大部分偏移量都会通过检查，遍历的额外开销可以忽略。

内容的提问来源于stack exchange，提问作者Neptunium-Eater