# My Algorithm by Adam Milazzo in Dart

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

## Dart Port of My Algorithm

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

The advantages of this algorithm are discussed here:

### 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,
);

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

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.
// _isOutOfBounds(x, y) ? null :

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

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