[Scummvm-cvs-logs] scummvm master -> e4427fd5893953271739ee55ae12a4712272c3b0

zeldin marcus at mc.pp.se
Thu Jul 21 13:42:35 CEST 2011


This automated email contains information about 1 new commit which have been
pushed to the 'scummvm' repo located at https://github.com/scummvm/scummvm .

Summary:
e4427fd589 TOON: Fix off-by-one use of path heap array


Commit: e4427fd5893953271739ee55ae12a4712272c3b0
    https://github.com/scummvm/scummvm/commit/e4427fd5893953271739ee55ae12a4712272c3b0
Author: Marcus Comstedt (marcus at mc.pp.se)
Date: 2011-07-21T04:09:18-07:00

Commit Message:
TOON: Fix off-by-one use of path heap array

The first element of the _data array in PathFindingHeap was never
used, fix that.

Changed paths:
    engines/toon/path.cpp



diff --git a/engines/toon/path.cpp b/engines/toon/path.cpp
index 6ffe8b3..785b84a 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++;
 			}






More information about the Scummvm-git-logs mailing list