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]);
}
};
@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