Shadowcasting
Shadowcasting is a way to implement field of vision. A destination square is considered visible from a source square if no obtrusions block the line of sight path to the destination.
Typical field of vision approaches given a radius, to trace all lines from the source to the perimeter checking obstructions along the way. If blocked, all squares beyond the blocked obstacle are ignored.
Shadowcasting is implemented in a totally unique way, calculating scans across rows or columns. It seeks to improve performance over line of sight checks and duplicate tile inspections.
Algorithm
Shadowcasting divides the FOV calculations into eight octants and visits the mapcells in a totally different way than normal raycasting, described above. Instead of tracing lines from the center out to the edges, shadowcasting visits mapcells row by row or column by column, starting with the nearest row or column and working it's way outward.
Here is an order of scanning:
------> 6 row 6 last
-----> 5 .
----> 4 .
---> 3 .
--> 2 row 2 second
-> 1 row 1 is scanned first
@ @ this is the starting pointWhen a scan comes across a cell that blocks LOS it calculates which other cells in rows/columns farther away that isn't visible because of the blocker. Those cells are "in shadow", hence the term shadowcasting.
-...--- - = visible cells
-..--- # = blocking cell
-#--- . = cells in blocker's shadow
----
---
--
@Understanding Slope
In order to understand how it works we must understand what the slope and inverse slope of a line means.
Slope: slope = (x1 - x2) / (y1 - y2)
Example: slope = (6 - 5) / (6 - 3) = 1 / 3 = 0.33333
Inverse Slope: inverse slope = 1 / slope
Example: inverse slope = 1 / 0.33333 = ~3
Recursive Shadowcasting
The scan is done across 8 octants, each sharing the edge of its neighbors like so:
Shared
edge by
Shared 1 & 2 Shared
edge by\ | /edge by
1 & 8 \ | / 2 & 3
\1111|2222/
8\111|222/3
88\11|22/33
888\1|2/333
Shared 8888\|/3333 Shared
edge by-------@-------edge by
7 & 8 7777/|\4444 3 & 4
777/6|5\444
77/66|55\44
7/666|555\4
/6666|5555\
Shared / | \ Shared
edge by/ | \edge by
6 & 7 Shared 4 & 5
edge by
5 & 6An octant is scanned as described above, starting with the cells closest to the starting point.
In octant 1 and 6 the scans are performed row by row, going from the leftmost cell to the rightmost cell in each row.
In octant 2 and 5 the scans are performed row by row, going from the rightmost cell to the leftmost cell in each row.
In octant 3 and 8 the scans are performed column by column, going from the topmost cell to the bottom most cell in each column.
In octant 4 and 7 the scans are performed column by column, going from the bottom most cell to the topmost cell in each column.
When a blocking cell is found a new scan is recursivly started one row/column further away.
Example area we want to calculate:
................. 16 @ = starting cell
......###....... 15 # = blocking cell
.....###....... 14 . = non-blocking cell
....###..#..## 13
...##........ 12
............ 11
........... 10
.......... 9
......... 8
........ 7
....... 6
...... 5
..... 4
.... 3
... 2
.. 1
@Rows 1 through 11 are all scanned without any problems from left to right. When the rightmost cell is reached a new scan is started one row further away.
The line on the left most cells has a slope of -1 and the line on the right most cells has a slope of 0 (thinking in cartesian coordinates).
At row 12, recursion begins once we hit our first blocked cell:
................. 16 # = blocking cell
......###....... 15 . = non-blocking cell
.....###....... 14
....###..#..## 13
...x#........ 12 x = first blocking cellSince we want to start a recursive scan to ignore all cells beyond the blocked cell as out of line of sight, we can calculate the slope to our starting point since it is not 1 from this position.
slope = 12 rows away / -9 columns to the left = -.75
Scan 1 will continue along its original row, skipping any successively connected blocked obstacles. Scan 2 will use the original slope of -1 as its left edge and the slope calculated as its right boundary -.75, i.e. does not include it in the scan.
2222............. 16 # = blocking cell
2222..###....... 15 . = non-blocking cell
222..###....... 14
222.###..#..## 13 1 = original scan
111##11111111 12 2 = new scanScan 1 skips the successively blocking cells until it finds its next open cell.
................. 16 # = blocking cell
......###....... 15 . = non-blocking cell
.....###....... 14
....###..#..## 13
...##o....... 12 o = first non-blocking cell after a section of blockers
`
The slope is again calculated for this cell `slope = 12 rows / -7 columns = -0.58333`. This becomes the new starting edge of Scan 1 and it continues.
When the original scan starts on row 13 a blocking cell is immediately found:
``` text
................. 16 # = blocking cell
......###....... 15 . = non-blocking cell
.....###....... 14
....##x..#..## 13 x = blocking cell in original scanScan 1 spawns a second recurisive scan, Scan 3 like it did with Scan 2 to calculate the vision beyond. It uses its parent left slope -1 as its left edge and a new slope calculated for its right boundary.
We can see at this point that the child scans carry out the vision of the parent scan in the same angles of the parent scan just with the right edge being a new slope.
Scan 1 continues to the left until it finds another non-blocking cell. When it is located we calculate our new edge slope and continue.
................. 16 # = blocking cell
......###....... 15 . = non-blocking cell
.....###....... 14
....##...x..## 13 x = blocking cell in original scanAt this point Scan 1, and child Scans 2 and 3 are running.
2222......33..... 16
2222..##333..... 15 first cell in 3 is blocked, others are not
222..##333..... 14 first cell in 3 is blocked, others are not
222.###11#11## 13The newly located blocked cell in Scan 1 spawns a new Scan 4 and it processes Scan 1's vision beyond that point.
2222......33444.. 16
2222..##333.44.. 15
222..##333.44.. 14
222.##111#11## 13When the original scan ends at the rightmost cell in row 13 we end with a blocking instead of a non-blocking, as we did in row 12. Since the original scan ended with a blocking cell a new scan is NOT started one row further away. We now have scan 2, 3 and 4 to do the job of scanning the rest of the field of view. These scans follow the same procedures and rules as the original scan.
When the scans are done we get this field of view:
....ssssss.....ss 16 @ = starting cell
....ssss#..s..ss 15 # = blocking cell
...ssss#..s..ss 14 . = non-blocking cell
...ss##..#..## 13 s = shadowed cells
...##........ 12
............ 11
........... 10
.......... 9
......... 8
........ 7
....... 6
...... 5
..... 4
.... 3
... 2
.. 1
@Updated Shadowcaster in C
The C++ implementation below had the side effect of testing tiles multiple times. This meant that if you wanted to inspect each lit tile one time, it would cause issues testing the same tiles more than once. Think of implementing a lighting engine of of this. Each light casts luminosity onto tiles in an additive way. If we add luminosity for one cast across the same tile more than once we get incorretly brightened patterns.
My C++ implementation around this was to have a static ID that would incremement only when the alogirthm ran. You could check your tile's shadowcasted id and if was different then apply your changes to that tile and reset it. This was obviously a hack and eventually broke down when I needed to run nested shadowcasting, i.e. when one shadowcast triggered another, the ID would increment.
My real solution was reimplemented in C which abandons the shadowcaster id and instead creates a shadowcast test array in memory. Values are only ever calculated if their position in the array has not been tested before.
The original C++ implementation is further down for posterity.
Implementation in C
///////////////////////////
// SHADOWCASTING START
int shadow_multiples[4][8] = {
{1, 0, 0, -1, -1, 0, 0, 1},
{0, 1, -1, 0, 0, -1, 1, 0},
{0, 1, 1, 0, 0, -1, -1, 0},
{1, 0, 0, 1, -1, 0, 0, -1},
};
bool dm_sc_is_leakageblocked(int x, int y, int ax, int ay, bool (*is_blocked)(int, int))
{
double dirf_x, dirf_y;
dm_direction((double)x, (double)y, (double)ax, (double)ay, &dirf_x, &dirf_y);
int rx = (int)dm_ceil_out(dirf_x);
int ry = (int)dm_ceil_out(dirf_y);
//if (!is_blocked(ax, ay)) { // uncomment this if you want to show blocked cells, but it hints at things on the map if you do
if (is_blocked(ax - rx, ay) && is_blocked(ax, ay - ry)) {
return true;
}
//}
return false;
}
void dm_shadowcast_r(
int x, int y,
int xmax, int ymax,
unsigned int radius,
bool (*is_blocked)(int, int),
void (*on_visible)(int, int, double),
bool allow_leakage,
int octant, int row, double start_slope, double end_slope,
int xx, int xy, int yx, int yy,
int *history
)
{
int radius2 = radius * radius;
// FINALLY GOING TO SIT DOWN AND RESOLVE THIS ONCE AND FOR ALL WITH ITS DOUBLING UP
// If light start is less than light end, return
if (start_slope < end_slope)
return;
double next_start_slope = start_slope;
// Loop moves outward from current row (or column if octant) to final radius in rows
// row is passed in since this is recursive
for (int i = row; i <= radius; i++) {
bool blocked = false;
// Loop moves across columns (or row if octant) until the right most
// border is reacheda
for (int dx = -i, dy = -i; dx <= 0; dx++) {
// l_slope and r_slope store the slopes of the left and right extremities of the square we're considering:
double l_slope = (dx - 0.5f) / (dy + 0.5f);
double r_slope = (dx + 0.5f) / (dy - 0.5f);
if (start_slope < r_slope)
continue;
else if (end_slope > l_slope)
break;
int sax = dx * xx + dy * xy;
int say = dx * yx + dy * yy;
if ((sax < 0 && abs(sax) > x) || (say < 0 && abs(say) > y))
continue;
int ax = x + sax;
int ay = y + say;
// Dont look out of bounds
if (ax >= xmax || ay >= ymax)
continue;
// Todo, check to see if we are leaking through diagonal walls?
bool leakage_blocked = false;
if (!allow_leakage) {
leakage_blocked = dm_sc_is_leakageblocked(x, y, ax, ay, is_blocked);
}
// Our light beam is touching this square; light it if it has not been tested before
// Convert our coordinate to our radius temp map which is just the radius squared
if ((int)(dx * dx + dy * dy) < radius2 && !leakage_blocked) {// && history[hindex] == 0) {
int dimensions = radius * 2 - 1; // a 3x3 is 3 on left, 2 on right, center coord is not counted twice
int hx = ax - x + (dimensions)/2;
int hy = ay - y + (dimensions)/2;
int hindex = hy * (dimensions) + hx;
//int size = dimensions*dimensions; // add 1 for our center coord
//printf("x=%d,y=%d,r=%d ax=%d,ay=%d hx=%d,hy=%d,hindex=%d,h=%d\n", x,y,radius, ax,ay, hx,hy,hindex,history[hindex]);
if (history[hindex] == 0) {
history[hindex] = 1; // mark this as viewed
on_visible(ax, ay, (double)i / (double)radius);
}
}
if (blocked) {
// We're scanning a row of blocked squares
if (is_blocked(ax, ay) || leakage_blocked) {
next_start_slope = r_slope;
continue;
} else {
blocked = false;
start_slope = next_start_slope;
}
} else if (is_blocked(ax, ay) || leakage_blocked) {
blocked = true;
next_start_slope = r_slope;
dm_shadowcast_r(x, y, xmax, ymax, radius, is_blocked, on_visible, allow_leakage, octant, i + 1, start_slope, l_slope, xx, xy, yx, yy, history);
}
}
if (blocked)
break;
}
}
void dm_shadowcast(int x, int y, int xmax, int ymax, unsigned int radius, bool (*is_blocked)(int, int), void (*on_visible)(int, int, double), bool allow_leakage)
{
on_visible(x, y, 0); // visible the center coord
// There was a bug in this algorithm that when it circled it would run is_visible on tiles twice
// this was because as it circled and filled out octant areas they would overlap previous octact edge by one
// When this happened on_visible ran on the same tile twice and i had to do some dumb
// checking to make it so I would not double effect lit tiles
// I fixed this by creating a temporary map of tiles to
int dimensions = radius * 2 - 1;
int size = dimensions*dimensions; // add 1 for our center coord
int history[size];
for (int i=0; i < size; i++)
history[i] = 0;
for (int octant = 0; octant < 8; octant++) { // 8 octants
dm_shadowcast_r(
x, y, xmax, ymax, radius,
is_blocked, on_visible, allow_leakage,
octant, 1, 1.0, 0.0,
shadow_multiples[0][octant], shadow_multiples[1][octant], shadow_multiples[2][octant], shadow_multiples[3][octant],
history
);
//if (i % 2 == 0)
// dm_shadowcast_r(x, y, xmax, ymax, radius, is_blocked, on_visible, allow_leakage, i, 1, 1.0, 0.0, shadow_multiples[0][i], shadow_multiples[1][i], shadow_multiples[2][i], shadow_multiples[3][i]);
//else
// dm_shadowcast_r(x, y, xmax, ymax, radius-1, is_blocked, on_visible, allow_leakage, i, 1, 1.0, 0.0, shadow_multiples[0][i], shadow_multiples[1][i], shadow_multiples[2][i], shadow_multiples[3][i]);
}
}
// SHADOWCASTING END
///////////////////////////Usage in C
This function takes a game character and checks all other tiles in the vision of the character. The shadowcaster takes its two main functions: determining if a tile is block and what to do when something is visible.
void wld_mob_vision(struct wld_mob *mob, void (*on_see)(struct wld_mob*, int, int, double))
{
// todo get radius of mobs vision?
struct wld_map* map = mob->map;
bool wld_ss_isblocked(int x, int y)
{
struct wld_tile *t = wld_map_get_tile_at(map, x, y);
return wld_tile_is_blocked_vision(t);
}
void wld_ss_onvisible(int x, int y, double radius)
{
struct wld_tile *t = wld_map_get_tile_at(map, x, y);
on_see(mob, x, y, radius);
}
dm_shadowcast(mob->map_x, mob->map_y, map->cols, map->rows, mob->vision + mob->vision_boost, wld_ss_isblocked, wld_ss_onvisible, false); // no leakage allowed
}Original Shadowcaster in C++
In this example implementation a game character computes its field of view to see all visible tiles within a certain range:
void Character::inspectVisibleTiles(std::function<void(Tile* t)> inspector)
{
Character* character = this;
// Pass our starting position, the max width and height of the level to calculate, and a vision radius to stop calculating at
// Pass a lambda function to inspect a tile the shadowcaster has determined is visible
// Pass a final lambda function to determine if a tile should be considered blocked
bit::Shadowcaster::computeFoV(Body::schema.x / level->tileWidth, Body::schema.y / level->tileHeight, level->tileColumns, level->tileRows, visionRadius,
[character, inspector] (int x, int y, float distance) {
Tile* tile = character->level->getTileAtIndices(x, y);
// To avoid duplicate inspection of edge tiles in our shadowcaster, limit how many times we look at a tile with a scan id
if(tile && tile->metadata_shadowcastId != bit::Shadowcaster::shadowcastId)
{
tile->metadata_shadowcastId = bit::Shadowcaster::shadowcastId;
inspector(tile);
}
},
std::bind(&Character::inspectTileVisuallyBlocked, this, std::placeholders::_1, std::placeholders::_2)
);
}Shadowcaster Implementation in C++
Shadowcaster.hpp
#pragma once
#ifndef BIT_SHADOWCASTER_H
#define BIT_SHADOWCASTER_H
#include <functional>
#include <complex>
#include <vector>
#include "../Math/Math.hpp"
#include "../Math/VectorMath.hpp"
namespace bit
{
class Shadowcaster
{
public:
static unsigned int shadowcastId;
// Determines which co-ordinates on a 2D grid are visible from a particular co-ordinate.
// x, y: center of view
// radius: how far field of view extends
static void computeFoV(
unsigned int x,
unsigned int y,
unsigned int xMax,
unsigned int yMax,
unsigned int radius,
std::function<void(int, int, float)> setVisible,
std::function<bool(int, int)> isBlocked)
{
// Increment our global usage id
shadowcastId++;
// Always mark base point
setVisible(x, y, 0);
// Iterate across the octants and cast
for (unsigned int i = 0; i < 8; i++)
{
castLight(x, y, xMax, yMax, radius, setVisible, isBlocked, i, 1, 1.0, 0.0, multipliers[0][i], multipliers[1][i], multipliers[2][i], multipliers[3][i]);
}
}
private:
static int multipliers[4][8];
// Recursive light casting function
static void castLight(
unsigned int x,
unsigned int y,
unsigned int xMax,
unsigned int yMax,
unsigned int radius,
std::function<void(int, int, float)> setVisible,
std::function<bool(int, int)> isBlocked,
unsigned int octanct,
unsigned int row,
float start_slope,
float end_slope,
unsigned int xx,
unsigned int xy,
unsigned int yx,
unsigned int yy)
{
// If light start is less than light end, return
if (start_slope < end_slope)
{
return;
}
float next_start_slope = start_slope;
// Loop moves outward from current row (or column if octant) to final radius in rows
// row is passed in since this is recursive
for (unsigned int i = row; i <= radius; i++)
{
bool blocked = false;
// Loop moves across columns (or row if octant) until the right most
// border is reached
for (int dx = -i, dy = -i; dx <= 0; dx++)
{
// l_slope and r_slope store the slopes of the left and right extremities of the square we're considering:
float l_slope = (dx - 0.5f) / (dy + 0.5f);
float r_slope = (dx + 0.5f) / (dy - 0.5f);
if (start_slope < r_slope)
{
continue;
}
else if (end_slope > l_slope)
{
break;
}
int sax = dx * xx + dy * xy;
int say = dx * yx + dy * yy;
if ((sax < 0 && (unsigned int)std::abs(sax) > x) || (say < 0 && (unsigned int)std::abs(say) > y))
{
continue;
}
unsigned int ax = x + sax;
unsigned int ay = y + say;
// Commenting this out to remove dependency on Map
// looks like bounds checking for perf boost in edget of map
//if (ax >= map.shadowcastGetWidth() || ay >= map.shadowcastGetHeight())
if (ax >= xMax || ay >= yMax)
{
continue;
}
// Our light beam is touching this square; light it
unsigned int radius2 = radius * radius;
if ((unsigned int)(dx * dx + dy * dy) < radius2)
{
setVisible(ax, ay, (float)i / (float)radius);
}
if (blocked)
{
// We're scanning a row of blocked squares
if (isBlocked(ax, ay))
{
next_start_slope = r_slope;
continue;
}
else
{
blocked = false;
start_slope = next_start_slope;
}
}
else if (isBlocked(ax, ay))
{
blocked = true;
next_start_slope = r_slope;
castLight(x, y, xMax, yMax, radius, setVisible, isBlocked, octanct, i + 1, start_slope, l_slope, xx, xy, yx, yy);
}
}
if (blocked)
{
break;
}
}
}
};
}
#endifShadowcaster.cpp
#include "Shadowcaster.hpp"
unsigned int bit::Shadowcaster::shadowcastId = 0;
int bit::Shadowcaster::multipliers[4][8] = {
{1, 0, 0, -1, -1, 0, 0, 1},
{0, 1, -1, 0, 0, -1, 1, 0},
{0, 1, 1, 0, 0, -1, -1, 0},
{1, 0, 0, 1, -1, 0, 0, -1}
};