mirror of
https://github.com/scummvm/scummvm.git
synced 2025-04-02 10:52:32 -04:00
f48703b090
Some merged polygons for obstacles would get duplicate vertices This could result in bad pathfinding and actors being stuck while walking to their destinations. A soft lock could occur, for example in RC02, with Runciter walking to his desk to get the camera disc, if he started at a point like -15.78f, -1238.894287f, 108432.14f (ie. Actor_Set_At_XYZ(kActorRunciter, -15.78f, -1238.894287f, 108432.14f, Actor_Query_Facing_1024(kActorRunciter));) Same could happen to the player's actor, but in Runciter's case from the above example, the player loses control until Runciter gets the disc and gives it to McCoy, but since Runctiter never reaches the waypoint to get the disc, the game is soft locked. This will not automatically fix a scene's obstacles loaded from an old saved game. For those cases, the player will have to exit the scene and re-enter for the obstacles to be properly recalculated.
1017 lines
32 KiB
C++
1017 lines
32 KiB
C++
/* ScummVM - Graphic Adventure Engine
|
|
*
|
|
* ScummVM is the legal property of its developers, whose names
|
|
* are too numerous to list here. Please refer to the COPYRIGHT
|
|
* file distributed with this source distribution.
|
|
*
|
|
* This program is free software: you can redistribute it and/or modify
|
|
* it under the terms of the GNU General Public License as published by
|
|
* the Free Software Foundation, either version 3 of the License, or
|
|
* (at your option) any later version.
|
|
*
|
|
* This program is distributed in the hope that it will be useful,
|
|
* but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
* GNU General Public License for more details.
|
|
*
|
|
* You should have received a copy of the GNU General Public License
|
|
* along with this program. If not, see <http://www.gnu.org/licenses/>.
|
|
*
|
|
*/
|
|
|
|
#include "bladerunner/obstacles.h"
|
|
|
|
#include "bladerunner/bladerunner.h"
|
|
|
|
#include "bladerunner/actor.h"
|
|
#include "bladerunner/savefile.h"
|
|
#include "bladerunner/scene.h" // for debug
|
|
#include "bladerunner/set.h"
|
|
#include "bladerunner/view.h"
|
|
|
|
#include "common/debug.h"
|
|
|
|
#define DISABLE_PATHFINDING 0
|
|
#define USE_PATHFINDING_EXPERIMENTAL_FIX_2 0 // Alternate Fix: Allows polygons merged on one point
|
|
|
|
#define WITHIN_TOLERANCE(a, b) (((a) - 0.009) < (b) && ((a) + 0.009) > (b))
|
|
|
|
namespace BladeRunner {
|
|
|
|
Obstacles::Obstacles(BladeRunnerEngine *vm) {
|
|
_vm = vm;
|
|
_polygons = new Polygon[kPolygonCount];
|
|
_polygonsBackup = new Polygon[kPolygonCount];
|
|
_path = new Vector2[kVertexCount];
|
|
clear();
|
|
}
|
|
|
|
Obstacles::~Obstacles() {
|
|
clear();
|
|
|
|
delete[] _polygons;
|
|
_polygons = nullptr;
|
|
|
|
delete[] _polygonsBackup;
|
|
_polygonsBackup = nullptr;
|
|
|
|
delete[] _path;
|
|
_path = nullptr;
|
|
}
|
|
|
|
void Obstacles::clear() {
|
|
for (int i = 0; i < kPolygonCount; ++i) {
|
|
_polygons[i].isPresent = false;
|
|
_polygons[i].verticeCount = 0;
|
|
for (int j = 0; j < kPolygonVertexCount; ++j) {
|
|
_polygons[i].vertices[j].x = 0.0f;
|
|
_polygons[i].vertices[j].y = 0.0f;
|
|
}
|
|
}
|
|
_pathSize = 0;
|
|
_backup = false;
|
|
_count = 0;
|
|
}
|
|
|
|
#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, int pathLengthSinceLastIntersection) {
|
|
bool hasIntersection = false;
|
|
float nearestIntersectionDistance = 0.0f;
|
|
|
|
for (int i = 0; i != polyB->verticeCount; ++i) {
|
|
LineSegment lineB; // An edge of the secondary polygon
|
|
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)) {
|
|
// NOTE: An edge type (eg lineAType) is set by its start point vertex type.
|
|
// The end point of the edge is the next vertex of the polygon going clock-wise.
|
|
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)
|
|
) {
|
|
// NOTE: pathLengthSinceLastIntersection is part of pathfinding fix 2
|
|
if ( (pathLengthSinceLastIntersection > 2)
|
|
|| ( (!(WITHIN_TOLERANCE(lineB.end.x, newIntersectionPoint.x) && WITHIN_TOLERANCE(lineB.end.y, newIntersectionPoint.y)))
|
|
&& (newIntersectionPoint != *intersectionPoint) )) {
|
|
float newIntersectionDistance = getLength(lineA.start.x, lineA.start.y, newIntersectionPoint.x, newIntersectionPoint.y);
|
|
// NOTE: We only want the *nearest* intersection point to the start of the line A
|
|
// We don't want the intersection point to be the end point of the line B (from secondary polygon),
|
|
// because in that case, switching to Polygon B (to make it primary) we'd get an "edge"
|
|
// from the intersection point to the end point of the line B (which was a vertex of Polygon B)
|
|
// which would result to an edge with the same start and end point, and thus duplicate vertices in the merged polygon.
|
|
//
|
|
// We do keep 0 length segments here from lineA start to the intersection point
|
|
// (which can happen when the polygons touch edges or corners)
|
|
// but those will be handled in the calling function.
|
|
if (!hasIntersection || newIntersectionDistance < nearestIntersectionDistance) {
|
|
hasIntersection = true;
|
|
nearestIntersectionDistance = newIntersectionDistance;
|
|
*intersectionPoint = newIntersectionPoint;
|
|
*intersectionIndex = i; // the index of the vertex for the start of the lineB edge (of Polygon B which will become primary)
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
return hasIntersection;
|
|
}
|
|
|
|
/*
|
|
* Polygons vertices are defined in clock-wise order
|
|
* starting at the top-most, left-most corner (eg. here B0).
|
|
*
|
|
* When merging two polygons, we start at the top-most, left-most vertex.
|
|
* The polygon with this vertex starts as 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;
|
|
int pathLengthSinceLastIntersection = 0; // Part of pathfinding fix 2. It's only updated when enabling that fix, otherwise it is always zero (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?
|
|
// The intersection point "inherits" the vertex type of the now-primary
|
|
// (which was "secondary" before the intersection swap) polygon's vertex,
|
|
// which was the start of the edge that intersected with the former-primary (now secondary) polygon.
|
|
polyPrimaryType = polyPrimary->vertexType[vertIndex];
|
|
|
|
if (flagAddVertexToVertexList) {
|
|
#if USE_PATHFINDING_EXPERIMENTAL_FIX_2
|
|
assert(polyMerged.verticeCount < kPolygonVertexCount);
|
|
#else
|
|
// In some cases polygons will have only one intersection (touching corners) and because of that second SWAP never occurs,
|
|
// algorithm will stop only when the merged polygon is full.
|
|
if (polyMerged.verticeCount >= kPolygonVertexCount) {
|
|
flagDidMergePolygons = false;
|
|
break;
|
|
}
|
|
#endif
|
|
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, pathLengthSinceLastIntersection)) {
|
|
if (WITHIN_TOLERANCE(intersectionPoint.x, polyLine.start.x) && WITHIN_TOLERANCE(intersectionPoint.y, polyLine.start.y)) {
|
|
// The start of the edge of the primary polygon is (very close to) the intersection point.
|
|
// This eg. does occur in RC02 (Set 16, Scene 79, chapter 1) (intersection point (x: -16.000000, y: 108303.968750))
|
|
|
|
// The code here ensures we keep the intersection point in the merged polygon (polyMerged)
|
|
// but *remove* the vertex that was the start of the edge (belonging to the primary polygon)
|
|
// However, unless the intersection point is exactly the same as the start of the line segment from the primary polygon,
|
|
// (which seems to practically be the case)
|
|
// this can *potentially* lead to slanted (so not strictly vertical or horizontal) lines in the merged polygon.
|
|
// TODO: Is there a case where we end up with slanted edges in the merged polygon?
|
|
flagAddVertexToVertexList = false;
|
|
// TODO: We don't check here for polyMerged.verticeCount > 0 before decrementing it,
|
|
// and this practically seems to not be an issue, but shouldn't we include this check just to be safe?
|
|
//
|
|
// TODO(madmoose): How would this work?
|
|
--(polyMerged.verticeCount);
|
|
} else {
|
|
// Obstacles::nop
|
|
}
|
|
vertIndex = polySecondaryIntersectionIndex;
|
|
flagDidFindIntersection = true;
|
|
|
|
SWAP(polyPrimary, polySecondary);
|
|
|
|
flagDidMergePolygons = true;
|
|
#if USE_PATHFINDING_EXPERIMENTAL_FIX_2
|
|
pathLengthSinceLastIntersection = 0;
|
|
#endif
|
|
} else {
|
|
vertIndex = (vertIndex + 1) % polyPrimary->verticeCount;
|
|
#if USE_PATHFINDING_EXPERIMENTAL_FIX_2
|
|
++pathLengthSinceLastIntersection;
|
|
#endif
|
|
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(RectFloat 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;
|
|
}
|
|
|
|
if (polyA.verticeCount == 0) {
|
|
continue;
|
|
}
|
|
|
|
for (int j = i+1; j < kPolygonCount; ++j) {
|
|
Polygon &polyB = _polygons[j];
|
|
if (!polyB.isPresent) {
|
|
continue;
|
|
}
|
|
|
|
if (polyB.verticeCount == 0) {
|
|
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);
|
|
}
|
|
|
|
#if DISABLE_PATHFINDING
|
|
bool Obstacles::findNextWaypoint(const Vector3 &from, const Vector3 &to, Vector3 *next) {
|
|
*next = to;
|
|
|
|
return true;
|
|
}
|
|
#else
|
|
|
|
bool Obstacles::findNextWaypoint(const Vector3 &from, const Vector3 &to, Vector3 *next) {
|
|
static int recursionLevel = 0;
|
|
static bool polygonVisited[kPolygonCount];
|
|
|
|
if (++recursionLevel == 1) {
|
|
clearPath();
|
|
for (int i = 0; i != kPolygonCount; ++i) {
|
|
polygonVisited[i] = false;
|
|
}
|
|
}
|
|
|
|
int polyIndex = -1;
|
|
int polyNearVertIndex = -1;
|
|
float polyNearDist = 0.0f;
|
|
Vector2 polyNearPos;
|
|
int polyFarVertIndex = -1;
|
|
float polyFarDist = 0.0f;
|
|
Vector2 polyFarPos;
|
|
|
|
for (int i = 0; i != kPolygonCount; ++i) {
|
|
Polygon &poly = _polygons[i];
|
|
if (!poly.isPresent || polygonVisited[i]) {
|
|
continue;
|
|
}
|
|
|
|
int nearVertIndex;
|
|
float nearDist;
|
|
Vector2 nearPos;
|
|
|
|
if (!findIntersectionNearest(i, from.xz(), to.xz(), &nearVertIndex, &nearDist, &nearPos)) {
|
|
continue;
|
|
}
|
|
|
|
int farVertIndex;
|
|
float farDist;
|
|
Vector2 farPos;
|
|
|
|
int hasFar = findIntersectionFarthest(i, from.xz(), to.xz(), &farVertIndex, &farDist, &farPos);
|
|
assert(hasFar);
|
|
|
|
if (polyIndex == -1 || nearDist < polyNearDist) {
|
|
polyNearDist = nearDist;
|
|
polyNearPos = nearPos;
|
|
polyFarDist = farDist;
|
|
polyFarPos = farPos;
|
|
polyIndex = i;
|
|
polyNearVertIndex = nearVertIndex;
|
|
polyFarVertIndex = farVertIndex;
|
|
}
|
|
}
|
|
|
|
if (polyIndex < 0) {
|
|
assert(_pathSize < kVertexCount);
|
|
_path[_pathSize++] = to.xz();
|
|
} else {
|
|
polygonVisited[polyIndex] = true;
|
|
|
|
if (polyNearDist == 0.0f && polyFarDist == 0.0f) {
|
|
assert(_pathSize < kVertexCount);
|
|
_path[_pathSize++] = polyNearPos;
|
|
} else {
|
|
Vector2 pathA[kMaxPathSize];
|
|
Vector2 pathB[kMaxPathSize];
|
|
|
|
bool pathABlocked;
|
|
bool pathBBlocked;
|
|
|
|
int pathASize = buildNegativePath(polyIndex, polyNearVertIndex, polyNearPos, polyFarVertIndex, polyFarPos, pathA, kMaxPathSize, &pathABlocked);
|
|
int pathBSize = buildPositivePath(polyIndex, polyNearVertIndex, polyNearPos, polyFarVertIndex, polyFarPos, pathB, kMaxPathSize, &pathBBlocked);
|
|
|
|
float pathATotalDistance = pathTotalDistance(pathA, pathASize, from.xz(), to.xz());
|
|
float pathBTotalDistance = pathTotalDistance(pathB, pathBSize, from.xz(), to.xz());
|
|
|
|
bool usePathA;
|
|
if (pathABlocked && !pathBBlocked) {
|
|
usePathA = false;
|
|
} else if (pathBBlocked && !pathABlocked) {
|
|
usePathA = true;
|
|
} else {
|
|
usePathA = pathATotalDistance <= pathBTotalDistance;
|
|
}
|
|
|
|
if (usePathA) {
|
|
assert(_pathSize + pathASize < kVertexCount);
|
|
for (int i = 0; i != pathASize; ++i) {
|
|
_path[_pathSize + i] = pathA[i];
|
|
}
|
|
_pathSize += pathASize;
|
|
} else {
|
|
assert(_pathSize + pathBSize < kVertexCount);
|
|
for (int i = 0; i != pathBSize; ++i) {
|
|
_path[_pathSize + i] = pathB[i];
|
|
}
|
|
_pathSize += pathBSize;
|
|
}
|
|
}
|
|
assert(_pathSize > 0);
|
|
Vector3 lastPathPos(_path[_pathSize - 1].x, from.y, _path[_pathSize - 1].y);
|
|
findNextWaypoint(lastPathPos, to, next);
|
|
}
|
|
|
|
if (--recursionLevel > 1) {
|
|
// NOTE: Basically this allows at most 1 level of recursion
|
|
return false;
|
|
}
|
|
|
|
return findFarthestAvailablePathVertex(_path, _pathSize, from, next);
|
|
}
|
|
#endif
|
|
|
|
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;
|
|
}
|
|
|
|
float Obstacles::pathTotalDistance(const Vector2 *path, int pathSize, Vector2 from, Vector2 to) const {
|
|
// Yes, 'to' and 'from' are ignored.
|
|
float totalDistance = 0.0f;
|
|
for (int i = 0; i != pathSize - 1; ++i) {
|
|
totalDistance += distance(path[i], path[i+1]);
|
|
}
|
|
return totalDistance;
|
|
}
|
|
|
|
|
|
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 != _polygons[i].verticeCount; ++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, int startSearchFromPolygonIdx) const {
|
|
*polygonIndex = -1;
|
|
*verticeIndex = -1;
|
|
|
|
// for (int i = 0; i != kPolygonCount; ++i) {
|
|
for (int countUp = 0, i = startSearchFromPolygonIdx; countUp != kPolygonCount; ++countUp, ++i) {
|
|
i = i % kPolygonCount; // we want to circle around to go through all polygons
|
|
if (!_polygons[i].isPresent || _polygons[i].verticeCount == 0) {
|
|
continue;
|
|
}
|
|
|
|
for (int j = 0; j != _polygons[i].verticeCount; ++j) {
|
|
if (WITHIN_TOLERANCE(_polygons[i].vertices[j].x, x) && WITHIN_TOLERANCE(_polygons[i].vertices[j].y, z)) {
|
|
*polygonIndex = i;
|
|
*verticeIndex = j;
|
|
return true;
|
|
}
|
|
}
|
|
}
|
|
|
|
return false;
|
|
}
|
|
|
|
void Obstacles::clearPath() {
|
|
_pathSize = 0;
|
|
}
|
|
|
|
int Obstacles::buildNegativePath(int polyIndex, int vertStartIndex, Vector2 startPos, int vertEndIndex, Vector2 endPos, Vector2 *path, int pathCapacity, bool *pathBlocked) {
|
|
int pathSize = 0;
|
|
*pathBlocked = false;
|
|
Polygon *poly = &_polygons[polyIndex];
|
|
|
|
/* Add start position to path */
|
|
if (_vm->_scene->_set->findWalkbox(startPos.x, startPos.y) == -1) {
|
|
*pathBlocked = true;
|
|
}
|
|
assert(pathSize < pathCapacity);
|
|
path[pathSize++] = startPos;
|
|
|
|
int i = vertStartIndex;
|
|
|
|
/* Add polygon vertices in negative iteration order */
|
|
while (true) {
|
|
Vector2 v = poly->vertices[i];
|
|
if (_vm->_scene->_set->findWalkbox(v.x, v.y) == -1) {
|
|
*pathBlocked = true;
|
|
}
|
|
|
|
assert(pathSize < pathCapacity);
|
|
path[pathSize++] = v;
|
|
|
|
i = (i + poly->verticeCount - 1) % poly->verticeCount;
|
|
if (i == vertEndIndex) {
|
|
break;
|
|
}
|
|
}
|
|
|
|
/* Add end position to path */
|
|
if (_vm->_scene->_set->findWalkbox(endPos.x, endPos.y) == -1) {
|
|
*pathBlocked = true;
|
|
}
|
|
assert(pathSize < pathCapacity);
|
|
path[pathSize++] = endPos;
|
|
|
|
return pathSize;
|
|
}
|
|
|
|
int Obstacles::buildPositivePath(int polyIndex, int vertStartIndex, Vector2 startPos, int vertEndIndex, Vector2 endPos, Vector2 *path, int pathCapacity, bool *pathBlocked) {
|
|
int pathSize = 0;
|
|
*pathBlocked = false;
|
|
Polygon *poly = &_polygons[polyIndex];
|
|
|
|
/* Add start position to path */
|
|
if (_vm->_scene->_set->findWalkbox(startPos.x, startPos.y) == -1) {
|
|
*pathBlocked = true;
|
|
}
|
|
assert(pathSize < pathCapacity);
|
|
path[pathSize++] = startPos;
|
|
|
|
int i = (vertStartIndex + 1) % poly->verticeCount;
|
|
|
|
/* Add polygon vertices in positive iteration order */
|
|
while (true) {
|
|
Vector2 v = poly->vertices[i];
|
|
if (_vm->_scene->_set->findWalkbox(v.x, v.y) == -1) {
|
|
*pathBlocked = true;
|
|
}
|
|
|
|
assert(pathSize < pathCapacity);
|
|
path[pathSize++] = v;
|
|
|
|
if (i == vertEndIndex) {
|
|
break;
|
|
}
|
|
|
|
i = (i + 1) % poly->verticeCount;
|
|
}
|
|
|
|
/* Add end position to path */
|
|
if (_vm->_scene->_set->findWalkbox(endPos.x, endPos.y) == -1) {
|
|
*pathBlocked = true;
|
|
}
|
|
assert(pathSize < pathCapacity);
|
|
path[pathSize++] = endPos;
|
|
|
|
return pathSize;
|
|
}
|
|
|
|
bool Obstacles::verticesCanIntersect(int lineType0, int lineType1, float x0, float y0, float x1, float y1) const {
|
|
if (lineType0 == TOP_LEFT && lineType1 == TOP_RIGHT) {
|
|
if (x0 > x1 && y0 < y1) return true;
|
|
}
|
|
if (lineType0 == TOP_RIGHT && lineType1 == BOTTOM_RIGHT) {
|
|
if (x0 > x1 && y0 > y1) return true;
|
|
}
|
|
if (lineType0 == BOTTOM_RIGHT && lineType1 == BOTTOM_LEFT) {
|
|
if (x0 < x1 && y0 > y1) return true;
|
|
}
|
|
if (lineType0 == BOTTOM_LEFT && lineType1 == TOP_LEFT) {
|
|
if (x0 < x1 && y0 < y1) return true;
|
|
}
|
|
if (lineType0 == TOP_RIGHT && lineType1 == TOP_LEFT) {
|
|
if (x0 > x1 || y0 < y1) return true;
|
|
}
|
|
if (lineType0 == BOTTOM_RIGHT && lineType1 == TOP_RIGHT) {
|
|
if (x0 > x1 || y0 > y1) return true;
|
|
}
|
|
if (lineType0 == BOTTOM_LEFT && lineType1 == BOTTOM_RIGHT) {
|
|
if (x0 < x1 || y0 > y1) return true;
|
|
}
|
|
if (lineType0 == TOP_LEFT && lineType1 == BOTTOM_LEFT) {
|
|
if (x0 < x1 || y0 < y1) return true;
|
|
}
|
|
return false;
|
|
}
|
|
|
|
bool Obstacles::findFarthestAvailablePathVertex(Vector2 *path, int pathSize, Vector3 start, Vector3 *next) const {
|
|
if (pathSize == 0) {
|
|
*next = start;
|
|
return false;
|
|
}
|
|
|
|
int vertexTypeStart = -1;
|
|
int vertexTypeStartPrev = -1;
|
|
int polygonIndexStart = -1;
|
|
int vertexIndexStart = -1;
|
|
bool startOnPolygon = findPolygonVerticeByXZWithinTolerance(start.x, start.z, &polygonIndexStart, &vertexIndexStart, 0);
|
|
if (startOnPolygon) {
|
|
int vertexIndexStartPrev = (vertexIndexStart - 1 + _polygons[polygonIndexStart].verticeCount) % _polygons[polygonIndexStart].verticeCount;
|
|
|
|
vertexTypeStart = _polygons[polygonIndexStart].vertexType[vertexIndexStart];
|
|
vertexTypeStartPrev = _polygons[polygonIndexStart].vertexType[vertexIndexStartPrev];
|
|
}
|
|
|
|
signed int farthestPathIndex = -1;
|
|
for (int pathVertexIdx = 0; pathVertexIdx < pathSize; ++pathVertexIdx) {
|
|
bool foundVertexNeighbor = false;
|
|
int polygonIndexPath = -1;
|
|
int vertexIndexPath = -1;
|
|
bool pathVertexOnPolygon = findPolygonVerticeByXZWithinTolerance(path[pathVertexIdx].x, path[pathVertexIdx].y, &polygonIndexPath, &vertexIndexPath, 0) == 1;
|
|
|
|
//start and current path vertices are on same polygon and are next to each other
|
|
if (pathVertexOnPolygon && polygonIndexStart == polygonIndexPath) {
|
|
int vertexIndexStartPrev = (vertexIndexStart - 1 + _polygons[polygonIndexPath].verticeCount) % _polygons[polygonIndexPath].verticeCount;
|
|
int vertexIndexStartNext = (vertexIndexStart + 1 ) % _polygons[polygonIndexPath].verticeCount;
|
|
|
|
if (vertexIndexPath == vertexIndexStartNext || vertexIndexPath == vertexIndexStartPrev || vertexIndexPath == vertexIndexStart) {
|
|
foundVertexNeighbor = true;
|
|
}
|
|
}
|
|
|
|
// neighboring vertices are always available
|
|
if (foundVertexNeighbor) {
|
|
farthestPathIndex = pathVertexIdx;
|
|
continue;
|
|
}
|
|
|
|
bool pathVertexAvailable = true;
|
|
for (int currentPolygonIdx = 0; currentPolygonIdx < kPolygonCount && pathVertexAvailable; ++currentPolygonIdx) {
|
|
Polygon *polygon = &_polygons[currentPolygonIdx];
|
|
|
|
if (!polygon->isPresent || polygon->verticeCount == 0) {
|
|
continue;
|
|
}
|
|
|
|
for (int polygonVertexIdx = 0; polygonVertexIdx < polygon->verticeCount && pathVertexAvailable; ++polygonVertexIdx) {
|
|
int polygonVertexNextIdx = (polygonVertexIdx + 1) % polygon->verticeCount;
|
|
|
|
// check intersection between start -> path and polygon edge
|
|
Vector2 intersection;
|
|
if (!lineIntersection(Vector2(start.x, start.z), path[pathVertexIdx], polygon->vertices[polygonVertexIdx], polygon->vertices[polygonVertexNextIdx], &intersection)) {
|
|
continue;
|
|
}
|
|
|
|
// intersection has to be at end of one of these points (either on this polygon or on the path or at start)
|
|
if (!(
|
|
(WITHIN_TOLERANCE(intersection.x, start.x) && WITHIN_TOLERANCE(intersection.y, start.z) )
|
|
|| (WITHIN_TOLERANCE(intersection.x, path[pathVertexIdx].x) && WITHIN_TOLERANCE(intersection.y, path[pathVertexIdx].y) )
|
|
|| (WITHIN_TOLERANCE(intersection.x, polygon->vertices[polygonVertexIdx].x) && WITHIN_TOLERANCE(intersection.y, polygon->vertices[polygonVertexIdx].y) )
|
|
|| (WITHIN_TOLERANCE(intersection.x, polygon->vertices[polygonVertexNextIdx].x) && WITHIN_TOLERANCE(intersection.y, polygon->vertices[polygonVertexNextIdx].y))
|
|
)) {
|
|
pathVertexAvailable = false;
|
|
break;
|
|
}
|
|
|
|
int polygonIndexIntersection = -1;
|
|
int vertexIndexIntersection = -1;
|
|
if (findPolygonVerticeByXZWithinTolerance(intersection.x, intersection.y, &polygonIndexIntersection, &vertexIndexIntersection, currentPolygonIdx)) {
|
|
// Intersection has to be vertex only on current polygon
|
|
// Part of pathfinding fix 2 (dealing with merge on only one edge point)
|
|
// but also speeds up process:
|
|
// we start (a cyclical) searching in Polygons array
|
|
// beginning from the current polygon index
|
|
assert(polygonIndexIntersection == currentPolygonIdx);
|
|
|
|
if (verticesCanIntersect(vertexTypeStartPrev, vertexTypeStart, start.x, start.z, path[pathVertexIdx].x, path[pathVertexIdx].y)) {
|
|
pathVertexAvailable = false;
|
|
break;
|
|
}
|
|
|
|
if ((currentPolygonIdx == polygonIndexPath && vertexIndexIntersection == vertexIndexPath)
|
|
|| (currentPolygonIdx == polygonIndexStart && vertexIndexIntersection == vertexIndexStart)
|
|
) {
|
|
continue;
|
|
}
|
|
|
|
int vertexIndexIntersectionprev = (vertexIndexIntersection - 1 + _polygons[polygonIndexIntersection].verticeCount ) % _polygons[polygonIndexIntersection].verticeCount;
|
|
if (verticesCanIntersect(_polygons[polygonIndexIntersection].vertexType[vertexIndexIntersectionprev], _polygons[polygonIndexIntersection].vertexType[vertexIndexIntersection], intersection.x, intersection.y, path[pathVertexIdx].x, path[pathVertexIdx].y)) {
|
|
pathVertexAvailable = false;
|
|
break;
|
|
}
|
|
} else {
|
|
bool startIntersectionWithinTolerance = false;
|
|
if (WITHIN_TOLERANCE(intersection.x, start.x)
|
|
&& WITHIN_TOLERANCE(intersection.y, start.z)
|
|
) {
|
|
startIntersectionWithinTolerance = true;
|
|
}
|
|
|
|
if (currentPolygonIdx == polygonIndexStart || startIntersectionWithinTolerance) {
|
|
if (polygonIndexStart >= 0 || !startIntersectionWithinTolerance) {
|
|
pathVertexAvailable = false;
|
|
break;
|
|
}
|
|
|
|
int polygonVertexType = polygon->vertexType[polygonVertexIdx];
|
|
if ((polygonVertexType == TOP_LEFT && intersection.y < path[pathVertexIdx].y)
|
|
|| (polygonVertexType == TOP_RIGHT && intersection.x > path[pathVertexIdx].x)
|
|
|| (polygonVertexType == BOTTOM_RIGHT && intersection.y > path[pathVertexIdx].y)
|
|
|| (polygonVertexType == BOTTOM_LEFT && intersection.x < path[pathVertexIdx].x)
|
|
) {
|
|
pathVertexAvailable = false;
|
|
break;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
if (pathVertexAvailable) {
|
|
farthestPathIndex = pathVertexIdx;
|
|
}
|
|
}
|
|
|
|
if (farthestPathIndex == -1) {
|
|
*next = start;
|
|
return false;
|
|
}
|
|
|
|
next->x = path[farthestPathIndex].x;
|
|
next->z = path[farthestPathIndex].y;
|
|
|
|
bool walkboxFound;
|
|
float walkboxAltitude = _vm->_scene->_set->getAltitudeAtXZ(next->x, next->z, &walkboxFound);
|
|
|
|
if (walkboxFound) {
|
|
next->y = walkboxAltitude;
|
|
return true;
|
|
} else {
|
|
next->y = start.y;
|
|
return false;
|
|
}
|
|
}
|
|
|
|
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() {
|
|
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);
|
|
f.writeInt(_count);
|
|
for (int i = 0; i < _count; ++i) {
|
|
Polygon &p = _polygonsBackup[i];
|
|
f.writeBool(p.isPresent);
|
|
f.writeInt(p.verticeCount);
|
|
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]);
|
|
}
|
|
for (int j = 0; j < kPolygonVertexCount; ++j) {
|
|
f.writeInt(p.vertexType[j]);
|
|
}
|
|
}
|
|
for (int i = 0; i < kVertexCount; ++i) {
|
|
f.writeVector2(_path[i]);
|
|
}
|
|
f.writeInt(_pathSize);
|
|
}
|
|
|
|
void Obstacles::load(SaveFileReadStream &f) {
|
|
for (int i = 0; i < kPolygonCount; ++i) {
|
|
_polygons[i].isPresent = false;
|
|
_polygons[i].verticeCount = 0;
|
|
_polygonsBackup[i].isPresent = false;
|
|
_polygonsBackup[i].verticeCount = 0;
|
|
}
|
|
|
|
_backup = f.readBool();
|
|
_count = f.readInt();
|
|
for (int i = 0; i < _count; ++i) {
|
|
Polygon &p = _polygonsBackup[i];
|
|
p.isPresent = f.readBool();
|
|
p.verticeCount = f.readInt();
|
|
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] = (VertexType)f.readInt();
|
|
}
|
|
}
|
|
|
|
for (int i = 0; i < kPolygonCount; ++i) {
|
|
_polygons[i] = _polygonsBackup[i];
|
|
}
|
|
|
|
for (int i = 0; i < kVertexCount; ++i) {
|
|
_path[i] = f.readVector2();
|
|
}
|
|
_pathSize = f.readInt();
|
|
}
|
|
|
|
// This is used when debugger is set to draw obstacles
|
|
void Obstacles::draw() {
|
|
float y = _vm->_playerActor->getY();
|
|
|
|
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,
|
|
y,
|
|
_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,
|
|
y,
|
|
_polygons[i].vertices[j].y
|
|
));
|
|
|
|
_vm->_surfaceFront.drawLine(p0.x, p0.y, p1.x, p1.y, _vm->_surfaceFront.format.RGBToColor(255, 255, 255));
|
|
|
|
p0 = p1;
|
|
}
|
|
}
|
|
|
|
// draw actor's box - only for the player (McCoy)
|
|
{
|
|
Vector3 playerPos = _vm->_playerActor->getXYZ();
|
|
Vector3 p0 = _vm->_view->calculateScreenPosition(playerPos + Vector3(-12.0f, 0.0f, -12.0f));
|
|
Vector3 p1 = _vm->_view->calculateScreenPosition(playerPos + Vector3( 12.0f, 0.0f, -12.0f));
|
|
Vector3 p2 = _vm->_view->calculateScreenPosition(playerPos + Vector3( 12.0f, 0.0f, 12.0f));
|
|
Vector3 p3 = _vm->_view->calculateScreenPosition(playerPos + Vector3(-12.0f, 0.0f, 12.0f));
|
|
|
|
_vm->_surfaceFront.drawLine(p0.x, p0.y, p1.x, p1.y, _vm->_surfaceFront.format.RGBToColor(255, 0, 0));
|
|
_vm->_surfaceFront.drawLine(p1.x, p1.y, p2.x, p2.y, _vm->_surfaceFront.format.RGBToColor(255, 0, 0));
|
|
_vm->_surfaceFront.drawLine(p2.x, p2.y, p3.x, p3.y, _vm->_surfaceFront.format.RGBToColor(255, 0, 0));
|
|
_vm->_surfaceFront.drawLine(p3.x, p3.y, p0.x, p0.y, _vm->_surfaceFront.format.RGBToColor(255, 0, 0));
|
|
}
|
|
|
|
// draw path along polygons
|
|
for (int i = 1; i < _pathSize; ++i) {
|
|
Vector3 p0 = _vm->_view->calculateScreenPosition(Vector3(_path[i - 1].x, y, _path[i - 1].y));
|
|
Vector3 p1 = _vm->_view->calculateScreenPosition(Vector3(_path[i].x, y, _path[i].y));
|
|
_vm->_surfaceFront.drawLine(p0.x, p0.y, p1.x, p1.y, _vm->_surfaceFront.format.RGBToColor(255, 0, 0));
|
|
}
|
|
|
|
// draw "next" vertex
|
|
{
|
|
//TODO
|
|
}
|
|
|
|
|
|
}
|
|
|
|
} // End of namespace BladeRunner
|