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.

score 39 · Accepted Answer · edited May 23 '17 at 12:09

39

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

edited May 23 '17 at 12:09

Community

1
1

answered Jul 21 '10 at 23:39

brainjam

18,863
8
57
82

2

Thanks! The supercover line is a better fit than the basic Bresenham line. Switching this to the accepted response. – Mason Wheeler Jul 22 '10 at 00:26
This image has squares that _are_ on the line, but aren't highlighted. Why is this? --- Edit: I understand now. Here's a link that modifies the algorithm to get the supercover http://eugen.dedu.free.fr/projects/bresenham/. – byxor May 29 '17 at 11:21

score 8 · Answer 2 · answered Jul 21 '10 at 21:19

8

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

answered Jul 21 '10 at 21:19

High Performance Mark

77,191
7
105
161

Thanks. I hadn't heard of that before, but it looks like what I'm looking for. – Mason Wheeler Jul 21 '10 at 21:32

score 8 · Answer 3 · answered Jul 22 '10 at 10:21

8

Here's an implementation I wrote in C.

answered Jul 22 '10 at 10:21

Nick Johnson

100,655
16
128
198

1

You. are an evil person. You will receive an upvote just because it was amusing :-) – rhbvkleef Jul 19 '17 at 18:39
Here's the solution in 1 click, solved it on my first try: https://imgur.com/a/ZXaHn0Y – Andrew Apr 29 '20 at 03:33

score 1 · Answer 4 · answered Jul 21 '10 at 21:19

1

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

answered Jul 21 '10 at 21:19

Ian Mercer

38,490
8
97
133

score 0 · Answer 5 · answered Jun 17 '22 at 04:47

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 Answers5

Linked

Related