如何在一条线上找到所有网格方块？

Question

我正在尝试在二维网格上实现视线算法.我知道它在概念上需要如何工作,但我想不出如何将其作为算法实现.

基本想法很简单.在伪代码中:

function LineOfSight(point1, point2): boolean
  squares = GetListOfSquaresOnLine(point1, point2)
  for each square in squares
    if square.IsOpaque then return false
  return true

GetListOfSquaresOnLine将(概念上)从点1处的网格正方形的中心到点2处的网格正方形的中心绘制一条直线,并返回该线经过的所有正方形的列表.但那是我不知道如何实施的部分.有人知道怎么做吗？Delphi或C示例首选,但不是必需的.

Answer 1

到目前为止,这两个答案都指向维基百科关于Bresenhams算法的文章.这是文章给出的全尺寸图示.请注意,该线穿过未突出显示的网格方块,因此Bresenham的算法仅提供您想要的子集.

既然你提到了"视线",听起来你想要一个算法来枚举线经过的所有网格方块.该集合有时被称为超级封面(线条),这里描述了一种算法.

在这个问题的答案中给出了一些其他方法.

更新: 这是另一个参考

Answer 2

不是Bresenham的算法你在寻找什么？

Answer 3

这是我在C中写的一个实现.