0
\$\begingroup\$

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 :)

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

4 Answers 4

3
\$\begingroup\$

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.

\$\endgroup\$
4
  • \$\begingroup\$ The thing is, I don't get that algorithm. I haven't found a comprehensible (for me) tutorial on it yet. \$\endgroup\$
    – user45971
    May 16, 2014 at 20:29
  • \$\begingroup\$ @user45971 : keep searching, or just drop the feature. \$\endgroup\$ May 16, 2014 at 20:46
  • \$\begingroup\$ Bresenham is for drawing pixel perfect lines. Thing is, you don't need or want pixel perfect lines. \$\endgroup\$
    – API-Beast
    May 18, 2014 at 21:03
  • \$\begingroup\$ 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. \$\endgroup\$
    – Mario
    May 19, 2014 at 7:32
2
\$\begingroup\$

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)
\$\endgroup\$
1
0
\$\begingroup\$

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/

enter image description here

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);
    }
}
\$\endgroup\$
4
  • \$\begingroup\$ 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. \$\endgroup\$
    – amitp
    May 18, 2014 at 17:07
  • \$\begingroup\$ 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) \$\endgroup\$
    – amitp
    May 18, 2014 at 17:15
  • \$\begingroup\$ Sorry - I forgot to "save" the jsfiddle code. See jsfiddle.net/M9y6z/2 \$\endgroup\$
    – amitp
    May 18, 2014 at 17:30
  • \$\begingroup\$ Most interesting comments, thanks. I updated my post. \$\endgroup\$ May 18, 2014 at 18:10
0
\$\begingroup\$

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
\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .