Skip to content

Instantly share code, notes, and snippets.

Embed
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

This comment has been minimized.

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!

@as-f

This comment has been minimized.

Copy link
Owner Author

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
You can’t perform that action at this time.
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.