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.cpp370
1 files changed, 370 insertions, 0 deletions
diff --git a/engines/toon/path.cpp b/engines/toon/path.cpp
new file mode 100644
index 0000000000..484e621a64
--- /dev/null
+++ b/engines/toon/path.cpp
@@ -0,0 +1,370 @@
+/* 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 2
+* 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, write to the Free Software
+* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+*
+* $URL$
+* $Id$
+*
+*/
+
+#include "toon/path.h"
+
+namespace Toon {
+
+int32 PathFindingHeap::init(int32 size) {
+ debugC(1, kDebugPath, "init(%d)", size);
+
+ _data = new HeapDataGrid[size * 2];
+ memset(_data, 0, sizeof(HeapDataGrid) * size * 2);
+ _count = 0;
+ _alloc = size;
+ return size;
+}
+
+int PathFindingHeap::unload() {
+ if (_data)
+ delete[] _data;
+ return 0;
+}
+
+int PathFindingHeap::clear() {
+ //debugC(1, kDebugPath, "clear()");
+
+ _count = 0;
+ memset(_data, 0, sizeof(HeapDataGrid) * _alloc * 2);
+ return 1;
+}
+
+int PathFindingHeap::push(int x, int y, int weight) {
+ //debugC(6, kDebugPath, "push(%d, %d, %d)", x, y, weight);
+
+ _count++;
+ _data[_count]._x = x;
+ _data[_count]._y = y;
+ _data[_count]._weight = weight;
+
+ int32 lMax = _count;
+ int32 lT = 0;
+
+ while (1) {
+ lT = lMax / 2;
+ if (lT < 1)
+ break;
+
+ if (_data[lT]._weight > _data[lMax]._weight) {
+ HeapDataGrid temp;
+ temp = _data[lT];
+ _data[lT] = _data[lMax];
+ _data[lMax] = temp;
+ lMax = lT;
+ } else {
+ break;
+ }
+ }
+ return 1;
+}
+
+int32 PathFindingHeap::pop(int32 *x, int32 *y, int32 *weight) {
+ //debugC(6, kDebugPath, "pop(x, y, weight)");
+
+ if (!_count)
+ return 0;
+
+ *x = _data[1]._x;
+ *y = _data[1]._y;
+ *weight = _data[1]._weight;
+
+ _data[1] = _data[_count];
+ _count--;
+ if (!_count)
+ return 0;
+
+ int32 lMin = 1;
+ int32 lT = 1;
+
+ while (1) {
+ lT = lMin << 1;
+ if (lT <= _count) {
+ if (lT < _count) {
+ if (_data[lT + 1]._weight < _data[lT]._weight)
+ lT++;
+ }
+ if (_data[lT]._weight <= _data[lMin]._weight) {
+ HeapDataGrid temp;
+ temp = _data[lMin];
+ _data[lMin] = _data[lT];
+ _data[lT] = temp;
+
+ lMin = lT;
+ } else {
+ break;
+ }
+ } else {
+ break;
+ }
+ }
+ return 0;
+}
+
+PathFinding::PathFinding(ToonEngine *vm) : _vm(vm) {
+ _width = 0;
+ _height = 0;
+ _heap = new PathFindingHeap();
+ _gridTemp = 0;
+ _numBlockingRects = 0;
+}
+
+PathFinding::~PathFinding(void) {
+ if (_heap) {
+ _heap->unload();
+ delete _heap;
+ }
+}
+
+bool PathFinding::isWalkable(int32 x, int32 y) {
+ //debugC(6, kDebugPath, "isWalkable(%d, %d)", x, y);
+
+ bool maskWalk = (_currentMask->getData(x, y) & 0x1f) > 0;
+ for (int32 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);
+ if ((dx << 8) / _blockingRects[i][2] < (1 << 8) && (dy << 8) / _blockingRects[i][3] < (1 << 8)) {
+ return false;
+ }
+ }
+ }
+ return maskWalk;
+}
+
+int32 PathFinding::findClosestWalkingPoint(int32 xx, int32 yy, int32 *fxx, int32 *fyy, int origX, int origY) {
+ debugC(1, kDebugPath, "findClosestWalkingPoint(%d, %d, fxx, fyy, %d, %d)", xx, yy, origX, origY);
+
+ int32 currentFound = -1;
+ int32 dist = -1;
+ int32 dist2 = -1;
+
+ if (origX == -1)
+ origX = xx;
+ if (origY == -1)
+ origY = yy;
+
+ for (int y = 0; y < _height; y++) {
+ for (int x = 0; x < _width; x++) {
+ if (isWalkable(x, y)) {
+ int32 ndist = (x - xx) * (x - xx) + (y - yy) * (y - yy);
+ int32 ndist2 = (x - origX) * (x - origX) + (y - origY) * (y - origY);
+ if (currentFound < 0 || ndist < dist || (ndist == dist && ndist2 < dist2)) {
+ dist = ndist;
+ dist2 = ndist2;
+ currentFound = y * _width + x;
+ }
+ }
+ }
+ }
+
+ if (currentFound != -1) {
+ *fxx = currentFound % _width;
+ *fyy = currentFound / _width;
+ return 1;
+ } else {
+ *fxx = 0;
+ *fyy = 0;
+ return 0;
+ }
+}
+
+int PathFinding::findPath(int32 x, int32 y, int32 destx, int32 desty) {
+ debugC(1, kDebugPath, "findPath(%d, %d, %d, %d)", x, y, destx, desty);
+
+ if (x == destx && y == desty) {
+ _gridPathCount = 0;
+ return true;
+ }
+
+ memset(_gridTemp , 0, _width * _height * sizeof(int32));
+ _heap->clear();
+ int32 curX = x;
+ int32 curY = y;
+ int32 curWeight = 0;
+ int32 *sq = _gridTemp;
+
+ sq[curX + curY *_width] = 1;
+ _heap->push(curX, curY, abs(destx - x) + abs(desty - y));
+ int wei = 0;
+
+// Strangerke - Commented (not used)
+// byte *mask = _currentMask->getDataPtr();
+
+ while (_heap->_count) {
+ wei = 0;
+ _heap->pop(&curX, &curY, &curWeight);
+ int curNode = curX + curY * _width;
+
+ int32 endX = MIN(curX + 1, _width - 1);
+ int32 endY = MIN(curY + 1, _height - 1);
+ int32 startX = MAX(curX - 1, 0);
+ int32 startY = MAX(curY - 1, 0);
+
+ for (int32 px = startX; px <= endX; px++) {
+ for (int py = startY; py <= endY; py++) {
+ if (px != curX || py != curY) {
+ wei = abs(px - curX) + abs(py - curY);
+
+ int32 curPNode = px + py * _width;
+ if (isWalkable(px, py)) { // walkable ?
+ int sum = sq[curNode] + wei;
+ if (sq[curPNode] > sum || !sq[curPNode]) {
+ int newWeight = abs(destx - px) + abs(desty - py);
+ sq[curPNode] = sum;
+ _heap->push(px, py, sq[curPNode] + newWeight);
+ if (!newWeight)
+ goto next; // we found it !
+ }
+ }
+ }
+ }
+ }
+ }
+
+next:
+
+ // let's see if we found a result !
+ if (!_gridTemp[destx + desty * _width]) {
+ // didn't find anything
+ _gridPathCount = 0;
+ return false;
+ }
+
+ curX = destx;
+ curY = desty;
+
+ int32 retPathX[4096];
+ int32 retPathY[4096];
+ int32 numpath = 0;
+
+ retPathX[numpath] = curX;
+ retPathY[numpath] = curY;
+ numpath++;
+ int32 bestscore = sq[destx + desty * _width];
+
+ while (1) {
+ int32 bestX = -1;
+ int32 bestY = -1;
+
+ int32 endX = MIN(curX + 1, _width - 1);
+ int32 endY = MIN(curY + 1, _height - 1);
+ int32 startX = MAX(curX - 1, 0);
+ int32 startY = MAX(curY - 1, 0);
+
+ for (int32 px = startX; px <= endX; px++) {
+ for (int32 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];
+ bestX = px;
+ bestY = py;
+ }
+ }
+ }
+ }
+ }
+
+ if (bestX < 0 || bestY < 0)
+ return 0;
+
+ retPathX[numpath] = bestX;
+ retPathY[numpath] = bestY;
+ numpath++;
+
+ if ((bestX == x && bestY == y)) {
+ _gridPathCount = numpath;
+
+ memcpy(_tempPathX, retPathX, sizeof(int32) * numpath);
+ memcpy(_tempPathY, retPathY, sizeof(int32) * numpath);
+ return true;
+ }
+
+ curX = bestX;
+ curY = bestY;
+ }
+
+ return false;
+}
+
+void PathFinding::init(Picture *mask) {
+ debugC(1, kDebugPath, "init(mask)");
+
+ _width = mask->getWidth();
+ _height = mask->getHeight();
+ _currentMask = mask;
+ _heap->unload();
+ _heap->init(_width * _height);
+ if (_gridTemp)
+ delete[] _gridTemp;
+ _gridTemp = new int32[_width*_height];
+}
+
+void PathFinding::resetBlockingRects() {
+ _numBlockingRects = 0;
+}
+
+void PathFinding::addBlockingRect(int32 x1, int32 y1, int32 x2, int32 y2) {
+ debugC(1, kDebugPath, "addBlockingRect(%d, %d, %d, %d)", x1, y1, x2, y2);
+
+ _blockingRects[_numBlockingRects][0] = x1;
+ _blockingRects[_numBlockingRects][1] = y1;
+ _blockingRects[_numBlockingRects][2] = x2;
+ _blockingRects[_numBlockingRects][3] = y2;
+ _blockingRects[_numBlockingRects][4] = 0;
+ _numBlockingRects++;
+}
+
+void PathFinding::addBlockingEllipse(int32 x1, int32 y1, int32 w, int32 h) {
+ debugC(1, kDebugPath, "addBlockingRect(%d, %d, %d, %d)", x1, y1, w, h);
+
+ _blockingRects[_numBlockingRects][0] = x1;
+ _blockingRects[_numBlockingRects][1] = y1;
+ _blockingRects[_numBlockingRects][2] = w;
+ _blockingRects[_numBlockingRects][3] = h;
+ _blockingRects[_numBlockingRects][4] = 1;
+ _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-10-31 18:36:30 +0000