Precise Shadowcasting in JavaScript

From RogueBasin
(Difference between revisions)
Jump to: navigation, search
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 ===
 
=== Half-angle backward shift ===
 
  
 
=== Working with shadow queue ===
 
=== Working with shadow queue ===

Revision as of 09: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

  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

Advanced topics: tricks and tweaks

Half-angle backward shift

Cutoff and angle wrapping

Symbolic angles

Working with shadow queue

Links

Personal tools