Line of sight on a 2d grid

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); } } 

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