algorithm - 如何找到一条线上的所有网格方 block ？

Question

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

基本思想非常简单。在伪代码中:

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

GetListOfSquaresOnLine 将(概念上)从 point1 的网格正方形中心到 point2 的网格正方形中心绘制一条直线，并返回这条线穿过的所有正方形的列表.但那是我不知道如何实现的部分。有人知道怎么做吗？首选 Delphi 或 C 示例，但不是必需的。

Answer 1

到目前为止，这两个答案都指向关于 Bresenhams 的维基百科文章的算法。这是文章给出的全尺寸插图。请注意，该线穿过未突出显示的网格方 block ，因此 Bresenham 算法仅给出您想要的部分内容。

由于您提到“视线”，听起来您想要一种算法来枚举该线经过的所有网格方 block 。这个集合有时被称为 super 封面(线)，和one algorithm is described here .

还有一些其他方法，在 this question 的答案中给出。 .

更新: Here's another reference