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

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示例，但不是必需的。

- Mason Wheeler

Answer 1

到目前为止，两个答案都指向了维基百科上Bresenhams算法的文章。以下是该文章给出的插图，以全尺寸展示。请注意，直线穿过未高亮显示的网格方块，因此Bresenham算法仅提供您想要的子集。

既然你提到了“视线”，那么你想要的算法似乎是枚举直线经过的所有网格方块。这个集合有时被称为超级覆盖（直线的），这里描述了一种算法。

还有其他一些方法，给出在这个问题的答案中。

更新：这里有另一个参考资料

- brainjam

---

谢谢！超级覆盖线比基本的Bresenham线更适合。将其切换为接受的响应。 - Mason Wheeler

这张图片有一些正好在直线上的方块，但没有被突出显示。为什么会这样呢？---编辑：我现在明白了。这里有一个链接可以修改算法以获得超级覆盖 http://eugen.dedu.free.fr/projects/bresenham/。 - byxor

Answer 2

不是布雷森汉姆算法正是您所需要的吗？

- High Performance Mark

---

谢谢。我之前没听说过这个，但看起来正是我需要的东西。 - Mason Wheeler

Answer 3

这是我用C语言编写的实现代码。

- Nick Johnson

---

你是一个邪恶的人。因为这很有趣，所以你将收到一张赞票 :-) - rhbvkleef

这是一键解决方案，我第一次尝试就解决了：https://imgur.com/a/ZXaHn0Y - Andrew

Answer 4

请查看http://en.wikipedia.org/wiki/Bresenham's_line_algorithm

- Ian Mercer

Answer 5

这是一个测试正方形网格上被阻挡的瓦片视线的函数。

你需要自己编写以下函数：

ValidSquare(x,y)（如果瓦片在地图范围内则返回true）

CheckSquare(y,x)（如果瓦片可见则返回true）

Function CheckSquareLOS(ByVal srow, ByVal scol, ByVal trow, ByVal tcol) As Boolean

Dim sx As Long, sy As Long, tx As Long, ty As Long, ex As Long, ey As Long
Dim x As Double, y As Double


' First check if the values are in range
  If Not ValidSquare(P(scol, srow)) Then Stop ' : Exit Function
  If Not ValidSquare(P(tcol, trow)) Then Stop ' : Exit Function

  sx = scol * 3780: sy = srow * 3780
  tx = tcol * 3780: ty = trow * 3780
  tx = tx - sx: ty = ty - sy: sx = 0: sy = 0: x = scol: y = srow


' Repeat the following until we reach the target square or we are blocked

  While (srow <> trow) Or (scol <> tcol)

    If ty = 0 Then
      ' NPrint "Horizontal straight line"
      scol = scol + 1 * Sgn(tx)
    Else
      If tx = 0 Then
        ' NPrint "Vertical straight line"
        srow = srow + 1 * Sgn(ty)
      Else
        ey = 1890 * Sgn(ty)
        ex = sx + (ey - sy) * tx / ty
        If Abs(ex) < 1890 Then
          sx = ex: sy = -ey: srow = srow + Sgn(ty)
        Else
          ex = 1890 * Sgn(tx)
          ey = sy + (ex - sx) * ty / tx
          If Abs(ey) < 1890 Then
            sx = -ex: sy = ey: scol = scol + Sgn(tx)
          Else
          ' We must be going through a corner
            If Not CheckSquare(srow + Sgn(ty), scol) And Not CheckSquare(srow, scol + Sgn(tx)) Then
              CheckSquareLOS = False: Exit Function
            End If
            sx = -ex: sy = -ey: srow = srow + Sgn(ty): scol = scol + Sgn(tx)
          End If
        End If
      End If
    End If

    If (srow <> trow) Or (scol <> tcol) Then
    
      If CheckSquare(srow, scol) = False Then
        CheckSquareLOS = False: Exit Function
      End If
      
    End If

  Wend

' If view hasn't been blocked up until now, it must be a clear LOS

  CheckSquareLOS = True
  
End Function

- Ratbyte Boss