SCUMM: add support for diagonal walking between boxes (e.g. used for meteor opening scene)

2 files changed, 89 insertions, 9 deletions

diff --git a/engines/scumm/actor.cpp b/engines/scumm/actor.cpp
index bc336292dc..1ba0eafc06 100644
--- a/engines/scumm/actor.cpp
+++ b/engines/scumm/actor.cpp
@@ -567,6 +567,90 @@ void Actor::walkActor() {
 	calcMovementFactor(_walkdata.dest);
 }
 
+bool Actor_v2::checkWalkboxesHaveDirectPath(Common::Point &foundPath) {
+	// only MM v0 supports walking in direct line between walkboxes.
+	// MM v1 already does not support it anymore.
+	return false;
+}
+
+bool Actor_v0::intersectLineSegments(const Common::Point &line1Start, const Common::Point &line1End, 
+	const Common::Point &line2Start, const Common::Point &line2End, Common::Point &result) 
+{
+	const Common::Point v1 = line1End - line1Start; // line1(n1) = line1Start + n1 * v1
+	const Common::Point v2 = line2End - line2Start; // line2(n2) = line2Start + n2 * v2
+	
+	double det = v2.x * v1.y - v1.x * v2.y;
+	if (det == 0)
+		return false;
+
+	double n1 = ((double)v2.x * (line2Start.y - line1Start.y) - 
+		         (double)v2.y * (line2Start.x - line1Start.x)) / det;
+	double n2 = ((double)v1.x * (line2Start.y - line1Start.y) - 
+		         (double)v1.y * (line2Start.x - line1Start.x)) / det;
+
+	// both coefficients have to be in [0, 1], otherwise the intersection is
+	// not inside of at least one of the two line segments
+	if (n1 < 0.0 || n1 > 1.0 || n2 < 0.0 || n2 > 1.0)
+		return false;
+
+	result.x = line1Start.x + (int)(n1 * v1.x);
+	result.y = line1Start.y + (int)(n1 * v1.y);
+	return true;
+}
+
+/*
+ * MM v0 allows the actor to walk in a direct line between boxes to the target 
+ * if actor and target share a horizontal or vertical corridor.
+ * If such a corridor is found the actor is not forced to go horizontally or 
+ * vertically from one box to the next but can also walk diagonally.
+ *
+ * Note: the original v0 interpreter sets the target destination for diagonal 
+ * walking only once and then rechecks whenever the actor reaches a new box if the
+ * walk destination is still suitable for the current box. 
+ * ScummVM does not perform such a check, so it is possible to leave the walkboxes 
+ * in some cases, for example L-shaped rooms like the swimming pool (actor walks over water) 
+ * or the medical room (actor walks over examination table).
+ * To solve this we intersect the new walk destination with the actor's walkbox borders,
+ * so a recheck is done when the actor leaves his box. This is done by the
+ * intersectLineSegments() routine calls.
+ */
+bool Actor_v0::checkWalkboxesHaveDirectPath(Common::Point &foundPath) {
+	BoxCoords boxCoords = _vm->getBoxCoordinates(_walkbox);
+	BoxCoords curBoxCoords = _vm->getBoxCoordinates(_walkdata.curbox);
+
+	// check if next walkbox is left or right to actor's box
+	if (boxCoords.ll.x > curBoxCoords.lr.x || boxCoords.lr.x < curBoxCoords.ll.x) {
+		// determine horizontal corridor gates
+		int gateUpper = MAX(boxCoords.ul.y, curBoxCoords.ul.y);
+		int gateLower = MIN(boxCoords.ll.y, curBoxCoords.ll.y);
+
+		// check if actor and target are in the same horizontal corridor between the boxes
+		if ((_pos.y >= gateUpper && _pos.y <= gateLower) &&
+			(_walkdata.dest.y >= gateUpper && _walkdata.dest.y <= gateLower)) {
+			if (boxCoords.ll.x > curBoxCoords.lr.x) // next box is left
+				return intersectLineSegments(_pos, _walkdata.dest, boxCoords.ll, boxCoords.ul, foundPath);
+			else // next box is right
+				return intersectLineSegments(_pos, _walkdata.dest, boxCoords.lr, boxCoords.ur, foundPath);
+		}
+	// check if next walkbox is above or below actor's box
+	} else if (boxCoords.ul.y > curBoxCoords.ll.y || boxCoords.ll.y < curBoxCoords.ul.y) {
+		// determine vertical corridor gates
+		int gateLeft = MAX(boxCoords.ll.x, curBoxCoords.ll.x);
+		int gateRight = MIN(boxCoords.lr.x, curBoxCoords.lr.x);
+
+		// check if actor and target are in the same vertical corridor between the boxes
+		if ((_pos.x >= gateLeft && _pos.x <= gateRight) &&
+			(_walkdata.dest.x >= gateLeft && _walkdata.dest.x <= gateRight)) {
+			if (boxCoords.ul.y > curBoxCoords.ll.y) // next box is above
+				return intersectLineSegments(_pos, _walkdata.dest, boxCoords.ul, boxCoords.ur, foundPath);
+			else // next box is below
+				return intersectLineSegments(_pos, _walkdata.dest, boxCoords.ll, boxCoords.lr, foundPath);
+		}
+	}
+
+	return false;
+}
+
 void Actor_v2::walkActor() {
 	Common::Point foundPath, tmp;
 	int new_dir, next_box;
@@ -618,14 +702,7 @@ void Actor_v2::walkActor() {
 
 				_walkdata.curbox = next_box;
 
-				// WORKAROUND: The route of the meteor landing in the introduction isn't correct.
-				// MM V0 in contrast to MM V2 uses two walkboxes instead of just one. Hence a route
-				// from walkbox 1 to 0 is calculated first. This causes the meteor to fly on a
-				// horizontal line to walkbox 0 then vertically to the ground.
-				// To fix this problem, the box-to-box routing has been disabled in room 33.
-				if (_vm->_game.version == 0 && _vm->_currentRoom == 33) {
-					foundPath = _walkdata.dest;
-				} else {
+				if (!checkWalkboxesHaveDirectPath(foundPath)) {
 					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);
 				}
diff --git a/engines/scumm/actor.h b/engines/scumm/actor.h
index 69cfbfe398..0ed239d005 100644
--- a/engines/scumm/actor.h
+++ b/engines/scumm/actor.h
@@ -333,6 +333,7 @@ public:
 protected:
 	virtual bool isPlayer();
 	virtual void prepareDrawActorCostume(BaseCostumeRenderer *bcr);
+	virtual bool checkWalkboxesHaveDirectPath(Common::Point &foundPath);
 };
 
 enum ActorV0MiscFlags {
@@ -376,7 +377,9 @@ public:
 	virtual void saveLoadWithSerializer(Serializer *ser);
 
 protected:
-
+	bool intersectLineSegments(const Common::Point &line1Start, const Common::Point &line1End, 
+		const Common::Point &line2Start, const Common::Point &line2End, Common::Point &result);
+	virtual bool checkWalkboxesHaveDirectPath(Common::Point &foundPath);
 };