# Grid-based line of sight

3 replies to this topic

### #1 witchmaster

witchmaster

GMC Member

• GMC Member
• 44 posts
• Version:GM:Studio

Posted 09 October 2014 - 10:10 AM

This script checks line of sight between two points in a ds_grid and returns true if there is line of sight, false otherwise. It's based on the following code: http://lifc.univ-fco...ects/bresenham/, and has been modified to check for collisions. It's based on the Bresenham's line algorithm modified for supercover.

The yellow tiles in the picture below shows all the tiles being checked for obstacles, the green tiles are start and end points (can be included or excluded in the checks). The red tiles are obstacles. The blue tiles shows a special case. If the line goes exactly through the corner then the script interprets a collision if BOTH these blue tiles have obstacles, this behaviour can be changed if needed.

Try it out and let me know what you think and please let me know if you find any bugs or things to improve.

The script:

```/* Line of Sight script using Bresenham-based supercover line algorithm

Converted and modified by WitchMaster (Mikael Norrgård)
using the C-code at http://lifc.univ-fcomte.fr/home/~ededu/projects/bresenham/

Description: Checks if there is a line of sight between two points in a ds_grid
Usage:  ds_grid_line_of_sight(grid,x1,y1,x2,y2,max_distance,check_start,check_end);
Notes:
grid: Any value above 0 in the grid is interpreted as an obstacle)
max_distance: If max_distance is 0 it won't be checked
check_start, check_end: true or false to check start and end coordinates also
*/
{
var grid = argument0;
var x1 = argument1;
var y1 = argument2;
var x2 = argument3;
var y2 = argument4;
var max_distance = argument5;
var check_start = argument6;
var check_end = argument7;

var i;               // Loop counter
var ystep, xstep;    // The step on y and x axes
var error;           // The error accumulated during the increment
var errorprev;       // Stores the previous value of the error variable
var yy = y1, xx = x1;// The line points
var ddy, ddx;        // Compulsory variables: the double values of dy and dx
var dx = x2 - x1;
var dy = y2 - y1;

// If you want to make the script failsafe, you should see if any coordinate is outside of the grid here

// Check distance start and end coordinates
if(max_distance > 0 && point_distance(x1,y1,x2,y2) > max_distance)
return false;

// Check start and end coordinates directly to save possible execution time
if( (check_start && ds_grid_get(grid,x1,y1) > 0) || (check_end && ds_grid_get(grid,x2,y2) > 0))
return false;

if (dy < 0){
ystep = -1;
dy = -dy;
}else
ystep = 1;
if (dx < 0){
xstep = -1;
dx = -dx;
}else
xstep = 1;
ddy = 2 * dy; // Work with double values for full precision
ddx = 2 * dx;
if (ddx >= ddy){ // First octant (0 <= slope <= 1)
// Compulsory initialization (even for errorprev, needed when dx==dy)
errorprev = dx; // Start in the middle of the square
error = dx;
for (i=0 ; i < dx ; i++){ // Do not use the first point (already done)
xx += xstep;
error += ddy;
if (error > ddx){  // Increment y if AFTER the middle ( > )
yy += ystep;
error -= ddx;
// Three cases (octant == right->right-top for directions below):
if (error + errorprev < ddx) { // Bottom square also
if(ds_grid_get(grid,xx,yy-ystep) > 0)
return false;
}
else if (error + errorprev > ddx) {  // Left square also
if(ds_grid_get(grid,xx-xstep,yy) > 0)
return false;
}
else { // Corner: bottom and left squares also (line goes exactly through corner of cells)
if(ds_grid_get(grid,xx,yy-ystep) > 0 && ds_grid_get(grid,xx-xstep,yy) > 0) // If both positions are occupied we return false, the AND can be changed to OR
return false;
}
}
if(ds_grid_get(grid,xx,yy) > 0)
return false;
errorprev = error;
}
} else {  // The same as above
errorprev = dy;
error = dy;
for (i=0 ; i < dy ; i++){
yy += ystep;
error += ddx;
if (error > ddy){
xx += xstep;
error -= ddy;
if (error + errorprev < ddy) {
if(ds_grid_get(grid,xx-xstep,yy) > 0)
return false;
}
else if (error + errorprev > ddy) {
if(ds_grid_get(grid,xx,yy-ystep) > 0)
return false;
}
else {
if(ds_grid_get(grid,xx-xstep,yy) > 0 && ds_grid_get(grid,xx,yy-ystep) > 0)
return false;
}
}
if(ds_grid_get(grid,xx,yy) > 0)
return false;
errorprev = error;
}
}

// We have reached the end point so return true, we have line of sight
return true;
}
```

Edited by witchmaster, 09 October 2014 - 10:12 AM.

• 3

### #2 Caracol

Caracol

GMC Member

• GMC Member
• 290 posts
• Version:GM:Studio

Posted 02 December 2014 - 06:29 AM

Exactly what I was looking for, seems to work fantastically. Thanks!

• 0

### #3 TBK_Joshu@

TBK_Joshu@

TBK Games.Inc

• GMC Member
• 255 posts
• Version:GM:Studio

Posted 29 August 2015 - 02:41 AM

How will a if statement look like, I can't get this to work??
• 0

### #4 witchmaster

witchmaster

GMC Member

• GMC Member
• 44 posts
• Version:GM:Studio

Posted 29 August 2015 - 06:06 AM

Did you setup your grid correctly? Can you post some code? But anyway, an if statement would simply look like:

```if( ds_grid_line_of_sight(grid,x1,y1,x2,y2,max_distance,check_start,check_end) )
{
// There is line of sight between x1,y1 and x2,y2
}
else
{
// No line of sight
}
```

• 0