DiscreteShadowcasting.js

/**
* "Nulls" cells of the given lightmaps that aren't visible
* because light is blocked.
*
* Code is based on:
* http://code.google.com/p/js-like/wiki/DiscreteShadowcasting
*/
_applyShadows = function(posX, posY, lightCaster, lightMap) {
  var self = this;

  /**
   * Retrieves the arc from the center of the cell
   * defined by x1/y1 to the square on cell x2/y2.
   *
   * Sample & Illustration
   *  |2|  Point 1 is the origin
   * -+-+- Point 2 is the cell we need an arc for
   *  |1|  The function returns  [-45,45], as an arc
   * -+-+  using these angles would fully contain cell 2
   *  | |
   */
  var getArc = function(x1, y1, x2, y2) {
    // If both points are identical, the light caster
    // can't see anything
    if (x1 === x2 && y1 === y2) {
      return ([0, 360])
    }

    // Shift position to center of cell
    x1 += 0.5;
    y1 += 0.5;

    // All extremal points of the square 
    // defining the target point.
    var extremalPoints = [[x2 + 0, y2 + 0],
                          [x2 + 1, y2 + 0],
                          [x2 + 1, y2 + 1],
                          [x2 + 0, y2 + 1]];
    // Minimum and maximum angle
    var angles = []

    // Iterate over all extremal points and calculate their
    // angles.
    for (var i = 0; i < extremalPoints.length; ++i) {
      var angle = Math.atan2((x1 - extremalPoints[i][0]),
                             (y1 - extremalPoints[i][1]));

      // Convert to degrees and scale to interval [0, 360]
      var angle = angle * (180 / Math.PI) + 180;
      angles.push(angle);
    }

    // Build all non-reflexive angle pairs to find the maximum  internal angle.
    var pairs = [];
    for (var i = 0; i < angles.length; ++i) {
      for (var j = 0; j < angles.length; ++j) {
        if (i === j) {
          continue;
        }

        var left = angles[i];
        var right = angles[j];
        var internalAngle = Math.abs(right - left);

        if (internalAngle > 180) {
          internalAngle = 360 - internalAngle;
        }

        pairs.push([left, right, internalAngle]);
      }
    }

    // Find the maximum pair
    var maxPair = pairs[0];
    for (var i = 1; i < pairs.length; ++i) {
      if (pairs[i][2] > maxPair[2]) {
        maxPair = pairs[i];
      }
    }

    // We need an ordering that guarantees the pairs we return
    // are sorted clockwise, beginning at 0.
    if (maxPair[1] + maxPair[0] >= 360) {
      return ([maxPair[0], maxPair[1]]);
    } else {
      return ([maxPair[1], maxPair[0]]);
    }
    
  };

  /**
   * Exentds the given list of shadow arcs with the new
   * shadow arc, if its not fully contained inside the
   * existing shadow arcs.
   *
   * Shadow list examples:
   *   [] - empty shadow array, no arcs are occluded.
   *   [15, 45] - there is an occluded arc between 15 and 45 degrees; 
   *              cells within these angles cannot be seen.
   *   [15, 60, 120, 200] - there are two occluded arcs; 
   *                        one is 15-60 degrees, second is 120-200 degrees.
   *   [0, 360] - nothing can be seen, all angles are occluded, algorithm stops. 
   *
   */
  var addToShadowArcs = function(currentShadowArcs, newArc) {

  }

  /**
   * Returns true, if the given arc is contained in the given
   * list of shadow arcs.
   */
  var isInShadowArray = function(currentShadowArcs, arc) {

  }

  // Finds out width and height of the given lightmap
  var height = lightMap.length;
  var width = lightMap[0].length;
  
  // Finds out the radius, note that for this to work,
  // the lightmaps MUST be of odd size and height.
  var radiusHeight = (height - 1) / 2;
  var radiusWidth = (width - 1) / 2;

  var currentShadowArcs = [];

  // TODO: Begin iteration from center
  // Iterate over all cells to check whether they need
  // to be occluded
  var xIndex = 0;
  var yIndex = 0;
  for (var x = posX - radiusWidth; x <= posX + radiusWidth; ++x) {        
    for (var y = posY - radiusHeight; y <= posY + radiusHeight; ++y) {
      // Compute relevant values for the current cell
      var arc = getArc(posX, posY, x, y)

      // If the cell is already blocked, set its
      // light value to 0
      if (isInShadowArray(currentShadowArcs, arc)) {
        lightMap[yIndex][xIndex] = 0;
      }

      // If the cell blocks light, extend the shadow arc list
      if (self.isCellLightBlocker(x, y)) {
        addToShadowArcs(currentShadowArcs, arc);
      }
      
      ++yIndex;
    }
    ++xIndex;
    yIndex = 0;
  }
}