可见性算法：如何检测网格中两点间向量穿过的格子？

嘿，这个问题正好是网格可见性检测里的经典场景！你需要的是Amanatides-Woo网格步进算法（也叫Grid Traversal Algorithm），它能精准找出两点之间的直线穿过的所有网格单元格，完全适配你的障碍物检测需求——毕竟只要直线穿过的任何一个格子是障碍，那B就没法被A看到。

核心思路 #

这个算法的本质是模拟直线在网格中“前进”的过程，每次只跨越一个网格边界（要么是x方向的列边界，要么是y方向的行边界），同时记录经过的每一个网格单元。相比常用的Bresenham直线算法，它不会漏掉那些斜向穿过的网格单元（比如对角线穿过4个格子的情况，Bresenham可能只标记2个，而这个算法会全部捕捉到），更适合你的可见性判断场景。

步骤拆解（伪代码示例） #

假设你的二维数组是grid[row][col]，点A的坐标是(x0, y0)，点B是(x1, y1)（这里的坐标可以是连续的空间坐标，也可以是网格单元的中心坐标，算法会自动映射到对应的网格单元）：

import math

def get_traversed_cells(x0, y0, x1, y1):
    traversed = []
    
    # 转换为网格单元坐标（假设网格单元的左下角是整数坐标，比如单元(i,j)覆盖[i,i+1)x[j,j+1)）
    current_cell = (int(math.floor(x0)), int(math.floor(y0)))
    end_cell = (int(math.floor(x1)), int(math.floor(y1)))
    traversed.append(current_cell)
    
    # 计算方向向量和步进方向
    dx = x1 - x0
    dy = y1 - y0
    step_x = 1 if dx > 0 else -1 if dx < 0 else 0
    step_y = 1 if dy > 0 else -1 if dy < 0 else 0
    
    # 计算每次跨越x/y边界需要的距离增量
    t_delta_x = abs(1.0 / dx) if dx != 0 else float('inf')
    t_delta_y = abs(1.0 / dy) if dy != 0 else float('inf')
    
    # 计算到达下一个x/y边界的初始距离
    if dx > 0:
        t_max_x = (math.floor(x0) + 1 - x0) * t_delta_x
    elif dx < 0:
        t_max_x = (x0 - math.floor(x0)) * t_delta_x
    else:
        t_max_x = float('inf')
        
    if dy > 0:
        t_max_y = (math.floor(y0) + 1 - y0) * t_delta_y
    elif dy < 0:
        t_max_y = (y0 - math.floor(y0)) * t_delta_y
    else:
        t_max_y = float('inf')
    
    # 开始步进遍历网格
    while current_cell != end_cell:
        if t_max_x < t_max_y:
            t_max_x += t_delta_x
            current_cell = (current_cell[0] + step_x, current_cell[1])
        else:
            t_max_y += t_delta_y
            current_cell = (current_cell[0], current_cell[1] + step_y)
        traversed.append(current_cell)
    
    return traversed

适配你的场景使用 #

1. 调用上面的函数，传入A和B的坐标，得到所有穿过的网格单元列表
2. 遍历这个列表，检查每个单元在你的二维数组中是否是障碍物（比如假设grid[i][j] == 1代表障碍）
3. 如果列表中存在任何一个障碍单元，直接判定Point B无法被Point A看到

注意事项 #

• 如果你的A和B坐标本身就是网格单元的索引（比如A1是行号，A2是列号），可以先把它们转换为单元中心的连续坐标（比如x0 = A1 + 0.5, y0 = A2 + 0.5），再传入算法，这样能保证直线是从单元中心出发的
• 这个算法的时间复杂度是O(n)，n是穿过的网格单元数量，效率非常高，适合大规模网格的可见性检测

内容的提问来源于stack exchange，提问作者Ferran Capallera Guirado