A long time ago, in a virtual machine far, far away...

It is a period of bug fixing. Rebel
developers, coding from a public
project, have won their umpteenth victory
against the evil Actor Walk Bugs.
 
During the debugging, programmers 
used secret plans to the LucasArts'
ultimate tool, the SCUMM engine, an
extensible scripting system with enough
power to create an entire adventure.

Pursued by ensuing sinister regressions,
High King Fingolfin gleefully jumps up
and down, making use of the hotkey
that can save his games and restore
them back again later....

[With apologies to George Lucas. Good
riddance to bugs #751662, #771483, #959001,
#1329457, #1329498, #1329529, #1527672,
#1538260, #1571701, #1571705, #1571740,
and a warm welcome to the regressions
this change will cause. :-) ]

svn-id: r26090

5 files changed, 177 insertions, 58 deletions

diff --git a/engines/scumm/actor.cpp b/engines/scumm/actor.cpp
index bb9b935be2..df143f6288 100644
--- a/engines/scumm/actor.cpp
+++ b/engines/scumm/actor.cpp
@@ -164,12 +164,8 @@ void Actor::initActor(int mode) {
 void Actor_v2::initActor(int mode) {
 	Actor::initActor(mode);
 
-	if (mode == -1) {
-		_speedx = 1;
-		_speedy = 1;
-	}
-
-	setActorWalkSpeed(1, 1);
+	_speedx = 1;
+	_speedy = 1;
 
 	_initFrame = 2;
 	_walkFrame = 0;
@@ -378,23 +374,29 @@ void Actor::startWalkActor(int destX, int destY, int dir) {
 		return;
 	}
 
-	if (_ignoreBoxes) {
-		abr.box = kInvalidBox;
-		_walkbox = kInvalidBox;
+	if (_vm->_game.version <= 2) {
+		abr = adjustXYToBeInBox(abr.x, abr.y);
+		if (_pos.x == abr.x && _pos.y == abr.y && (dir == -1 || _facing == dir))
+			return;
 	} else {
-		if (_vm->checkXYInBoxBounds(_walkdata.destbox, abr.x, abr.y)) {
-			abr.box = _walkdata.destbox;
+		if (_ignoreBoxes) {
+			abr.box = kInvalidBox;
+			_walkbox = kInvalidBox;
 		} else {
-			abr = adjustXYToBeInBox(abr.x, abr.y);
+			if (_vm->checkXYInBoxBounds(_walkdata.destbox, abr.x, abr.y)) {
+				abr.box = _walkdata.destbox;
+			} else {
+				abr = adjustXYToBeInBox(abr.x, abr.y);
+			}
+			if (_moving && _walkdata.destdir == dir && _walkdata.dest.x == abr.x && _walkdata.dest.y == abr.y)
+				return;
 		}
-		if (_moving && _walkdata.destdir == dir && _walkdata.dest.x == abr.x && _walkdata.dest.y == abr.y)
+	
+		if (_pos.x == abr.x && _pos.y == abr.y) {
+			if (dir != _facing)
+				turnToDirection(dir);
 			return;
-	}
-
-	if (_pos.x == abr.x && _pos.y == abr.y) {
-		if (dir != _facing)
-			turnToDirection(dir);
-		return;
+		}
 	}
 
 	_walkdata.dest.x = abr.x;
@@ -500,7 +502,7 @@ void Actor::walkActor() {
 		if (_walkbox == _walkdata.destbox)
 			break;
 
-		next_box = _vm->getPathToDestBox(_walkbox, _walkdata.destbox);
+		next_box = _vm->getNextBox(_walkbox, _walkdata.destbox);
 		if (next_box < 0) {
 			_walkdata.destbox = _walkbox;
 			_moving |= MF_LAST_LEG;
@@ -522,13 +524,13 @@ void Actor::walkActor() {
 	calcMovementFactor(_walkdata.dest);
 }
 
-/*
-void Actor::walkActor() {
+void Actor_v2::walkActor() {
 	Common::Point foundPath, tmp;
 	int new_dir, next_box;
 
 	if (_moving & MF_TURN) {
 		new_dir = updateActorDirection(false);
+		// FIXME -- is this correct?
 		if (_facing != new_dir)
 			setDirection(new_dir);
 		else
@@ -553,7 +555,7 @@ void Actor::walkActor() {
 				foundPath = _walkdata.dest;
 				_moving |= MF_LAST_LEG;
 			} else {
-				next_box = _vm->getPathToDestBox(_walkbox, _walkdata.destbox);
+				next_box = _vm->getNextBox(_walkbox, _walkdata.destbox);
 				if (next_box < 0) {
 					_moving |= MF_LAST_LEG;
 					return;
@@ -561,20 +563,20 @@ void Actor::walkActor() {
 
 				// Can't walk through locked boxes
 				int flags = _vm->getBoxFlags(next_box);
-				if (flags & kBoxLocked && !(flags & kBoxPlayerOnly && !isPlayer())) {
+				if ((flags & kBoxLocked) && !((flags & kBoxPlayerOnly) && !isPlayer())) {
 					_moving |= MF_LAST_LEG;
+					//_walkdata.destdir = -1;
 				}
 
 				_walkdata.curbox = next_box;
 
-				getClosestPtOnBox(_vm->getBoxCoordinates(_walkdata.curbox), x, y, tmp.x, tmp.y);
+				getClosestPtOnBox(_vm->getBoxCoordinates(_walkdata.curbox), _pos.x, _pos.y, tmp.x, tmp.y);
 				getClosestPtOnBox(_vm->getBoxCoordinates(_walkbox), tmp.x, tmp.y, foundPath.x, foundPath.y);
 			}
 			calcMovementFactor(foundPath);
 		}
 	}
 }
-*/
 
 void Actor_v3::walkActor() {
 	Common::Point p2, p3;	// Gate locations
@@ -627,7 +629,7 @@ void Actor_v3::walkActor() {
 		if (_walkbox == _walkdata.destbox)
 			break;
 
-		next_box = _vm->getPathToDestBox(_walkbox, _walkdata.destbox);
+		next_box = _vm->getNextBox(_walkbox, _walkdata.destbox);
 
 		// WORKAROUND: To fully fix bug #774783, we add a special case
 		// here, resulting in a different next_box value for Hitler.
@@ -641,32 +643,22 @@ void Actor_v3::walkActor() {
 
 		// Can't walk through locked boxes
 		int flags = _vm->getBoxFlags(next_box);
-		if (flags & kBoxLocked && !(flags & kBoxPlayerOnly && !isPlayer())) {
+		if ((flags & kBoxLocked) && !((flags & kBoxPlayerOnly) && !isPlayer())) {
 			_moving |= MF_LAST_LEG;
-// FIXME: Work in progress
-//			_walkdata.destdir = _facing;
 			return;
 		}
 
 		_walkdata.curbox = next_box;
 
-		if (_vm->_game.version <= 2) {
-			getClosestPtOnBox(_vm->getBoxCoordinates(_walkdata.curbox), _pos.x, _pos.y, p2.x, p2.y);
-			getClosestPtOnBox(_vm->getBoxCoordinates(_walkbox), p2.x, p2.y, p3.x, p3.y);
-// FIXME: Work in progress
-//			calcMovementFactor(p3);
-//			return;
-		} else {
-			findPathTowardsOld(_walkbox, next_box, _walkdata.destbox, p2, p3);
-			if (p2.x == 32000 && p3.x == 32000) {
-				break;
-			}
+		findPathTowardsOld(_walkbox, next_box, _walkdata.destbox, p2, p3);
+		if (p2.x == 32000 && p3.x == 32000) {
+			break;
+		}
 
-			if (p2.x != 32000) {
-				if (calcMovementFactor(p2)) {
-					_walkdata.point3 = p3;
-					return;
-				}
+		if (p2.x != 32000) {
+			if (calcMovementFactor(p2)) {
+				_walkdata.point3 = p3;
+				return;
 			}
 		}
 		if (calcMovementFactor(p3))
@@ -950,6 +942,124 @@ static bool inBoxQuickReject(const BoxCoords &box, int x, int y, int threshold)
 	return false;
 }
 
+static int checkXYInBoxBounds(int boxnum, int x, int y, int &destX, int &destY) {
+	BoxCoords box = g_scumm->getBoxCoordinates(boxnum);
+	int xmin, xmax;
+	
+	// We are supposed to determine the point (destX,destY) contained in
+	// the given box which is closest to the point (x,y), and then return
+	// some kind of "distance" between the two points.
+
+	// First, we determine destY and a range (xmin to xmax) in which destX
+	// is contained.
+	if (y < box.ul.y) {
+		// Point is above the box
+		destY = box.ul.y;
+		xmin = box.ul.x;
+		xmax = box.ur.x;
+	} else if (y >= box.ll.y) {
+		// Point is below the box
+		destY = box.ll.y;
+		xmin = box.ll.x;
+		xmax = box.lr.x;
+	} else if ((x >= box.ul.x) && (x >= box.ll.x) && (x < box.ur.x) && (x < box.lr.x)) {
+		// Point is strictly inside the box
+		destX = x;
+		destY = y;
+		xmin = xmax = x;
+	} else {
+		// Point is to the left or right of the box,
+		// so the y coordinate remains unchanged
+		destY = y;
+		int ul = box.ul.x;
+		int ll = box.ll.x;
+		int ur = box.ur.x;
+		int lr = box.lr.x;
+		int top = box.ul.y;
+		int bottom = box.ll.y;
+		int cury;
+
+		// Perform a binary search to determine the x coordinate.
+		// Note: It would be possible to compute this value in a
+		// single step simply by calculating the slope of the left
+		// resp. right side and using that to find the correct
+		// result. However, the original engine did use the search
+		// approach, so we do that, too.
+		do {
+			xmin = (ul + ll) / 2;
+			xmax = (ur + lr) / 2;
+			cury = (top + bottom) / 2;
+	
+			if (cury < y) {
+				top = cury;
+				ul = xmin;
+				ur = xmax;
+			} else if (cury > y) {
+				bottom = cury;
+				ll = xmin;
+				lr = xmax;
+			}
+		} while (cury != y);
+	}
+	
+	// Now that we have limited the value of destX to a fixed
+	// interval, it's a trivial matter to finally determine it.
+	if (x < xmin) {
+		destX = xmin;
+	} else if (x > xmax) {
+		destX = xmax;
+	} else {
+		destX = x;
+	}
+
+	// Compute the distance of the points. We measure the
+	// distance with a granularity of 8x8 blocks only (hence
+	// yDist must be divided by 4, as we are using 8x2 pixels
+	// blocks for actor coordinates).
+	int xDist = ABS(x - destX);
+	int yDist = ABS(y - destY) / 4;
+	int dist;
+
+	if (xDist < yDist)
+		dist = (xDist >> 1) + yDist;
+	else
+		dist = (yDist >> 1) + xDist;
+
+	return dist;
+}
+
+AdjustBoxResult Actor_v2::adjustXYToBeInBox(const int dstX, const int dstY) {
+	AdjustBoxResult abr;
+
+	abr.x = dstX;
+	abr.y = dstY;
+	abr.box = kInvalidBox;
+
+	int numBoxes = _vm->getNumBoxes() - 1;
+	int bestDist = 0xFF;
+	for (int box = numBoxes; box >= 0; box--) {
+		int foundX, foundY;
+		int flags = _vm->getBoxFlags(box);
+		if ((flags & kBoxInvisible) && !((flags & kBoxPlayerOnly) && !isPlayer()))
+			continue;
+		int dist = checkXYInBoxBounds(box, dstX, dstY, foundX, foundY);	// also merged with getClosestPtOnBox
+		if (dist == 0) {
+			abr.x = foundX;
+			abr.y = foundY;
+			abr.box = box;
+			break;
+		}
+		if (dist < bestDist) {
+			bestDist = dist;
+			abr.x = foundX;
+			abr.y = foundY;
+			abr.box = box;
+		}
+	}
+
+	return abr;
+}
+
 AdjustBoxResult Actor::adjustXYToBeInBox(int dstX, int dstY) {
 	const uint thresholdTable[] = { 30, 80, 0 };
 	AdjustBoxResult abr;
@@ -982,7 +1092,7 @@ AdjustBoxResult Actor::adjustXYToBeInBox(int dstX, int dstY) {
 			flags = _vm->getBoxFlags(box);
 
 			// Skip over invisible boxes
-			if (flags & kBoxInvisible && !(flags & kBoxPlayerOnly && !isPlayer()))
+			if ((flags & kBoxInvisible) && !((flags & kBoxPlayerOnly) && !isPlayer()))
 				continue;
 
 			// For increased performance, we perform a quick test if
diff --git a/engines/scumm/actor.h b/engines/scumm/actor.h
index 23b11cba99..61c5216133 100644
--- a/engines/scumm/actor.h
+++ b/engines/scumm/actor.h
@@ -213,7 +213,7 @@ protected:
 
 public:
 	void adjustActorPos();
-	AdjustBoxResult adjustXYToBeInBox(int dstX, int dstY);
+	virtual AdjustBoxResult adjustXYToBeInBox(int dstX, int dstY);
 
 	void setDirection(int direction);
 	void faceToObject(int obj);
@@ -348,7 +348,8 @@ public:
 	Actor_v2(int id) : Actor_v3(id) {}
 
 	virtual void initActor(int mode);
-	//virtual void walkActor();
+	virtual void walkActor();
+	virtual AdjustBoxResult adjustXYToBeInBox(int dstX, int dstY);
 
 protected:
 	virtual bool isPlayer();
diff --git a/engines/scumm/boxes.cpp b/engines/scumm/boxes.cpp
index f6bae90dc8..b343fde319 100644
--- a/engines/scumm/boxes.cpp
+++ b/engines/scumm/boxes.cpp
@@ -688,7 +688,7 @@ byte *ScummEngine::getBoxMatrixBaseAddr() {
  * way to 'to' (this can be 'to' itself or a third box).
  * If there is no connection -1 is return.
  */
-int ScummEngine::getPathToDestBox(byte from, byte to) {
+int ScummEngine::getNextBox(byte from, byte to) {
 	const byte *boxm;
 	byte i;
 	const int numOfBoxes = getNumBoxes();
@@ -1002,7 +1002,7 @@ void ScummEngine::createBoxMatrix() {
 	// itineray box. Assuming we are in the 5th "row" and encounter
 	// the triplet 7,11,15: this means to get from box 5 to any of
 	// the boxes 7,8,9,10,11 the shortest way is to go via box 15.
-	// See also getPathToDestBox.
+	// See also getNextBox.
 
 	byte *matrixStart = _res->createResource(rtMatrix, 1, BOX_MATRIX_SIZE);
 	const byte *matrixEnd = matrixStart + BOX_MATRIX_SIZE;
@@ -1042,7 +1042,7 @@ bool ScummEngine::areBoxesNeighbours(int box1nr, int box2nr) {
 	BoxCoords box;
 	BoxCoords box2;
 
-	if (getBoxFlags(box1nr) & kBoxInvisible || getBoxFlags(box2nr) & kBoxInvisible)
+	if ((getBoxFlags(box1nr) & kBoxInvisible) || (getBoxFlags(box2nr) & kBoxInvisible))
 		return false;
 
 	assert(_game.version >= 3);
@@ -1159,11 +1159,10 @@ void Actor_v3::findPathTowardsOld(byte box1, byte box2, byte finalBox, Common::P
 		}
 	}
 
-	p3 = pt = closestPtOnLine(gateA[1], gateB[1], _pos);
+	p3 = closestPtOnLine(gateA[1], gateB[1], _pos);
 
 	if (compareSlope(_pos, p3, gateA[0]) == compareSlope(_pos, p3, gateB[0])) {
-		closestPtOnLine(gateA[0], gateB[0], _pos);
-		p2 = pt;	// if point 2 between gates, ignore!
+		p2 = closestPtOnLine(gateA[0], gateB[0], _pos);
 	}
 }
 
diff --git a/engines/scumm/script_v2.cpp b/engines/scumm/script_v2.cpp
index a71e2596b4..9fc0f0659f 100644
--- a/engines/scumm/script_v2.cpp
+++ b/engines/scumm/script_v2.cpp
@@ -1202,6 +1202,9 @@ void ScummEngine_v2::o2_walkActorToObject() {
 	if (whereIsObject(obj) != WIO_NOT_FOUND) {
 		int x, y, dir;
 		getObjectXYPos(obj, x, y, dir);
+		AdjustBoxResult r = a->adjustXYToBeInBox(x, y);
+		x = r.x;
+		y = r.y;
 		a->startWalkActor(x, y, dir);
 	}
 }
@@ -1212,9 +1215,12 @@ void ScummEngine_v2::o2_putActorAtObject() {
 
 	a = derefActor(getVarOrDirectByte(PARAM_1), "o2_putActorAtObject");
 	obj = getVarOrDirectWord(PARAM_2);
-	if (whereIsObject(obj) != WIO_NOT_FOUND)
+	if (whereIsObject(obj) != WIO_NOT_FOUND) {
 		getObjectXYPos(obj, x, y);
-	else {
+		AdjustBoxResult r = a->adjustXYToBeInBox(x, y);
+		x = r.x;
+		y = r.y;
+	} else {
 		x = 30;
 		y = 60;
 	}
@@ -1374,6 +1380,9 @@ void ScummEngine_v2::o2_loadRoomWithEgo() {
 	startScene(a->_room, a, obj);
 
 	getObjectXYPos(obj, x2, y2, dir);
+	AdjustBoxResult r = a->adjustXYToBeInBox(x2, y2);
+	x2 = r.x;
+	y2 = r.y;
 	a->putActor(x2, y2, _currentRoom);
 	a->setDirection(dir + 180);
 
diff --git a/engines/scumm/scumm.h b/engines/scumm/scumm.h
index 5522814d39..d31ea1a2fb 100644
--- a/engines/scumm/scumm.h
+++ b/engines/scumm/scumm.h
@@ -1105,7 +1105,7 @@ public:
 
 	byte getNumBoxes();
 	byte *getBoxMatrixBaseAddr();
-	int getPathToDestBox(byte from, byte to);
+	int getNextBox(byte from, byte to);
 
 	void setBoxFlags(int box, int val);
 	void setBoxScale(int box, int b);