Calculate visibility / field of view / line of sight for tile based maps as often found in roguelike games, by Adam Milazzo.

myvisibility.dart

import 'dart:math';

/// This is a port to Dart of "My algorithm" by Adam Milazzo.
///
/// It calculates visibility / field of view / line of sight for tile
/// based maps as often found in roguelike games.
///
/// The advantages of this algorithm are discussed here:
///
/// http://www.adammil.net/blog/v125_Roguelike_Vision_Algorithms.html#code
///
/// Note
///
/// The algorithm requires a map surrounded by obstacles, this protects
/// against out-of-bounds exceptions. The function [isObstacle] has to return
/// false for the coordinates at the circumference of the map.
///
/// Usage
///
/// ```dart
/// bool isObstacle(int x, int y) {
///   final t = getTile(x, y);
///   return (t is MapTileWall || t is MapTileDoor);
/// }
///
/// final visibility = MyVisibility(isObstacle);
/// final circle = visibility.circle(
///   startTile.x,
///   startTile.y,
///   startDistance.toInt(),
/// );
///
/// for (final (x, y, isVisible) in circle) {
///   final endTile = getTile(x, y);
///
///   if (isVisible) {
///     // Show tiles in full view.
///   } else if (endTile.renderModifier == RenderModifier.fullrender) {
///     // Show tiles previously in full view but not anymore.
///     // Assign a different color like grey etc.
///   }
/// }
/// ```
class MyVisibility {
  final List<(int x, int y, bool isVisible)> _points = [];

  /// A function testing the visibility of a coordindate.
  final bool Function(int x, int y) _isObstacle;

  MyVisibility(this._isObstacle);

  /// Returns all coordinates within the circle defined by [x], [y] and the [radius].
  ///
  /// [isSymmetricView] turns on symmetry, which is important for symmetric
  /// Player-Monster visibility: Coordinate-A sees Coordinate-B and vice versa.
  ///
  /// The returned coordinates have a boolean indicator [isVisibale], which is useful
  /// for modfying tiles that had been fully visible previously but aren't anymore.
  List<(int x, int y, bool isVisible)> circle(int x, int y, int radius,
      {isSymmetricView = false}) {
    final Point<int> origin = Point(x, y);

    _addVisiblePoint(origin.x, origin.y, true);

    for (int octant = 0; octant < 8; octant++) {
      _compute(octant, origin, radius, 1, _Slope(1, 1), _Slope(0, 1),
          isSymmetricView);
    }

    return _points;
  }

  /// Add a point to the visibility list.
  _addVisiblePoint(int x, int y, bool isVisible) =>
      _points.add((x, y, isVisible));

  double _getDistance(int x, int y) => sqrt(x * x + y * y);

  void _compute(final int octant, final Point<int> origin, final int radius,
      int x, _Slope top, _Slope bottom, bool isSymmetricView) {
    for (; x <= radius; x++) {
      int topY;
      if (top.X == 1) {
        topY = x;
      } else {
        topY = ((x * 2 - 1) * top.Y + top.X) ~/ (top.X * 2);

        if (_blocksLight(x, topY, octant, origin)) {
          if (top.greaterOrEqual(topY * 2 + 1, x * 2) &&
              !_blocksLight(x, topY + 1, octant, origin)) topY++;
        } else {
          int ax = x * 2;

          if (_blocksLight(x + 1, topY + 1, octant, origin)) {
            ax++;
          }
          if (top.greater(topY * 2 + 1, ax)) {
            topY++;
          }
        }
      }

      int bottomY;
      if (bottom.Y == 0) {
        bottomY = 0;
      } else {
        bottomY = ((x * 2 - 1) * bottom.Y + bottom.X) ~/ (bottom.X * 2);

        if (bottom.greaterOrEqual(bottomY * 2 + 1, x * 2) &&
            _blocksLight(x, bottomY, octant, origin) &&
            !_blocksLight(x, bottomY + 1, octant, origin)) {
          bottomY++;
        }
      }

      int wasOpaque = -1;
      for (int y = topY; y >= bottomY; y--) {
        if (radius < 0 || _getDistance(x, y) <= radius) {
          bool isOpaque = _blocksLight(x, y, octant, origin);

          bool isVisible;

          if (isSymmetricView == false) {
            isVisible = isOpaque ||
                ((y != topY || top.greater(y * 4 - 1, x * 4 + 1)) &&
                    (y != bottomY || bottom.less(y * 4 + 1, x * 4 - 1)));
          } else {
            isVisible = ((y != topY || top.greaterOrEqual(y, x)) &&
                (y != bottomY || bottom.lessOrEqual(y, x)));
          }
          // if (isVisible) {
          _setVisible(x, y, octant, origin, isVisible);
          // }

          if (x != radius) {
            if (isOpaque) {
              if (wasOpaque == 0) {
                int nx = x * 2;
                int ny = y * 2 + 1;

                if (isSymmetricView == true) {
                  if (_blocksLight(x, y + 1, octant, origin)) {
                    nx--;
                  }
                }

                if (top.greater(ny, nx)) {
                  if (y == bottomY) {
                    bottom = _Slope(ny, nx);
                    break;
                  } else {
                    _compute(octant, origin, radius, x + 1, top, _Slope(ny, nx),
                        isSymmetricView);
                  }
                } else {
                  if (y == bottomY) {
                    return;
                  }
                }
              }
              wasOpaque = 1;
            } else {
              if (wasOpaque > 0) {
                int nx = x * 2;
                int ny = y * 2 + 1;

                if (isSymmetricView == true) {
                  if (_blocksLight(x + 1, y + 1, octant, origin)) {
                    nx++;
                  }
                }

                if (bottom.greaterOrEqual(ny, nx)) {
                  return;
                }
                top = _Slope(ny, nx);
              }
              wasOpaque = 0;
            }
          }
        }
      }

      if (wasOpaque != 0) {
        break;
      }
    }
  }

  bool _blocksLight(
      final int x, final int y, final int octant, final Point<int> origin) {
    int nx = origin.x;
    int ny = origin.y;
    switch (octant) {
      case 0:
        nx += x;
        ny -= y;
        break;
      case 1:
        nx += y;
        ny -= x;
        break;
      case 2:
        nx -= y;
        ny -= x;
        break;
      case 3:
        nx -= x;
        ny -= y;
        break;
      case 4:
        nx -= x;
        ny += y;
        break;
      case 5:
        nx -= y;
        ny += x;
        break;
      case 6:
        nx += y;
        ny += x;
        break;
      case 7:
        nx += x;
        ny += y;
        break;
    }
    return _isObstacle(nx, ny);
  }

  void _setVisible(final int x, final int y, int octant, Point<int> origin,
      final bool isVisible) {
    int nx = origin.x, ny = origin.y;
    switch (octant) {
      case 0:
        nx += x;
        ny -= y;
        break;
      case 1:
        nx += y;
        ny -= x;
        break;
      case 2:
        nx -= y;
        ny -= x;
        break;
      case 3:
        nx -= x;
        ny -= y;
        break;
      case 4:
        nx -= x;
        ny += y;
        break;
      case 5:
        nx -= y;
        ny += x;
        break;
      case 6:
        nx += y;
        ny += x;
        break;
      case 7:
        nx += x;
        ny += y;
        break;
    }
    _addVisiblePoint(nx, ny, isVisible);
  }
}

class _Slope {
  _Slope(this.Y, this.X);

  bool greater(int y, int x) {
    return Y * x > X * y;
  }

  bool greaterOrEqual(int y, int x) {
    return Y * x >= X * y;
  }

  bool less(int y, int x) {
    return Y * x < X * y;
  }

  bool lessOrEqual(int y, int x) {
    return Y * x <= X * y;
  }

  final int X, Y;
}