TOON: Merged Toon engine to ScummVM trunk

svn-id: r53087

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..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