Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
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 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!

Owner

as-f 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.

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