Skinny Wall Recursive Shadowcasting

skinnyfov

import { AdjTypes } from "./Map";
import { gameData } from "../GameManager";

const isOpen = (adj: AdjTypes) => {
  return adj !== AdjTypes.WALL;
};

/** Octants used for translating recursive shadowcasting offsets */
const OCTANTS = [
  [-1, 0, 0, 1], //2 R->L (B->T) oy -1 -1 ** yy | iy 0
  [0, -1, 1, 0], //3 T->B (L->R) oy 0 | iy 1 yx
  [0, -1, -1, 0], //4 B->T (L->R) oy 0 | iy yx
  [-1, 0, 0, -1], //5 R->L (T->B) oy 1 -1 ** yy | iy 0
  [1, 0, 0, -1], //6 L->R (T->B)  oy -1 * yy | iy 0
  [0, 1, -1, 0], //7 B->T (R->L)  oy 0 | iy -1 yx
  [0, 1, 1, 0], //8 T->B (R->L)
  [1, 0, 0, 1], //1 L->R (B->T)
];

//dx -> axis of row clear
//dy -> axis of row transition
//[0] == xx = x difference for "row"/inner scan
//[1] == xy = -1 * x difference for outer scan
//[2] == yx = y diff for "row"/inner scan
//[3] == yy = -1 * y diff for "col"/outer scan
//const mapX = startX + dx * xx + dy * xy;
//const mapY = startY + dx * yx + dy * yy;

type RVisiblity = (x: number, y: number, R: number, visible: number) => void;
type RLightPasses = (
  x: number,
  y: number,
  xx: number,
  xy: number,
  yx: number,
  yy: number
) => boolean;
/**
 * @class Recursive shadowcasting algorithm
 * Currently only supports 4/8 topologies, not hexagonal.
 * Based on Peter Harkins' implementation of Björn Bergström's algorithm described here: http://www.roguebasin.com/index.php?title=FOV_using_recursive_shadowcasting
 * @augments ROT.FOV
 */
export class SkinnyRecursiveShadowcasting {
  _lightCasts: RLightPasses;
  _lightPasses: RLightPasses;

  constructor(
    lightCastsCallback: RLightPasses,
    lightPassesCallback: RLightPasses
  ) {
    this._lightCasts = lightCastsCallback;
    this._lightPasses = lightPassesCallback;
  }

  /**
   * Compute visibility for a 360-degree circle
   * @param {int} x
   * @param {int} y
   * @param {int} R Maximum visibility radius
   * @param {function} callback
   */
  compute(x: number, y: number, R: number, callback: RVisiblity) {
    //You can always see your own tile
    callback(x, y, 0, 1);
    for (let i = 0; i < OCTANTS.length; i++) {
      this._renderOctant(x, y, OCTANTS[i], R, callback);
    }
  }

  /**
   * Compute visibility for a 180-degree arc
   * @param {int} x
   * @param {int} y
   * @param {int} R Maximum visibility radius
   * @param {int} dir Direction to look in (expressed in a ROT.DIRS value);
   * @param {function} callback
   */
  compute180(
    x: number,
    y: number,
    R: number,
    dir: number,
    callback: RVisiblity
  ) {
    //You can always see your own tile
    callback(x, y, 0, 1);
    const previousOctant = (dir - 1 + 8) % 8; //Need to retrieve the previous octant to render a full 180 degrees
    const nextPreviousOctant = (dir - 2 + 8) % 8; //Need to retrieve the previous two octants to render a full 180 degrees
    const nextOctant = (dir + 1 + 8) % 8; //Need to grab to next octant to render a full 180 degrees
    this._renderOctant(x, y, OCTANTS[nextPreviousOctant], R, callback);
    this._renderOctant(x, y, OCTANTS[previousOctant], R, callback);
    this._renderOctant(x, y, OCTANTS[dir], R, callback);
    this._renderOctant(x, y, OCTANTS[nextOctant], R, callback);
  }

  /**
   * Compute visibility for a 90-degree arc
   * @param {int} x
   * @param {int} y
   * @param {int} R Maximum visibility radius
   * @param {int} dir Direction to look in (expressed in a ROT.DIRS value);
   * @param {function} callback
   */
  compute90(
    x: number,
    y: number,
    R: number,
    dir: number,
    callback: RVisiblity
  ) {
    //You can always see your own tile
    callback(x, y, 0, 1);
    const previousOctant = (dir - 1 + 8) % 8; //Need to retrieve the previous octant to render a full 90 degrees
    this._renderOctant(x, y, OCTANTS[dir], R, callback);
    this._renderOctant(x, y, OCTANTS[previousOctant], R, callback);
  }

  /**
   * Render one octant (45-degree arc) of the viewshed
   * @param {int} x
   * @param {int} y
   * @param {int} octant Octant to be rendered
   * @param {int} R Maximum visibility radius
   * @param {function} callback
   */
  _renderOctant(
    x: number,
    y: number,
    octant: number[],
    R: number,
    callback: RVisiblity
  ) {
    if (
      this._lightPasses(
        x,
        y,
        octant[0],
        -1 * octant[1],
        octant[2],
        -1 * octant[3]
      )
    ) {
      //Radius incremented by 1 to provide same coverage area as other shadowcasting radiuses
      this._castVisibility(
        x,
        y,
        1,
        1.0,
        0.0,
        R + 1,
        octant[0],
        octant[1],
        octant[2],
        octant[3],
        callback
      );
    }
  }

  /**
   * Actually calculates the visibility
   * @param {int} startX The starting X coordinate
   * @param {int} startY The starting Y coordinate
   * @param {int} row The row to render
   * @param {float} visSlopeStart The slope to start at
   * @param {float} visSlopeEnd The slope to end at
   * @param {int} radius The radius to reach out to
   * @param {int} xx
   * @param {int} xy
   * @param {int} yx
   * @param {int} yy
   * @param {function} callback The callback to use when we hit a block that is visible
   */
  _castVisibility(
    startX: number,
    startY: number,
    row: number,
    visSlopeStart: number,
    visSlopeEnd: number,
    radius: number,
    xx: number,
    xy: number,
    yx: number,
    yy: number,
    callback: RVisiblity
  ) {
    if (visSlopeStart < visSlopeEnd) {
      return;
    }
    for (let i = row; i <= radius; i++) {
      let dx = -i - 1;
      const dy = -i;
      let blocked = false;
      let newStart = 0;

      //'Row' could be column, names here assume octant 0 and would be flipped for half the octants
      while (dx <= 0) {
        dx += 1;

        //Translate from relative coordinates to map coordinates
        const mapX = startX + dx * xx + dy * xy;
        const mapY = startY + dx * yx + dy * yy;

        //Range of the row
        const slopeStart = (dx - 0.5) / (dy + 0.5);
        const slopeEnd = (dx + 0.5) / (dy - 0.5);

        //Ignore if not yet at left edge of Octant
        if (slopeEnd > visSlopeStart) {
          continue;
        }

        //Done if past right edge
        if (slopeStart < visSlopeEnd) {
          break;
        }

        const casts = this._lightCasts(mapX, mapY, xx, -1 * xy, yx, -1 * yy);
        //If it's in range, it's visible
        if (dx * dx + dy * dy < radius * radius && (casts || dx === 0)) {
          //&& this._lightHits(mapX, mapY, xx, xy, yx, yy)) {
          callback(mapX, mapY, i, 1);
        }

        if (!blocked) {
          //If tile is a blocking tile, cast around it
          const passes =
            this._lightPasses(mapX, mapY, xx, -1 * xy, yx, -1 * yy) &&
            i < radius;
          if (!passes) {
            this._castVisibility(
              startX,
              startY,
              i + 1,
              visSlopeStart,
              slopeStart,
              radius,
              xx,
              xy,
              yx,
              yy,
              callback
            );
            newStart = slopeEnd;
            blocked = true;
          } else if (!casts && dx < 0) {
            this._castVisibility(
              startX,
              startY,
              i + 1,
              visSlopeStart,
              slopeStart,
              radius,
              xx,
              xy,
              yx,
              yy,
              callback
            );
            newStart = slopeEnd;
            blocked = true;
          }
        } else {
          //Keep narrowing if scanning across a block
          if (!this._lightPasses(mapX, mapY, xx, -1 * xy, yx, -1 * yy)) {
            newStart = slopeEnd;
            continue;
          }

          //Block has ended
          blocked = false;
          visSlopeStart = newStart;
        }
      }
      if (blocked) {
        break;
      }
    }
  }
}

export const PlayerVisibility = new SkinnyRecursiveShadowcasting(
  (x, y, innerX, outerX, innerY, outerY) => {
    //  [0, -1, 1, 0], //3 T->B (L->R)
    //[0, -1, -1, 0], //4 B->T (L->R)
    const map = gameData.current;
    if (0 <= x && x < map.width && 0 <= y && y < map.height) {
      if (innerX === -1) {
        return map.tiles[x + y * map.width].adj.left !== AdjTypes.WALL;
      } else if (innerX === 1) {
        return map.tiles[x + y * map.width].adj.right !== AdjTypes.WALL;
      }

      if (innerY === -1) {
        return map.tiles[x + y * map.width].adj.up !== AdjTypes.WALL;
      } else if (innerY === 1) {
        return map.tiles[x + y * map.width].adj.down !== AdjTypes.WALL;
      }
    }
    return false;
  },
  (x, y, innerX, outerX, innerY, outerY) => {
    const map = gameData.current;
    if (0 <= x && x < map.width && 0 <= y && y < map.height) {
      if (outerX === -1) {
        return map.tiles[x + y * map.width].adj.left !== AdjTypes.WALL;
      } else if (outerX === 1) {
        return map.tiles[x + y * map.width].adj.right !== AdjTypes.WALL;
      }

      if (outerY === -1) {
        return map.tiles[x + y * map.width].adj.up !== AdjTypes.WALL;
      } else if (outerY === 1) {
        return map.tiles[x + y * map.width].adj.down !== AdjTypes.WALL;
      }
    }

    return false;
  }
);

export const getPlayerVisibility = (
  width: number,
  x: number,
  y: number,
  range: number,
  result = new Map<number, boolean>()
) => {
  result.clear();
  PlayerVisibility.compute(x, y, range, (x, y, _, visible) => {
    if (visible) {
      result.set(x + y * width, true);
    }
  });
  /**result.set(gameData.player.x + gameData.player.y * width, true);
  PlayerVisibility._renderOctant(
    x,
    y,
    OCTANTS[7],
    range,
    (x, y, _, visible) => {
      if (visible) {
        result.set(x + y * width, true);
      }
    }
  );**/
};