From cf82bef02ee2941ddad6664e34f3c94e35e015a3 Mon Sep 17 00:00:00 2001 From: Eugene Sandulenko Date: Fri, 8 Oct 2010 22:30:39 +0000 Subject: TOON: Merged Toon engine to ScummVM trunk svn-id: r53087 --- engines/toon/path.cpp | 370 ++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 370 insertions(+) create mode 100644 engines/toon/path.cpp (limited to 'engines/toon/path.cpp') diff --git a/engines/toon/path.cpp b/engines/toon/path.cpp new file mode 100644 index 0000000000..fbc9d64ddb --- /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 "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; +} + +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 -- cgit v1.2.3