More efficient way to implement Line of sight on a 2d grid with ray casting?

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.

• "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. – MichaelHouse Jan 17 '13 at 19:38
• How many cells are you expecting to have around the player? – Luis Estrada Jan 17 '13 at 19:44
• @Luis probably a radius of 7 or 8 cells. – CodeMoose Jan 17 '13 at 20:27
• You'll recall gamedev.stackexchange.com/a/47560/4129 You can do it in an O(n) sweep. – Will Jan 17 '13 at 20:38
• 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. – Djentleman Jan 17 '13 at 22:06

You could try casting "shadow arcs" to cover larger areas at once. While the actual details are a bit involved, Eric Lippert has a very in-depth explanation (with live Silverlight demo) at http://blogs.msdn.com/b/ericlippert/archive/2011/12/12/shadowcasting-in-c-part-one.aspx.

• the blog link is dead. Any update on this answer? – Neon Warge Feb 8 '18 at 8:28
• 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? – DMGregory Feb 8 '18 at 8:45

I have implemented the algorithm suggested by Jimmy.

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

/*
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
*/

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 bitmapWidth, int bitmapHeight,
int octant,
int skipAttenuation,
int darkWalls,
const unsigned char *inBitmap,
unsigned char *outBitmap ) {
#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
{
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 );
}
}
prevPixel = pixel;
}
}
}
ci = c2Add( ci, e0 );
}

if ( ! skipAttenuation ) {
c2_t ci = origin;
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;
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 );
}
}
}