http://roguebasin.com/api.php?action=feedcontributions&user=Nornagon&feedformat=atomRogueBasin - User contributions [en]2021-12-06T14:07:03ZUser contributionsMediaWiki 1.36.0http://roguebasin.com/index.php?title=FOV_using_recursive_shadowcasting&diff=11974FOV using recursive shadowcasting2007-10-09T09:07:41Z<p>Nornagon: Wikified</p>
<hr />
<div>FOV using recursive shadowcasting - Bj&ouml;rn Bergstr&ouml;m [bjorn.bergstrom@roguelikedevelopment.org]<br />
<br />
==Introduction==<br />
A working field-of-view (or commonly known as line of sight) algorithm is one of<br />
the essential parts in any roguelike. A FOV algorithm is used to calculate which<br />
mapcells, within a given radius, that can be seen, or in the case of a<br />
lightsource, which mapcells that are lit.<br />
<br />
The simplest approach is to trace lines from the center out to all of the<br />
mapcells at the edge of the radius and stopping when a mapcell is blocking line<br />
of sight. The problem with this approach is that many mapcells are visited<br />
several times, most often near the starting point and more seldom at the edges.<br />
There are a few things that can improve the performance of this simple approach.<br />
The most obvious is improvement can be made when a blocking mapcell is hit.<br />
Using a simple calculation all rays that cross the blocking mapcell can be<br />
skipped, hence improving performance. All of this is covered in detail in other<br />
LOS articles. "Line of Sight" by Tobias Downer is a good starting point.<br />
<br />
Even if the "rayskipping" described above is implemented many mapcells will be<br />
visited more than once, thus wasting CPU time. To overcome this a totally<br />
different approach must be used. This approach is called shadowcasting.<br />
<br />
<br />
==Shadowcasting==<br />
Shadowcasting divides the FOV calculations into eight octants and visits the<br />
mapcells in a totally different way than normal raycasting, described above.<br />
Instead of tracing lines from the center out to the edges, shadowcasting visits<br />
mapcells row by row or column by column, starting with the nearest row or column<br />
and working it's way outward.<br />
<br />
<pre><br />
------> 6 row 6 last<br />
-----> 5 .<br />
----> 4 .<br />
---> 3 .<br />
--> 2 row 2 second<br />
-> 1 row 1 is scanned first<br />
@ @ this is the starting point <br />
<br />
Fig.2a Shadowcasting order of scanning<br />
</pre><br />
<br />
When a scan comes across a cell that blocks LOS it calculates which other cells<br />
in rows/columns farther away that isn't visible because of the blocker. Those<br />
cells are "in shadow", hence the term shadowcasting.<br />
<br />
<pre><br />
-...--- - = visible cells<br />
-..--- # = blocking cell<br />
-#--- . = cells in blocker's shadow<br />
----<br />
---<br />
--<br />
@<br />
<br />
Fig.2b Cells in shadow of blocker<br />
</pre><br />
<br />
Normal shadowcasting is described in detail in the article "Computing LOS for<br />
Large Areas" by Gordon Lipford. Gordon's algorithm uses a temporary array and<br />
is rather complex. Using recursion one can achieve a clean and pretty fast<br />
algorithm that only visits non blocking and blocking cells, leaving out the<br />
cells in shadow. The algorithm is especially fast in confined areas such as<br />
corridors and small rooms.<br />
<br />
==Definitions==<br />
In order to understand recursive shadowcasting one need to understand what the<br />
slope and inverse slope of a line means. The slope is calculated using this<br />
simple formula:<br />
<br />
slope = (x1 - x2) / (y1 - y2)<br />
<br />
If we draw a line between [6,6] and [5,3] the slope would be:<br />
<br />
slope = (6 - 5) / (6 - 3) = 1 / 3 = 0.33333<br />
<br />
If we were to walk along this line we would find that for each step that we<br />
decreased y, x would be decreased 0.3333.<br />
<br />
The inverse slope is simply 1 / slope.<br />
<br />
<br />
<br />
==Recursive Shadowcasting==<br />
<br />
Recursive shadowcasting divides the field of view into eight octants with shared<br />
edges. The field of view will look like this when the octants are marked:<br />
<br />
<pre><br />
Shared<br />
edge by<br />
Shared 1 & 2 Shared<br />
edge by\ | /edge by<br />
1 & 8 \ | / 2 & 3<br />
\1111|2222/<br />
8\111|222/3<br />
88\11|22/33<br />
888\1|2/333<br />
Shared 8888\|/3333 Shared<br />
edge by-------@-------edge by<br />
7 & 8 7777/|\4444 3 & 4<br />
777/6|5\444<br />
77/66|55\44<br />
7/666|555\4<br />
/6666|5555\<br />
Shared / | \ Shared<br />
edge by/ | \edge by<br />
6 & 7 Shared 4 & 5<br />
edge by <br />
5 & 6<br />
<br />
Fig.4a Area of coverage by each octant<br />
</pre><br />
<br />
As with normal shadowcasting, this recursive shadowcasting algorithm scans an<br />
octant row by row or column by column, depending on the octant. In each octant<br />
the rows/columns closest to the starting point are scanned first.<br />
<br />
<br />
In octant 1 and 6 the scans are performed row by row, going from the leftmost<br />
cell to the rightmost cell in each row.<br />
<br />
In octant 2 and 5 the scans are performed row by row, going from the rightmost<br />
cell to the leftmost cell in each row.<br />
<br />
In octant 3 and 8 the scans are performed column by column, going from the<br />
topmost cell to the bottom most cell in each column.<br />
<br />
In octant 4 and 7 the scans are performed column by column, going from the<br />
bottom most cell to the topmost cell in each column.<br />
<br />
<br />
When a blocking cell is found a new scan is recursivly started one row/column<br />
further away, covering the area up until the first cell in shadow of the<br />
blocker. The rest of the initial row/column is scanned and subsequent blocking<br />
cells directly adjacent to the initial blocker is skipped. If a new section of<br />
non-blocking cells, followed by a blocker, is found the procedure is repeated.<br />
<br />
I will try to illustrate the procedure described above using some simple ascii<br />
drawings. The area that we wish to calculate a field of view for looks like<br />
this:<br />
<br />
<pre><br />
................. 16 @ = starting cell<br />
......###....... 15 # = blocking cell<br />
.....###....... 14 . = non-blocking cell<br />
....###..#..## 13 <br />
...##........ 12<br />
............ 11<br />
........... 10<br />
.......... 9<br />
......... 8<br />
........ 7<br />
....... 6<br />
...... 5<br />
..... 4<br />
.... 3<br />
... 2<br />
.. 1<br />
@<br />
<br />
Fig.4b Field of view<br />
</pre><br />
<br />
Rows 1 through 11 are all scanned without any problems from left to right. When<br />
the rightmost cell is reached a new scan is started one row further away, just<br />
as described before.<br />
<br />
If we were to draw a line from the center of the starting cell to the center of<br />
the leftmost cell in any of these rows we would find that the slope is 1. We<br />
call this the scan's start slope. If we would do the same for the rightmost cell<br />
the slope would be 0. This slope is ofcourse called the end slope.<br />
<br />
When we reach the 12th row things are becoming a bit more interesting. The<br />
recursion is started when we get to row 12 and hit the blocking cells.<br />
<br />
<pre><br />
................. 16 # = blocking cell<br />
......###....... 15 . = non-blocking cell<br />
.....###....... 14 <br />
....###..#..## 13 <br />
...x#........ 12 x = first blocking cell<br />
<br />
Fig.4c The first blocking cell<br />
</pre><br />
<br />
When the first blocking cell is hit (x) a new scan is started on row 13. The<br />
start slope is ofcourse the same as for all of the previous rows (ie. 1), but<br />
the end slope is different. The end slope is calculated using a line from the<br />
starting point to a point that 'brushes' by to the left of the blocking cell. If<br />
we zoom in it looks something like this:<br />
<br />
<pre><br />
+---+xxxxx##### x = first blocking cell<br />
| |xxxxx##### a = point that 'brushes' by to<br />
| |xxxxx##### the left of the blocking cell<br />
| |xxxxx#####<br />
+---axxxxx#####<br />
+---++---++---+<br />
| || || |<br />
| || || |<br />
| || || |<br />
+---++---++---+<br />
<br />
Fig.4d Zoom in on the first blocking cell<br />
</pre><br />
<br />
Thus, the end slope is obtained using a line from the center starting cell to<br />
the point marked 'a' in the figure. This gives an end slope of about 0.82.<br />
<br />
Ok, so now we have two scans; the original that continues to scan row 12 until<br />
the rightmost cell is reached and a new scan that scans row 13 from the leftmost<br />
cell (start slope 1) to the cell at row 13 that intersects the line with a slope<br />
of 0.82 (end slope):<br />
<br />
<pre><br />
2222............. 16 # = blocking cell<br />
2222..###....... 15 . = non-blocking cell<br />
222..###....... 14 <br />
222.###..#..## 13 1 = original scan <br />
111##11111111 12 2 = new scan<br />
<br />
Fig.4e Current scans<br />
</pre><br />
<br />
Ok, lets return to the original scan on row 12. The scan had just come across<br />
the first blocking cell and recursivly started a new scan one row further away<br />
with a new end slope. The original scan now checks the next cell and finds that<br />
this one is also a blocking cell. Since the previous cell was a blocking cell<br />
too, we have come across a section of blocker and just continue scanning until<br />
we reach a non blocking cell:<br />
<br />
<pre><br />
................. 16 # = blocking cell<br />
......###....... 15 . = non-blocking cell<br />
.....###....... 14 <br />
....###..#..## 13 <br />
...##o....... 12 o = first non-blocking cell after a section of blockers<br />
<br />
Fig.4f First non-blocking cell after a blocker<br />
</pre><br />
<br />
When the first non-blocking cell is found after a section of blockers we need to<br />
calculate a new start slope for the scan. This is done using a line from the<br />
center of the starting cell to a point that 'brushes' by to the right of the<br />
blocking cell. If we zoom in it looks something like this:<br />
<br />
<pre><br />
##########aoooo o = first non-blocking cell<br />
##########o o a = point that 'brushes' by to the<br />
##########o o right of the blocking cell<br />
##########o o<br />
##########ooooo<br />
+---++---++---+<br />
| || || |<br />
| || || |<br />
| || || |<br />
+---++---++---+<br />
<br />
Fig.4g Zoom in on the first non-blocking cell<br />
</pre><br />
<br />
Thus, the new start slope of the original scan is obtained using a line from the<br />
center of the starting cell to the point marked 'a' in the figure. This gives a<br />
start slope of about 0.68.<br />
<br />
Ok, once a scan has reached it's last cell the scan is finished and a new scan<br />
is started one row further away if, and only if, the last cell was a<br />
non-blocking cell. In the case of our original scan the last cell was a<br />
non-blocking cell so a new scan is started one row further away with the new<br />
start slope of 0.68 (instead of the old 1).<br />
<br />
<br />
When the original scan starts on row 13 a blocking cell is immediately found:<br />
<br />
<pre><br />
................. 16 # = blocking cell<br />
......###....... 15 . = non-blocking cell<br />
.....###....... 14 <br />
....##x..#..## 13 x = blocking cell in original scan<br />
<br />
Fig.4h Starting with a blocking cell<br />
</pre><br />
<br />
When this happens we continue scanning until a non-blocking cell is found. In<br />
this case the next cell is a non-blocking cell and we calculate a new start<br />
slope in the same manner as on row 12 when we passed the section of blockers.<br />
After this is done we continue to scan from left to right until we reach the<br />
last cell or until we hit a blocking cell. In our example a blocking cell is<br />
found before we reach the last cell:<br />
<br />
<pre><br />
................. 16 # = blocking cell<br />
......###....... 15 . = non-blocking cell<br />
.....###....... 14 <br />
....##...x..## 13 x = blocking cell in original scan<br />
<br />
Fig.4i Another blocking cell<br />
</pre><br />
<br />
A new scan is now recursivly started in the same way as on row 12. The scan has<br />
the same start slope as the original scan (0.68) and an end slope of a line that<br />
'brushes' by to the left of the blocking cell (marked x in fig.4i). Now we have<br />
three active scans:<br />
<br />
<pre><br />
2222......33..... 16<br />
2222..##333..... 15<br />
222..##333..... 14 <br />
222.###11#11## 13 <br />
<br />
Fig.4j Active scans<br />
</pre><br />
<br />
The same procedure is repeated once more when we move out of the blocking cell,<br />
find two new non-blocking cells and the run into yet another blocking cell:<br />
<br />
<pre><br />
2222......33444.. 16<br />
2222..##333.44.. 15<br />
222..##333.44.. 14 <br />
222.##111#11## 13 <br />
<br />
Fig.4k Active scans<br />
</pre><br />
<br />
When the original scan ends at the rightmost cell in row 13 we end with a<br />
blocking instead of a non-blocking, as we did in row 12. Since the original scan<br />
ended with a blocking cell a new scan is NOT started one row further away. We<br />
now have scan 2, 3 and 4 to do the job of scanning the rest of the field of<br />
view. These scans follow the same procedures and rules as the original scan.<br />
<br />
When the scans are done we get this field of view:<br />
<br />
<pre><br />
....ssssss.....ss 16 @ = starting cell<br />
....ssss#..s..ss 15 # = blocking cell<br />
...ssss#..s..ss 14 . = non-blocking cell<br />
...ss##..#..## 13 s = shadowed cells<br />
...##........ 12<br />
............ 11<br />
........... 10<br />
.......... 9<br />
......... 8<br />
........ 7<br />
....... 6<br />
...... 5<br />
..... 4<br />
.... 3<br />
... 2<br />
.. 1<br />
@<br />
</pre><br />
<br />
This procedure is repeated on the other octants, thus producing a complete<br />
field of view. An implementation along with source and DOS executable can<br />
be found here.<br />
<br />
Copyright 2001 Bj&ouml;rn Bergstr&ouml;m<br />
bjorn.bergstrom@roguelikedevelopment.org<br />
<br />
An [[PythonShadowcastingImplementation|implementation]] of this algorithm in Python.<br />
<br />
[[Category:Articles]][[Category:LOS]]</div>Nornagon