My Algorithm by Adam Milazzo in Dart

Dart Port of My Algorithm

This is a Dart port of My Algorithm by Adam Milazzo.

The advantages of this algorithm are discussed here:

http://www.adammil.net/blog/v125_Roguelike_Vision_Algorithms.html

Note

The original algorithm does not check for out-of-bounds errors. The implementation below corrects that by adding the parameter bool Function(int x, int y) isOutOfBounds.

Usage

// Helper function tests whether a coordinate is out-of-bounds.

bool isOutOfBounds(int x, int y) {
  if (x < 0 || x > width - 1 || y < 0 || y > height - 1) {
    return true;
  }
  return false;
}

// Helper function tests whether a coordinate is a visual obstacle.

bool isObstacle(int x, int y) => (getRoot(x, y).isTransparent() == false);

final visibility = MyVisibility(isObstacle, isOutOfBounds);

final Set<(int x, int y)> circle = visibility.circle(
  startTile.x,
  startTile.y,
  startRadius.toInt(),
);

for (final (x, y) in circle) {
  // ... do something
}

My Algorithm

import 'dart:math';

class MyVisibility {
  final List<(int x, int y)> _points = [];

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

  MyVisibility(bool Function(int x, int y) isObstacle, this._isOutOfBounds) {
    _isObstacle = (int x, int y) => _isOutOfBounds(x, y) || isObstacle(x, y);
  }

  /// 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.
  Set<(int x, int y)> circle(int x, int y, int radius,
      {isSymmetricView = false}) {
    final Point<int> origin = Point(x, y);

    _addVisiblePoint(origin.x, origin.y);

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

    return _points.where((p) => _isOutOfBounds(p.$1, p.$2) == false).toSet();
  }

  /// Add a point to the visibility list.
  _addVisiblePoint(int x, int y) =>
      // _isOutOfBounds(x, y) ? null :
      _points.add((x, y));

  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);
          }

          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) {
    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);
  }
}

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;
}