1 /* ScummVM - Graphic Adventure Engine
2 *
3 * ScummVM is the legal property of its developers, whose names
4 * are too numerous to list here. Please refer to the COPYRIGHT
5 * file distributed with this source distribution.
6 *
7 * This program is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU General Public License
9 * as published by the Free Software Foundation; either version 2
10 * of the License, or (at your option) any later version.
11 *
12 * This program is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with this program; if not, write to the Free Software
19 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
20 *
21 */
22
23 #include "bladerunner/obstacles.h"
24
25 #include "bladerunner/bladerunner.h"
26
27 #include "bladerunner/actor.h"
28 #include "bladerunner/savefile.h"
29 #include "bladerunner/scene.h" // for debug
30 #include "bladerunner/set.h"
31 #include "bladerunner/view.h"
32
33 #include "common/debug.h"
34
35 #define DISABLE_PATHFINDING 0
36 #define USE_PATHFINDING_EXPERIMENTAL_FIX_2 0 // Alternate Fix: Allows polygons merged on one point
37
38 #define WITHIN_TOLERANCE(a, b) (((a) - 0.009) < (b) && ((a) + 0.009) > (b))
39
40 namespace BladeRunner {
41
Obstacles(BladeRunnerEngine * vm)42 Obstacles::Obstacles(BladeRunnerEngine *vm) {
43 _vm = vm;
44 _polygons = new Polygon[kPolygonCount];
45 _polygonsBackup = new Polygon[kPolygonCount];
46 _path = new Vector2[kVertexCount];
47 clear();
48 }
49
~Obstacles()50 Obstacles::~Obstacles() {
51 clear();
52
53 delete[] _polygons;
54 _polygons = nullptr;
55
56 delete[] _polygonsBackup;
57 _polygonsBackup = nullptr;
58
59 delete[] _path;
60 _path = nullptr;
61 }
62
clear()63 void Obstacles::clear() {
64 for (int i = 0; i < kPolygonCount; ++i) {
65 _polygons[i].isPresent = false;
66 _polygons[i].verticeCount = 0;
67 for (int j = 0; j < kPolygonVertexCount; ++j) {
68 _polygons[i].vertices[j].x = 0.0f;
69 _polygons[i].vertices[j].y = 0.0f;
70 }
71 }
72 _pathSize = 0;
73 _backup = false;
74 _count = 0;
75 }
76
77 #define IN_RANGE(v, start, end) ((start) <= (v) && (v) <= (end))
78
79 /*
80 * This function is limited to finding intersections between
81 * horizontal and vertical lines!
82 *
83 * The original implementation is more general but obstacle
84 * polygons only consists of horizontal and vertical lines,
85 * and this is more numerically stable.
86 */
lineLineIntersection(LineSegment a,LineSegment b,Vector2 * intersection)87 bool Obstacles::lineLineIntersection(LineSegment a, LineSegment b, Vector2 *intersection) {
88 assert(a.start.x == a.end.x || a.start.y == a.end.y);
89 assert(b.start.x == b.end.x || b.start.y == b.end.y);
90
91 if (a.start.x > a.end.x) SWAP(a.start.x, a.end.x);
92 if (a.start.y > a.end.y) SWAP(a.start.y, a.end.y);
93 if (b.start.x > b.end.x) SWAP(b.start.x, b.end.x);
94 if (b.start.y > b.end.y) SWAP(b.start.y, b.end.y);
95
96 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)) {
97 // A is vertical, B is horizontal
98 *intersection = Vector2(a.start.x, b.start.y);
99 return true;
100 }
101
102 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)) {
103 // A is horizontal, B is vertical
104 *intersection = Vector2(b.start.x, a.start.y);
105 return true;
106 }
107
108 return false;
109 }
110
linePolygonIntersection(LineSegment lineA,VertexType lineAType,Polygon * polyB,Vector2 * intersectionPoint,int * intersectionIndex,int pathLengthSinceLastIntersection)111 bool Obstacles::linePolygonIntersection(LineSegment lineA, VertexType lineAType, Polygon *polyB, Vector2 *intersectionPoint, int *intersectionIndex, int pathLengthSinceLastIntersection) {
112 bool hasIntersection = false;
113 float nearestIntersectionDistance = 0.0f;
114
115 for (int i = 0; i != polyB->verticeCount; ++i) {
116 LineSegment lineB;
117 lineB.start = polyB->vertices[i];
118 lineB.end = polyB->vertices[(i+1) % polyB->verticeCount];
119
120 VertexType lineBType = polyB->vertexType[i];
121
122 Vector2 newIntersectionPoint;
123
124 if (lineLineIntersection(lineA, lineB, &newIntersectionPoint)) {
125 if ((lineAType == TOP_RIGHT && lineBType == TOP_LEFT)
126 || (lineAType == BOTTOM_RIGHT && lineBType == TOP_RIGHT)
127 || (lineAType == BOTTOM_LEFT && lineBType == BOTTOM_RIGHT)
128 || (lineAType == TOP_LEFT && lineBType == BOTTOM_LEFT)
129 ) {
130 if ( (pathLengthSinceLastIntersection > 2)
131 || ( (!(WITHIN_TOLERANCE(lineB.end.x, intersectionPoint->x) && WITHIN_TOLERANCE(lineB.end.y, intersectionPoint->y)))
132 && (newIntersectionPoint != *intersectionPoint) )) {
133 float newIntersectionDistance = getLength(lineA.start.x, lineA.start.y, newIntersectionPoint.x, newIntersectionPoint.y);
134 if (!hasIntersection || newIntersectionDistance < nearestIntersectionDistance) {
135 hasIntersection = true;
136 nearestIntersectionDistance = newIntersectionDistance;
137 *intersectionPoint = newIntersectionPoint;
138 *intersectionIndex = i;
139 }
140 }
141 }
142 }
143 }
144
145 return hasIntersection;
146 }
147
148 /*
149 * Polygons vertices are defined in clock-wise order
150 * starting at the top-most, right-most corner.
151 *
152 * When merging two polygons, we start at the top-most, right-most vertex.
153 * The polygon with this vertex starts is the primary polygon.
154 * We follow the edges until we find an intersection with the secondary polygon,
155 * in which case we switch primary and secondary and continue following the new edges.
156 *
157 * Luckily the first two polygons added in RC01 (A, then B) are laid as as below,
158 * making an ideal test case.
159 *
160 * Merge order: (B0,B1) (B1,B2) (B2,J) (J,A2) (A2,A3) (A3,A0) (A0,I) (I,B0)
161 *
162 * 0,0 ---> x
163 * |
164 * | primary
165 * | B 0 ----- 1
166 * | | |
167 * | A 0 --I-- 1 |
168 * | | | | |
169 * | | 3 --J-- 2
170 * | | |
171 * | 3 ----- 2
172 * | secondary
173 * v y
174 */
175
mergePolygons(Polygon & polyA,Polygon & polyB)176 bool Obstacles::mergePolygons(Polygon &polyA, Polygon &polyB) {
177 bool flagDidMergePolygons = false;
178 Polygon polyMerged;
179 polyMerged.rect = merge(polyA.rect, polyB.rect);
180
181 Polygon *polyPrimary, *polySecondary;
182 if (polyA.rect.y0 < polyB.rect.y0 || (polyA.rect.y0 == polyB.rect.y0 && polyA.rect.x0 < polyB.rect.x0)) {
183 polyPrimary = &polyA;
184 polySecondary = &polyB;
185 } else {
186 polyPrimary = &polyB;
187 polySecondary = &polyA;
188 }
189
190 Vector2 intersectionPoint;
191 LineSegment polyLine;
192 bool flagAddVertexToVertexList = true;
193 bool flagDidFindIntersection = false;
194 int vertIndex = 0;
195 int pathLengthSinceLastIntersection = 0; // Part of pathfinding fix 2. It's only updated when enabling that fix, otherwise it is always zero (0).
196
197 Polygon *startingPolygon = polyPrimary;
198 int flagDone = false;
199 while (!flagDone) {
200 VertexType polyPrimaryType;
201
202 polyLine.start = flagDidFindIntersection ? intersectionPoint : polyPrimary->vertices[vertIndex];
203 polyLine.end = polyPrimary->vertices[(vertIndex + 1) % polyPrimary->verticeCount];
204
205 // TODO(madmoose): How does this work when adding a new intersection point?
206 polyPrimaryType = polyPrimary->vertexType[vertIndex];
207
208 if (flagAddVertexToVertexList) {
209 #if USE_PATHFINDING_EXPERIMENTAL_FIX_2
210 assert(polyMerged.verticeCount < kPolygonVertexCount);
211 #else
212 // In some cases polygons will have only one intersection (touching corners) and because of that second SWAP never occurs,
213 // algorithm will stop only when the merged polygon is full.
214 if (polyMerged.verticeCount >= kPolygonVertexCount) {
215 flagDidMergePolygons = false;
216 break;
217 }
218 #endif
219 polyMerged.vertices[polyMerged.verticeCount] = polyLine.start;
220 polyMerged.vertexType[polyMerged.verticeCount] = polyPrimaryType;
221 ++(polyMerged.verticeCount);
222 }
223
224 flagAddVertexToVertexList = true;
225 int polySecondaryIntersectionIndex = -1;
226
227 if (linePolygonIntersection(polyLine, polyPrimaryType, polySecondary, &intersectionPoint, &polySecondaryIntersectionIndex, pathLengthSinceLastIntersection)) {
228 if (WITHIN_TOLERANCE(intersectionPoint.x, polyLine.start.x) && WITHIN_TOLERANCE(intersectionPoint.y, polyLine.start.y)) {
229 flagAddVertexToVertexList = false;
230 // TODO(madmoose): How would this work?
231 --(polyMerged.verticeCount);
232 } else {
233 // Obstacles::nop
234 }
235 vertIndex = polySecondaryIntersectionIndex;
236 flagDidFindIntersection = true;
237
238 SWAP(polyPrimary, polySecondary);
239
240 flagDidMergePolygons = true;
241 #if USE_PATHFINDING_EXPERIMENTAL_FIX_2
242 pathLengthSinceLastIntersection = 0;
243 #endif
244 } else {
245 vertIndex = (vertIndex + 1) % polyPrimary->verticeCount;
246 #if USE_PATHFINDING_EXPERIMENTAL_FIX_2
247 ++pathLengthSinceLastIntersection;
248 #endif
249 flagDidFindIntersection = false;
250 }
251 if (polyPrimary->vertices[vertIndex] == startingPolygon->vertices[0]) {
252 flagDone = true;
253 }
254 }
255
256 if (flagDidMergePolygons) {
257 *startingPolygon = polyMerged;
258 startingPolygon->isPresent = true;
259 if (startingPolygon == &polyA) {
260 polyB.isPresent = false;
261 } else {
262 polyA.isPresent = false;
263 }
264 }
265
266 return flagDidMergePolygons;
267 }
268
add(RectFloat rect)269 void Obstacles::add(RectFloat rect) {
270 int polygonIndex = findEmptyPolygon();
271 if (polygonIndex < 0) {
272 return;
273 }
274
275 rect.expand(12.0f);
276 rect.trunc_2_decimals();
277
278 Polygon &poly = _polygons[polygonIndex];
279
280 poly.rect = rect;
281
282 poly.vertices[0] = Vector2(rect.x0, rect.y0);
283 poly.vertexType[0] = TOP_LEFT;
284
285 poly.vertices[1] = Vector2(rect.x1, rect.y0);
286 poly.vertexType[1] = TOP_RIGHT;
287
288 poly.vertices[2] = Vector2(rect.x1, rect.y1);
289 poly.vertexType[2] = BOTTOM_RIGHT;
290
291 poly.vertices[3] = Vector2(rect.x0, rect.y1);
292 poly.vertexType[3] = BOTTOM_LEFT;
293
294 poly.isPresent = true;
295 poly.verticeCount = 4;
296
297 restart:
298 for (int i = 0; i < kPolygonCount; ++i) {
299 Polygon &polyA = _polygons[i];
300 if (!polyA.isPresent) {
301 continue;
302 }
303
304 if (polyA.verticeCount == 0) {
305 continue;
306 }
307
308 for (int j = i+1; j < kPolygonCount; ++j) {
309 Polygon &polyB = _polygons[j];
310 if (!polyB.isPresent) {
311 continue;
312 }
313
314 if (polyB.verticeCount == 0) {
315 continue;
316 }
317
318 if (!overlaps(polyA.rect, polyB.rect)) {
319 continue;
320 }
321
322 if (mergePolygons(polyA, polyB)) {
323 goto restart;
324 }
325 }
326 }
327 }
328
findEmptyPolygon() const329 int Obstacles::findEmptyPolygon() const {
330 for (int i = 0; i < kPolygonCount; ++i) {
331 if (!_polygons[i].isPresent) {
332 return i;
333 }
334 }
335 return -1;
336 }
337
getLength(float x0,float z0,float x1,float z1)338 float Obstacles::getLength(float x0, float z0, float x1, float z1) {
339 if (x0 == x1) {
340 return fabs(z1 - z0);
341 }
342 return fabs(x1 - x0);
343 }
344
345 #if DISABLE_PATHFINDING
findNextWaypoint(const Vector3 & from,const Vector3 & to,Vector3 * next)346 bool Obstacles::findNextWaypoint(const Vector3 &from, const Vector3 &to, Vector3 *next) {
347 *next = to;
348
349 return true;
350 }
351 #else
352
findNextWaypoint(const Vector3 & from,const Vector3 & to,Vector3 * next)353 bool Obstacles::findNextWaypoint(const Vector3 &from, const Vector3 &to, Vector3 *next) {
354 static int recursionLevel = 0;
355 static bool polygonVisited[kPolygonCount];
356
357 if (++recursionLevel == 1) {
358 clearPath();
359 for (int i = 0; i != kPolygonCount; ++i) {
360 polygonVisited[i] = false;
361 }
362 }
363
364 int polyIndex = -1;
365 int polyNearVertIndex = -1;
366 float polyNearDist = 0.0f;
367 Vector2 polyNearPos;
368 int polyFarVertIndex = -1;
369 float polyFarDist = 0.0f;
370 Vector2 polyFarPos;
371
372 for (int i = 0; i != kPolygonCount; ++i) {
373 Polygon &poly = _polygons[i];
374 if (!poly.isPresent || polygonVisited[i]) {
375 continue;
376 }
377
378 int nearVertIndex;
379 float nearDist;
380 Vector2 nearPos;
381
382 if (!findIntersectionNearest(i, from.xz(), to.xz(), &nearVertIndex, &nearDist, &nearPos)) {
383 continue;
384 }
385
386 int farVertIndex;
387 float farDist;
388 Vector2 farPos;
389
390 int hasFar = findIntersectionFarthest(i, from.xz(), to.xz(), &farVertIndex, &farDist, &farPos);
391 assert(hasFar);
392
393 if (polyIndex == -1 || nearDist < polyNearDist) {
394 polyNearDist = nearDist;
395 polyNearPos = nearPos;
396 polyFarDist = farDist;
397 polyFarPos = farPos;
398 polyIndex = i;
399 polyNearVertIndex = nearVertIndex;
400 polyFarVertIndex = farVertIndex;
401 }
402 }
403
404 if (polyIndex < 0) {
405 assert(_pathSize < kVertexCount);
406 _path[_pathSize++] = to.xz();
407 } else {
408 polygonVisited[polyIndex] = true;
409
410 if (polyNearDist == 0.0f && polyFarDist == 0.0f) {
411 assert(_pathSize < kVertexCount);
412 _path[_pathSize++] = polyNearPos;
413 } else {
414 Vector2 pathA[kMaxPathSize];
415 Vector2 pathB[kMaxPathSize];
416
417 bool pathABlocked;
418 bool pathBBlocked;
419
420 int pathASize = buildNegativePath(polyIndex, polyNearVertIndex, polyNearPos, polyFarVertIndex, polyFarPos, pathA, kMaxPathSize, &pathABlocked);
421 int pathBSize = buildPositivePath(polyIndex, polyNearVertIndex, polyNearPos, polyFarVertIndex, polyFarPos, pathB, kMaxPathSize, &pathBBlocked);
422
423 float pathATotalDistance = pathTotalDistance(pathA, pathASize, from.xz(), to.xz());
424 float pathBTotalDistance = pathTotalDistance(pathB, pathBSize, from.xz(), to.xz());
425
426 bool usePathA;
427 if (pathABlocked && !pathBBlocked) {
428 usePathA = false;
429 } else if (pathBBlocked && !pathABlocked) {
430 usePathA = true;
431 } else {
432 usePathA = pathATotalDistance <= pathBTotalDistance;
433 }
434
435 if (usePathA) {
436 assert(_pathSize + pathASize < kVertexCount);
437 for (int i = 0; i != pathASize; ++i) {
438 _path[_pathSize + i] = pathA[i];
439 }
440 _pathSize += pathASize;
441 } else {
442 assert(_pathSize + pathBSize < kVertexCount);
443 for (int i = 0; i != pathBSize; ++i) {
444 _path[_pathSize + i] = pathB[i];
445 }
446 _pathSize += pathBSize;
447 }
448 }
449 assert(_pathSize > 0);
450 Vector3 lastPathPos(_path[_pathSize - 1].x, from.y, _path[_pathSize - 1].y);
451 findNextWaypoint(lastPathPos, to, next);
452 }
453
454 if (--recursionLevel > 1) {
455 return false;
456 }
457
458 return findFarthestAvailablePathVertex(_path, _pathSize, from, next);
459 }
460 #endif
461
findIntersectionNearest(int polygonIndex,Vector2 from,Vector2 to,int * outVertexIndex,float * outDistance,Vector2 * out) const462 bool Obstacles::findIntersectionNearest(int polygonIndex, Vector2 from, Vector2 to,
463 int *outVertexIndex, float *outDistance, Vector2 *out) const
464 {
465 float minDistance = 0.0f;
466 Vector2 minIntersection;
467 int minVertexIndex = -1;
468
469 bool hasDistance = false;
470
471 for (int i = 0; i < _polygons[polygonIndex].verticeCount; ++i) {
472 int nextIndex = (i + 1) % _polygons[polygonIndex].verticeCount;
473 Vector2 *vertices = _polygons[polygonIndex].vertices;
474 Vector2 intersection;
475 bool intersects = lineIntersection(from, to, vertices[i], vertices[nextIndex], &intersection);
476 if (intersects) {
477 float distance2 = distance(from, intersection);
478 if (!hasDistance || distance2 < minDistance) {
479 minDistance = distance2;
480 minIntersection = intersection;
481 minVertexIndex = i;
482 hasDistance = true;
483 }
484 }
485 }
486
487 *outDistance = minDistance;
488 *outVertexIndex = minVertexIndex;
489 *out = minIntersection;
490
491 return minVertexIndex != -1;
492 }
493
findIntersectionFarthest(int polygonIndex,Vector2 from,Vector2 to,int * outVertexIndex,float * outDistance,Vector2 * out) const494 bool Obstacles::findIntersectionFarthest(int polygonIndex, Vector2 from, Vector2 to,
495 int *outVertexIndex, float *outDistance, Vector2 *out) const
496 {
497 float maxDistance = 0.0f;
498 Vector2 maxIntersection;
499 int maxVertexIndex = -1;
500
501 bool hasDistance = false;
502
503 for (int i = 0; i < _polygons[polygonIndex].verticeCount; ++i) {
504 int nextIndex = (i + 1) % _polygons[polygonIndex].verticeCount;
505 Vector2 *vertices = _polygons[polygonIndex].vertices;
506 Vector2 intersection;
507 bool intersects = lineIntersection(from, to, vertices[i], vertices[nextIndex], &intersection);
508 if (intersects) {
509 float distance2 = distance(from, intersection);
510 if (!hasDistance || distance2 > maxDistance) {
511 maxDistance = distance2;
512 maxIntersection = intersection;
513 maxVertexIndex = i;
514 hasDistance = true;
515 }
516 }
517 }
518
519 *outDistance = maxDistance;
520 *outVertexIndex = maxVertexIndex;
521 *out = maxIntersection;
522
523 return maxVertexIndex != -1;
524 }
525
pathTotalDistance(const Vector2 * path,int pathSize,Vector2 from,Vector2 to) const526 float Obstacles::pathTotalDistance(const Vector2 *path, int pathSize, Vector2 from, Vector2 to) const {
527 // Yes, 'to' and 'from' are ignored.
528 float totalDistance = 0.0f;
529 for (int i = 0; i != pathSize - 1; ++i) {
530 totalDistance += distance(path[i], path[i+1]);
531 }
532 return totalDistance;
533 }
534
535
findPolygonVerticeByXZ(int * polygonIndex,int * verticeIndex,int * verticeCount,float x,float z) const536 bool Obstacles::findPolygonVerticeByXZ(int *polygonIndex, int *verticeIndex, int *verticeCount, float x, float z) const {
537 *polygonIndex = -1;
538 *verticeIndex = -1;
539 *verticeCount = -1;
540
541 for (int i = 0; i != kPolygonCount; ++i) {
542 if (!_polygons[i].isPresent || _polygons[i].verticeCount == 0) {
543 continue;
544 }
545
546 for (int j = 0; j != _polygons[i].verticeCount; ++j) {
547 if (_polygons[i].vertices[j].x == x && _polygons[i].vertices[j].y == z) {
548 *polygonIndex = i;
549 *verticeIndex = j;
550 *verticeCount = _polygons[i].verticeCount;
551 return true;
552 }
553 }
554 }
555
556 return false;
557 }
558
findPolygonVerticeByXZWithinTolerance(float x,float z,int * polygonIndex,int * verticeIndex,int startSearchFromPolygonIdx) const559 bool Obstacles::findPolygonVerticeByXZWithinTolerance(float x, float z, int *polygonIndex, int *verticeIndex, int startSearchFromPolygonIdx) const {
560 *polygonIndex = -1;
561 *verticeIndex = -1;
562
563 // for (int i = 0; i != kPolygonCount; ++i) {
564 for (int countUp = 0, i = startSearchFromPolygonIdx; countUp != kPolygonCount; ++countUp, ++i) {
565 i = i % kPolygonCount; // we want to circle around to go through all polygons
566 if (!_polygons[i].isPresent || _polygons[i].verticeCount == 0) {
567 continue;
568 }
569
570 for (int j = 0; j != _polygons[i].verticeCount; ++j) {
571 if (WITHIN_TOLERANCE(_polygons[i].vertices[j].x, x) && WITHIN_TOLERANCE(_polygons[i].vertices[j].y, z)) {
572 *polygonIndex = i;
573 *verticeIndex = j;
574 return true;
575 }
576 }
577 }
578
579 return false;
580 }
581
clearPath()582 void Obstacles::clearPath() {
583 _pathSize = 0;
584 }
585
buildNegativePath(int polyIndex,int vertStartIndex,Vector2 startPos,int vertEndIndex,Vector2 endPos,Vector2 * path,int pathCapacity,bool * pathBlocked)586 int Obstacles::buildNegativePath(int polyIndex, int vertStartIndex, Vector2 startPos, int vertEndIndex, Vector2 endPos, Vector2 *path, int pathCapacity, bool *pathBlocked) {
587 int pathSize = 0;
588 *pathBlocked = false;
589 Polygon *poly = &_polygons[polyIndex];
590
591 /* Add start position to path */
592 if (_vm->_scene->_set->findWalkbox(startPos.x, startPos.y) == -1) {
593 *pathBlocked = true;
594 }
595 assert(pathSize < pathCapacity);
596 path[pathSize++] = startPos;
597
598 int i = vertStartIndex;
599
600 /* Add polygon vertices in negative iteration order */
601 while (true) {
602 Vector2 v = poly->vertices[i];
603 if (_vm->_scene->_set->findWalkbox(v.x, v.y) == -1) {
604 *pathBlocked = true;
605 }
606
607 assert(pathSize < pathCapacity);
608 path[pathSize++] = v;
609
610 i = (i + poly->verticeCount - 1) % poly->verticeCount;
611 if (i == vertEndIndex) {
612 break;
613 }
614 }
615
616 /* Add end position to path */
617 if (_vm->_scene->_set->findWalkbox(endPos.x, endPos.y) == -1) {
618 *pathBlocked = true;
619 }
620 assert(pathSize < pathCapacity);
621 path[pathSize++] = endPos;
622
623 return pathSize;
624 }
625
buildPositivePath(int polyIndex,int vertStartIndex,Vector2 startPos,int vertEndIndex,Vector2 endPos,Vector2 * path,int pathCapacity,bool * pathBlocked)626 int Obstacles::buildPositivePath(int polyIndex, int vertStartIndex, Vector2 startPos, int vertEndIndex, Vector2 endPos, Vector2 *path, int pathCapacity, bool *pathBlocked) {
627 int pathSize = 0;
628 *pathBlocked = false;
629 Polygon *poly = &_polygons[polyIndex];
630
631 /* Add start position to path */
632 if (_vm->_scene->_set->findWalkbox(startPos.x, startPos.y) == -1) {
633 *pathBlocked = true;
634 }
635 assert(pathSize < pathCapacity);
636 path[pathSize++] = startPos;
637
638 int i = (vertStartIndex + 1) % poly->verticeCount;
639
640 /* Add polygon vertices in positive iteration order */
641 while (true) {
642 Vector2 v = poly->vertices[i];
643 if (_vm->_scene->_set->findWalkbox(v.x, v.y) == -1) {
644 *pathBlocked = true;
645 }
646
647 assert(pathSize < pathCapacity);
648 path[pathSize++] = v;
649
650 if (i == vertEndIndex) {
651 break;
652 }
653
654 i = (i + 1) % poly->verticeCount;
655 }
656
657 /* Add end position to path */
658 if (_vm->_scene->_set->findWalkbox(endPos.x, endPos.y) == -1) {
659 *pathBlocked = true;
660 }
661 assert(pathSize < pathCapacity);
662 path[pathSize++] = endPos;
663
664 return pathSize;
665 }
666
verticesCanIntersect(int lineType0,int lineType1,float x0,float y0,float x1,float y1) const667 bool Obstacles::verticesCanIntersect(int lineType0, int lineType1, float x0, float y0, float x1, float y1) const {
668 if (lineType0 == TOP_LEFT && lineType1 == TOP_RIGHT) {
669 if (x0 > x1 && y0 < y1) return true;
670 }
671 if (lineType0 == TOP_RIGHT && lineType1 == BOTTOM_RIGHT) {
672 if (x0 > x1 && y0 > y1) return true;
673 }
674 if (lineType0 == BOTTOM_RIGHT && lineType1 == BOTTOM_LEFT) {
675 if (x0 < x1 && y0 > y1) return true;
676 }
677 if (lineType0 == BOTTOM_LEFT && lineType1 == TOP_LEFT) {
678 if (x0 < x1 && y0 < y1) return true;
679 }
680 if (lineType0 == TOP_RIGHT && lineType1 == TOP_LEFT) {
681 if (x0 > x1 || y0 < y1) return true;
682 }
683 if (lineType0 == BOTTOM_RIGHT && lineType1 == TOP_RIGHT) {
684 if (x0 > x1 || y0 > y1) return true;
685 }
686 if (lineType0 == BOTTOM_LEFT && lineType1 == BOTTOM_RIGHT) {
687 if (x0 < x1 || y0 > y1) return true;
688 }
689 if (lineType0 == TOP_LEFT && lineType1 == BOTTOM_LEFT) {
690 if (x0 < x1 || y0 < y1) return true;
691 }
692 return false;
693 }
694
findFarthestAvailablePathVertex(Vector2 * path,int pathSize,Vector3 start,Vector3 * next) const695 bool Obstacles::findFarthestAvailablePathVertex(Vector2 *path, int pathSize, Vector3 start, Vector3 *next) const {
696 if (pathSize == 0) {
697 *next = start;
698 return false;
699 }
700
701 int vertexTypeStart = -1;
702 int vertexTypeStartPrev = -1;
703 int polygonIndexStart = -1;
704 int vertexIndexStart = -1;
705 bool startOnPolygon = findPolygonVerticeByXZWithinTolerance(start.x, start.z, &polygonIndexStart, &vertexIndexStart, 0);
706 if (startOnPolygon) {
707 int vertexIndexStartPrev = (vertexIndexStart - 1 + _polygons[polygonIndexStart].verticeCount) % _polygons[polygonIndexStart].verticeCount;
708
709 vertexTypeStart = _polygons[polygonIndexStart].vertexType[vertexIndexStart];
710 vertexTypeStartPrev = _polygons[polygonIndexStart].vertexType[vertexIndexStartPrev];
711 }
712
713 signed int farthestPathIndex = -1;
714 for (int pathVertexIdx = 0; pathVertexIdx < pathSize; ++pathVertexIdx) {
715 bool foundVertexNeighbor = false;
716 int polygonIndexPath = -1;
717 int vertexIndexPath = -1;
718 bool pathVertexOnPolygon = findPolygonVerticeByXZWithinTolerance(path[pathVertexIdx].x, path[pathVertexIdx].y, &polygonIndexPath, &vertexIndexPath, 0) == 1;
719
720 //start and current path vertices are on same polygon and are next to each other
721 if (pathVertexOnPolygon && polygonIndexStart == polygonIndexPath) {
722 int vertexIndexStartPrev = (vertexIndexStart - 1 + _polygons[polygonIndexPath].verticeCount) % _polygons[polygonIndexPath].verticeCount;
723 int vertexIndexStartNext = (vertexIndexStart + 1 ) % _polygons[polygonIndexPath].verticeCount;
724
725 if (vertexIndexPath == vertexIndexStartNext || vertexIndexPath == vertexIndexStartPrev || vertexIndexPath == vertexIndexStart) {
726 foundVertexNeighbor = true;
727 }
728 }
729
730 // neighboring vertices are always available
731 if (foundVertexNeighbor) {
732 farthestPathIndex = pathVertexIdx;
733 continue;
734 }
735
736 bool pathVertexAvailable = true;
737 for (int currentPolygonIdx = 0; currentPolygonIdx < kPolygonCount && pathVertexAvailable; ++currentPolygonIdx) {
738 Polygon *polygon = &_polygons[currentPolygonIdx];
739
740 if (!polygon->isPresent || polygon->verticeCount == 0) {
741 continue;
742 }
743
744 for (int polygonVertexIdx = 0; polygonVertexIdx < polygon->verticeCount && pathVertexAvailable; ++polygonVertexIdx) {
745 int polygonVertexNextIdx = (polygonVertexIdx + 1) % polygon->verticeCount;
746
747 // check intersection between start -> path and polygon edge
748 Vector2 intersection;
749 if (!lineIntersection(Vector2(start.x, start.z), path[pathVertexIdx], polygon->vertices[polygonVertexIdx], polygon->vertices[polygonVertexNextIdx], &intersection)) {
750 continue;
751 }
752
753 // intersection has to be at end of one of these points (either on this polygon or on the path or at start)
754 if (!(
755 (WITHIN_TOLERANCE(intersection.x, start.x) && WITHIN_TOLERANCE(intersection.y, start.z) )
756 || (WITHIN_TOLERANCE(intersection.x, path[pathVertexIdx].x) && WITHIN_TOLERANCE(intersection.y, path[pathVertexIdx].y) )
757 || (WITHIN_TOLERANCE(intersection.x, polygon->vertices[polygonVertexIdx].x) && WITHIN_TOLERANCE(intersection.y, polygon->vertices[polygonVertexIdx].y) )
758 || (WITHIN_TOLERANCE(intersection.x, polygon->vertices[polygonVertexNextIdx].x) && WITHIN_TOLERANCE(intersection.y, polygon->vertices[polygonVertexNextIdx].y))
759 )) {
760 pathVertexAvailable = false;
761 break;
762 }
763
764 int polygonIndexIntersection = -1;
765 int vertexIndexIntersection = -1;
766 if (findPolygonVerticeByXZWithinTolerance(intersection.x, intersection.y, &polygonIndexIntersection, &vertexIndexIntersection, currentPolygonIdx)) {
767 // Intersection has to be vertex only on current polygon
768 // Part of pathfinding fix 2 (dealing with merge on only one edge point)
769 // but also speeds up process:
770 // we start (a cyclical) searching in Polygons array
771 // beginning from the current polygon index
772 assert(polygonIndexIntersection == currentPolygonIdx);
773
774 if (verticesCanIntersect(vertexTypeStartPrev, vertexTypeStart, start.x, start.z, path[pathVertexIdx].x, path[pathVertexIdx].y)) {
775 pathVertexAvailable = false;
776 break;
777 }
778
779 if ((currentPolygonIdx == polygonIndexPath && vertexIndexIntersection == vertexIndexPath)
780 || (currentPolygonIdx == polygonIndexStart && vertexIndexIntersection == vertexIndexStart)
781 ) {
782 continue;
783 }
784
785 int vertexIndexIntersectionprev = (vertexIndexIntersection - 1 + _polygons[polygonIndexIntersection].verticeCount ) % _polygons[polygonIndexIntersection].verticeCount;
786 if (verticesCanIntersect(_polygons[polygonIndexIntersection].vertexType[vertexIndexIntersectionprev], _polygons[polygonIndexIntersection].vertexType[vertexIndexIntersection], intersection.x, intersection.y, path[pathVertexIdx].x, path[pathVertexIdx].y)) {
787 pathVertexAvailable = false;
788 break;
789 }
790 } else {
791 bool startIntersectionWithinTolerance = false;
792 if (WITHIN_TOLERANCE(intersection.x, start.x)
793 && WITHIN_TOLERANCE(intersection.y, start.z)
794 ) {
795 startIntersectionWithinTolerance = true;
796 }
797
798 if (currentPolygonIdx == polygonIndexStart || startIntersectionWithinTolerance) {
799 if (polygonIndexStart >= 0 || !startIntersectionWithinTolerance) {
800 pathVertexAvailable = false;
801 break;
802 }
803
804 int polygonVertexType = polygon->vertexType[polygonVertexIdx];
805 if ((polygonVertexType == TOP_LEFT && intersection.y < path[pathVertexIdx].y)
806 || (polygonVertexType == TOP_RIGHT && intersection.x > path[pathVertexIdx].x)
807 || (polygonVertexType == BOTTOM_RIGHT && intersection.y > path[pathVertexIdx].y)
808 || (polygonVertexType == BOTTOM_LEFT && intersection.x < path[pathVertexIdx].x)
809 ) {
810 pathVertexAvailable = false;
811 break;
812 }
813 }
814 }
815 }
816 }
817
818 if (pathVertexAvailable) {
819 farthestPathIndex = pathVertexIdx;
820 }
821 }
822
823 if (farthestPathIndex == -1) {
824 *next = start;
825 return false;
826 }
827
828 next->x = path[farthestPathIndex].x;
829 next->z = path[farthestPathIndex].y;
830
831 bool walkboxFound;
832 float walkboxAltitude = _vm->_scene->_set->getAltitudeAtXZ(next->x, next->z, &walkboxFound);
833
834 if (walkboxFound) {
835 next->y = walkboxAltitude;
836 return true;
837 } else {
838 next->y = start.y;
839 return false;
840 }
841 }
842
backup()843 void Obstacles::backup() {
844 for (int i = 0; i != kPolygonCount; ++i) {
845 _polygonsBackup[i].isPresent = false;
846 }
847
848 int count = 0;
849 for (int i = 0; i != kPolygonCount; ++i) {
850 if (_polygons[i].isPresent) {
851 _polygonsBackup[count] = _polygons[i];
852 ++count;
853 }
854 }
855
856 for (int i = 0; i != kPolygonCount; ++i) {
857 _polygons[i] = _polygonsBackup[count];
858 }
859
860 _count = count;
861 _backup = true;
862 }
863
restore()864 void Obstacles::restore() {
865 for (int i = 0; i != kPolygonCount; ++i) {
866 _polygons[i].isPresent = false;
867 }
868 for (int i = 0; i != kPolygonCount; ++i) {
869 _polygons[i] = _polygonsBackup[i];
870 }
871 }
872
save(SaveFileWriteStream & f)873 void Obstacles::save(SaveFileWriteStream &f) {
874 f.writeBool(_backup);
875 f.writeInt(_count);
876 for (int i = 0; i < _count; ++i) {
877 Polygon &p = _polygonsBackup[i];
878 f.writeBool(p.isPresent);
879 f.writeInt(p.verticeCount);
880 f.writeFloat(p.rect.x0);
881 f.writeFloat(p.rect.y0);
882 f.writeFloat(p.rect.x1);
883 f.writeFloat(p.rect.y1);
884 for (int j = 0; j < kPolygonVertexCount; ++j) {
885 f.writeVector2(p.vertices[j]);
886 }
887 for (int j = 0; j < kPolygonVertexCount; ++j) {
888 f.writeInt(p.vertexType[j]);
889 }
890 }
891 for (int i = 0; i < kVertexCount; ++i) {
892 f.writeVector2(_path[i]);
893 }
894 f.writeInt(_pathSize);
895 }
896
load(SaveFileReadStream & f)897 void Obstacles::load(SaveFileReadStream &f) {
898 for (int i = 0; i < kPolygonCount; ++i) {
899 _polygons[i].isPresent = false;
900 _polygons[i].verticeCount = 0;
901 _polygonsBackup[i].isPresent = false;
902 _polygonsBackup[i].verticeCount = 0;
903 }
904
905 _backup = f.readBool();
906 _count = f.readInt();
907 for (int i = 0; i < _count; ++i) {
908 Polygon &p = _polygonsBackup[i];
909 p.isPresent = f.readBool();
910 p.verticeCount = f.readInt();
911 p.rect.x0 = f.readFloat();
912 p.rect.y0 = f.readFloat();
913 p.rect.x1 = f.readFloat();
914 p.rect.y1 = f.readFloat();
915 for (int j = 0; j < kPolygonVertexCount; ++j) {
916 p.vertices[j] = f.readVector2();
917 }
918 for (int j = 0; j < kPolygonVertexCount; ++j) {
919 p.vertexType[j] = (VertexType)f.readInt();
920 }
921 }
922
923 for (int i = 0; i < kPolygonCount; ++i) {
924 _polygons[i] = _polygonsBackup[i];
925 }
926
927 for (int i = 0; i < kVertexCount; ++i) {
928 _path[i] = f.readVector2();
929 }
930 _pathSize = f.readInt();
931 }
932
draw()933 void Obstacles::draw() {
934 float y = _vm->_playerActor->getY();
935
936 for (int i = 0; i != kPolygonCount; ++i) {
937 if (!_polygons[i].isPresent) {
938 continue;
939 }
940
941 Vector3 p0 = _vm->_view->calculateScreenPosition(Vector3(
942 _polygons[i].vertices[_polygons[i].verticeCount - 1].x,
943 y,
944 _polygons[i].vertices[_polygons[i].verticeCount - 1].y
945 ));
946
947 for (int j = 0; j != _polygons[i].verticeCount; ++j) {
948 Vector3 p1 = _vm->_view->calculateScreenPosition(Vector3(
949 _polygons[i].vertices[j].x,
950 y,
951 _polygons[i].vertices[j].y
952 ));
953
954 _vm->_surfaceFront.drawLine(p0.x, p0.y, p1.x, p1.y, _vm->_surfaceFront.format.RGBToColor(255, 255, 255));
955
956 p0 = p1;
957 }
958 }
959
960 // draw actor's box
961 {
962 Vector3 playerPos = _vm->_playerActor->getXYZ();
963 Vector3 p0 = _vm->_view->calculateScreenPosition(playerPos + Vector3(-12.0f, 0.0f, -12.0f));
964 Vector3 p1 = _vm->_view->calculateScreenPosition(playerPos + Vector3( 12.0f, 0.0f, -12.0f));
965 Vector3 p2 = _vm->_view->calculateScreenPosition(playerPos + Vector3( 12.0f, 0.0f, 12.0f));
966 Vector3 p3 = _vm->_view->calculateScreenPosition(playerPos + Vector3(-12.0f, 0.0f, 12.0f));
967
968 _vm->_surfaceFront.drawLine(p0.x, p0.y, p1.x, p1.y, _vm->_surfaceFront.format.RGBToColor(255, 0, 0));
969 _vm->_surfaceFront.drawLine(p1.x, p1.y, p2.x, p2.y, _vm->_surfaceFront.format.RGBToColor(255, 0, 0));
970 _vm->_surfaceFront.drawLine(p2.x, p2.y, p3.x, p3.y, _vm->_surfaceFront.format.RGBToColor(255, 0, 0));
971 _vm->_surfaceFront.drawLine(p3.x, p3.y, p0.x, p0.y, _vm->_surfaceFront.format.RGBToColor(255, 0, 0));
972 }
973
974 // draw path along polygons
975 for (int i = 1; i < _pathSize; ++i) {
976 Vector3 p0 = _vm->_view->calculateScreenPosition(Vector3(_path[i - 1].x, y, _path[i - 1].y));
977 Vector3 p1 = _vm->_view->calculateScreenPosition(Vector3(_path[i].x, y, _path[i].y));
978 _vm->_surfaceFront.drawLine(p0.x, p0.y, p1.x, p1.y, _vm->_surfaceFront.format.RGBToColor(255, 0, 0));
979 }
980
981 // draw "next" vertex
982 {
983 //TODO
984 }
985
986
987 }
988
989 } // End of namespace BladeRunner
990