# Precise Shadowcasting in JavaScript

This pages describes and explains the Precise Shadowcasting algorithm, developed and implemented by Ondřej Žára in rot.js.

WORK IN PROGRESS

## Contents

In a cellular level, this algorithm computes a set of all cells visible from a certain fixed (starting) point. This set is limited by a given maximum sight range, e.g. no cell in a distance larger than that could be visible.

Cells can be either blocking (they are obstacles and stuff behind them cannot be seen) or non-blocking.

This shadowcasting is topology-invariant: its implementation is the same in all topologies. There are two basic concepts and tools:

1. A ring is a set of all cells with a constant distance from a center.

```..x..
.x.x.
x.@.x    Ring 2 in 4-topology (set of all cells with distance=2)
.x.x.
..x..
```
```xxxxx
x...x
x.@.x    Ring 2 in 8-topology (set of all cells with distance=2)
x...x
xxxxx
```

2. Shadow queue is a list of all angles which are blocked (by a blocking cells). This list is intially empty; as cells are examined, some of them (those who are blocking) cast shadows, which are added to the shadow queue.

## General algorithm workflow

1. Let `[x,y]` be the player coordinates
2. Initialize the empty shadow queue
3. For `R=1` up to maximum visibility range do:
1. Retrieve all cells whose range from `[x,y]` is `R`
2. Make sure these cells are in correct order (clockwise or counter-clockwise; every iteration starting at the same angle)
3. For every cell in this "ring":
1. Determine the corresponding arc `[a1,a2]`
2. Consult the shadow queue to determine whether `[a1,a2]` is fully shadowed
3. If no part of `[a1,a2]` is visible, mark the cell as not visible and advance to next cell
4. If some part of `[a1,a2]` is visible, merge it into the shadow queue; mark the cell as visible

```.....    Sample scenario (topology 4). Cell "#" [3,2] is blocking. It is the first cell of ring1 and thus adds [-45 .. 45] to the shadow queue.
....b
..@#a    Cell "a" [4,2] is the first cell of ring2 and corresponds to arc [-22.5 .. 22.5]. Since this is a subset of the shadow queue, the cell is not visible.
.....
.....    Cell "b" [4,3] is the second cell of ring2 and corresponds to arc [22.5 .. 67.5]. It is not fully shadowed, so the cell is visible.
```