aboutsummaryrefslogtreecommitdiff
path: root/engines/toon/path.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'engines/toon/path.cpp')
-rw-r--r--engines/toon/path.cpp267
1 files changed, 115 insertions, 152 deletions
diff --git a/engines/toon/path.cpp b/engines/toon/path.cpp
index 2dd5fc45e2..7914aed595 100644
--- a/engines/toon/path.cpp
+++ b/engines/toon/path.cpp
@@ -60,12 +60,12 @@ void PathFindingHeap::clear() {
memset(_data, 0, sizeof(HeapDataGrid) * _size);
}
-void PathFindingHeap::push(int32 x, int32 y, int32 weight) {
+void PathFindingHeap::push(int16 x, int16 y, uint16 weight) {
debugC(2, kDebugPath, "push(%d, %d, %d)", x, y, weight);
if (_count == _size) {
// Increase size by 50%
- int newSize = _size + (_size >> 1) + 1;
+ uint32 newSize = _size + (_size / 2) + 1;
HeapDataGrid *newData;
newData = (HeapDataGrid *)realloc(_data, sizeof(HeapDataGrid) * newSize);
@@ -84,13 +84,13 @@ void PathFindingHeap::push(int32 x, int32 y, int32 weight) {
_data[_count]._weight = weight;
_count++;
- int32 lMax = _count-1;
- int32 lT = 0;
+ uint32 lMax = _count - 1;
+ uint32 lT = 0;
- while (1) {
+ while (true) {
if (lMax <= 0)
break;
- lT = (lMax-1) / 2;
+ lT = (lMax - 1) / 2;
if (_data[lT]._weight > _data[lMax]._weight) {
HeapDataGrid temp;
@@ -104,7 +104,7 @@ void PathFindingHeap::push(int32 x, int32 y, int32 weight) {
}
}
-void PathFindingHeap::pop(int32 *x, int32 *y, int32 *weight) {
+void PathFindingHeap::pop(int16 *x, int16 *y, uint16 *weight) {
debugC(2, kDebugPath, "pop(x, y, weight)");
if (!_count) {
@@ -120,13 +120,13 @@ void PathFindingHeap::pop(int32 *x, int32 *y, int32 *weight) {
if (!_count)
return;
- int32 lMin = 0;
- int32 lT = 0;
+ uint32 lMin = 0;
+ uint32 lT = 0;
- while (1) {
- lT = (lMin << 1) + 1;
+ while (true) {
+ lT = (lMin * 2) + 1;
if (lT < _count) {
- if (lT < _count-1) {
+ if (lT < _count - 1) {
if (_data[lT + 1]._weight < _data[lT]._weight)
lT++;
}
@@ -146,11 +146,11 @@ void PathFindingHeap::pop(int32 *x, int32 *y, int32 *weight) {
}
}
-PathFinding::PathFinding(ToonEngine *vm) : _vm(vm) {
+PathFinding::PathFinding() {
_width = 0;
_height = 0;
_heap = new PathFindingHeap();
- _gridTemp = NULL;
+ _sq = NULL;
_numBlockingRects = 0;
}
@@ -158,17 +158,29 @@ PathFinding::~PathFinding(void) {
if (_heap)
_heap->unload();
delete _heap;
- delete[] _gridTemp;
+ delete[] _sq;
}
-bool PathFinding::isLikelyWalkable(int32 x, int32 y) {
- for (int32 i = 0; i < _numBlockingRects; i++) {
+void PathFinding::init(Picture *mask) {
+ debugC(1, kDebugPath, "init(mask)");
+
+ _width = mask->getWidth();
+ _height = mask->getHeight();
+ _currentMask = mask;
+ _heap->unload();
+ _heap->init(500);
+ delete[] _sq;
+ _sq = new uint16[_width * _height];
+}
+
+bool PathFinding::isLikelyWalkable(int16 x, int16 y) {
+ for (uint8 i = 0; i < _numBlockingRects; i++) {
if (_blockingRects[i][4] == 0) {
if (x >= _blockingRects[i][0] && x <= _blockingRects[i][2] && y >= _blockingRects[i][1] && y < _blockingRects[i][3])
return false;
} else {
- int32 dx = abs(_blockingRects[i][0] - x);
- int32 dy = abs(_blockingRects[i][1] - y);
+ int16 dx = abs(_blockingRects[i][0] - x);
+ int16 dy = abs(_blockingRects[i][1] - y);
if ((dx << 8) / _blockingRects[i][2] < (1 << 8) && (dy << 8) / _blockingRects[i][3] < (1 << 8)) {
return false;
}
@@ -177,15 +189,13 @@ bool PathFinding::isLikelyWalkable(int32 x, int32 y) {
return true;
}
-bool PathFinding::isWalkable(int32 x, int32 y) {
+bool PathFinding::isWalkable(int16 x, int16 y) {
debugC(2, kDebugPath, "isWalkable(%d, %d)", x, y);
- bool maskWalk = (_currentMask->getData(x, y) & 0x1f) > 0;
-
- return maskWalk;
+ return (_currentMask->getData(x, y) & 0x1f) > 0;
}
-int32 PathFinding::findClosestWalkingPoint(int32 xx, int32 yy, int32 *fxx, int32 *fyy, int origX, int origY) {
+bool PathFinding::findClosestWalkingPoint(int16 xx, int16 yy, int16 *fxx, int16 *fyy, int16 origX, int16 origY) {
debugC(1, kDebugPath, "findClosestWalkingPoint(%d, %d, fxx, fyy, %d, %d)", xx, yy, origX, origY);
int32 currentFound = -1;
@@ -197,8 +207,8 @@ int32 PathFinding::findClosestWalkingPoint(int32 xx, int32 yy, int32 *fxx, int32
if (origY == -1)
origY = yy;
- for (int y = 0; y < _height; y++) {
- for (int x = 0; x < _width; x++) {
+ for (int16 y = 0; y < _height; y++) {
+ for (int16 x = 0; x < _width; x++) {
if (isWalkable(x, y) && isLikelyWalkable(x, y)) {
int32 ndist = (x - xx) * (x - xx) + (y - yy) * (y - yy);
int32 ndist2 = (x - origX) * (x - origX) + (y - origY) * (y - origY);
@@ -214,15 +224,15 @@ int32 PathFinding::findClosestWalkingPoint(int32 xx, int32 yy, int32 *fxx, int32
if (currentFound != -1) {
*fxx = currentFound % _width;
*fyy = currentFound / _width;
- return 1;
+ return true;
} else {
*fxx = 0;
*fyy = 0;
- return 0;
+ return false;
}
}
-bool PathFinding::walkLine(int32 x, int32 y, int32 x2, int32 y2) {
+void PathFinding::walkLine(int16 x, int16 y, int16 x2, int16 y2) {
uint32 bx = x << 16;
int32 dx = x2 - x;
uint32 by = y << 16;
@@ -238,24 +248,17 @@ bool PathFinding::walkLine(int32 x, int32 y, int32 x2, int32 y2) {
int32 cdx = (dx << 16) / t;
int32 cdy = (dy << 16) / t;
- int32 i = t;
- _gridPathCount = 0;
- while (i) {
- _tempPathX[i] = bx >> 16;
- _tempPathY[i] = by >> 16;
- _gridPathCount++;
+ _tempPath.clear();
+ for (int32 i = t; i > 0; i--) {
+ _tempPath.insert_at(0, Common::Point(bx >> 16, by >> 16));
bx += cdx;
by += cdy;
- i--;
}
- _tempPathX[0] = x2;
- _tempPathY[0] = y2;
-
- return true;
+ _tempPath.insert_at(0, Common::Point(x2, y2));
}
-bool PathFinding::lineIsWalkable(int32 x, int32 y, int32 x2, int32 y2) {
+bool PathFinding::lineIsWalkable(int16 x, int16 y, int16 x2, int16 y2) {
uint32 bx = x << 16;
int32 dx = x2 - x;
uint32 by = y << 16;
@@ -271,27 +274,26 @@ bool PathFinding::lineIsWalkable(int32 x, int32 y, int32 x2, int32 y2) {
int32 cdx = (dx << 16) / t;
int32 cdy = (dy << 16) / t;
- int32 i = t;
- while (i) {
+ for (int32 i = t; i > 0; i--) {
if (!isWalkable(bx >> 16, by >> 16))
return false;
bx += cdx;
by += cdy;
- i--;
}
return true;
}
-int32 PathFinding::findPath(int32 x, int32 y, int32 destx, int32 desty) {
+
+bool PathFinding::findPath(int16 x, int16 y, int16 destx, int16 desty) {
debugC(1, kDebugPath, "findPath(%d, %d, %d, %d)", x, y, destx, desty);
if (x == destx && y == desty) {
- _gridPathCount = 0;
+ _tempPath.clear();
return true;
}
// ignore path finding if the character is outside the screen
if (x < 0 || x > 1280 || y < 0 || y > 400 || destx < 0 || destx > 1280 || desty < 0 || desty > 400) {
- _gridPathCount = 0;
+ _tempPath.clear();
return true;
}
@@ -302,40 +304,45 @@ int32 PathFinding::findPath(int32 x, int32 y, int32 destx, int32 desty) {
}
// no direct line, we use the standard A* algorithm
- memset(_gridTemp , 0, _width * _height * sizeof(int32));
+ memset(_sq , 0, _width * _height * sizeof(uint16));
_heap->clear();
- int32 curX = x;
- int32 curY = y;
- int32 curWeight = 0;
- int32 *sq = _gridTemp;
+ int16 curX = x;
+ int16 curY = y;
+ uint16 curWeight = 0;
- sq[curX + curY *_width] = 1;
+ _sq[curX + curY *_width] = 1;
_heap->push(curX, curY, abs(destx - x) + abs(desty - y));
- int wei = 0;
while (_heap->getCount()) {
- wei = 0;
_heap->pop(&curX, &curY, &curWeight);
- int curNode = curX + curY * _width;
+ int32 curNode = curX + curY * _width;
- int32 endX = MIN<int32>(curX + 1, _width - 1);
- int32 endY = MIN<int32>(curY + 1, _height - 1);
- int32 startX = MAX<int32>(curX - 1, 0);
- int32 startY = MAX<int32>(curY - 1, 0);
+ int16 endX = MIN<int16>(curX + 1, _width - 1);
+ int16 endY = MIN<int16>(curY + 1, _height - 1);
+ int16 startX = MAX<int16>(curX - 1, 0);
+ int16 startY = MAX<int16>(curY - 1, 0);
bool next = false;
- for (int32 px = startX; px <= endX && !next; px++) {
- for (int py = startY; py <= endY && !next; py++) {
+ for (int16 px = startX; px <= endX && !next; px++) {
+ for (int16 py = startY; py <= endY && !next; py++) {
if (px != curX || py != curY) {
- wei = ((abs(px - curX) + abs(py - curY)));
+ uint16 wei = abs(px - curX) + abs(py - curY);
- int32 curPNode = px + py * _width;
if (isWalkable(px, py)) { // walkable ?
- int sum = sq[curNode] + wei * (1 + (isLikelyWalkable(px, py) ? 5 : 0));
- if (sq[curPNode] > sum || !sq[curPNode]) {
- int newWeight = abs(destx - px) + abs(desty - py);
- sq[curPNode] = sum;
- _heap->push(px, py, sq[curPNode] + newWeight);
+ int32 curPNode = px + py * _width;
+ uint32 sum = _sq[curNode] + wei * (1 + (isLikelyWalkable(px, py) ? 5 : 0));
+ if (sum > (uint32)0xFFFF) {
+ warning("PathFinding::findPath sum exceeds maximum representable!");
+ sum = (uint32)0xFFFF;
+ }
+ if (_sq[curPNode] > sum || !_sq[curPNode]) {
+ _sq[curPNode] = sum;
+ uint32 newWeight = _sq[curPNode] + abs(destx - px) + abs(desty - py);
+ if (newWeight > (uint32)0xFFFF) {
+ warning("PathFinding::findPath newWeight exceeds maximum representable!");
+ newWeight = (uint16)0xFFFF;
+ }
+ _heap->push(px, py, newWeight);
if (!newWeight)
next = true; // we found it !
}
@@ -346,49 +353,37 @@ int32 PathFinding::findPath(int32 x, int32 y, int32 destx, int32 desty) {
}
// let's see if we found a result !
- if (!_gridTemp[destx + desty * _width]) {
+ if (!_sq[destx + desty * _width]) {
// didn't find anything
- _gridPathCount = 0;
+ _tempPath.clear();
return false;
}
curX = destx;
curY = desty;
- int32 *retPathX = (int32 *)malloc(4096 * sizeof(int32));
- int32 *retPathY = (int32 *)malloc(4096 * sizeof(int32));
- if (!retPathX || !retPathY) {
- free(retPathX);
- free(retPathY);
-
- error("[PathFinding::findPath] Cannot allocate pathfinding buffers");
- }
-
- int32 numpath = 0;
+ Common::Array<Common::Point> retPath;
+ retPath.push_back(Common::Point(curX, curY));
- retPathX[numpath] = curX;
- retPathY[numpath] = curY;
- numpath++;
- int32 bestscore = sq[destx + desty * _width];
+ uint16 bestscore = _sq[destx + desty * _width];
- while (1) {
- int32 bestX = -1;
- int32 bestY = -1;
+ bool retVal = false;
+ while (true) {
+ int16 bestX = -1;
+ int16 bestY = -1;
- int32 endX = MIN<int32>(curX + 1, _width - 1);
- int32 endY = MIN<int32>(curY + 1, _height - 1);
- int32 startX = MAX<int32>(curX - 1, 0);
- int32 startY = MAX<int32>(curY - 1, 0);
+ int16 endX = MIN<int16>(curX + 1, _width - 1);
+ int16 endY = MIN<int16>(curY + 1, _height - 1);
+ int16 startX = MAX<int16>(curX - 1, 0);
+ int16 startY = MAX<int16>(curY - 1, 0);
- for (int32 px = startX; px <= endX; px++) {
- for (int32 py = startY; py <= endY; py++) {
+ for (int16 px = startX; px <= endX; px++) {
+ for (int16 py = startY; py <= endY; py++) {
if (px != curX || py != curY) {
- wei = abs(px - curX) + abs(py - curY);
-
- int PNode = px + py * _width;
- if (sq[PNode] && (isWalkable(px, py))) {
- if (sq[PNode] < bestscore) {
- bestscore = sq[PNode];
+ int32 PNode = px + py * _width;
+ if (_sq[PNode] && (isWalkable(px, py))) {
+ if (_sq[PNode] < bestscore) {
+ bestscore = _sq[PNode];
bestX = px;
bestY = py;
}
@@ -397,57 +392,33 @@ int32 PathFinding::findPath(int32 x, int32 y, int32 destx, int32 desty) {
}
}
- if (bestX < 0 || bestY < 0) {
- free(retPathX);
- free(retPathY);
-
- return 0;
- }
+ if (bestX < 0 || bestY < 0)
+ break;
- retPathX[numpath] = bestX;
- retPathY[numpath] = bestY;
- numpath++;
+ retPath.push_back(Common::Point(bestX, bestY));
if ((bestX == x && bestY == y)) {
- _gridPathCount = numpath;
-
- memcpy(_tempPathX, retPathX, sizeof(int32) * numpath);
- memcpy(_tempPathY, retPathY, sizeof(int32) * numpath);
-
- free(retPathX);
- free(retPathY);
+ _tempPath.clear();
+ for (uint32 i = 0; i < retPath.size(); i++)
+ _tempPath.push_back(retPath[i]);
- return true;
+ retVal = true;
+ break;
}
curX = bestX;
curY = bestY;
}
- free(retPathX);
- free(retPathY);
-
- return false;
+ return retVal;
}
-void PathFinding::init(Picture *mask) {
- debugC(1, kDebugPath, "init(mask)");
-
- _width = mask->getWidth();
- _height = mask->getHeight();
- _currentMask = mask;
- _heap->unload();
- _heap->init(500);
- delete[] _gridTemp;
- _gridTemp = new int32[_width*_height];
-}
-
-void PathFinding::resetBlockingRects() {
- _numBlockingRects = 0;
-}
-
-void PathFinding::addBlockingRect(int32 x1, int32 y1, int32 x2, int32 y2) {
+void PathFinding::addBlockingRect(int16 x1, int16 y1, int16 x2, int16 y2) {
debugC(1, kDebugPath, "addBlockingRect(%d, %d, %d, %d)", x1, y1, x2, y2);
+ if (_numBlockingRects >= kMaxBlockingRects) {
+ warning("Maximum number of %d Blocking Rects reached!", kMaxBlockingRects);
+ return;
+ }
_blockingRects[_numBlockingRects][0] = x1;
_blockingRects[_numBlockingRects][1] = y1;
@@ -457,8 +428,12 @@ void PathFinding::addBlockingRect(int32 x1, int32 y1, int32 x2, int32 y2) {
_numBlockingRects++;
}
-void PathFinding::addBlockingEllipse(int32 x1, int32 y1, int32 w, int32 h) {
- debugC(1, kDebugPath, "addBlockingRect(%d, %d, %d, %d)", x1, y1, w, h);
+void PathFinding::addBlockingEllipse(int16 x1, int16 y1, int16 w, int16 h) {
+ debugC(1, kDebugPath, "addBlockingEllipse(%d, %d, %d, %d)", x1, y1, w, h);
+ if (_numBlockingRects >= kMaxBlockingRects) {
+ warning("Maximum number of %d Blocking Rects reached!", kMaxBlockingRects);
+ return;
+ }
_blockingRects[_numBlockingRects][0] = x1;
_blockingRects[_numBlockingRects][1] = y1;
@@ -468,16 +443,4 @@ void PathFinding::addBlockingEllipse(int32 x1, int32 y1, int32 w, int32 h) {
_numBlockingRects++;
}
-int32 PathFinding::getPathNodeCount() const {
- return _gridPathCount;
-}
-
-int32 PathFinding::getPathNodeX(int32 nodeId) const {
- return _tempPathX[ _gridPathCount - nodeId - 1];
-}
-
-int32 PathFinding::getPathNodeY(int32 nodeId) const {
- return _tempPathY[ _gridPathCount - nodeId - 1];
-}
-
} // End of namespace Toon
generated by cgit v1.2.3 (git 2.25.1) at 2025-07-24 04:11:25 +0000