Jump to content


Photo

Grid-based line of sight


  • Please log in to reply
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.

 

lineofsight.png

 

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

thy-sword-banner-noflash.gif


#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

thy-sword-banner-noflash.gif