# 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? – badweasel May 17 '14 at 12:45
• at any angle, they can rotate 360, but i used bresenham and it works. – user45971 May 17 '14 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. – user45971 May 16 '14 at 20:29
• @user45971 : keep searching, or just drop the feature. – GameAlchemist May 16 '14 at 20:46
• Bresenham is for drawing pixel perfect lines. Thing is, you don't need or want pixel perfect lines. – API-Beast May 18 '14 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. – Mario May 19 '14 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. – amitp May 18 '14 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) – amitp May 18 '14 at 17:15
• Sorry - I forgot to "save" the jsfiddle code. See jsfiddle.net/M9y6z/2 – amitp May 18 '14 at 17:30
• Most interesting comments, thanks. I updated my post. – GameAlchemist May 18 '14 at 18:10