Precise Shadowcasting in JavaScript

From RogueBasin
Revision as of 15:25, 3 January 2013 by Ondras (talk | contribs)
Jump to navigation Jump to search

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

WORK IN PROGRESS

About

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 invisible 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

Tweaks, tricks and advanced topics

Symbolic angles

Half-angle backward shift

Working with shadow queue