aboutsummaryrefslogtreecommitdiff
path: root/engines/bladerunner/obstacles.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'engines/bladerunner/obstacles.cpp')
-rw-r--r--engines/bladerunner/obstacles.cpp454
1 files changed, 441 insertions, 13 deletions
diff --git a/engines/bladerunner/obstacles.cpp b/engines/bladerunner/obstacles.cpp
index 69d1ba47c3..b8fc1f16fa 100644
--- a/engines/bladerunner/obstacles.cpp
+++ b/engines/bladerunner/obstacles.cpp
@@ -25,6 +25,12 @@
#include "bladerunner/bladerunner.h"
#include "bladerunner/savefile.h"
+#include "bladerunner/scene.h" // for debug
+#include "bladerunner/view.h"
+
+#include "common/debug.h"
+
+#define WITHIN_TOLERANCE(a, b) (((a) - 0.009) < (b) && ((a) + 0.009) > (b))
namespace BladeRunner {
@@ -37,9 +43,16 @@ Obstacles::Obstacles(BladeRunnerEngine *vm) {
}
Obstacles::~Obstacles() {
- delete[] _vertices;
- delete[] _polygonsBackup;
+ clear();
+
delete[] _polygons;
+ _polygons = nullptr;
+
+ delete[] _polygonsBackup;
+ _polygonsBackup = nullptr;
+
+ delete[] _vertices;
+ _vertices = nullptr;
}
void Obstacles::clear() {
@@ -56,7 +69,250 @@ void Obstacles::clear() {
_count = 0;
}
-void Obstacles::add(float x0, float z0, float x1, float z1) {
+#define IN_RANGE(v, start, end) ((start) <= (v) && (v) <= (end))
+
+/*
+ * This function is limited to finding intersections between
+ * horizontal and vertical lines!
+ *
+ * The original implementation is more general but obstacle
+ * polygons only consists of horizontal and vertical lines,
+ * and this is more numerically stable.
+ */
+bool Obstacles::lineLineIntersection(LineSegment a, LineSegment b, Vector2 *intersection) {
+ assert(a.start.x == a.end.x || a.start.y == a.end.y);
+ assert(b.start.x == b.end.x || b.start.y == b.end.y);
+
+ if (a.start.x > a.end.x) SWAP(a.start.x, a.end.x);
+ if (a.start.y > a.end.y) SWAP(a.start.y, a.end.y);
+ if (b.start.x > b.end.x) SWAP(b.start.x, b.end.x);
+ if (b.start.y > b.end.y) SWAP(b.start.y, b.end.y);
+
+ if (a.start.x == a.end.x && b.start.y == b.end.y && IN_RANGE(a.start.x, b.start.x, b.end.x) && IN_RANGE(b.start.y, a.start.y, a.end.y)) {
+ // A is vertical, B is horizontal
+ *intersection = Vector2 { a.start.x, b.start.y };
+ return true;
+ }
+
+ if (a.start.y == a.end.y && b.start.x == b.end.x && IN_RANGE(a.start.y, b.start.y, b.end.y) && IN_RANGE(b.start.x, a.start.x, a.end.x)) {
+ // A is horizontal, B is vertical
+ *intersection = Vector2 { b.start.x, a.start.y };
+ return true;
+ }
+
+ return false;
+}
+
+bool Obstacles::linePolygonIntersection(LineSegment lineA, VertexType lineAType, Polygon *polyB, Vector2 *intersectionPoint, int *intersectionIndex) {
+ bool hasIntersection = false;
+ float nearestIntersectionDistance = 0.0f;
+
+ for (int i = 0; i != polyB->verticeCount; ++i) {
+ LineSegment lineB;
+ lineB.start = polyB->vertices[i];
+ lineB.end = polyB->vertices[(i+1) % polyB->verticeCount];
+
+ VertexType lineBType = polyB->vertexType[i];
+
+ Vector2 newIntersectionPoint;
+
+ if (lineLineIntersection(lineA, lineB, &newIntersectionPoint)) {
+ if (lineAType == TOP_RIGHT && lineBType == TOP_LEFT
+ || lineAType == BOTTOM_RIGHT && lineBType == TOP_RIGHT
+ || lineAType == BOTTOM_LEFT && lineBType == BOTTOM_RIGHT
+ || lineAType == TOP_LEFT && lineBType == BOTTOM_LEFT
+ ) {
+ if (!WITHIN_TOLERANCE(lineB.end.x, intersectionPoint->x)
+ || !WITHIN_TOLERANCE(lineB.end.y, intersectionPoint->y)) {
+ if (newIntersectionPoint != *intersectionPoint) {
+ float newIntersectionDistance = getLength(lineA.start.x, lineA.start.y, newIntersectionPoint.x, newIntersectionPoint.y);
+ if (!hasIntersection || newIntersectionDistance < nearestIntersectionDistance) {
+ hasIntersection = true;
+ nearestIntersectionDistance = newIntersectionDistance;
+ *intersectionPoint = newIntersectionPoint;
+ *intersectionIndex = i;
+ }
+ }
+ }
+ }
+ }
+ }
+
+ return hasIntersection;
+}
+
+/*
+ * Polygons vertices are defined in clock-wise order
+ * starting at the top-most, right-most corner.
+ *
+ * When merging two polygons, we start at the top-most, right-most vertex.
+ * The polygon with this vertex starts is the primary polygon.
+ * We follow the edges until we find an intersection with the secondary polygon,
+ * in which case we switch primary and secondary and continue following the new edges.
+ *
+ * Luckily the first two polygons added in RC01 (A, then B) are laid as as below,
+ * making an ideal test case.
+ *
+ * Merge order: (B0,B1) (B1,B2) (B2,J) (J,A2) (A2,A3) (A3,A0) (A0,I) (I,B0)
+ *
+ * 0,0 ---> x
+ * |
+ * | primary
+ * | B 0 ----- 1
+ * | | |
+ * | A 0 --I-- 1 |
+ * | | | | |
+ * | | 3 --J-- 2
+ * | | |
+ * | 3 ----- 2
+ * | secondary
+ * v y
+ */
+
+bool Obstacles::mergePolygons(Polygon &polyA, Polygon &polyB) {
+ bool flagDidMergePolygons = false;
+ Polygon polyMerged;
+ polyMerged.rect = merge(polyA.rect, polyB.rect);
+
+ Polygon *polyPrimary, *polySecondary;
+ if (polyA.rect.y0 < polyB.rect.y0 || (polyA.rect.y0 == polyB.rect.y0 && polyA.rect.x0 < polyB.rect.x0)) {
+ polyPrimary = &polyA;
+ polySecondary = &polyB;
+ } else {
+ polyPrimary = &polyB;
+ polySecondary = &polyA;
+ }
+
+ Vector2 intersectionPoint;
+ LineSegment polyLine;
+ bool flagAddVertexToVertexList = true;
+ bool flagDidFindIntersection = false;
+ int vertIndex = 0;
+
+ Polygon *startingPolygon = polyPrimary;
+ int flagDone = false;
+ while (!flagDone) {
+ VertexType polyPrimaryType;
+
+ polyLine.start = flagDidFindIntersection ? intersectionPoint : polyPrimary->vertices[vertIndex];
+ polyLine.end = polyPrimary->vertices[(vertIndex + 1) % polyPrimary->verticeCount];
+
+ // TODO(madmoose): How does this work when adding a new intersection point?
+ polyPrimaryType = polyPrimary->vertexType[vertIndex];
+
+ if (flagAddVertexToVertexList) {
+ assert(polyMerged.verticeCount < kPolygonVertexCount);
+ polyMerged.vertices[polyMerged.verticeCount] = polyLine.start;
+ polyMerged.vertexType[polyMerged.verticeCount] = polyPrimaryType;
+ polyMerged.verticeCount++;
+ }
+
+ flagAddVertexToVertexList = true;
+ int polySecondaryIntersectionIndex = -1;
+
+ if (linePolygonIntersection(polyLine, polyPrimaryType, polySecondary, &intersectionPoint, &polySecondaryIntersectionIndex)) {
+ if (WITHIN_TOLERANCE(intersectionPoint.x, polyLine.start.x) && WITHIN_TOLERANCE(intersectionPoint.y, polyLine.start.y)) {
+ warning("Set: %d Scene: %d", _vm->_scene->getSetId(), _vm->_scene->getSceneId());
+ assert(0 && "Report instances of this to madmoose!");
+ flagAddVertexToVertexList = false;
+ polyMerged.verticeCount--; // TODO(madmoose): How would this work?
+ } else {
+ // Obstacles::nop
+ }
+ vertIndex = polySecondaryIntersectionIndex;
+ flagDidFindIntersection = true;
+
+ SWAP(polyPrimary, polySecondary);
+
+ flagDidMergePolygons = true;
+ } else {
+ vertIndex = (vertIndex + 1) % polyPrimary->verticeCount;
+ flagDidFindIntersection = false;
+ }
+ if (polyPrimary->vertices[vertIndex] == startingPolygon->vertices[0]) {
+ flagDone = true;
+ }
+ }
+
+ if (flagDidMergePolygons) {
+ *startingPolygon = polyMerged;
+ startingPolygon->isPresent = true;
+ if (startingPolygon == &polyA) {
+ polyB.isPresent = false;
+ } else {
+ polyA.isPresent = false;
+ }
+ }
+
+ return flagDidMergePolygons;
+}
+
+void Obstacles::add(Rect rect) {
+ int polygonIndex = findEmptyPolygon();
+ if (polygonIndex < 0) {
+ return;
+ }
+
+ rect.expand(12.0f);
+ rect.trunc_2_decimals();
+
+ Polygon &poly = _polygons[polygonIndex];
+
+ poly.rect = rect;
+
+ poly.vertices[0] = Vector2(rect.x0, rect.y0);
+ poly.vertexType[0] = TOP_LEFT;
+
+ poly.vertices[1] = Vector2(rect.x1, rect.y0);
+ poly.vertexType[1] = TOP_RIGHT;
+
+ poly.vertices[2] = Vector2(rect.x1, rect.y1);
+ poly.vertexType[2] = BOTTOM_RIGHT;
+
+ poly.vertices[3] = Vector2(rect.x0, rect.y1);
+ poly.vertexType[3] = BOTTOM_LEFT;
+
+ poly.isPresent = true;
+ poly.verticeCount = 4;
+
+restart:
+ for (int i = 0; i < kPolygonCount; ++i) {
+ Polygon &polyA = _polygons[i];
+ if (!polyA.isPresent) {
+ continue;
+ }
+
+ for (int j = i+1; j < kPolygonCount; ++j) {
+ Polygon &polyB = _polygons[j];
+ if (!polyB.isPresent) {
+ continue;
+ }
+
+ if (!overlaps(polyA.rect, polyB.rect)) {
+ continue;
+ }
+
+ if (mergePolygons(polyA, polyB)) {
+ goto restart;
+ }
+ }
+ }
+}
+
+int Obstacles::findEmptyPolygon() const {
+ for (int i = 0; i < kPolygonCount; i++) {
+ if (!_polygons[i].isPresent) {
+ return i;
+ }
+ }
+ return -1;
+}
+
+float Obstacles::getLength(float x0, float z0, float x1, float z1) {
+ if (x0 == x1) {
+ return fabs(z1 - z0);
+ }
+ return fabs(x1 - x0);
}
bool Obstacles::find(const Vector3 &from, const Vector3 &to, Vector3 *next) const {
@@ -65,10 +321,157 @@ bool Obstacles::find(const Vector3 &from, const Vector3 &to, Vector3 *next) cons
return true;
}
+bool Obstacles::findIntersectionNearest(int polygonIndex, Vector2 from, Vector2 to,
+ int *outVertexIndex, float *outDistance, Vector2 *out) const
+{
+ float minDistance = 0.0f;
+ Vector2 minIntersection;
+ int minVertexIndex = -1;
+
+ bool hasDistance = false;
+
+ for (int i = 0; i < _polygons[polygonIndex].verticeCount; ++i) {
+ int nextIndex = (i + 1) % _polygons[polygonIndex].verticeCount;
+ Vector2 *vertices = _polygons[polygonIndex].vertices;
+ Vector2 intersection;
+ bool intersects = lineIntersection(from, to, vertices[i], vertices[nextIndex], &intersection);
+ if (intersects) {
+ float distance2 = distance(from, intersection);
+ if (!hasDistance || distance2 < minDistance) {
+ minDistance = distance2;
+ minIntersection = intersection;
+ minVertexIndex = i;
+ hasDistance = true;
+ }
+ }
+ }
+
+ *outDistance = minDistance;
+ *outVertexIndex = minVertexIndex;
+ *out = minIntersection;
+
+ return minVertexIndex != -1;
+}
+
+bool Obstacles::findIntersectionFarthest(int polygonIndex, Vector2 from, Vector2 to,
+ int *outVertexIndex, float *outDistance, Vector2 *out) const
+{
+ float maxDistance = 0.0f;
+ Vector2 maxIntersection;
+ int maxVertexIndex = -1;
+
+ bool hasDistance = false;
+
+ for (int i = 0; i < _polygons[polygonIndex].verticeCount; ++i) {
+ int nextIndex = (i + 1) % _polygons[polygonIndex].verticeCount;
+ Vector2 *vertices = _polygons[polygonIndex].vertices;
+ Vector2 intersection;
+ bool intersects = lineIntersection(from, to, vertices[i], vertices[nextIndex], &intersection);
+ if (intersects) {
+ float distance2 = distance(from, intersection);
+ if (!hasDistance || distance2 > maxDistance) {
+ maxDistance = distance2;
+ maxIntersection = intersection;
+ maxVertexIndex = i;
+ hasDistance = true;
+ }
+ }
+ }
+
+ *outDistance = maxDistance;
+ *outVertexIndex = maxVertexIndex;
+ *out = maxIntersection;
+
+ return maxVertexIndex != -1;
+}
+
+bool Obstacles::findPolygonVerticeByXZ(int *polygonIndex, int *verticeIndex, int *verticeCount, float x, float z) const {
+ *polygonIndex = -1;
+ *verticeIndex = -1;
+ *verticeCount = -1;
+
+ for (int i = 0; i != kPolygonCount; ++i) {
+ if (!_polygons[i].isPresent || _polygons[i].verticeCount == 0) {
+ continue;
+ }
+
+ for (int j = 0; j != kPolygonVertexCount; ++j) {
+ if (_polygons[i].vertices[j].x == x && _polygons[i].vertices[j].y == z) {
+ *polygonIndex = i;
+ *verticeIndex = j;
+ *verticeCount = _polygons[i].verticeCount;
+ return true;
+ }
+ }
+ }
+
+ return false;
+}
+
+bool Obstacles::findPolygonVerticeByXZWithinTolerance(float x, float z, int *polygonIndex, int *verticeIndex) const {
+ *polygonIndex = -1;
+ *verticeIndex = -1;
+
+ for (int i = 0; i != kPolygonCount; ++i) {
+ if (!_polygons[i].isPresent || _polygons[i].verticeCount == 0) {
+ continue;
+ }
+
+ for (int j = 0; j != kPolygonVertexCount; ++j) {
+ if (WITHIN_TOLERANCE(_polygons[i].vertices[j].x, x)) {
+ if (WITHIN_TOLERANCE(_polygons[i].vertices[j].y, z)) {
+ *polygonIndex = i;
+ *verticeIndex = j;
+ return true;
+ }
+ }
+ }
+ }
+
+ return false;
+}
+
+void Obstacles::clearVertices() {
+ _verticeCount = 0;
+}
+
+void Obstacles::copyVerticesReverse() {
+
+}
+
+void Obstacles::copyVertices() {
+
+}
+
void Obstacles::backup() {
+ for (int i = 0; i != kPolygonCount; ++i) {
+ _polygonsBackup[i].isPresent = false;
+ }
+
+ int count = 0;
+ for (int i = 0; i != kPolygonCount; ++i) {
+ if (_polygons[i].isPresent) {
+ _polygonsBackup[count] = _polygons[i];
+ ++count;
+ }
+ }
+
+ for (int i = 0; i != kPolygonCount; ++i) {
+ _polygons[i] = _polygonsBackup[count];
+ }
+
+ _count = count;
+ _backup = true;
}
-void Obstacles::restore() {}
+void Obstacles::restore() {
+ for (int i = 0; i != kPolygonCount; ++i) {
+ _polygons[i].isPresent = false;
+ }
+ for (int i = 0; i != kPolygonCount; ++i) {
+ _polygons[i] = _polygonsBackup[i];
+ }
+}
void Obstacles::save(SaveFileWriteStream &f) {
f.writeBool(_backup);
@@ -77,10 +480,10 @@ void Obstacles::save(SaveFileWriteStream &f) {
Polygon &p = _polygonsBackup[i];
f.writeBool(p.isPresent);
f.writeInt(p.verticeCount);
- f.writeFloat(p.left);
- f.writeFloat(p.bottom);
- f.writeFloat(p.right);
- f.writeFloat(p.top);
+ f.writeFloat(p.rect.x0);
+ f.writeFloat(p.rect.y0);
+ f.writeFloat(p.rect.x1);
+ f.writeFloat(p.rect.y1);
for (int j = 0; j < kPolygonVertexCount; ++j) {
f.writeVector2(p.vertices[j]);
}
@@ -108,15 +511,15 @@ void Obstacles::load(SaveFileReadStream &f) {
Polygon &p = _polygonsBackup[i];
p.isPresent = f.readBool();
p.verticeCount = f.readInt();
- p.left = f.readFloat();
- p.bottom = f.readFloat();
- p.right = f.readFloat();
- p.top = f.readFloat();
+ p.rect.x0 = f.readFloat();
+ p.rect.y0 = f.readFloat();
+ p.rect.x1 = f.readFloat();
+ p.rect.y1 = f.readFloat();
for (int j = 0; j < kPolygonVertexCount; ++j) {
p.vertices[j] = f.readVector2();
}
for (int j = 0; j < kPolygonVertexCount; ++j) {
- p.vertexType[j] = f.readInt();
+ p.vertexType[j] = (VertexType)f.readInt();
}
}
@@ -130,5 +533,30 @@ void Obstacles::load(SaveFileReadStream &f) {
_verticeCount = f.readInt();
}
+void Obstacles::draw() {
+ for (int i = 0; i != kPolygonCount; ++i) {
+ if (!_polygons[i].isPresent) {
+ continue;
+ }
+
+ Vector3 p0 = _vm->_view->calculateScreenPosition(Vector3(
+ _polygons[i].vertices[_polygons[i].verticeCount - 1].x,
+ 0,
+ _polygons[i].vertices[_polygons[i].verticeCount - 1].y
+ ));
+
+ for (int j = 0; j != _polygons[i].verticeCount; ++j) {
+ Vector3 p1 = _vm->_view->calculateScreenPosition(Vector3(
+ _polygons[i].vertices[j].x,
+ 0.0f,
+ _polygons[i].vertices[j].y
+ ));
+
+ _vm->_surfaceFront.drawLine(p0.x, p0.y, p1.x, p1.y, 0x7FE0);
+
+ p0 = p1;
+ }
+ }
+}
} // End of namespace BladeRunner
generated by cgit v1.2.3 (git 2.25.1) at 2024-08-22 06:07:35 +0000