aboutsummaryrefslogtreecommitdiff
path: root/engines/scumm/boxes.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'engines/scumm/boxes.cpp')
-rw-r--r--engines/scumm/boxes.cpp1271
1 files changed, 1271 insertions, 0 deletions
diff --git a/engines/scumm/boxes.cpp b/engines/scumm/boxes.cpp
new file mode 100644
index 0000000000..4460519480
--- /dev/null
+++ b/engines/scumm/boxes.cpp
@@ -0,0 +1,1271 @@
+/* ScummVM - Scumm Interpreter
+ * Copyright (C) 2001 Ludvig Strigeus
+ * Copyright (C) 2001-2006 The ScummVM project
+ *
+ * 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 "common/stdafx.h"
+#include "scumm/scumm.h"
+#include "scumm/actor.h"
+#include "scumm/boxes.h"
+#include "scumm/util.h"
+
+#include "common/util.h"
+
+namespace Scumm {
+
+#if !defined(__GNUC__)
+ #pragma START_PACK_STRUCTS
+#endif
+
+struct Box { /* Internal walkbox file format */
+ union {
+ struct {
+ byte uy;
+ byte ly;
+ byte ulx;
+ byte urx;
+ byte llx;
+ byte lrx;
+ byte mask;
+ byte flags;
+ } GCC_PACK v2;
+
+ struct {
+ int16 ulx, uly;
+ int16 urx, ury;
+ int16 lrx, lry;
+ int16 llx, lly;
+ byte mask;
+ byte flags;
+ uint16 scale;
+ } GCC_PACK old;
+
+ struct {
+ int32 ulx, uly;
+ int32 urx, ury;
+ int32 lrx, lry;
+ int32 llx, lly;
+ uint32 mask;
+ uint32 flags;
+ uint32 scaleSlot;
+ uint32 scale;
+ uint32 unk2;
+ uint32 unk3;
+ } GCC_PACK v8;
+ } GCC_PACK;
+} GCC_PACK;
+
+#if !defined(__GNUC__)
+ #pragma END_PACK_STRUCTS
+#endif
+
+#define BOX_MATRIX_SIZE 2000
+#define BOX_DEBUG 0
+
+
+static bool compareSlope(int X1, int Y1, int X2, int Y2, int X3, int Y3);
+static Common::Point closestPtOnLine(const Common::Point &start, const Common::Point &end, int x, int y);
+
+
+byte ScummEngine::getMaskFromBox(int box) {
+ // Fix for bug #740244 and #755863. This appears to have been a
+ // long standing bug in the original engine?
+ if (_version <= 3 && box == 255)
+ return 1;
+
+ Box *ptr = getBoxBaseAddr(box);
+ if (!ptr)
+ return 0;
+
+ // WORKAROUND for bug #847827: This is a bug in the data files, as it also
+ // occurs with the original engine. We work around it here anyway.
+ if (_gameId == GID_INDY4 && _currentRoom == 225 && _roomResource == 94 && box == 8)
+ return 0;
+
+ if (_version == 8)
+ return (byte) FROM_LE_32(ptr->v8.mask);
+ else if (_version <= 2)
+ return ptr->v2.mask;
+ else
+ return ptr->old.mask;
+}
+
+void ScummEngine::setBoxFlags(int box, int val) {
+ debug(2, "setBoxFlags(%d, 0x%02x)", box, val);
+
+ /* SCUMM7+ stuff */
+ if (val & 0xC000) {
+ assert(box >= 0 && box < 65);
+ _extraBoxFlags[box] = val;
+ } else {
+ Box *ptr = getBoxBaseAddr(box);
+ if (!ptr)
+ return;
+ if (_version == 8)
+ ptr->v8.flags = TO_LE_32(val);
+ else if (_version <= 2)
+ ptr->v2.flags = val;
+ else
+ ptr->old.flags = val;
+ }
+}
+
+byte ScummEngine::getBoxFlags(int box) {
+ Box *ptr = getBoxBaseAddr(box);
+ if (!ptr)
+ return 0;
+ if (_version == 8)
+ return (byte) FROM_LE_32(ptr->v8.flags);
+ else if (_version <= 2)
+ return ptr->v2.flags;
+ else
+ return ptr->old.flags;
+}
+
+void ScummEngine::setBoxScale(int box, int scale) {
+ Box *ptr = getBoxBaseAddr(box);
+ assert(ptr);
+ if (_version == 8)
+ ptr->v8.scale = TO_LE_32(scale);
+ else if (_version <= 2)
+ error("This should not ever be called!");
+ else
+ ptr->old.scale = TO_LE_16(scale);
+}
+
+void ScummEngine::setBoxScaleSlot(int box, int slot) {
+ Box *ptr = getBoxBaseAddr(box);
+ assert(ptr);
+ ptr->v8.scaleSlot = TO_LE_32(slot);
+}
+
+int ScummEngine::getScale(int box, int x, int y) {
+ if (_features & GF_NO_SCALING)
+ return 255;
+
+ Box *ptr = getBoxBaseAddr(box);
+ if (!ptr)
+ return 255;
+
+ int slot , scale;
+
+ if (_version == 8) {
+ // COMI has a separate field for the scale slot...
+ slot = FROM_LE_32(ptr->v8.scaleSlot);
+ scale = FROM_LE_32(ptr->v8.scale);
+ } else {
+ scale = READ_LE_UINT16(&ptr->old.scale);
+ if (scale & 0x8000)
+ slot = (scale & 0x7FFF) + 1;
+ else
+ slot = 0;
+ }
+
+ // Was a scale slot specified? If so, we compute the effective scale
+ // from it, ignoring the box scale.
+ if (slot)
+ scale = getScaleFromSlot(slot, x, y);
+
+ return scale;
+}
+
+
+int ScummEngine::getScaleFromSlot(int slot, int x, int y) {
+ assert(1 <= slot && slot <= ARRAYSIZE(_scaleSlots));
+ int scale;
+ int scaleX = 0, scaleY = 0;
+ ScaleSlot &s = _scaleSlots[slot-1];
+
+ if (s.y1 == s.y2 && s.x1 == s.x2)
+ error("Invalid scale slot %d", slot);
+
+ if (s.y1 != s.y2) {
+ if (y < 0)
+ y = 0;
+
+ scaleY = (s.scale2 - s.scale1) * (y - s.y1) / (s.y2 - s.y1) + s.scale1;
+ }
+ if (s.x1 == s.x2) {
+ scale = scaleY;
+ } else {
+ scaleX = (s.scale2 - s.scale1) * (x - s.x1) / (s.x2 - s.x1) + s.scale1;
+
+ if (s.y1 == s.y2) {
+ scale = scaleX;
+ } else {
+ scale = (scaleX + scaleY) / 2;
+ }
+ }
+
+ // Clip the scale to range 1-255
+ if (scale < 1)
+ scale = 1;
+ else if (scale > 255)
+ scale = 255;
+
+ return scale;
+}
+
+int ScummEngine::getBoxScale(int box) {
+ if (_features & GF_NO_SCALING)
+ return 255;
+ Box *ptr = getBoxBaseAddr(box);
+ if (!ptr)
+ return 255;
+ if (_version == 8)
+ return FROM_LE_32(ptr->v8.scale);
+ else
+ return READ_LE_UINT16(&ptr->old.scale);
+}
+
+/**
+ * Convert a rtScaleTable resource to a corresponding scale slot entry.
+ *
+ * At some point, we discovered that the old scale items (stored in rtScaleTable
+ * resources) are in fact the same as (or rather, a predecessor of) the
+ * scale slots used in COMI. While not being precomputed (and thus slightly
+ * slower), scale slots are more flexible, and most importantly, can cope with
+ * rooms higher than 200 pixels. That's an essential feature for DIG and FT
+ * and in fact the lack of it caused various bugs in the past.
+ *
+ * Hence, we decided to switch all games to use the more powerful scale slots.
+ * To accomodate old savegames, we attempt here to convert rtScaleTable
+ * resources to scale slots.
+ */
+void ScummEngine::convertScaleTableToScaleSlot(int slot) {
+ assert(1 <= slot && slot <= ARRAYSIZE(_scaleSlots));
+
+ byte *resptr = getResourceAddress(rtScaleTable, slot);
+ int lowerIdx, upperIdx;
+ float m, oldM;
+
+ // Do nothing if the given scale table doesn't exist
+ if (resptr == 0)
+ return;
+
+ if (resptr[0] == resptr[199]) {
+ // The scale is constant. This usually means we encountered one of the
+ // "broken" cases. We set pseudo scale item values which lead to a
+ // constant scale of 255.
+ setScaleSlot(slot, 0, 0, 255, 0, 199, 255);
+ return;
+ }
+
+ /*
+ * Essentially, what we are doing here is some kind of "line fitting"
+ * algorithm. The data in the scale table represents a linear graph. What
+ * we want to find is the slope and (vertical) offset of this line. Things
+ * are complicated by the fact that the line is cut of vertically at 1 and
+ * 255. We have to be careful in handling this and some border cases.
+ *
+ * Some typical graphs look like these:
+ * --- --- ---
+ * / --- \
+ * ___/ --- \___
+ *
+ * The method used here is to compute the slope of secants fixed at the
+ * left and right end. For most cases this detects the cut-over points
+ * quite accurately.
+ */
+
+ // Search for the bend on the left side
+ m = (resptr[199] - resptr[0]) / 199.0;
+ for (lowerIdx = 0; lowerIdx < 199 && (resptr[lowerIdx] == 1 || resptr[lowerIdx] == 255); lowerIdx++) {
+ oldM = m;
+ m = (resptr[199] - resptr[lowerIdx+1]) / (float)(199 - (lowerIdx+1));
+ if (m > 0) {
+ if (m <= oldM)
+ break;
+ } else {
+ if (m >= oldM)
+ break;
+ }
+ }
+
+ // Search for the bend on the right side
+ m = (resptr[199] - resptr[0]) / 199.0;
+ for (upperIdx = 199; upperIdx > 1 && (resptr[upperIdx] == 1 || resptr[upperIdx] == 255); upperIdx--) {
+ oldM = m;
+ m = (resptr[upperIdx-1] - resptr[0]) / (float)(upperIdx-1);
+ if (m > 0) {
+ if (m <= oldM)
+ break;
+ } else {
+ if (m >= oldM)
+ break;
+ }
+ }
+
+ // If lowerIdx and upperIdx are equal, we assume that there
+ // was no bend at all, and go for the maximum range.
+ if (lowerIdx == upperIdx) {
+ lowerIdx = 0;
+ upperIdx = 199;
+ }
+
+ // The values of y1 and y2, as well as the scale, can now easily be computed
+ setScaleSlot(slot, 0, lowerIdx, resptr[lowerIdx], 0, upperIdx, resptr[upperIdx]);
+
+ // Compute the variance, for debugging. It shouldn't exceed 1
+ ScaleSlot &s = _scaleSlots[slot-1];
+ int y;
+ int sum = 0;
+ int scale;
+ float variance;
+ for (y = 0; y < 200; y++) {
+ scale = (s.scale2 - s.scale1) * (y - s.y1) / (s.y2 - s.y1) + s.scale1;
+ if (scale < 1)
+ scale = 1;
+ else if (scale > 255)
+ scale = 255;
+
+ sum += (resptr[y] - scale) * (resptr[y] - scale);
+ }
+ variance = sum / (200.0 - 1.0);
+ if (variance > 1)
+ debug(1, "scale item %d, variance %f exceeds 1 (room %d)", slot, variance, _currentRoom);
+}
+
+void ScummEngine::setScaleSlot(int slot, int x1, int y1, int scale1, int x2, int y2, int scale2) {
+ assert(1 <= slot && slot <= ARRAYSIZE(_scaleSlots));
+ ScaleSlot &s = _scaleSlots[slot-1];
+ s.x2 = x2;
+ s.y2 = y2;
+ s.scale2 = scale2;
+ s.x1 = x1;
+ s.y1 = y1;
+ s.scale1 = scale1;
+}
+
+byte ScummEngine::getNumBoxes() {
+ byte *ptr = getResourceAddress(rtMatrix, 2);
+ if (!ptr)
+ return 0;
+ if (_version == 8)
+ return (byte) READ_LE_UINT32(ptr);
+ else
+ return ptr[0];
+}
+
+Box *ScummEngine::getBoxBaseAddr(int box) {
+ byte *ptr = getResourceAddress(rtMatrix, 2);
+ if (!ptr || box == 255)
+ return NULL;
+
+ // The NES version of Maniac Mansion attempts to set flags for boxes 2-4
+ // when there are only three boxes (0-2) when walking out to the garage.
+ if ((_gameId == GID_MANIAC) && (_platform == Common::kPlatformNES) && (box >= ptr[0]))
+ return NULL;
+
+ // FIXME: In "pass to adventure", the loom demo, when bobbin enters
+ // the tent to the elders, box = 2, but ptr[0] = 2 -> errors out.
+ // Hence we disable the check for now. Maybe in PASS (and other old games)
+ // we shouldn't subtract 1 from ptr[0] when performing the check?
+ // this also seems to be incorrect for atari st demo of zak
+ // and assumingly other v2 games
+ // The same happens in Indy3EGA (see bug #770351)
+ // Also happens in ZakEGA (see bug #771803).
+ //
+ // This *might* mean that we have a bug in our box implementation
+ // OTOH, the original engine, unlike ScummVM, performed no bound
+ // checking at all. All the problems so far have been cases where
+ // the value was exactly one more than what we consider the maximum.
+ // So it's very well possible that all of these are script errors.
+ if (_version <= 4 && ptr[0] == box)
+ box--;
+
+ checkRange(ptr[0] - 1, 0, box, "Illegal box %d");
+ if (_version <= 2)
+ return (Box *)(ptr + box * SIZEOF_BOX_V2 + 1);
+ else if (_version == 3)
+ return (Box *)(ptr + box * SIZEOF_BOX_V3 + 1);
+ else if (_features & GF_SMALL_HEADER)
+ return (Box *)(ptr + box * SIZEOF_BOX + 1);
+ else if (_version == 8)
+ return (Box *)(ptr + box * SIZEOF_BOX_V8 + 4);
+ else
+ return (Box *)(ptr + box * SIZEOF_BOX + 2);
+}
+
+int ScummEngine::getSpecialBox(int x, int y) {
+ int i;
+ int numOfBoxes;
+ byte flag;
+
+ numOfBoxes = getNumBoxes() - 1;
+
+ for (i = numOfBoxes; i >= 0; i--) {
+ flag = getBoxFlags(i);
+
+ if (!(flag & kBoxInvisible) && (flag & kBoxPlayerOnly))
+ return (-1);
+
+ if (checkXYInBoxBounds(i, x, y))
+ return (i);
+ }
+
+ return (-1);
+}
+
+bool ScummEngine::checkXYInBoxBounds(int b, int x, int y) {
+ BoxCoords box;
+
+ if (b < 0 || b == Actor::kInvalidBox)
+ return false;
+
+ getBoxCoordinates(b, &box);
+
+ if (x < box.ul.x && x < box.ur.x && x < box.lr.x && x < box.ll.x)
+ return false;
+
+ if (x > box.ul.x && x > box.ur.x && x > box.lr.x && x > box.ll.x)
+ return false;
+
+ if (y < box.ul.y && y < box.ur.y && y < box.lr.y && y < box.ll.y)
+ return false;
+
+ if (y > box.ul.y && y > box.ur.y && y > box.lr.y && y > box.ll.y)
+ return false;
+
+ if (box.ul.x == box.ur.x && box.ul.y == box.ur.y && box.lr.x == box.ll.x && box.lr.y == box.ll.y ||
+ box.ul.x == box.ll.x && box.ul.y == box.ll.y && box.ur.x == box.lr.x && box.ur.y == box.lr.y) {
+
+ Common::Point pt;
+ pt = closestPtOnLine(box.ul, box.lr, x, y);
+ if (distanceFromPt(x, y, pt.x, pt.y) <= 4)
+ return true;
+ }
+
+ if (!compareSlope(box.ul.x, box.ul.y, box.ur.x, box.ur.y, x, y))
+ return false;
+
+ if (!compareSlope(box.ur.x, box.ur.y, box.lr.x, box.lr.y, x, y))
+ return false;
+
+ if (!compareSlope(box.ll.x, box.ll.y, x, y, box.lr.x, box.lr.y))
+ return false;
+
+ if (!compareSlope(box.ul.x, box.ul.y, x, y, box.ll.x, box.ll.y))
+ return false;
+
+ return true;
+}
+
+void ScummEngine::getBoxCoordinates(int boxnum, BoxCoords *box) {
+ Box *bp = getBoxBaseAddr(boxnum);
+ assert(bp);
+
+ if (_version == 8) {
+ box->ul.x = (short)FROM_LE_32(bp->v8.ulx);
+ box->ul.y = (short)FROM_LE_32(bp->v8.uly);
+ box->ur.x = (short)FROM_LE_32(bp->v8.urx);
+ box->ur.y = (short)FROM_LE_32(bp->v8.ury);
+
+ box->ll.x = (short)FROM_LE_32(bp->v8.llx);
+ box->ll.y = (short)FROM_LE_32(bp->v8.lly);
+ box->lr.x = (short)FROM_LE_32(bp->v8.lrx);
+ box->lr.y = (short)FROM_LE_32(bp->v8.lry);
+
+ // FIXME: Some walkboxes in CMI appear to have been flipped,
+ // in the sense that for instance the lower boundary is above
+ // the upper one. Can that really be the case, or is there
+ // some more sinister problem afoot?
+ //
+ // Is this fix sufficient, or will we need something more
+ // elaborate?
+
+ if (box->ul.y > box->ll.y && box->ur.y > box->lr.y) {
+ SWAP(box->ul, box->ll);
+ SWAP(box->ur, box->lr);
+ }
+
+ if (box->ul.x > box->ur.x && box->ll.x > box->lr.x) {
+ SWAP(box->ul, box->ur);
+ SWAP(box->ll, box->lr);
+ }
+ } else if (_version <= 2) {
+ box->ul.x = bp->v2.ulx * 8;
+ box->ul.y = bp->v2.uy * 2;
+ box->ur.x = bp->v2.urx * 8;
+ box->ur.y = bp->v2.uy * 2;
+
+ box->ll.x = bp->v2.llx * 8;
+ box->ll.y = bp->v2.ly * 2;
+ box->lr.x = bp->v2.lrx * 8;
+ box->lr.y = bp->v2.ly * 2;
+ } else {
+ box->ul.x = (int16)READ_LE_UINT16(&bp->old.ulx);
+ box->ul.y = (int16)READ_LE_UINT16(&bp->old.uly);
+ box->ur.x = (int16)READ_LE_UINT16(&bp->old.urx);
+ box->ur.y = (int16)READ_LE_UINT16(&bp->old.ury);
+
+ box->ll.x = (int16)READ_LE_UINT16(&bp->old.llx);
+ box->ll.y = (int16)READ_LE_UINT16(&bp->old.lly);
+ box->lr.x = (int16)READ_LE_UINT16(&bp->old.lrx);
+ box->lr.y = (int16)READ_LE_UINT16(&bp->old.lry);
+ }
+}
+
+uint ScummEngine::distanceFromPt(int x, int y, int ptx, int pty) {
+ int diffx, diffy;
+
+ diffx = ABS(ptx - x);
+
+ if (diffx >= 0x1000)
+ return 0xFFFFFF;
+
+ diffy = ABS(pty - y);
+
+ if (diffy >= 0x1000)
+ return 0xFFFFFF;
+ diffx *= diffx;
+ diffy *= diffy;
+ return diffx + diffy;
+}
+
+
+bool compareSlope(int X1, int Y1, int X2, int Y2, int X3, int Y3) {
+ return (Y2 - Y1) * (X3 - X1) <= (Y3 - Y1) * (X2 - X1);
+}
+
+/**
+ * Find the point on a line segment which is closest to a given point.
+ *
+ * @param start the start of the line segment
+ * @param end the end of the line segment
+ * @param x the x coordinate of the point which we want to 'project' on the line segment
+ * @param y the y coordinate of the point which we want to 'project' on the line segment
+ * @return the point on the line segmen closes to the given point
+ */
+Common::Point closestPtOnLine(const Common::Point &start, const Common::Point &end, int x, int y) {
+ Common::Point pt;
+
+ const int lxdiff = end.x - start.x;
+ const int lydiff = end.y - start.y;
+
+ if (end.x == start.x) { // Vertical line?
+ pt.x = start.x;
+ pt.y = y;
+ } else if (end.y == start.y) { // Horizontal line?
+ pt.x = x;
+ pt.y = start.y;
+ } else {
+ const int dist = lxdiff * lxdiff + lydiff * lydiff;
+ int a, b, c;
+ if (ABS(lxdiff) > ABS(lydiff)) {
+ a = start.x * lydiff / lxdiff;
+ b = x * lxdiff / lydiff;
+
+ c = (a + b - start.y + y) * lydiff * lxdiff / dist;
+
+ pt.x = c;
+ pt.y = c * lydiff / lxdiff - a + start.y;
+ } else {
+ a = start.y * lxdiff / lydiff;
+ b = y * lydiff / lxdiff;
+
+ c = (a + b - start.x + x) * lydiff * lxdiff / dist;
+
+ pt.y = c;
+ pt.x = c * lxdiff / lydiff - a + start.x;
+ }
+ }
+
+ if (ABS(lydiff) < ABS(lxdiff)) {
+ if (lxdiff > 0) {
+ if (pt.x < start.x)
+ pt = start;
+ else if (pt.x > end.x)
+ pt = end;
+ } else {
+ if (pt.x > start.x)
+ pt = start;
+ else if (pt.x < end.x)
+ pt = end;
+ }
+ } else {
+ if (lydiff > 0) {
+ if (pt.y < start.y)
+ pt = start;
+ else if (pt.y > end.y)
+ pt = end;
+ } else {
+ if (pt.y > start.y)
+ pt = start;
+ else if (pt.y < end.y)
+ pt = end;
+ }
+ }
+
+ return pt;
+}
+
+bool ScummEngine::inBoxQuickReject(int b, int x, int y, int threshold) {
+ int t;
+ BoxCoords box;
+
+ getBoxCoordinates(b, &box);
+
+ t = x - threshold;
+ if (t > box.ul.x && t > box.ur.x && t > box.lr.x && t > box.ll.x)
+ return true;
+
+ t = x + threshold;
+ if (t < box.ul.x && t < box.ur.x && t < box.lr.x && t < box.ll.x)
+ return true;
+
+ t = y - threshold;
+ if (t > box.ul.y && t > box.ur.y && t > box.lr.y && t > box.ll.y)
+ return true;
+
+ t = y + threshold;
+ if (t < box.ul.y && t < box.ur.y && t < box.lr.y && t < box.ll.y)
+ return true;
+
+ return false;
+}
+
+int ScummEngine::getClosestPtOnBox(int b, int x, int y, int16& outX, int16& outY) {
+ Common::Point pt;
+ uint dist;
+ uint bestdist = 0xFFFFFF;
+ BoxCoords box;
+
+ getBoxCoordinates(b, &box);
+
+ pt = closestPtOnLine(box.ul, box.ur, x, y);
+ dist = distanceFromPt(x, y, pt.x, pt.y);
+ if (dist < bestdist) {
+ bestdist = dist;
+ outX = pt.x;
+ outY = pt.y;
+ }
+
+ pt = closestPtOnLine(box.ur, box.lr, x, y);
+ dist = distanceFromPt(x, y, pt.x, pt.y);
+ if (dist < bestdist) {
+ bestdist = dist;
+ outX = pt.x;
+ outY = pt.y;
+ }
+
+ pt = closestPtOnLine(box.lr, box.ll, x, y);
+ dist = distanceFromPt(x, y, pt.x, pt.y);
+ if (dist < bestdist) {
+ bestdist = dist;
+ outX = pt.x;
+ outY = pt.y;
+ }
+
+ pt = closestPtOnLine(box.ll, box.ul, x, y);
+ dist = distanceFromPt(x, y, pt.x, pt.y);
+ if (dist < bestdist) {
+ bestdist = dist;
+ outX = pt.x;
+ outY = pt.y;
+ }
+
+ return bestdist;
+}
+
+byte *ScummEngine::getBoxMatrixBaseAddr() {
+ byte *ptr = getResourceAddress(rtMatrix, 1);
+ assert(ptr);
+ if (*ptr == 0xFF)
+ ptr++;
+ return ptr;
+}
+
+/*
+ * Compute if there is a way that connects box 'from' with box 'to'.
+ * Returns the number of a box adjactant to 'from' that is the next on the
+ * 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) {
+ const byte *boxm;
+ byte i;
+ const int numOfBoxes = getNumBoxes();
+ int dest = -1;
+
+ if (from == to)
+ return to;
+
+ if (to == Actor::kInvalidBox)
+ return -1;
+
+ if (from == Actor::kInvalidBox)
+ return to;
+
+ assert(from < numOfBoxes);
+ assert(to < numOfBoxes);
+
+ boxm = getBoxMatrixBaseAddr();
+
+ if (_version <= 2) {
+ // The v2 box matrix is a real matrix with numOfBoxes rows and columns.
+ // The first numOfBoxes bytes contain indices to the start of the corresponding
+ // row (although that seems unnecessary to me - the value is easily computable.
+ boxm += numOfBoxes + boxm[from];
+ return (int8)boxm[to];
+ }
+
+ // WORKAROUND #1: It seems that in some cases, the box matrix is corrupt
+ // (more precisely, is too short) in the datafiles already. In
+ // particular this seems to be the case in room 46 of Indy3 EGA (see
+ // also bug #770690). This didn't cause problems in the original
+ // engine, because there, the memory layout is different. After the
+ // walkbox would follow the rest of the room file, thus the program
+ // always behaved the same (and by chance, correct). Not so for us,
+ // since random data may follow after the resource in ScummVM.
+ //
+ // As a workaround, we add a check for the end of the box matrix
+ // resource, and abort the search once we reach the end.
+ const byte *end = boxm + getResourceSize(rtMatrix, 1);
+
+ // WORKAROUND #2: In addition to the above, we have to add this special
+ // case to fix the scene in Indy3 where Indy meets Hitler in Berlin.
+ // See bug #770690 and also bug #774783.
+ if ((_gameId == GID_INDY3) && _roomResource == 46 && from == 1 && to == 0)
+ return 0;
+
+ // Skip up to the matrix data for box 'from'
+ for (i = 0; i < from && boxm < end; i++) {
+ while (boxm < end && *boxm != 0xFF)
+ boxm += 3;
+ boxm++;
+ }
+
+ // Now search for the entry for box 'to'
+ while (boxm < end && boxm[0] != 0xFF) {
+ if (boxm[0] <= to && to <= boxm[1])
+ dest = (int8)boxm[2];
+ boxm += 3;
+ }
+
+ if (boxm >= end)
+ debug(0, "The box matrix apparently is truncated (room %d)", _roomResource);
+
+ return dest;
+}
+
+/*
+ * Computes the next point actor a has to walk towards in a straight
+ * line in order to get from box1 to box3 via box2.
+ */
+bool Actor::findPathTowards(byte box1nr, byte box2nr, byte box3nr, Common::Point &foundPath) {
+ BoxCoords box1;
+ BoxCoords box2;
+ Common::Point tmp;
+ int i, j;
+ int flag;
+ int q, pos;
+
+ _vm->getBoxCoordinates(box1nr, &box1);
+ _vm->getBoxCoordinates(box2nr, &box2);
+
+ for (i = 0; i < 4; i++) {
+ for (j = 0; j < 4; j++) {
+ if (box1.ul.x == box1.ur.x && box1.ul.x == box2.ul.x && box1.ul.x == box2.ur.x) {
+ flag = 0;
+ if (box1.ul.y > box1.ur.y) {
+ SWAP(box1.ul.y, box1.ur.y);
+ flag |= 1;
+ }
+
+ if (box2.ul.y > box2.ur.y) {
+ SWAP(box2.ul.y, box2.ur.y);
+ flag |= 2;
+ }
+
+ if (box1.ul.y > box2.ur.y || box2.ul.y > box1.ur.y ||
+ (box1.ur.y == box2.ul.y || box2.ur.y == box1.ul.y) &&
+ box1.ul.y != box1.ur.y && box2.ul.y != box2.ur.y) {
+ if (flag & 1)
+ SWAP(box1.ul.y, box1.ur.y);
+ if (flag & 2)
+ SWAP(box2.ul.y, box2.ur.y);
+ } else {
+ pos = _pos.y;
+ if (box2nr == box3nr) {
+ int diffX = _walkdata.dest.x - _pos.x;
+ int diffY = _walkdata.dest.y - _pos.y;
+ int boxDiffX = box1.ul.x - _pos.x;
+
+ if (diffX != 0) {
+ int t;
+
+ diffY *= boxDiffX;
+ t = diffY / diffX;
+ if (t == 0 && (diffY <= 0 || diffX <= 0)
+ && (diffY >= 0 || diffX >= 0))
+ t = -1;
+ pos = _pos.y + t;
+ }
+ }
+
+ q = pos;
+ if (q < box2.ul.y)
+ q = box2.ul.y;
+ if (q > box2.ur.y)
+ q = box2.ur.y;
+ if (q < box1.ul.y)
+ q = box1.ul.y;
+ if (q > box1.ur.y)
+ q = box1.ur.y;
+ if (q == pos && box2nr == box3nr)
+ return true;
+ foundPath.y = q;
+ foundPath.x = box1.ul.x;
+ return false;
+ }
+ }
+
+ if (box1.ul.y == box1.ur.y && box1.ul.y == box2.ul.y && box1.ul.y == box2.ur.y) {
+ flag = 0;
+ if (box1.ul.x > box1.ur.x) {
+ SWAP(box1.ul.x, box1.ur.x);
+ flag |= 1;
+ }
+
+ if (box2.ul.x > box2.ur.x) {
+ SWAP(box2.ul.x, box2.ur.x);
+ flag |= 2;
+ }
+
+ if (box1.ul.x > box2.ur.x || box2.ul.x > box1.ur.x ||
+ (box1.ur.x == box2.ul.x || box2.ur.x == box1.ul.x) &&
+ box1.ul.x != box1.ur.x && box2.ul.x != box2.ur.x) {
+ if (flag & 1)
+ SWAP(box1.ul.x, box1.ur.x);
+ if (flag & 2)
+ SWAP(box2.ul.x, box2.ur.x);
+ } else {
+
+ if (box2nr == box3nr) {
+ int diffX = _walkdata.dest.x - _pos.x;
+ int diffY = _walkdata.dest.y - _pos.y;
+ int boxDiffY = box1.ul.y - _pos.y;
+
+ pos = _pos.x;
+ if (diffY != 0) {
+ pos += diffX * boxDiffY / diffY;
+ }
+ } else {
+ pos = _pos.x;
+ }
+
+ q = pos;
+ if (q < box2.ul.x)
+ q = box2.ul.x;
+ if (q > box2.ur.x)
+ q = box2.ur.x;
+ if (q < box1.ul.x)
+ q = box1.ul.x;
+ if (q > box1.ur.x)
+ q = box1.ur.x;
+ if (q == pos && box2nr == box3nr)
+ return true;
+ foundPath.x = q;
+ foundPath.y = box1.ul.y;
+ return false;
+ }
+ }
+ tmp = box1.ul;
+ box1.ul = box1.ur;
+ box1.ur = box1.lr;
+ box1.lr = box1.ll;
+ box1.ll = tmp;
+ }
+ tmp = box2.ul;
+ box2.ul = box2.ur;
+ box2.ur = box2.lr;
+ box2.lr = box2.ll;
+ box2.ll = tmp;
+ }
+ return false;
+}
+
+#if BOX_DEBUG
+static void printMatrix(byte *boxm, int num) {
+ int i;
+ for (i = 0; i < num; i++) {
+ printf("%d: ", i);
+ while (*boxm != 0xFF) {
+ printf("%d, ", *boxm);
+ boxm++;
+ }
+ boxm++;
+ printf("\n");
+ }
+}
+
+static void printMatrix2(byte *matrix, int num) {
+ int i, j;
+ printf(" ");
+ for (i = 0; i < num; i++)
+ printf("%2d ", i);
+ printf("\n");
+ for (i = 0; i < num; i++) {
+ printf("%2d: ", i);
+ for (j = 0; j < num; j++) {
+ int val = matrix[i * 64 + j];
+ if (val == Actor::kInvalidBox)
+ printf(" ? ");
+ else
+ printf("%2d ", val);
+ }
+ printf("\n");
+ }
+}
+#endif
+
+void ScummEngine::createBoxMatrix() {
+ int num, i, j, k;
+ byte *adjacentMatrix, *itineraryMatrix;
+
+ // The total number of boxes
+ num = getNumBoxes();
+ assert(num <= 64);
+
+ // Allocate the adjacent & itinerary matrices
+ adjacentMatrix = (byte *)malloc(64 * 64);
+ itineraryMatrix = (byte *)malloc(64 * 64);
+
+ // Initialise the adjacent matrix: each box has distance 0 to itself,
+ // and distance 1 to its direct neighbors. Initially, it has distance
+ // 255 (= infinity) to all other boxes.
+ for (i = 0; i < num; i++) {
+ for (j = 0; j < num; j++) {
+ if (i == j) {
+ adjacentMatrix[i * 64 + j] = 0;
+ itineraryMatrix[i * 64 + j] = j;
+ } else if (areBoxesNeighbours(i, j)) {
+ adjacentMatrix[i * 64 + j] = 1;
+ itineraryMatrix[i * 64 + j] = j;
+ } else {
+ adjacentMatrix[i * 64 + j] = 255;
+ itineraryMatrix[i * 64 + j] = Actor::kInvalidBox;
+ }
+ }
+ }
+
+ // Compute the shortest routes between boxes via Kleene's algorithm.
+ // The original code used some kind of mangled Dijkstra's algorithm;
+ // while that might in theory be slightly faster, it was
+ // a) extremly obfuscated
+ // b) incorrect: it didn't always find the shortest paths
+ // c) not any faster in reality for our sparse & small adjacent matrices
+ for (k = 0; k < num; k++) {
+ for (i = 0; i < num; i++) {
+ for (j = 0; j < num; j++) {
+ if (i == j)
+ continue;
+ byte distIK = adjacentMatrix[64 * i + k];
+ byte distKJ = adjacentMatrix[64 * k + j];
+ if (adjacentMatrix[64 * i + j] > distIK + distKJ) {
+ adjacentMatrix[64 * i + j] = distIK + distKJ;
+ itineraryMatrix[64 * i + j] = itineraryMatrix[64 * i + k];
+ }
+ }
+ }
+
+ }
+
+ // "Compress" the distance matrix into the box matrix format used
+ // by the engine. The format is like this:
+ // For each box (from 0 to num) there is first a byte with value 0xFF,
+ // followed by an arbitrary number of byte triples; the end is marked
+ // again by the lead 0xFF for the next "row". The meaning of the
+ // byte triples is as follows: the first two bytes define a range
+ // of box numbers (e.g. 7-11), while the third byte defines an
+ // 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.
+
+ byte *matrixStart = res.createResource(rtMatrix, 1, BOX_MATRIX_SIZE);
+ const byte *matrixEnd = matrixStart + BOX_MATRIX_SIZE;
+
+ #define addToMatrix(b) do { *matrixStart++ = (b); assert(matrixStart < matrixEnd); } while (0)
+
+ for (i = 0; i < num; i++) {
+ addToMatrix(0xFF);
+ for (j = 0; j < num; j++) {
+ byte itinerary = itineraryMatrix[64 * i + j];
+ if (itinerary != Actor::kInvalidBox) {
+ addToMatrix(j);
+ while (j < num - 1 && itinerary == itineraryMatrix[64 * i + (j + 1)])
+ j++;
+ addToMatrix(j);
+ addToMatrix(itinerary);
+ }
+ }
+ }
+ addToMatrix(0xFF);
+
+
+#if BOX_DEBUG
+ printf("Itinerary matrix:\n");
+ printMatrix2(itineraryMatrix, num);
+ printf("compressed matrix:\n");
+ printMatrix(getBoxMatrixBaseAddr(), num);
+#endif
+
+ free(adjacentMatrix);
+ free(itineraryMatrix);
+}
+
+/** Check if two boxes are neighbours. */
+bool ScummEngine::areBoxesNeighbours(int box1nr, int box2nr) {
+ Common::Point tmp;
+ BoxCoords box;
+ BoxCoords box2;
+
+ if (getBoxFlags(box1nr) & kBoxInvisible || getBoxFlags(box2nr) & kBoxInvisible)
+ return false;
+
+ getBoxCoordinates(box1nr, &box2);
+ getBoxCoordinates(box2nr, &box);
+
+ // Roughly, the idea of this algorithm is to check if we can find
+ // two sides of the two given boxes which touch.
+ // In order to keep te code simple, we only match the upper sides;
+ // then, we "rotate" the box coordinates four times each, for a total
+ // of 16 comparisions (four sides compared with four sides each).
+ for (int j = 0; j < 4; j++) {
+ for (int k = 0; k < 4; k++) {
+ // Are the "upper" sides of the boxes on a single vertical line
+ // (i.e. all share one x value) ?
+ if (box2.ur.x == box2.ul.x && box.ul.x == box2.ul.x && box.ur.x == box2.ul.x) {
+ bool swappedBox2 = false, swappedBox1 = false;
+ if (box2.ur.y < box2.ul.y) {
+ swappedBox2 = 1;
+ SWAP(box2.ur.y, box2.ul.y);
+ }
+ if (box.ur.y < box.ul.y) {
+ swappedBox1 = 1;
+ SWAP(box.ur.y, box.ul.y);
+ }
+ if (box.ur.y < box2.ul.y ||
+ box.ul.y > box2.ur.y ||
+ (box.ul.y == box2.ur.y ||
+ box.ur.y == box2.ul.y) && box2.ur.y != box2.ul.y && box.ul.y != box.ur.y) {
+ } else {
+ return true;
+ }
+
+ // Swap back if necessary
+ if (swappedBox2) {
+ SWAP(box2.ur.y, box2.ul.y);
+ }
+ if (swappedBox1) {
+ SWAP(box.ur.y, box.ul.y);
+ }
+ }
+
+ // Are the "upper" sides of the boxes on a single horizontal line
+ // (i.e. all share one y value) ?
+ if (box2.ur.y == box2.ul.y && box.ul.y == box2.ul.y && box.ur.y == box2.ul.y) {
+ bool swappedBox2 = false, swappedBox1 = false;
+ if (box2.ur.x < box2.ul.x) {
+ swappedBox2 = 1;
+ SWAP(box2.ur.x, box2.ul.x);
+ }
+ if (box.ur.x < box.ul.x) {
+ swappedBox1 = 1;
+ SWAP(box.ur.x, box.ul.x);
+ }
+ if (box.ur.x < box2.ul.x ||
+ box.ul.x > box2.ur.x ||
+ (box.ul.x == box2.ur.x ||
+ box.ur.x == box2.ul.x) && box2.ur.x != box2.ul.x && box.ul.x != box.ur.x) {
+
+ } else {
+ return true;
+ }
+
+ // Swap back if necessary
+ if (swappedBox2) {
+ SWAP(box2.ur.x, box2.ul.x);
+ }
+ if (swappedBox1) {
+ SWAP(box.ur.x, box.ul.x);
+ }
+ }
+
+ // "Rotate" the box coordinates
+ tmp = box2.ul;
+ box2.ul = box2.ur;
+ box2.ur = box2.lr;
+ box2.lr = box2.ll;
+ box2.ll = tmp;
+ }
+
+ // "Rotate" the box coordinates
+ tmp = box.ul;
+ box.ul = box.ur;
+ box.ur = box.lr;
+ box.lr = box.ll;
+ box.ll = tmp;
+ }
+
+ return false;
+}
+
+void Actor::findPathTowardsOld(byte box1, byte box2, byte finalBox, Common::Point &p2, Common::Point &p3) {
+ Common::Point pt;
+ Common::Point gateA[2];
+ Common::Point gateB[2];
+
+ _vm->getGates(box1, box2, gateA, gateB);
+
+ p2.x = 32000;
+ p3.x = 32000;
+
+ // next box (box2) = final box?
+ if (box2 == finalBox) {
+ // In Indy3, the masks (= z-level) have to match, too -- needed for the
+ // 'maze' in the zeppeling (see bug #1032964).
+ if (_vm->_gameId != GID_INDY3 || _vm->getMaskFromBox(box1) == _vm->getMaskFromBox(box2)) {
+ // Is the actor (x,y) between both gates?
+ if (compareSlope(_pos.x, _pos.y, _walkdata.dest.x, _walkdata.dest.y, gateA[0].x, gateA[0].y) !=
+ compareSlope(_pos.x, _pos.y, _walkdata.dest.x, _walkdata.dest.y, gateB[0].x, gateB[0].y) &&
+ compareSlope(_pos.x, _pos.y, _walkdata.dest.x, _walkdata.dest.y, gateA[1].x, gateA[1].y) !=
+ compareSlope(_pos.x, _pos.y, _walkdata.dest.x, _walkdata.dest.y, gateB[1].x, gateB[1].y)) {
+ return;
+ }
+ }
+ }
+
+ p3 = pt = closestPtOnLine(gateA[1], gateB[1], _pos.x, _pos.y);
+
+ if (compareSlope(_pos.x, _pos.y, p3.x, p3.y, gateA[0].x, gateA[0].y) ==
+ compareSlope(_pos.x, _pos.y, p3.x, p3.y, gateB[0].x, gateB[0].y)) {
+ closestPtOnLine(gateA[0], gateB[0], _pos.x, _pos.y);
+ p2 = pt; // if point 2 between gates, ignore!
+ }
+}
+
+/**
+ * Compute the "gate" between two boxes. The gate is a pair of two lines which
+ * both start on box 'box1' and end on 'box2'. For both lines, one of its
+ * end points is the corner point of one of the two boxes. The other end point
+ * is a point on the other point closest to first end point.
+ * This way the lines bound a 'corridor' between the two boxes, through which
+ * the actor has to walk to get from box1 to box2.
+ */
+void ScummEngine::getGates(int box1, int box2, Common::Point gateA[2], Common::Point gateB[2]) {
+ int i, j;
+ int dist[8];
+ int minDist[3];
+ int closest[3];
+ int box[3];
+ BoxCoords coords;
+ Common::Point closestPoint[8];
+ Common::Point boxCorner[8];
+ int line1, line2;
+
+ // For all corner coordinates of the first box, compute the point closest
+ // to them on the second box (and also compute the distance of these points).
+ getBoxCoordinates(box1, &coords);
+ boxCorner[0] = coords.ul;
+ boxCorner[1] = coords.ur;
+ boxCorner[2] = coords.lr;
+ boxCorner[3] = coords.ll;
+ for (i = 0; i < 4; i++) {
+ dist[i] = getClosestPtOnBox(box2, boxCorner[i].x, boxCorner[i].y, closestPoint[i].x, closestPoint[i].y);
+ }
+
+ // Now do the same but with the roles of the first and second box swapped.
+ getBoxCoordinates(box2, &coords);
+ boxCorner[4] = coords.ul;
+ boxCorner[5] = coords.ur;
+ boxCorner[6] = coords.lr;
+ boxCorner[7] = coords.ll;
+ for (i = 4; i < 8; i++) {
+ dist[i] = getClosestPtOnBox(box1, boxCorner[i].x, boxCorner[i].y, closestPoint[i].x, closestPoint[i].y);
+ }
+
+ // Find the three closest "close" points between the two boxes.
+ for (j = 0; j < 3; j++) {
+ minDist[j] = 0xFFFF;
+ for (i = 0; i < 8; i++) {
+ if (dist[i] < minDist[j]) {
+ minDist[j] = dist[i];
+ closest[j] = i;
+ }
+ }
+ dist[closest[j]] = 0xFFFF;
+ minDist[j] = (int)sqrt((double)minDist[j]);
+ box[j] = (closest[j] > 3); // Is the point on the first or on the second box?
+ }
+
+
+ // Finally, compute the actual "gate".
+
+ if (box[0] == box[1] && ABS(minDist[0] - minDist[1]) < 4) {
+ line1 = closest[0];
+ line2 = closest[1];
+
+ } else if (box[0] == box[1] && minDist[0] == minDist[1]) { // parallel
+ line1 = closest[0];
+ line2 = closest[1];
+ } else if (box[0] == box[2] && minDist[0] == minDist[2]) { // parallel
+ line1 = closest[0];
+ line2 = closest[2];
+ } else if (box[1] == box[2] && minDist[1] == minDist[2]) { // parallel
+ line1 = closest[1];
+ line2 = closest[2];
+
+ } else if (box[0] == box[2] && ABS(minDist[0] - minDist[2]) < 4) {
+ line1 = closest[0];
+ line2 = closest[2];
+ } else if (ABS(minDist[0] - minDist[2]) < 4) {
+ line1 = closest[1];
+ line2 = closest[2];
+ } else if (ABS(minDist[0] - minDist[1]) < 4) {
+ line1 = closest[0];
+ line2 = closest[1];
+ } else {
+ line1 = closest[0];
+ line2 = closest[0];
+ }
+
+ // Set the gate
+ if (line1 < 4) {
+ gateA[0] = boxCorner[line1];
+ gateA[1] = closestPoint[line1];
+ } else {
+ gateA[1] = boxCorner[line1];
+ gateA[0] = closestPoint[line1];
+ }
+
+ if (line2 < 4) {
+ gateB[0] = boxCorner[line2];
+ gateB[1] = closestPoint[line2];
+ } else {
+ gateB[1] = boxCorner[line2];
+ gateB[0] = closestPoint[line2];
+ }
+}
+
+} // End of namespace Scumm
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-30 00:00:44 +0000