CODEWITHSUNDEEP
algorithmgeometry
Mason Wheeler
Mason Wheeler

Reputation: 84540

How to find all grid squares on a line?

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.

Upvotes: 29

Views: 16876

Answers (4)

Ratbyte Boss
Ratbyte Boss

Reputation: 471

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

Upvotes: 0

brainjam
brainjam

Reputation: 19005

Both of the answers so far point to a Wikipedia article on Bresenhams's algorithm. Here's the illustration the article gives, at full size. Notice that the line passes through grid squares that aren't highlighted, so Bresenham's algorithm only gives a subset of what you want.

alt text

Since you mention "line of sight", it sounds like you want an algorithm that enumerates all of the grid squares that the line goes through. This set is sometimes referred to as the super cover (of the line), and one algorithm is described here.

There are also some other approaches, given in the answers to this question.

Update: Here's another reference

Upvotes: 40

Ian Mercer
Ian Mercer

Reputation: 39277

See http://en.wikipedia.org/wiki/Bresenham's_line_algorithm

Upvotes: 0

High Performance Mark
High Performance Mark

Reputation: 78306

Isn't Bresenham's Algorithm what you are looking for ?

Upvotes: 7

Related Questions