From d035bcae826e4212ddda531633d3cf0666d57109 Mon Sep 17 00:00:00 2001 From: D G Turner Date: Wed, 20 Jul 2011 23:05:24 +0100 Subject: TOON: Cleanup and Memory Usage Reduction fixes in PathFinding Heap. This halves the size of the pathifnding heap, but adds warnings if push() is attempted on a full heap. --- engines/toon/path.cpp | 50 +++++++++++++++++++++++++++----------------------- 1 file changed, 27 insertions(+), 23 deletions(-) (limited to 'engines/toon/path.cpp') diff --git a/engines/toon/path.cpp b/engines/toon/path.cpp index 43a134e39b..6ffe8b3672 100644 --- a/engines/toon/path.cpp +++ b/engines/toon/path.cpp @@ -28,7 +28,7 @@ namespace Toon { PathFindingHeap::PathFindingHeap() { _count = 0; - _alloc = 0; + _size = 0; _data = NULL; } @@ -36,33 +36,37 @@ PathFindingHeap::~PathFindingHeap() { delete[] _data; } -int32 PathFindingHeap::init(int32 size) { +void PathFindingHeap::init(int32 size) { debugC(1, kDebugPath, "init(%d)", size); + _size = size; delete[] _data; - _data = new HeapDataGrid[size * 2]; - memset(_data, 0, sizeof(HeapDataGrid) * size * 2); + _data = new HeapDataGrid[_size]; + memset(_data, 0, sizeof(HeapDataGrid) * _size); _count = 0; - _alloc = size; - return size; } -int32 PathFindingHeap::unload() { +void PathFindingHeap::unload() { + _count = 0; + _size = 0; delete[] _data; _data = NULL; - return 0; } -int32 PathFindingHeap::clear() { - //debugC(1, kDebugPath, "clear()"); +void PathFindingHeap::clear() { + debugC(1, kDebugPath, "clear()"); _count = 0; - memset(_data, 0, sizeof(HeapDataGrid) * _alloc * 2); - return 1; + memset(_data, 0, sizeof(HeapDataGrid) * _size); } -int32 PathFindingHeap::push(int32 x, int32 y, int32 weight) { - //debugC(6, kDebugPath, "push(%d, %d, %d)", x, y, weight); +void PathFindingHeap::push(int32 x, int32 y, int32 weight) { + debugC(2, kDebugPath, "push(%d, %d, %d)", x, y, weight); + + if (_count == _size - 1) { + warning("Aborting attempt to push onto PathFindingHeap at maximum size: %d", _count); + return; + } _count++; _data[_count]._x = x; @@ -87,14 +91,15 @@ int32 PathFindingHeap::push(int32 x, int32 y, int32 weight) { break; } } - return 1; } -int32 PathFindingHeap::pop(int32 *x, int32 *y, int32 *weight) { - //debugC(6, kDebugPath, "pop(x, y, weight)"); +void PathFindingHeap::pop(int32 *x, int32 *y, int32 *weight) { + debugC(2, kDebugPath, "pop(x, y, weight)"); - if (!_count) - return 0; + if (!_count) { + warning("Attempt to pop empty PathFindingHeap!"); + return; + } *x = _data[1]._x; *y = _data[1]._y; @@ -103,7 +108,7 @@ int32 PathFindingHeap::pop(int32 *x, int32 *y, int32 *weight) { _data[1] = _data[_count]; _count--; if (!_count) - return 0; + return; int32 lMin = 1; int32 lT = 1; @@ -129,7 +134,6 @@ int32 PathFindingHeap::pop(int32 *x, int32 *y, int32 *weight) { break; } } - return 0; } PathFinding::PathFinding(ToonEngine *vm) : _vm(vm) { @@ -164,7 +168,7 @@ bool PathFinding::isLikelyWalkable(int32 x, int32 y) { } bool PathFinding::isWalkable(int32 x, int32 y) { - //debugC(6, kDebugPath, "isWalkable(%d, %d)", x, y); + debugC(2, kDebugPath, "isWalkable(%d, %d)", x, y); bool maskWalk = (_currentMask->getData(x, y) & 0x1f) > 0; @@ -299,7 +303,7 @@ int32 PathFinding::findPath(int32 x, int32 y, int32 destx, int32 desty) { _heap->push(curX, curY, abs(destx - x) + abs(desty - y)); int wei = 0; - while (_heap->_count) { + while (_heap->getCount()) { wei = 0; _heap->pop(&curX, &curY, &curWeight); int curNode = curX + curY * _width; -- cgit v1.2.3 From e4427fd5893953271739ee55ae12a4712272c3b0 Mon Sep 17 00:00:00 2001 From: Marcus Comstedt Date: Mon, 18 Jul 2011 15:28:54 +0200 Subject: TOON: Fix off-by-one use of path heap array The first element of the _data array in PathFindingHeap was never used, fix that. --- engines/toon/path.cpp | 29 ++++++++++++++--------------- 1 file changed, 14 insertions(+), 15 deletions(-) (limited to 'engines/toon/path.cpp') diff --git a/engines/toon/path.cpp b/engines/toon/path.cpp index 6ffe8b3672..785b84a78e 100644 --- a/engines/toon/path.cpp +++ b/engines/toon/path.cpp @@ -63,23 +63,23 @@ void PathFindingHeap::clear() { void PathFindingHeap::push(int32 x, int32 y, int32 weight) { debugC(2, kDebugPath, "push(%d, %d, %d)", x, y, weight); - if (_count == _size - 1) { + if (_count == _size) { warning("Aborting attempt to push onto PathFindingHeap at maximum size: %d", _count); return; } - _count++; _data[_count]._x = x; _data[_count]._y = y; _data[_count]._weight = weight; + _count++; - int32 lMax = _count; + int32 lMax = _count-1; int32 lT = 0; while (1) { - lT = lMax / 2; - if (lT < 1) + if (lMax <= 0) break; + lT = (lMax-1) / 2; if (_data[lT]._weight > _data[lMax]._weight) { HeapDataGrid temp; @@ -101,22 +101,21 @@ void PathFindingHeap::pop(int32 *x, int32 *y, int32 *weight) { return; } - *x = _data[1]._x; - *y = _data[1]._y; - *weight = _data[1]._weight; + *x = _data[0]._x; + *y = _data[0]._y; + *weight = _data[0]._weight; - _data[1] = _data[_count]; - _count--; + _data[0] = _data[--_count]; if (!_count) return; - int32 lMin = 1; - int32 lT = 1; + int32 lMin = 0; + int32 lT = 0; while (1) { - lT = lMin << 1; - if (lT <= _count) { - if (lT < _count) { + lT = (lMin << 1) + 1; + if (lT < _count) { + if (lT < _count-1) { if (_data[lT + 1]._weight < _data[lT]._weight) lT++; } -- cgit v1.2.3 From a7e49f294502c4c2efa2b37eb2c5b0ae3d1b66f7 Mon Sep 17 00:00:00 2001 From: Marcus Comstedt Date: Thu, 21 Jul 2011 15:00:04 +0200 Subject: TOON: Grow size of path finding heap dynamically --- engines/toon/path.cpp | 29 ++++++++++++++++++----------- 1 file changed, 18 insertions(+), 11 deletions(-) (limited to 'engines/toon/path.cpp') diff --git a/engines/toon/path.cpp b/engines/toon/path.cpp index 785b84a78e..60ca007930 100644 --- a/engines/toon/path.cpp +++ b/engines/toon/path.cpp @@ -33,15 +33,15 @@ PathFindingHeap::PathFindingHeap() { } PathFindingHeap::~PathFindingHeap() { - delete[] _data; + free(_data); } void PathFindingHeap::init(int32 size) { debugC(1, kDebugPath, "init(%d)", size); _size = size; - delete[] _data; - _data = new HeapDataGrid[_size]; + free(_data); + _data = (HeapDataGrid *)malloc(sizeof(HeapDataGrid) * _size); memset(_data, 0, sizeof(HeapDataGrid) * _size); _count = 0; } @@ -49,7 +49,7 @@ void PathFindingHeap::init(int32 size) { void PathFindingHeap::unload() { _count = 0; _size = 0; - delete[] _data; + free(_data); _data = NULL; } @@ -64,8 +64,19 @@ void PathFindingHeap::push(int32 x, int32 y, int32 weight) { debugC(2, kDebugPath, "push(%d, %d, %d)", x, y, weight); if (_count == _size) { - warning("Aborting attempt to push onto PathFindingHeap at maximum size: %d", _count); - return; + // Increase size by 50% + int newSize = _size + (_size >> 1) + 1; + HeapDataGrid *newData; + + newData = (HeapDataGrid *)realloc(_data, sizeof(HeapDataGrid) * newSize); + if (newData == NULL) { + warning("Aborting attempt to push onto PathFindingHeap at maximum size: %d", _count); + return; + } + + memset(newData + _size, 0, sizeof(HeapDataGrid) * (newSize - _size)); + _data = newData; + _size = newSize; } _data[_count]._x = x; @@ -427,11 +438,7 @@ void PathFinding::init(Picture *mask) { _height = mask->getHeight(); _currentMask = mask; _heap->unload(); - // In order to reduce memory fragmentation on small devices, we use the maximum - // possible size here which is TOON_BACKBUFFER_WIDTH. Even though this is - // 1280 as opposed to the possible 640, it actually helps memory allocation on - // those devices. - _heap->init(TOON_BACKBUFFER_WIDTH * _height); // should really be _width + _heap->init(500); delete[] _gridTemp; _gridTemp = new int32[_width*_height]; } -- cgit v1.2.3