diff options
author | Max Horn | 2002-08-21 16:07:07 +0000 |
---|---|---|
committer | Max Horn | 2002-08-21 16:07:07 +0000 |
commit | ce46866403fdcc479cf9d67e4d430409b15dadc3 (patch) | |
tree | 75ebfaa1ed13f549959d76d3ce101c3e66f5451b /scumm/boxes.cpp | |
parent | 662256f25dbe43abf67077a804e225738765f009 (diff) | |
download | scummvm-rg350-ce46866403fdcc479cf9d67e4d430409b15dadc3.tar.gz scummvm-rg350-ce46866403fdcc479cf9d67e4d430409b15dadc3.tar.bz2 scummvm-rg350-ce46866403fdcc479cf9d67e4d430409b15dadc3.zip |
Initial revision
svn-id: r4785
Diffstat (limited to 'scumm/boxes.cpp')
-rw-r--r-- | scumm/boxes.cpp | 1039 |
1 files changed, 1039 insertions, 0 deletions
diff --git a/scumm/boxes.cpp b/scumm/boxes.cpp new file mode 100644 index 0000000000..f8d68dca98 --- /dev/null +++ b/scumm/boxes.cpp @@ -0,0 +1,1039 @@ + /* ScummVM - Scumm Interpreter + * Copyright (C) 2001 Ludvig Strigeus + * Copyright (C) 2001/2002 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., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. + * + * $Header$ + * + */ + +#include "stdafx.h" +#include "scumm.h" +#include "actor.h" + +#include <math.h> + +#if !defined(__GNUC__) + #pragma START_PACK_STRUCTS +#endif + +struct Box { /* Internal walkbox file format */ + int16 ulx, uly; + int16 urx, ury; + int16 lrx, lry; + int16 llx, lly; + byte mask; + byte flags; + uint16 scale; +} GCC_PACK; + +#if !defined(__GNUC__) + #pragma END_PACK_STRUCTS +#endif + +struct PathNode { /* Linked list of walkpath nodes */ + uint index; + struct PathNode *left, *right; +}; + +struct PathVertex { /* Linked list of walkpath nodes */ + PathNode *left; + PathNode *right; +}; + +#define BOX_MATRIX_SIZE 2000 + + +PathVertex *unkMatrixProc1(PathVertex *vtx, PathNode *node); + + +byte Scumm::getMaskFromBox(int box) +{ + Box *ptr = getBoxBaseAddr(box); + if (!ptr) + return 0; + + return ptr->mask; +} + +void Scumm::setBoxFlags(int box, int val) +{ + debug(2, "setBoxFlags(%d, 0x%02x)", box, val); + + /* FULL_THROTTLE stuff */ + if (val & 0xC000) { + assert(box >= 0 && box < 65); + _extraBoxFlags[box] = val; + } else { + Box *b = getBoxBaseAddr(box); + b->flags = val; + } +} + +byte Scumm::getBoxFlags(int box) +{ + Box *ptr = getBoxBaseAddr(box); + if (!ptr) + return 0; + return ptr->flags; +} + +void Scumm::setBoxScale(int box, int scale) +{ + Box *b = getBoxBaseAddr(box); + b->scale = scale; +} + +int Scumm::getBoxScale(int box) +{ + if (_features & GF_NO_SCALLING) + return (255); + Box *ptr = getBoxBaseAddr(box); + if (!ptr) + return 255; + return FROM_LE_16(ptr->scale); +} + +byte Scumm::getNumBoxes() +{ + byte *ptr = getResourceAddress(rtMatrix, 2); + if (!ptr) + return 0; + return ptr[0]; +} + +Box *Scumm::getBoxBaseAddr(int box) +{ + byte *ptr = getResourceAddress(rtMatrix, 2); + if (!ptr) + return NULL; + checkRange(ptr[0] - 1, 0, box, "Illegal box %d"); + if (_features & GF_SMALL_HEADER) { + if (_features & GF_OLD256) + return (Box *)(ptr + box * (SIZEOF_BOX - 2) + 1); + else + return (Box *)(ptr + box * SIZEOF_BOX + 1); + } else + return (Box *)(ptr + box * SIZEOF_BOX + 2); +} + +int Scumm::getSpecialBox(int param1, int param2) +{ + 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, param1, param2)) + return (i); + } + + return (-1); +} + +bool Scumm::checkXYInBoxBounds(int b, int x, int y) +{ + BoxCoords box; + + if (b == 0 && (!(_features & GF_SMALL_HEADER))) + 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) { + + ScummPoint pt; + pt = closestPtOnLine(box.ul.x, box.ul.y, box.lr.x, box.lr.y, 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 Scumm::getBoxCoordinates(int boxnum, BoxCoords *box) +{ + Box *bp = getBoxBaseAddr(boxnum); + + box->ul.x = (int16)FROM_LE_16(bp->ulx); + box->ul.y = (int16)FROM_LE_16(bp->uly); + box->ur.x = (int16)FROM_LE_16(bp->urx); + box->ur.y = (int16)FROM_LE_16(bp->ury); + + box->ll.x = (int16)FROM_LE_16(bp->llx); + box->ll.y = (int16)FROM_LE_16(bp->lly); + box->lr.x = (int16)FROM_LE_16(bp->lrx); + box->lr.y = (int16)FROM_LE_16(bp->lry); +} + +uint Scumm::distanceFromPt(int x, int y, int ptx, int pty) +{ + int diffx, diffy; + + diffx = abs(ptx - x); + + if (diffx >= 0x100) + return 0xFFFF; + + diffy = abs(pty - y); + + if (diffy >= 0x100) + return 0xFFFF; + diffx *= diffx; + diffy *= diffy; + return diffx + diffy; +} + +ScummPoint Scumm::closestPtOnLine(int ulx, int uly, int llx, int lly, int x, int y) +{ + int lydiff, lxdiff; + int32 dist, a, b, c; + int x2, y2; + ScummPoint pt; + + if (llx == ulx) { // Vertical line? + x2 = ulx; + y2 = y; + } else if (lly == uly) { // Horizontal line? + x2 = x; + y2 = uly; + } else { + lydiff = lly - uly; + + lxdiff = llx - ulx; + + if (abs(lxdiff) > abs(lydiff)) { + dist = lxdiff * lxdiff + lydiff * lydiff; + + a = ulx * lydiff / lxdiff; + b = x * lxdiff / lydiff; + + c = (a + b - uly + y) * lydiff * lxdiff / dist; + + x2 = c; + y2 = c * lydiff / lxdiff - a + uly; + } else { + dist = lydiff * lydiff + lxdiff * lxdiff; + + a = uly * lxdiff / lydiff; + b = y * lydiff / lxdiff; + + c = (a + b - ulx + x) * lydiff * lxdiff / dist; + + y2 = c; + x2 = c * lxdiff / lydiff - a + ulx; + } + } + + lxdiff = llx - ulx; + lydiff = lly - uly; + + if (abs(lydiff) < abs(lxdiff)) { + if (lxdiff > 0) { + if (x2 < ulx) { + type1:; + x2 = ulx; + y2 = uly; + } else if (x2 > llx) { + type2:; + x2 = llx; + y2 = lly; + } + } else { + if (x2 > ulx) + goto type1; + if (x2 < llx) + goto type2; + } + } else { + if (lydiff > 0) { + if (y2 < uly) + goto type1; + if (y2 > lly) + goto type2; + } else { + if (y2 > uly) + goto type1; + if (y2 < lly) + goto type2; + } + } + + pt.x = x2; + pt.y = y2; + return pt; +} + +bool Scumm::inBoxQuickReject(int b, int x, int y, int threshold) +{ + int t; + BoxCoords box; + + getBoxCoordinates(b, &box); + + if (threshold == 0) + return true; + + t = x - threshold; + if (t > box.ul.x && t > box.ur.x && t > box.lr.x && t > box.ll.x) + return false; + + t = x + threshold; + if (t < box.ul.x && t < box.ur.x && t < box.lr.x && t < box.ll.x) + return false; + + t = y - threshold; + if (t > box.ul.y && t > box.ur.y && t > box.lr.y && t > box.ll.y) + return false; + + t = y + threshold; + if (t < box.ul.y && t < box.ur.y && t < box.lr.y && t < box.ll.y) + return false; + + return true; +} + +AdjustBoxResult Scumm::getClosestPtOnBox(int b, int x, int y) +{ + ScummPoint pt; + AdjustBoxResult best; + uint dist; + uint bestdist = (uint) 0xFFFF; + BoxCoords box; + + getBoxCoordinates(b, &box); + + pt = closestPtOnLine(box.ul.x, box.ul.y, box.ur.x, box.ur.y, x, y); + dist = distanceFromPt(x, y, pt.x, pt.y); + if (dist < bestdist) { + bestdist = dist; + best.x = pt.x; + best.y = pt.y; + } + + pt = closestPtOnLine(box.ur.x, box.ur.y, box.lr.x, box.lr.y, x, y); + dist = distanceFromPt(x, y, pt.x, pt.y); + if (dist < bestdist) { + bestdist = dist; + best.x = pt.x; + best.y = pt.y; + } + + pt = closestPtOnLine(box.lr.x, box.lr.y, box.ll.x, box.ll.y, x, y); + dist = distanceFromPt(x, y, pt.x, pt.y); + if (dist < bestdist) { + bestdist = dist; + best.x = pt.x; + best.y = pt.y; + } + + pt = closestPtOnLine(box.ll.x, box.ll.y, box.ul.x, box.ul.y, x, y); + dist = distanceFromPt(x, y, pt.x, pt.y); + if (dist < bestdist) { + bestdist = dist; + best.x = pt.x; + best.y = pt.y; + } + + best.dist = bestdist; + return best; +} + +byte *Scumm::getBoxMatrixBaseAddr() +{ + byte *ptr = getResourceAddress(rtMatrix, 1); + 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 Scumm::getPathToDestBox(byte from, byte to) +{ + byte *boxm; + byte i; + int dest = -1; + + if (from == to) + return to; + + boxm = getBoxMatrixBaseAddr(); + + i = 0; + while (i != from) { + while (*boxm != 0xFF) + boxm += 3; + i++; + boxm++; + } + + while (boxm[0] != 0xFF) { + if (boxm[0] <= to && boxm[1] >= to) + dest = boxm[2]; + boxm += 3; + } + 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 Scumm::findPathTowards(Actor *a, byte box1nr, byte box2nr, byte box3nr, int16 &foundPathX, int16 &foundPathY) +{ + BoxCoords box1; + BoxCoords box2; + ScummPoint tmp; + int i, j; + int flag; + int q, pos; + + getBoxCoordinates(box1nr, &box1); + 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 = a->y; + if (box2nr == box3nr) { + int diffX = a->walkdata.destx - a->x; + int diffY = a->walkdata.desty - a->y; + int boxDiffX = box1.ul.x - a->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 = a->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; + foundPathY = q; + foundPathX = 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 = a->walkdata.destx - a->x; + int diffY = a->walkdata.desty - a->y; + int boxDiffY = box1.ul.y - a->y; + + pos = a->x; + if (diffY != 0) { + pos += diffX * boxDiffY / diffY; + } + } else { + pos = a->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; + foundPathX = q; + foundPathY = 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; +} + +void Scumm::createBoxMatrix() +{ + byte *matrix_ptr; + int num, i, j; + byte flags; + int table_1[66], table_2[66]; + int counter, val; + int code; + + PathVertex *vtx; + PathNode *node, *node2 = NULL; + + _maxBoxVertexHeap = 1000; + + createResource(rtMatrix, 4, 1000); + createResource(rtMatrix, 3, 4160); //65 items of something of size 64 + createResource(rtMatrix, 1, BOX_MATRIX_SIZE); + + matrix_ptr = getResourceAddress(rtMatrix, 1); + + _boxMatrixPtr4 = getResourceAddress(rtMatrix, 4); + _boxMatrixPtr1 = getResourceAddress(rtMatrix, 1); + _boxMatrixPtr3 = getResourceAddress(rtMatrix, 3); + + _boxPathVertexHeapIndex = _boxMatrixItem = 0; + + num = getNumBoxes(); + + for (i = 0; i < num; i++) { + for (j = 0; j < num; j++) { + if (i == j) { + _boxMatrixPtr3[i * 64 + j] = 0; + } else if (areBoxesNeighbours(i, j)) { + _boxMatrixPtr3[i * 64 + j] = 1; + } else { + _boxMatrixPtr3[i * 64 + j] = 250; + } + } + } + + for (j = 0; j < num; j++) { + flags = getBoxFlags(j); + if (flags & kBoxInvisible) { + addToBoxMatrix(0xFF); + addToBoxMatrix(j); + addToBoxMatrix(j); + addToBoxMatrix(j); + } else { + vtx = addPathVertex(); + for (i = 0; i < num; i++) { + flags = getBoxFlags(j); + if (!(flags & kBoxInvisible)) { + node = unkMatrixProc2(vtx, i); + if (i == j) + node2 = node; + } + } + table_1[j] = 0; + table_2[j] = j; + vtx = unkMatrixProc1(vtx, node2); + node = vtx ? vtx->left : NULL; + + counter = 250; + while (node) { + val = _boxMatrixPtr3[j * 64 + node->index]; + table_1[node->index] = val; + if (val < counter) + counter = val; + + if (table_1[node->index] != 250) + table_2[node->index] = node->index; + else + table_2[node->index] = -1; + + node = node->left; + } + + while (vtx) { + counter = 250; + node2 = node = vtx->left; + + while (node) { + if (table_1[node->index] < counter) { + counter = table_1[node->index]; + node2 = node; + } + node = node->left; + } + vtx = unkMatrixProc1(vtx, node2); + node = vtx ? vtx->left : NULL; + while (node) { + code = _boxMatrixPtr3[node2->index * 64 + node->index]; + code += table_1[node2->index]; + if (code < table_1[node->index]) { + table_1[node->index] = code; + table_2[node->index] = table_2[node2->index]; + } + node = node->left; + } + } + + addToBoxMatrix(0xFF); + for (i = 1; i < num;) { + if (table_2[i - 1] != -1) { + addToBoxMatrix(i - 1); /* lo */ + if (table_2[i - 1] != table_2[i]) { + addToBoxMatrix(i - 1); /* hi */ + addToBoxMatrix(table_2[i - 1]); /* dst */ + } else { + while (table_2[i - 1] == table_2[i]) { + if (++i == num) + break; + } + addToBoxMatrix(i - 1); /* hi */ + addToBoxMatrix(table_2[i - 1]); /* dst */ + } + } + if (++i == num && table_2[i - 1] != -1) { + addToBoxMatrix(i - 1); /* lo */ + addToBoxMatrix(i - 1); /* hi */ + addToBoxMatrix(table_2[i - 1]); /* dest */ + } + } + } + } + + addToBoxMatrix(0xFF); + nukeResource(rtMatrix, 4); + nukeResource(rtMatrix, 3); +} + +PathVertex *unkMatrixProc1(PathVertex *vtx, PathNode *node) +{ + if (node == NULL || vtx == NULL) + return NULL; + + if (!node->right) { + vtx->left = node->left; + } else { + node->right->left = node->left; + } + + if (!node->left) { + vtx->right = node->right; + } else { + node->left->right = node->right; + } + + if (vtx->left) + return vtx; + + return NULL; +} + +PathNode *Scumm::unkMatrixProc2(PathVertex *vtx, int i) +{ + PathNode *node; + + if (vtx == NULL) + return NULL; + + if (!vtx->right) { + node = (PathNode *)addToBoxVertexHeap(sizeof(PathNode)); + vtx->left = vtx->right = node; + + node->index = i; + node->left = 0; + node->right = 0; + } else { + node = (PathNode *)addToBoxVertexHeap(sizeof(PathNode)); + vtx->right->left = node; + + node->right = vtx->right; + node->index = i; + node->left = 0; + + vtx->right = node; + } + + return vtx->right; +} + +/* Check if two boxes are neighbours */ +bool Scumm::areBoxesNeighbours(int box1nr, int box2nr) +{ + int j, k, m, n; + int tmp_x, tmp_y; + bool result; + BoxCoords box; + BoxCoords box2; + + if (getBoxFlags(box1nr) & kBoxInvisible || getBoxFlags(box2nr) & kBoxInvisible) + return false; + + getBoxCoordinates(box1nr, &box2); + getBoxCoordinates(box2nr, &box); + + result = false; + j = 4; + + do { + k = 4; + do { + if (box2.ur.x == box2.ul.x && box.ul.x == box2.ul.x && box.ur.x == box2.ur.x) { + n = m = 0; + if (box2.ur.y < box2.ul.y) { + n = 1; + SWAP(box2.ur.y, box2.ul.y); + } + if (box.ur.y < box.ul.y) { + m = 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) { + if (n) { + SWAP(box2.ur.y, box2.ul.y); + } + if (m) { + SWAP(box.ur.y, box.ul.y); + } + } else { + if (n) { + SWAP(box2.ur.y, box2.ul.y); + } + if (m) { + SWAP(box.ur.y, box.ul.y); + } + result = true; + } + } + + if (box2.ur.y == box2.ul.y && box.ul.y == box2.ul.y && box.ur.y == box2.ur.y) { + n = m = 0; + if (box2.ur.x < box2.ul.x) { + n = 1; + SWAP(box2.ur.x, box2.ul.x); + } + if (box.ur.x < box.ul.x) { + m = 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) { + + if (n) { + SWAP(box2.ur.x, box2.ul.x); + } + if (m) { + SWAP(box.ur.x, box.ul.x); + } + } else { + if (n) { + SWAP(box2.ur.x, box2.ul.x); + } + if (m) { + SWAP(box.ur.x, box.ul.x); + } + result = true; + } + } + + tmp_x = box2.ul.x; + tmp_y = box2.ul.y; + box2.ul.x = box2.ur.x; + box2.ul.y = box2.ur.y; + box2.ur.x = box2.lr.x; + box2.ur.y = box2.lr.y; + box2.lr.x = box2.ll.x; + box2.lr.y = box2.ll.y; + box2.ll.x = tmp_x; + box2.ll.y = tmp_y; + } while (--k); + + tmp_x = box.ul.x; + tmp_y = box.ul.y; + box.ul.x = box.ur.x; + box.ul.y = box.ur.y; + box.ur.x = box.lr.x; + box.ur.y = box.lr.y; + box.lr.x = box.ll.x; + box.lr.y = box.ll.y; + box.ll.x = tmp_x; + box.ll.y = tmp_y; + } while (--j); + + return result; +} + +void Scumm::addToBoxMatrix(byte b) +{ + if (++_boxMatrixItem > BOX_MATRIX_SIZE) + error("Box matrix overflow"); + *_boxMatrixPtr1++ = b; +} + +void *Scumm::addToBoxVertexHeap(int size) +{ + byte *ptr = _boxMatrixPtr4; + + _boxMatrixPtr4 += size; + _boxPathVertexHeapIndex += size; + + if (_boxPathVertexHeapIndex >= _maxBoxVertexHeap) + error("Box path vertex heap overflow"); + + return ptr; +} + +PathVertex *Scumm::addPathVertex() +{ + _boxMatrixPtr4 = getResourceAddress(rtMatrix, 4); + _boxPathVertexHeapIndex = 0; + + return (PathVertex *)addToBoxVertexHeap(sizeof(PathVertex)); +} + +void Scumm::findPathTowardsOld(Actor *actor, byte trap1, byte trap2, byte final_trap, ScummPoint gateLoc[5]) +{ + ScummPoint pt; + ScummPoint gateA[2]; + ScummPoint gateB[2]; + + getGates(trap1, trap2, gateA, gateB); + + gateLoc[1].x = actor->x; + gateLoc[1].y = actor->y; + gateLoc[2].x = 32000; + gateLoc[3].x = 32000; + gateLoc[4].x = 32000; + + if (trap2 == final_trap) { /* next = final box? */ + gateLoc[4].x = actor->walkdata.destx; + gateLoc[4].y = actor->walkdata.desty; + + if (getMaskFromBox(trap1) == getMaskFromBox(trap2) || 1) { + if (compareSlope(gateLoc[1].x, gateLoc[1].y, gateLoc[4].x, gateLoc[4].y, gateA[0].x, gateA[0].y) != + compareSlope(gateLoc[1].x, gateLoc[1].y, gateLoc[4].x, gateLoc[4].y, gateB[0].x, gateB[0].y) && + compareSlope(gateLoc[1].x, gateLoc[1].y, gateLoc[4].x, gateLoc[4].y, gateA[1].x, gateA[1].y) != + compareSlope(gateLoc[1].x, gateLoc[1].y, gateLoc[4].x, gateLoc[4].y, gateB[1].x, gateB[1].y)) { + return; /* same zplane and between both gates? */ + } + } + } + + pt = closestPtOnLine(gateA[1].x, gateA[1].y, gateB[1].x, gateB[1].y, gateLoc[1].x, gateLoc[1].y); + gateLoc[3].x = pt.x; + gateLoc[3].y = pt.y; + + if (compareSlope(gateLoc[1].x, gateLoc[1].y, gateLoc[3].x, gateLoc[3].y, gateA[0].x, gateA[0].y) == + compareSlope(gateLoc[1].x, gateLoc[1].y, gateLoc[3].x, gateLoc[3].y, gateB[0].x, gateB[0].y)) { + closestPtOnLine(gateA[0].x, gateA[0].y, gateB[0].x, gateB[0].y, gateLoc[1].x, gateLoc[1].y); + gateLoc[2].x = pt.x; /* if point 2 between gates, ignore! */ + gateLoc[2].y = pt.y; + } + + return; +} + +void Scumm::getGates(int trap1, int trap2, ScummPoint gateA[2], ScummPoint gateB[2]) +{ + int i, j; + int Dist[8]; + int MinDist[3]; + int Closest[3]; + int Box[3]; + BoxCoords box; + ScummPoint Clo[8]; + ScummPoint poly[8]; + AdjustBoxResult abr; + int line1, line2; + + // For all corner coordinates of the first box, compute the point cloest + // to them on the second box (and also compute the distance of these points). + getBoxCoordinates(trap1, &box); + poly[0] = box.ul; + poly[1] = box.ur; + poly[2] = box.lr; + poly[3] = box.ll; + for (i = 0; i < 4; i++) { + abr = getClosestPtOnBox(trap2, poly[i].x, poly[i].y); + Dist[i] = abr.dist; + Clo[i].x = abr.x; + Clo[i].y = abr.y; + } + + // Now do the same but with the roles of the first and second box swapped. + getBoxCoordinates(trap2, &box); + poly[4] = box.ul; + poly[5] = box.ur; + poly[6] = box.lr; + poly[7] = box.ll; + for (i = 4; i < 8; i++) { + abr = getClosestPtOnBox(trap1, poly[i].x, poly[i].y); + Dist[i] = abr.dist; + Clo[i].x = abr.x; + Clo[i].y = abr.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 poin on the first or on the second box? + } + + + // Finally, compute the "gate". That's a pair of two points that are + // in the same box (actually, on the border of that box), which both have + // "minimal" distance to the other box in a certain sense. + + 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) { /* if 1 close to 3 then use 2-3 */ + 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) { /* from box 1 to box 2 */ + gateA[0] = poly[line1]; + gateA[1] = Clo[line1]; + + } else { + gateA[1] = poly[line1]; + gateA[0] = Clo[line1]; + } + + if (line2 < 4) { /* from box */ + gateB[0] = poly[line2]; + gateB[1] = Clo[line2]; + + } else { + gateB[1] = poly[line2]; + gateB[0] = Clo[line2]; + } +} + +bool Scumm::compareSlope(int X1, int Y1, int X2, int Y2, int X3, int Y3) +{ + return (Y2 - Y1) * (X3 - X1) <= (Y3 - Y1) * (X2 - X1); +} |