My Algorithm by Adam Milazzo in Dart
(Redirected from My Algorithm by Adam Milazzo)
Jump to navigation
Jump to search
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;
}