Skip to content

Instantly share code, notes, and snippets.

@370417
Created April 24, 2016 15:10
Show Gist options
  • Save 370417/59bb06ced7e740e11ec7dda9d82717f6 to your computer and use it in GitHub Desktop.
Save 370417/59bb06ced7e740e11ec7dda9d82717f6 to your computer and use it in GitHub Desktop.
Symmetric recursive shadowcasting
/**
* Recursive shadowcasting algorithm.
* This algorithm creates a field of view centered around (x, y).
* Opaque tiles are treated as if they have beveled edges.
* Transparent tiles are visible only if their center is visible, so the
* algorithm is symmetric.
* @param cx - x coordinate of center
* @param cy - y coordinate of center
* @param transparent - function that takes (x, y) as arguments and returns the transparency of that tile
* @param reveal - callback function that reveals the tile at (x, y)
*/
rlt.shadowcast = function(cx, cy, transparent, reveal) {
'use strict';
/**
* Scan one row of one octant.
* @param y - distance from the row scanned to the center
* @param start - starting slope
* @param end - ending slope
* @param transform - describes the transfrom to apply on x and y; determines the octant
*/
var scan = function(y, start, end, transform) {
if (start >= end) {
return;
}
var xmin = Math.round((y - 0.5) * start);
var xmax = Math.ceil((y + 0.5) * end - 0.5);
for (var x = xmin; x <= xmax; x++) {
var realx = cx + transform.xx * x + transform.xy * y;
var realy = cy + transform.yx * x + transform.yy * y;
if (transparent(realx, realy)) {
if (x >= y * start && x <= y * end) {
reveal(realx, realy);
}
} else {
if (x >= (y - 0.5) * start && x - 0.5 <= y * end) {
reveal(realx, realy);
}
scan(y + 1, start, (x - 0.5) / y, transform);
start = (x + 0.5) / y;
if (start >= end) {
return;
}
}
}
scan(y + 1, start, end, transform);
};
// An array of transforms, each corresponding to one octant.
var transforms = [
{ xx: 1, xy: 0, yx: 0, yy: 1 },
{ xx: 1, xy: 0, yx: 0, yy: -1 },
{ xx: -1, xy: 0, yx: 0, yy: 1 },
{ xx: -1, xy: 0, yx: 0, yy: -1 },
{ xx: 0, xy: 1, yx: 1, yy: 0 },
{ xx: 0, xy: 1, yx: -1, yy: 0 },
{ xx: 0, xy: -1, yx: 1, yy: 0 },
{ xx: 0, xy: -1, yx: -1, yy: 0 }
];
reveal(cx, cy);
// Scan each octant
for (var i = 0; i < 8; i++) {
scan(1, 0, 1, transforms[i]);
}
};
@JVMartin
Copy link

JVMartin commented Sep 6, 2016

This is freaking awesome, thank you!

In the past, I was using the algorithm here:
http://www.roguebasin.com/index.php?title=FOV_using_recursive_shadowcasting

But I was super disappointed that it was not symmetric. Yours works great, so much cleaner! Can I ask how you designed this algorithm? Did you adapt it from that algorithm I linked to?

Thanks for any input on your process!

@370417
Copy link
Author

370417 commented Mar 20, 2017

I started with making recursive shadowcasting symmetric by only revealing tiles whose centers were visible. Then I noticed that the shadows looked too wide for my tastes, so I beveled the corners, inspired by another algorithm.

@Stakker
Copy link

Stakker commented Aug 26, 2021

This is the best shadowcasting implementation I've seen! Symmetric, concise and draws shadows with intuitive looking angles. Thank you so much!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment