9
\$\begingroup\$

Consider a 2d grid of tiles, and an approximated sphere of coordinates - centered on the player - that represents line of sight. The goal is to block the line of sight beyond obstacles (ie walls).

It's relatively simple to determine if an individual cell in the sphere of sight is visible: cast a ray from the player to the target cell, using Bresenham's - if one of the overlapping cells between the player and the target is an obstacle, the target cell is not visible.

Now, my first thought was to iterate through all grid cells in the line of sight - but this seems inefficient to me. For example, if the player is standing next to a wall, and you determine that the cell beyond the wall isn't visible, you can determine all cells on the ray after that won't be visible.

Also considered casting a ray to each cell along the perimeter of the sphere of sight, and iterating each cell along each ray - but then I'd be processing some cells more than once.

Is there a more efficient way to do this?

While iterating ~50 cells per turn is a relatively lightweight calculation, I'm going for speed - the goal is to be able to cycle a few turns per second on auto-play. So, the more efficient I can make this, the better.

\$\endgroup\$
7
  • \$\begingroup\$ "Best" questions don't usually do well. Since the best way is very specific to your goals and other features you need to support. I recommend you just profile the code and see if it's good enough for your needs now. Profiling will also show you the parts of your code you need to improve first for better performance. \$\endgroup\$
    – House
    Jan 17 '13 at 19:38
  • \$\begingroup\$ How many cells are you expecting to have around the player? \$\endgroup\$ Jan 17 '13 at 19:44
  • \$\begingroup\$ @Luis probably a radius of 7 or 8 cells. \$\endgroup\$
    – CodeMoose
    Jan 17 '13 at 20:27
  • 2
    \$\begingroup\$ You'll recall gamedev.stackexchange.com/a/47560/4129 You can do it in an O(n) sweep. \$\endgroup\$
    – Will
    Jan 17 '13 at 20:38
  • 2
    \$\begingroup\$ Are you sure that you need to optimise? Have you actually encountered a bottleneck that needs to be dealt with? Or are you simply guessing that it will be an issue in the future? If your code is relatively modular it should be the easiest thing in the world to develop a solution and then come back to it later IF optimisation is needed. \$\endgroup\$
    – Djentleman
    Jan 17 '13 at 22:06
8
\$\begingroup\$

Eric Lippert wrote a series of blog posts about using "shadow arcs" to only iterate over visible cells in linear time without having to search for obstacles in each cell's visibility check. The blog series is archived, but you can find some of it at Microsoft's MSDN blog archive or check the Internet Archive.

I've adapted the scanning logic and shown a simplified example below; see the function scan_arc. The core idea is to check all squares, starting from the close ones starting from distance = 0 and ending at distance >= SIGHT_RADIUS.

Each time you encounter an open cell, you mark it as "visible". Whenever you encounter a block, you reduce the angle and recursively scan around the side of the block.

This function only increments the distance in one direction, so we can cover the entire 360 degrees by scanning 90 degrees in each of 4 cardinal directions. Click the Run Code Snippet button below to see it in action.

function scan_arc(distance, min, max, rotate) {
  // we're finished scanning either when the distance is too far 
  // or when the angle between the two ends of the arc is 0 
  if (distance >= SIGHT_RADIUS || min >= max) return;
  // iterate over all integers between min and max  
  for (var i = Math.ceil(distance * min); i <= distance * max; i++) {
    // (distance, i) forms an offset from the player representing our current cell.
    // we rotate it by a multiple of 90 degrees so we can scan in 4 directions
    var x = player.x + rotate(distance, i)[0];
    var y = player.y + rotate(distance, i)[1];
    // if our line of sight is blocked,
    // recursively scan at depth + 1 to the side of the block.
    if (map.get(x, y) === BLOCK) {
      scan_arc(distance + 1, min, (i - 0.5) / distance, rotate);
      min = (i + 0.5) / distance;
    } else {
      // if the current cell is open, we mark it as visible
      map.set(x, y, VISIBLE);
    }
  }
  // when we finish scanning a row, continue by scanning the next row
  scan_arc(distance + 1, min, max, rotate);
}

class Map {
  constructor(N, pairs) {
    this.N = N;
    this.data = new Array(N).fill(0).map((x) => new Array(N).fill(0));
    for (var p of pairs)
      this.data[p[0]][p[1]] = 1;
    for(let i = 0; i < N; i++)
       for(let j = 0, tr = mapview.insertRow(); j < N; j++)
         tr.insertCell();
  }
  get(x, y) {
    if (x < 0 || y < 0 || x >= this.N || y >= this.N) return 0;
    return this.data[x][y];
  }
  set(x, y, val) {
    if (x < 0 || y < 0 || x >= this.N || y >= this.N) return;
    this.data[x][y] = val;
  }
  show() {
    for (let N = this.data.length, i = 0; i < N; i++)
      for (let j = 0; j < N; j++)
        mapview.rows[i].cells[j].className = "cell" + this.data[i][j];
  }
}
let SIGHT_RADIUS = 20,
  BLOCK = 1,
  VISIBLE = 2;
let map    = new Map(16, [[3, 3],[4, 3],[5, 3],[8, 7],[8, 5],[6, 9],[6, 10],[6, 11],[7, 11],[7, 10],[7, 9]])
let player = {x: 4, y: 5}
scan_arc(0, -1, 1, (x, y) => [x, y]);
scan_arc(0, -1, 1, (x, y) => [y, -x]);
scan_arc(0, -1, 1, (x, y) => [-x, -y]);
scan_arc(0, -1, 1, (x, y) => [-y, x]);
map.set(player.x, player.y, "player");
map.show()
td {
  width: 12px;
  height: 12px;
  border: 1px solid #999;
}

.cell0 {
  background: #999;
}

.cell1 {
  background: #66f;
}

.cellplayer {
  background: #fa6;
}
<table id=mapview></table>

\$\endgroup\$
2
  • \$\begingroup\$ the blog link is dead. Any update on this answer? \$\endgroup\$
    – Neon Warge
    Feb 8 '18 at 8:28
  • \$\begingroup\$ This is why we generally recommend answers include at least a rough summary of the techniques they propose, rather than relying wholly on external links. In this case, @NeonWarge, is Stoiko's implementation of this technique in a later answer a useful guide? \$\endgroup\$
    – DMGregory
    Feb 8 '18 at 8:45
7
\$\begingroup\$

I have implemented the algorithm suggested by Jimmy.

Video of the code in action here: https://youtu.be/lIlPfwlcbHo

Grid Field Of Vision

/*
   What this code does:
      Rasterizes a single Field Of View octant on a grid, similar to the way 
      FOV / shadowcasting is implemented in some roguelikes.
      Clips to bitmap
      Steps on pixel centers
      Optional attenuation
      Optional circle clip
      Optional lit blocking tiles

   To rasterize the entire FOV, call this in a loop with octant in range 0-7
   Inspired by http://blogs.msdn.com/b/ericlippert/archive/2011/12/12/shadowcasting-in-c-part-one.aspx
*/

static inline int Mini( int a, int b ) {
    return a < b ? a : b;
}

static inline int Maxi( int a, int b ) {
    return a > b ? a : b;
}

static inline int Clampi( int v, int min, int max ) {
    return Maxi( min, Mini( v, max ) );
}

typedef union c2_s {
    struct {
        int x, y;
    };
    int a[2];
} c2_t;

static const c2_t c2zero = { .a = { 0, 0 } };
static const c2_t c2one = { .a = { 1, 1 } };

static inline c2_t c2xy( int x, int y ) {
    c2_t c = { { x, y } };
    return c;
}

static inline c2_t c2Neg( c2_t c ) {
    return c2xy( -c.x, -c.y );
}

static inline c2_t c2Add( c2_t a, c2_t b ) {
    return c2xy( a.x + b.x, a.y + b.y );
}

static inline c2_t c2Sub( c2_t a, c2_t b ) {
    return c2xy( a.x - b.x, a.y - b.y );
}

static inline int c2Dot( c2_t a, c2_t b ) {
    return a.x * b.x + a.y * b.y;
}

static inline int c2CrossC( c2_t a, c2_t b ) {
    return a.x * b.y - a.y * b.x;
}

static inline c2_t c2Clamp( c2_t c, c2_t min, c2_t max ) {
    return c2xy( Clampi( c.x, min.x, max.x ), Clampi( c.y, min.y, max.y ) );
}

static inline c2_t c2Scale( c2_t a, int s ) {
    return c2xy( a.x * s, a.y * s );
}

void RasterizeFOVOctant( int originX, int originY,
                         int radius, 
                         int bitmapWidth, int bitmapHeight,
                         int octant,
                         int skipAttenuation,
                         int skipClampToRadius,
                         int darkWalls,
                         const unsigned char *inBitmap, 
                         unsigned char *outBitmap ) {
#define READ_PIXEL(c) inBitmap[(c).x+(c).y*bitmapWidth]
#define WRITE_PIXEL(c,color) outBitmap[(c).x+(c).y*bitmapWidth]=(color)
#define MAX_RAYS 64
#define ADD_RAY(c) {nextRays->rays[Mini(nextRays->numRays,MAX_RAYS-1)] = (c);nextRays->numRays++;}
#define IS_ON_MAP(c) ((c).x >= 0 && (c).x < bitmapWidth && (c).y >= 0 && (c).y < bitmapHeight)
    typedef struct {
        int numRays;
        c2_t rays[MAX_RAYS];
    } raysList_t;
    // keep these coupled like this
    static const const c2_t bases[] = {
        { { 1, 0  } }, { { 0, 1  } },
        { { 1, 0  } }, { { 0, -1 } },
        { { -1, 0 } }, { { 0, -1 } },
        { { -1, 0 } }, { { 0, 1  } },
        { { 0, 1  } }, { { -1, 0 } },
        { { 0, 1  } }, { { 1, 0  } },
        { { 0, -1 } }, { { 1, 0  } },
        { { 0, -1 } }, { { -1, 0 } },
    }; 
    c2_t e0 = bases[( octant * 2 + 0 ) & 15];
    c2_t e1 = bases[( octant * 2 + 1 ) & 15];
    raysList_t rayLists[2] = { {
        .numRays = 2,
        .rays = {
            c2xy( 1, 0 ),
            c2xy( 1, 1 ),
        }, 
    } };
    c2_t bitmapSize = c2xy( bitmapWidth, bitmapHeight );
    c2_t bitmapMax = c2Sub( bitmapSize, c2one );
    c2_t origin = c2Clamp( c2xy( originX, originY ), c2zero, bitmapMax );
    if ( READ_PIXEL( origin ) ) {
        WRITE_PIXEL( origin, 255 );
        return;
    }
    c2_t dmin = c2Neg( origin );
    c2_t dmax = c2Sub( bitmapMax, origin );
    int dmin0 = c2Dot( dmin, e0 );
    int dmax0 = c2Dot( dmax, e0 );
    int limit0 = Mini( radius, dmin0 > 0 ? dmin0 : dmax0 );
    int dmin1 = c2Dot( dmin, e1 );
    int dmax1 = c2Dot( dmax, e1 );
    int limit1 = Mini( radius, dmin1 > 0 ? dmin1 : dmax1 );
    c2_t ci = origin;
    for ( int i = 0; i <= limit0; i++ ) {
        int i2 = i * 2;
        raysList_t *currRays = &rayLists[( i + 0 ) & 1];
        raysList_t *nextRays = &rayLists[( i + 1 ) & 1];
        nextRays->numRays = 0;
        for ( int r = 0; r < currRays->numRays - 1; r += 2 ) {
            c2_t r0 = currRays->rays[r + 0];
            c2_t r1 = currRays->rays[r + 1];
            int inyr0 = ( i2 - 1 ) * r0.y / r0.x;
            int outyr0 = ( i2 + 1 ) * r0.y / r0.x;
            int inyr1 = ( i2 - 1 ) * r1.y / r1.x;
            int outyr1 = ( i2 + 1 ) * r1.y / r1.x;

            // every pixel with a center INSIDE the frustum is lit

            int starty = outyr0 + 1;
            if ( c2CrossC( r0, c2xy( i2, outyr0 ) ) < 0 ) {
                starty++;
            }
            starty /= 2;
            c2_t start = c2Add( ci, c2Scale( e1, starty ) );
            int endy = inyr1 + 1;
            if ( c2CrossC( r1, c2xy( i2, inyr1 + 1 ) ) > 0 ) {
                endy--;
            }
            endy /= 2;
            //c2_t end = c2Add( ci, c2Scale( e1, endy ) );
            {
                int y;
                c2_t p;
                int miny = starty;
                int maxy = Mini( endy, limit1 ); 
                for ( y = miny, p = start; y <= maxy; y++, p = c2Add( p, e1 ) ) {
                    WRITE_PIXEL( p, 255 );
                }
            }

            // push rays for the next column

            // correct the bounds first

            c2_t bounds0;
            c2_t bounds1;
            c2_t firstin = c2Add( ci, c2Scale( e1, ( inyr0 + 1 ) / 2 ) );
            c2_t firstout = c2Add( ci, c2Scale( e1, ( outyr0 + 1 ) / 2 ) );
            if ( ( IS_ON_MAP( firstin ) && ! READ_PIXEL( firstin ) )
                && ( IS_ON_MAP( firstout ) && ! READ_PIXEL( firstout ) ) ) {
                  bounds0 = r0;
            } else {
                int top = ( outyr0 + 1 ) / 2;
                int bottom = Mini( ( inyr1 + 1 ) / 2, limit1 );
                int y;
                c2_t p = c2Add( ci, c2Scale( e1, top ) );
                for ( y = top * 2; y <= bottom * 2; y += 2, p = c2Add( p, e1 ) ) {
                    if ( ! READ_PIXEL( p ) ) {
                        break;
                    }
                    // pixels that force ray corrections are lit too
                    WRITE_PIXEL( p, 255 );
                }
                bounds0 = c2xy( i2 - 1, y - 1 );
                inyr0 = ( i2 - 1 ) * bounds0.y / bounds0.x;
                outyr0 = ( i2 + 1 ) * bounds0.y / bounds0.x;
            }
            c2_t lastin = c2Add( ci, c2Scale( e1, ( inyr1 + 1 ) / 2 ) );
            c2_t lastout = c2Add( ci, c2Scale( e1, ( outyr1 + 1 ) / 2 ) );
            if ( ( IS_ON_MAP( lastin ) && ! READ_PIXEL( lastin ) )
                && ( IS_ON_MAP( lastout ) && ! READ_PIXEL( lastout ) ) ) {
                bounds1 = r1;
            } else {
                int top = ( outyr0 + 1 ) / 2;
                int bottom = Mini( ( inyr1 + 1 ) / 2, limit1 );
                int y;
                c2_t p = c2Add( ci, c2Scale( e1, bottom ) );
                for ( y = bottom * 2; y >= top * 2; y -= 2, p = c2Sub( p, e1 ) ) {
                    if ( ! READ_PIXEL( p ) ) {
                        break;
                    }
                    // pixels that force ray corrections are lit too
                    WRITE_PIXEL( p, 255 );
                }
                bounds1 = c2xy( i2 + 1, y + 1 );
                inyr1 = ( i2 - 1 ) * bounds1.y / bounds1.x;
                outyr1 = ( i2 + 1 ) * bounds1.y / bounds1.x;
            }

            // closed frustum - quit
            if ( c2CrossC( bounds0, bounds1 ) <= 0 ) {
                continue;
            }

            // push actual rays
            {
                ADD_RAY( bounds0 );
                int top = ( outyr0 + 1 ) / 2;
                int bottom = Mini( ( inyr1 + 1 ) / 2, limit1 );
                c2_t p = c2Add( ci, c2Scale( e1, top ) );
                int prevPixel = READ_PIXEL( p );
                for ( int y = top * 2; y <= bottom * 2; y += 2, p = c2Add( p, e1 ) ) {
                    int pixel = READ_PIXEL( p );
                    if ( prevPixel != pixel ) {
                        c2_t ray;
                        if ( pixel ) {
                            ray = c2xy( i2 + 1, y - 1 );
                        } else {
                            ray = c2xy( i2 - 1, y - 1 );
                        }
                        ADD_RAY( ray );
                    }
                    prevPixel = pixel;
                }
                ADD_RAY( bounds1 );
            }
        }
        ci = c2Add( ci, e0 );
    }

    if ( ! skipAttenuation ) {
        c2_t ci = origin;
        int rsq = radius * radius;
        for ( int i = 0; i <= limit0; i++ ) {
            c2_t p = ci;
            for ( int j = 0; j <= limit1; j++ ) {
                c2_t d = c2Sub( p, origin );
                int dsq = c2Dot( d, d );
                int mod = 255 - Mini( dsq * 255 / rsq, 255 );
                int lit = !! outBitmap[p.x + p.y * bitmapWidth];
                WRITE_PIXEL( p, mod * lit );
                p = c2Add( p, e1 );
            }
            ci = c2Add( ci, e0 );
        }
    } else if ( ! skipClampToRadius ) {
        c2_t ci = origin;
        int rsq = radius * radius;
        for ( int i = 0; i <= limit0; i++ ) {
            c2_t p = ci;
            for ( int j = 0; j <= limit1; j++ ) {
                c2_t d = c2Sub( p, origin );
                if ( c2Dot( d, d ) > rsq ) { 
                    WRITE_PIXEL( p, 0 );
                }
                p = c2Add( p, e1 );
            }
            ci = c2Add( ci, e0 );
        }
    }

    if ( darkWalls ) {
        c2_t ci = origin;
        for ( int i = 0; i <= limit0; i++ ) {
            c2_t p = ci;
            for ( int j = 0; j <= limit1; j++ ) {
                if ( READ_PIXEL( p ) ) { 
                    WRITE_PIXEL( p, 0 );
                }
                p = c2Add( p, e1 );
            }
            ci = c2Add( ci, e0 );
        }
    } 
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.