From 26ee630756ebdd7c96bccede0881a8c8b98e8f2b Mon Sep 17 00:00:00 2001 From: Max Horn Date: Sat, 11 Feb 2006 22:45:04 +0000 Subject: Moved engines to the new engines/ directory svn-id: r20582 --- engines/scumm/boxes.cpp | 1271 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 1271 insertions(+) create mode 100644 engines/scumm/boxes.cpp (limited to 'engines/scumm/boxes.cpp') 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 -- cgit v1.2.3