-
-
Notifications
You must be signed in to change notification settings - Fork 254
/
recursive-shadowcasting.ts
153 lines (139 loc) · 5.23 KB
/
recursive-shadowcasting.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
import FOV, { VisibilityCallback } from "./fov.js";
/** Octants used for translating recursive shadowcasting offsets */
const OCTANTS = [
[-1, 0, 0, 1],
[ 0, -1, 1, 0],
[ 0, -1, -1, 0],
[-1, 0, 0, -1],
[ 1, 0, 0, -1],
[ 0, 1, -1, 0],
[ 0, 1, 1, 0],
[ 1, 0, 0, 1]
];
/**
* @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 default class RecursiveShadowcasting extends FOV {
/**
* 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: VisibilityCallback) {
//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: VisibilityCallback) {
//You can always see your own tile
callback(x, y, 0, 1);
let previousOctant = (dir - 1 + 8) % 8; //Need to retrieve the previous octant to render a full 180 degrees
let nextPreviousOctant = (dir - 2 + 8) % 8; //Need to retrieve the previous two octants to render a full 180 degrees
let 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: VisibilityCallback) {
//You can always see your own tile
callback(x, y, 0, 1);
let 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: VisibilityCallback) {
//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: VisibilityCallback) {
if (visSlopeStart < visSlopeEnd) { return; }
for (let i = row; i <= radius; i++) {
let dx = -i - 1;
let 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
let mapX = startX + dx * xx + dy * xy;
let mapY = startY + dx * yx + dy * yy;
//Range of the row
let slopeStart = (dx - 0.5) / (dy + 0.5);
let 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; }
//If it's in range, it's visible
if ((dx * dx + dy * dy) < (radius * radius)) {
callback(mapX, mapY, i, 1);
}
if (!blocked) {
//If tile is a blocking tile, cast around it
if (!this._lightPasses(mapX, mapY) && i < radius) {
blocked = true;
this._castVisibility(startX, startY, i + 1, visSlopeStart, slopeStart, radius, xx, xy, yx, yy, callback);
newStart = slopeEnd;
}
} else {
//Keep narrowing if scanning across a block
if (!this._lightPasses(mapX, mapY)) {
newStart = slopeEnd;
continue;
}
//Block has ended
blocked = false;
visSlopeStart = newStart;
}
}
if (blocked) { break; }
}
}
}