How to find all grid squares on a line?

Question

I'm trying to implement a line-of-sight algorithm on a 2-dimensional grid. I know how it needs to work conceptually, but I can't think of how to implement it as an algorithm.

The basic idea is pretty simple. In pseudocode:

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

GetListOfSquaresOnLine would (conceptually) draw a straight line from the center of the grid square at point1 to the center of the grid square at point2, and return a list of all squares that this line passes through. But that's the part I have no idea how to implement. Anyone know how to do this? Delphi or C examples preferred, but not required.

user_10627282 · Answer

Here is my function that will test line of sight for blocked tiles on a square grid.

You need your own functions for:

ValidSquare(x,y) (returns true if tile is within your map bounds)

CheckSquare(y,x) (returns true if the tile is see through)

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

How to find all grid squares on a line?

5 Answers