# Precise Shadowcasting in JavaScript

Line 4: | Line 4: | ||

== About == | == About == | ||

+ | |||

+ | 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. | ||

+ | |||

+ | <pre> | ||

+ | ..x.. | ||

+ | .x.x. | ||

+ | x.@.x Ring 2 in 4-topology (set of all cells with distance=2) | ||

+ | .x.x. | ||

+ | ..x.. | ||

+ | </pre> | ||

+ | |||

+ | <pre> | ||

+ | xxxxx | ||

+ | x...x | ||

+ | x.@.x Ring 2 in 8-topology (set of all cells with distance=2) | ||

+ | x...x | ||

+ | xxxxx | ||

+ | </pre> | ||

+ | |||

+ | 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 == | == General algorithm workflow == | ||

Line 19: | Line 45: | ||

== Advanced topics: tricks and tweaks == | == Advanced topics: tricks and tweaks == | ||

+ | |||

+ | === Half-angle backward shift === | ||

=== Cutoff and angle wrapping === | === Cutoff and angle wrapping === | ||

=== Symbolic angles === | === Symbolic angles === | ||

− | |||

− | |||

=== Working with shadow queue === | === Working with shadow queue === |

## Revision as of 08:52, 4 January 2013

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

**WORK IN PROGRESS**

## Contents |

## About

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

- Let
`[x,y]`

be the player coordinates - Initialize the empty shadow queue
- For
`R=1`

up to maximum visibility range do:- Retrieve all cells whose range from
`[x,y]`

is`R`

- Make sure these cells are in correct order (clockwise or counter-clockwise; every iteration starting at the same angle)
- For every cell in this "ring":
- Determine the corresponding arc
`[a1,a2]`

- Consult the shadow queue to determine whether
`[a1,a2]`

is fully shadowed - If no part of
`[a1,a2]`

is visible, mark the cell as**not visible**and advance to next cell - If some part of
`[a1,a2]`

is visible, merge it into the shadow queue; mark the cell as**visible**

- Determine the corresponding arc

- Retrieve all cells whose range from