Skip to content

Instantly share code, notes, and snippets.

@Slogo

Slogo/skinnyfov Secret

Created July 16, 2021 04:15
Show Gist options
  • Save Slogo/2f1f1eed8231445a66c9a3aa14d31f27 to your computer and use it in GitHub Desktop.
Save Slogo/2f1f1eed8231445a66c9a3aa14d31f27 to your computer and use it in GitHub Desktop.
Skinny Wall Recursive Shadowcasting
import { AdjTypes } from "./Map";
import { gameData } from "../GameManager";
const isOpen = (adj: AdjTypes) => {
return adj !== AdjTypes.WALL;
};
/** Octants used for translating recursive shadowcasting offsets */
const OCTANTS = [
[-1, 0, 0, 1], //2 R->L (B->T) oy -1 -1 ** yy | iy 0
[0, -1, 1, 0], //3 T->B (L->R) oy 0 | iy 1 yx
[0, -1, -1, 0], //4 B->T (L->R) oy 0 | iy yx
[-1, 0, 0, -1], //5 R->L (T->B) oy 1 -1 ** yy | iy 0
[1, 0, 0, -1], //6 L->R (T->B) oy -1 * yy | iy 0
[0, 1, -1, 0], //7 B->T (R->L) oy 0 | iy -1 yx
[0, 1, 1, 0], //8 T->B (R->L)
[1, 0, 0, 1], //1 L->R (B->T)
];
//dx -> axis of row clear
//dy -> axis of row transition
//[0] == xx = x difference for "row"/inner scan
//[1] == xy = -1 * x difference for outer scan
//[2] == yx = y diff for "row"/inner scan
//[3] == yy = -1 * y diff for "col"/outer scan
//const mapX = startX + dx * xx + dy * xy;
//const mapY = startY + dx * yx + dy * yy;
type RVisiblity = (x: number, y: number, R: number, visible: number) => void;
type RLightPasses = (
x: number,
y: number,
xx: number,
xy: number,
yx: number,
yy: number
) => boolean;
/**
* @class Recursive shadowcasting algorithm
* Currently only supports 4/8 topologies, not hexagonal.
* Based on Peter Harkins' implementation of Björn Bergström's algorithm described here: http://www.roguebasin.com/index.php?title=FOV_using_recursive_shadowcasting
* @augments ROT.FOV
*/
export class SkinnyRecursiveShadowcasting {
_lightCasts: RLightPasses;
_lightPasses: RLightPasses;
constructor(
lightCastsCallback: RLightPasses,
lightPassesCallback: RLightPasses
) {
this._lightCasts = lightCastsCallback;
this._lightPasses = lightPassesCallback;
}
/**
* Compute visibility for a 360-degree circle
* @param {int} x
* @param {int} y
* @param {int} R Maximum visibility radius
* @param {function} callback
*/
compute(x: number, y: number, R: number, callback: RVisiblity) {
//You can always see your own tile
callback(x, y, 0, 1);
for (let i = 0; i < OCTANTS.length; i++) {
this._renderOctant(x, y, OCTANTS[i], R, callback);
}
}
/**
* Compute visibility for a 180-degree arc
* @param {int} x
* @param {int} y
* @param {int} R Maximum visibility radius
* @param {int} dir Direction to look in (expressed in a ROT.DIRS value);
* @param {function} callback
*/
compute180(
x: number,
y: number,
R: number,
dir: number,
callback: RVisiblity
) {
//You can always see your own tile
callback(x, y, 0, 1);
const previousOctant = (dir - 1 + 8) % 8; //Need to retrieve the previous octant to render a full 180 degrees
const nextPreviousOctant = (dir - 2 + 8) % 8; //Need to retrieve the previous two octants to render a full 180 degrees
const nextOctant = (dir + 1 + 8) % 8; //Need to grab to next octant to render a full 180 degrees
this._renderOctant(x, y, OCTANTS[nextPreviousOctant], R, callback);
this._renderOctant(x, y, OCTANTS[previousOctant], R, callback);
this._renderOctant(x, y, OCTANTS[dir], R, callback);
this._renderOctant(x, y, OCTANTS[nextOctant], R, callback);
}
/**
* Compute visibility for a 90-degree arc
* @param {int} x
* @param {int} y
* @param {int} R Maximum visibility radius
* @param {int} dir Direction to look in (expressed in a ROT.DIRS value);
* @param {function} callback
*/
compute90(
x: number,
y: number,
R: number,
dir: number,
callback: RVisiblity
) {
//You can always see your own tile
callback(x, y, 0, 1);
const previousOctant = (dir - 1 + 8) % 8; //Need to retrieve the previous octant to render a full 90 degrees
this._renderOctant(x, y, OCTANTS[dir], R, callback);
this._renderOctant(x, y, OCTANTS[previousOctant], R, callback);
}
/**
* Render one octant (45-degree arc) of the viewshed
* @param {int} x
* @param {int} y
* @param {int} octant Octant to be rendered
* @param {int} R Maximum visibility radius
* @param {function} callback
*/
_renderOctant(
x: number,
y: number,
octant: number[],
R: number,
callback: RVisiblity
) {
if (
this._lightPasses(
x,
y,
octant[0],
-1 * octant[1],
octant[2],
-1 * octant[3]
)
) {
//Radius incremented by 1 to provide same coverage area as other shadowcasting radiuses
this._castVisibility(
x,
y,
1,
1.0,
0.0,
R + 1,
octant[0],
octant[1],
octant[2],
octant[3],
callback
);
}
}
/**
* Actually calculates the visibility
* @param {int} startX The starting X coordinate
* @param {int} startY The starting Y coordinate
* @param {int} row The row to render
* @param {float} visSlopeStart The slope to start at
* @param {float} visSlopeEnd The slope to end at
* @param {int} radius The radius to reach out to
* @param {int} xx
* @param {int} xy
* @param {int} yx
* @param {int} yy
* @param {function} callback The callback to use when we hit a block that is visible
*/
_castVisibility(
startX: number,
startY: number,
row: number,
visSlopeStart: number,
visSlopeEnd: number,
radius: number,
xx: number,
xy: number,
yx: number,
yy: number,
callback: RVisiblity
) {
if (visSlopeStart < visSlopeEnd) {
return;
}
for (let i = row; i <= radius; i++) {
let dx = -i - 1;
const dy = -i;
let blocked = false;
let newStart = 0;
//'Row' could be column, names here assume octant 0 and would be flipped for half the octants
while (dx <= 0) {
dx += 1;
//Translate from relative coordinates to map coordinates
const mapX = startX + dx * xx + dy * xy;
const mapY = startY + dx * yx + dy * yy;
//Range of the row
const slopeStart = (dx - 0.5) / (dy + 0.5);
const slopeEnd = (dx + 0.5) / (dy - 0.5);
//Ignore if not yet at left edge of Octant
if (slopeEnd > visSlopeStart) {
continue;
}
//Done if past right edge
if (slopeStart < visSlopeEnd) {
break;
}
const casts = this._lightCasts(mapX, mapY, xx, -1 * xy, yx, -1 * yy);
//If it's in range, it's visible
if (dx * dx + dy * dy < radius * radius && (casts || dx === 0)) {
//&& this._lightHits(mapX, mapY, xx, xy, yx, yy)) {
callback(mapX, mapY, i, 1);
}
if (!blocked) {
//If tile is a blocking tile, cast around it
const passes =
this._lightPasses(mapX, mapY, xx, -1 * xy, yx, -1 * yy) &&
i < radius;
if (!passes) {
this._castVisibility(
startX,
startY,
i + 1,
visSlopeStart,
slopeStart,
radius,
xx,
xy,
yx,
yy,
callback
);
newStart = slopeEnd;
blocked = true;
} else if (!casts && dx < 0) {
this._castVisibility(
startX,
startY,
i + 1,
visSlopeStart,
slopeStart,
radius,
xx,
xy,
yx,
yy,
callback
);
newStart = slopeEnd;
blocked = true;
}
} else {
//Keep narrowing if scanning across a block
if (!this._lightPasses(mapX, mapY, xx, -1 * xy, yx, -1 * yy)) {
newStart = slopeEnd;
continue;
}
//Block has ended
blocked = false;
visSlopeStart = newStart;
}
}
if (blocked) {
break;
}
}
}
}
export const PlayerVisibility = new SkinnyRecursiveShadowcasting(
(x, y, innerX, outerX, innerY, outerY) => {
// [0, -1, 1, 0], //3 T->B (L->R)
//[0, -1, -1, 0], //4 B->T (L->R)
const map = gameData.current;
if (0 <= x && x < map.width && 0 <= y && y < map.height) {
if (innerX === -1) {
return map.tiles[x + y * map.width].adj.left !== AdjTypes.WALL;
} else if (innerX === 1) {
return map.tiles[x + y * map.width].adj.right !== AdjTypes.WALL;
}
if (innerY === -1) {
return map.tiles[x + y * map.width].adj.up !== AdjTypes.WALL;
} else if (innerY === 1) {
return map.tiles[x + y * map.width].adj.down !== AdjTypes.WALL;
}
}
return false;
},
(x, y, innerX, outerX, innerY, outerY) => {
const map = gameData.current;
if (0 <= x && x < map.width && 0 <= y && y < map.height) {
if (outerX === -1) {
return map.tiles[x + y * map.width].adj.left !== AdjTypes.WALL;
} else if (outerX === 1) {
return map.tiles[x + y * map.width].adj.right !== AdjTypes.WALL;
}
if (outerY === -1) {
return map.tiles[x + y * map.width].adj.up !== AdjTypes.WALL;
} else if (outerY === 1) {
return map.tiles[x + y * map.width].adj.down !== AdjTypes.WALL;
}
}
return false;
}
);
export const getPlayerVisibility = (
width: number,
x: number,
y: number,
range: number,
result = new Map<number, boolean>()
) => {
result.clear();
PlayerVisibility.compute(x, y, range, (x, y, _, visible) => {
if (visible) {
result.set(x + y * width, true);
}
});
/**result.set(gameData.player.x + gameData.player.y * width, true);
PlayerVisibility._renderOctant(
x,
y,
OCTANTS[7],
range,
(x, y, _, visible) => {
if (visible) {
result.set(x + y * width, true);
}
}
);**/
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment