# Line of sight on a 2d grid

I've been looking for similar questions here and on google, but none have worked for me yet. I have a game, where I have a 2d array of square tiles (they're objects with accessible x and y pixel coords, side length in pixels, and whether are they see-through).

In there, there are enemies and the player. They can move independently from the grid (as in, pardon the example, Minecraft), and I have got access to their coords. What I want is a function that will tell me if a given enemy can see the player or not (just returning bool). Can you help me?

EDIT: I used Bresenham. If anyone there is from Poland, a great description of Bresanham's jest tutaj :http://edu.i-lo.tarnow.pl/inf/utils/002_roz/2008_06.php :)

• Do you only need to know if they can see an enemy vertically or horizontally or at any angle? May 17, 2014 at 12:45
• at any angle, they can rotate 360, but i used bresenham and it works. May 17, 2014 at 19:41

Just use a line drawing algorithm, e.g. Bresenham's line algorithm.

Instead of using pixel coordinates, you're using tile offsets (round the position or do multiple checks). And rather than drawing the line, you're considering the "drawn on" tiles for lookup.

If you'd have to draw at tile (5, 4), then you'll check whether that tile is solid or not (i.e. whether it blocks line of sight).

If your line reaches the player without being blocked, the enemy is able to see them.

• The thing is, I don't get that algorithm. I haven't found a comprehensible (for me) tutorial on it yet. May 16, 2014 at 20:29
• @user45971 : keep searching, or just drop the feature. May 16, 2014 at 20:46
• Bresenham is for drawing pixel perfect lines. Thing is, you don't need or want pixel perfect lines. May 18, 2014 at 21:03
• Yes, it's not necessarily the perfect algorithm for this (as you mentioned, it might be too perfect). I've just picked the first best algorithm I've found. :) Although some inaccuracies might confuse players based on the tile size, enemy size, etc. - so I'd consider this on a case by case basis. May 19, 2014 at 7:32

I agree with Mario — use a line drawing algorithm. However, there are simpler algorithms for drawing lines. The one I use is based on interpolation. Off the top of my head:

len = max(abs(x2-x1), abs(y2-y1))
loop for i from 0 to len:
# interpolate between (x1,y1) and (x2,y2)
t = float(i)/len
# at t=0.0 we get (x1,y1); at t=1.0 we get (x2,y2)
x = round(x1 * (1.0-t) + x2 * t)
y = round(y1 * (1.0-t) + y2 * t)
# now check tile (x,y)


To draw a line you might use also the very simple algorithm that uses the very simple slope formula y=ax+b (or x=ay+b). It requires one div and then uses float computations, but divs are no longer that slow now, same for float operations, and anyway such cost has to be balanced with the high number of branches that Bresenham uses.
For C++ Bresenham will be faster, for javascript the branch cost is so high that using a plain for loop with no branch will be faster.
As for the coding, slope drawing is way simpler than Bresenham.

I made a small demo in javascript, in which i included the linear interpolation (lerp) method that @amitp mentions.

lerp, used with the proper distance, the manhattan distance, generates exactly the same pointset as slope. (thx to @amitp for his comments/fiddle) .

lerp uses 4 muls , 5 add, and 2 roundings per points, when slope uses 2 add and 1 rounding per point, but lerp win on the line of code count.

fiddle is here :

http://jsfiddle.net/gamealchemist/M9y6z/4/

Code for slope drawing :

// draws a line using y=ax+b or x=ay+b
function line_slope(x1, y1, x2, y2) {
// round input
x1 = Math.floor(x1);
x2 = Math.floor(x2);
y1 = Math.floor(y1);
y2 = Math.floor(y2);
var pxCount = 0;
if (Math.abs(x1 - x2) > Math.abs(y1 - y2)) {
// first quarter
if (x1 > x2) {
// make it from left to right
var swp = x1;
x1 = x2;
x2 = swp;
swp = y1;
y1 = y2;
y2 = swp;
}
pxCount = x2 - x1;
var slope = (y2 - y1) / (x2 - x1),
y = y1;
for (var x = x1; x <= x2; x++, y += slope) {
context.fillRect(x, y, 1, 1);
}
} else {
// second quarter
if (y1 > y2) {
// make it from top to bottom
var swp = x1;
x1 = x2;
x2 = swp;
swp = y1;
y1 = y2;
y2 = swp;
}
pxCount = y2 - y1;
var slope = (x2 - x1) / (y2 - y1),
x = x1;
for (var y = y1; y <= y2; y++, x += slope) {
context.fillRect(x, y, 1, 1);
}
}
}


and for linear interpolation (lerp) :

// draws a line using linear interpolation
function line_lerp(x1, y1, x2, y2) {
x1 = Math.floor(x1);
x2 = Math.floor(x2);
y1 = Math.floor(y1);
y2 = Math.floor(y2);
var length = Math.max(Math.abs(x1 - x2), Math.abs(y1 - y2));
var tIncr = 1/length ;
for (var t = 0; t <= 1; t+=tIncr) {
var lx = Math.round(x1 * t + x2 * (1 - t));
var ly = Math.round(y1 * t + y2 * (1 - t));
context.fillRect(lx, ly, 1, 1);
}
}

• BTW, use length = Math.max(Math.abs(x1 - x2), Math.abs(y1 - y2)) to match the interpolation code I posted. I believe it will not generate any duplicates, and then you don't need lastX and lastY. May 18, 2014 at 17:07
• I made an updated jsfiddle that shows how using manhattan length, as well as round instead of float, generates the same points as line_slope() but with much simpler code: jsfiddle.net/M9y6z (I also updated line_slope to use Math.round since the question is asking about tiles) May 18, 2014 at 17:15
• Sorry - I forgot to "save" the jsfiddle code. See jsfiddle.net/M9y6z/2 May 18, 2014 at 17:30
• Most interesting comments, thanks. I updated my post. May 18, 2014 at 18:10

Here is an old VB function that implements a solid square grid LOS that works great.

I hope this helps someone out.

Function CheckSquare(ByVal row, ByVal col) As Boolean
' Checks if the terrain type at map(col,row) is see through
Dim result As Boolean

'DotSquare P(col, row), vbBlue

CheckSquare = TerrainTypes(Map(col, row)).SeeThrough

End Function

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 (ValidSquare is a function to test the square is within bounds on your map)
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