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

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

这是an implementation I wrote in C。

Answer 2

到目前为止，这两个答案都指向维基百科关于Bresenhams算法的一篇文章。这是这篇文章的插图，全尺寸的。请注意，这条线穿过没有高亮显示的网格正方形，因此Bresenham的算法只给出了所需的一个子集。

既然你提到了“视线”，听起来你好像想要一个算法，枚举所有的方格线通过。这个集合有时被称为（行的）超级覆盖和one algorithm is described here。

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

更新：Here's another reference

Answer 3

你不是在找什么吗？