Efficient roguelike grid FOV / shadowcasting in a single C function inspired by http://blogs.msdn.com/b/ericlippert/archive/2011/12/12/shadowcasting-in-c-part-one.aspx
| /* | |
| What this function does: | |
| Rasterizes a single Field Of View octant on a grid, similar to the way | |
| FOV / shadowcasting is implemented in some roguelikes. | |
| Uses rays to define visible volumes instead of tracing lines from origin to pixels. | |
| Minimal processing per pixel (each pixel is hit only once most of the time). | |
| 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 | |
| See the result here: | |
| https://youtu.be/lIlPfwlcbHo | |
| */ | |
| 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 ); | |
| } | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
This comment has been minimized.