home *** CD-ROM | disk | FTP | other *** search
/ Chip 2002 February / chip_20022115.iso / amiga / chipgame / scummvm_aga.lha / ScummVM_AGA / src / boxes.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  2002-01-05  |  19.2 KB  |  828 lines
  1. /* ScummVM - Scumm Interpreter
  2.  * Copyright (C) 2001  Ludvig Strigeus
  3.  *
  4.  * This program is free software; you can redistribute it and/or
  5.  * modify it under the terms of the GNU General Public License
  6.  * as published by the Free Software Foundation; either version 2
  7.  * of the License, or (at your option) any later version.
  8.  
  9.  * This program is distributed in the hope that it will be useful,
  10.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12.  * GNU General Public License for more details.
  13.  
  14.  * You should have received a copy of the GNU General Public License
  15.  * along with this program; if not, write to the Free Software
  16.  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  17.  *
  18.  * $Header: /cvsroot/scummvm/scummvm/boxes.cpp,v 1.4 2001/11/06 20:00:47 strigeus Exp $
  19.  *
  20.  */
  21.  
  22. #include "stdafx.h"
  23. #include "scumm.h"
  24.  
  25. byte Scumm::getMaskFromBox(int box) {
  26.     Box *ptr = getBoxBaseAddr(box);
  27.     return ptr->mask;
  28. }
  29.  
  30. byte Scumm::getBoxFlags(int box) {
  31.     Box *ptr = getBoxBaseAddr(box);
  32.     return ptr->flags;
  33. }
  34.  
  35. int Scumm::getBoxScale(int box) {
  36.     Box *ptr = getBoxBaseAddr(box);
  37.     return FROM_LE_16(ptr->scale);
  38. }
  39.  
  40. byte Scumm::getNumBoxes() {
  41.     byte *ptr = getResourceAddress(rtMatrix, 2);
  42.     return ptr[8];
  43. }
  44.  
  45. Box *Scumm::getBoxBaseAddr(int box) {
  46.     byte *ptr = getResourceAddress(rtMatrix, 2);
  47.     checkRange(ptr[8]-1, 0, box, "Illegal box %d");
  48.     return (Box*)(ptr + box*SIZEOF_BOX + 10);
  49. }
  50.  
  51. bool Scumm::checkXYInBoxBounds(int b, int x, int y) {
  52.     if (b==0)
  53.         return 0;
  54.  
  55.     getBoxCoordinates(b);
  56.  
  57.     if (x < box.upperLeftX && x < box.upperRightX &&
  58.         x < box.lowerLeftX && x < box.lowerRightX)
  59.             return 0;
  60.     
  61.     if (x > box.upperLeftX && x > box.upperRightX &&
  62.         x > box.lowerLeftX && x > box.lowerRightX)
  63.             return 0;
  64.     
  65.     if (y < box.upperLeftY && y < box.upperRightY &&
  66.         y < box.lowerLeftY && y < box.lowerRightY)
  67.             return 0;
  68.  
  69.     if (y > box.upperLeftY && y > box.upperRightY &&
  70.         y > box.lowerLeftY && y > box.lowerRightY)
  71.             return 0;
  72.     
  73.     if (box.upperLeftX == box.upperRightX &&
  74.         box.upperLeftY == box.upperRightY &&
  75.         box.lowerLeftX == box.lowerRightX &&
  76.         box.lowerLeftY == box.lowerRightY ||
  77.         box.upperLeftX == box.lowerRightX &&
  78.         box.upperLeftY == box.lowerRightY &&
  79.         box.upperRightX== box.lowerLeftX &&
  80.         box.upperRightY== box.lowerLeftY) {
  81.  
  82.         Point pt;
  83.         pt = closestPtOnLine(box.upperLeftX, box.upperLeftY, box.lowerLeftX, box.lowerLeftY, x, y);
  84.         if (distanceFromPt(x, y, pt.x,pt.y) <= 4)
  85.             return 1;
  86.     }
  87.     
  88.     if (!getSideOfLine(
  89.         box.upperLeftX, box.upperLeftY, box.upperRightX, box.upperRightY, x,y,b))
  90.             return 0;
  91.     
  92.     if (!getSideOfLine(
  93.         box.upperRightX, box.upperRightY, box.lowerLeftX, box.lowerLeftY, x,y,b))
  94.             return 0;
  95.  
  96.     if (!getSideOfLine(
  97.         box.lowerLeftX, box.lowerLeftY, box.lowerRightX, box.lowerRightY, x,y,b))
  98.             return 0;
  99.  
  100.     if (!getSideOfLine(
  101.         box.lowerRightX, box.lowerRightY, box.upperLeftX, box.upperLeftY, x,y,b))
  102.             return 0;
  103.  
  104.     return 1;
  105. }
  106.  
  107. void Scumm::getBoxCoordinates(int b) {
  108.     Box *bp = getBoxBaseAddr(b);
  109.     box.upperLeftX = (int16)FROM_LE_16(bp->ulx);
  110.     box.upperRightX = (int16)FROM_LE_16(bp->urx);
  111.     box.lowerLeftX = (int16)FROM_LE_16(bp->llx);
  112.     box.lowerRightX = (int16)FROM_LE_16(bp->lrx);
  113.     box.upperLeftY = (int16)FROM_LE_16(bp->uly);
  114.     box.upperRightY = (int16)FROM_LE_16(bp->ury);
  115.     box.lowerLeftY = (int16)FROM_LE_16(bp->lly);
  116.     box.lowerRightY = (int16)FROM_LE_16(bp->lry);
  117. }
  118.  
  119. uint Scumm::distanceFromPt(int x, int y, int ptx, int pty) {
  120.     int diffx, diffy;
  121.     
  122.     diffx = abs(ptx-x);
  123.  
  124.     if (diffx >= 0x100)
  125.         return 0xFFFF;
  126.     
  127.     diffy = abs(pty - y);
  128.  
  129.     if (diffy >= 0x100)
  130.         return 0xFFFF;
  131.     diffx *= diffx;
  132.     diffy *= diffy;
  133.     return diffx + diffy;
  134. }
  135.  
  136. bool Scumm::getSideOfLine(int x1,int y1, int x2, int y2, int x, int y, int box) {
  137.     return (x-x1)*(y2-y1) <= (y-y1)*(x2-x1);
  138. }
  139.  
  140. Point Scumm::closestPtOnLine(int ulx, int uly, int llx, int lly, int x, int y) {
  141.     int lydiff,lxdiff;
  142.     int32 dist,a,b,c;
  143.     int x2,y2;
  144.     Point pt;
  145.  
  146.     if (llx==ulx) {
  147.         x2 = ulx;
  148.         y2 = y;
  149.     } else if (lly==uly) {
  150.         x2 = x;
  151.         y2 = uly;
  152.     } else {
  153.         lydiff = lly - uly;
  154.  
  155.         lxdiff = llx - ulx;
  156.  
  157.         if (abs(lxdiff) > abs(lydiff)) {
  158.             dist = lxdiff * lxdiff + lydiff * lydiff;
  159.  
  160.             a = ulx * lydiff / lxdiff;
  161.             b = x * lxdiff / lydiff;
  162.  
  163.             c = (a + b - uly + y) * lydiff * lxdiff / dist;
  164.  
  165.             x2 = c;
  166.             y2 = c * lydiff / lxdiff - a + uly;
  167.         } else {
  168.             dist = lydiff * lydiff + lxdiff * lxdiff;
  169.  
  170.             a = uly * lxdiff / lydiff;
  171.             b = y * lydiff / lxdiff;
  172.             
  173.             c = (a + b - ulx + x) * lydiff * lxdiff / dist;
  174.  
  175.             y2 = c;
  176.             x2 = c * lxdiff / lydiff - a + ulx;
  177.         }
  178.     }
  179.  
  180.     lxdiff = llx - ulx;
  181.     lydiff = lly - uly;
  182.  
  183.     if (abs(lydiff) < abs(lxdiff)) {
  184.         if (lxdiff > 0) {
  185.             if (x2 < ulx) {
  186. type1:;
  187.                 x2 = ulx;
  188.                 y2 = uly;
  189.             } else if (x2 > llx) {
  190. type2:;
  191.                 x2 = llx;
  192.                 y2 = lly;
  193.             }
  194.         } else {
  195.             if (x2 > ulx) goto type1;
  196.             if (x2 < llx) goto type2;
  197.         }
  198.     } else {
  199.         if (lydiff > 0) {
  200.             if (y2 < uly) goto type1;
  201.             if (y2 > lly) goto type2;
  202.         } else {
  203.             if (y2 > uly) goto type1;
  204.             if (y2 < lly) goto type2;
  205.         }
  206.     }
  207.  
  208.     pt.x = x2;
  209.     pt.y = y2;
  210.     return pt;
  211. }
  212.  
  213. bool Scumm::inBoxQuickReject(int b, int x, int y, int threshold) {
  214.     int t;
  215.  
  216.     getBoxCoordinates(b);
  217.  
  218.     if (threshold==0)
  219.         return 1;
  220.     
  221.     t = x - threshold;
  222.     if (t > box.upperLeftX && t > box.upperRightX &&
  223.         t > box.lowerLeftX && t > box.lowerRightX)
  224.             return 0;
  225.     
  226.     t = x + threshold;
  227.     if (t < box.upperLeftX && t < box.upperRightX &&
  228.         t < box.lowerLeftX && t < box.lowerRightX)
  229.             return 0;
  230.     
  231.     t = y - threshold;
  232.     if (t > box.upperLeftY && t > box.upperRightY &&
  233.         t > box.lowerLeftY && t > box.lowerRightY)
  234.             return 0;
  235.     
  236.     t = y + threshold;
  237.     if (t < box.upperLeftY && t < box.upperRightY &&
  238.             t < box.lowerLeftY && t < box.lowerRightY)
  239.             return 0;
  240.  
  241.     return 1;
  242. }
  243.  
  244. AdjustBoxResult Scumm::getClosestPtOnBox(int b, int x, int y) {
  245.     Point pt;
  246.     AdjustBoxResult best;
  247.     uint dist;
  248.     uint bestdist = (uint)0xFFFF;
  249.  
  250.     getBoxCoordinates(b);
  251.  
  252.     pt = closestPtOnLine(box.upperLeftX,box.upperLeftY,box.upperRightX,box.upperRightY,x,y);
  253.     dist = distanceFromPt(x, y, pt.x, pt.y);
  254.     if (dist < bestdist) {
  255.         bestdist = dist;
  256.         best.x = pt.x;
  257.         best.y = pt.y;
  258.     }
  259.  
  260.     pt = closestPtOnLine(box.upperRightX,box.upperRightY,box.lowerLeftX,box.lowerLeftY,x,y);
  261.     dist = distanceFromPt(x, y, pt.x, pt.y);
  262.     if (dist < bestdist) {
  263.         bestdist = dist;
  264.         best.x = pt.x;
  265.         best.y = pt.y;
  266.     }
  267.  
  268.     pt = closestPtOnLine(box.lowerLeftX,box.lowerLeftY,box.lowerRightX,box.lowerRightY,x,y);
  269.     dist = distanceFromPt(x, y, pt.x, pt.y);
  270.     if (dist < bestdist) {
  271.         bestdist = dist;
  272.         best.x = pt.x;
  273.         best.y = pt.y;
  274.     }
  275.  
  276.     pt = closestPtOnLine(box.lowerRightX,box.lowerRightY,box.upperLeftX,box.upperLeftY,x,y);
  277.     dist = distanceFromPt(x, y, pt.x, pt.y);
  278.     if (dist < bestdist) {
  279.         bestdist = dist;
  280.         best.x = pt.x;
  281.         best.y = pt.y;
  282.     }
  283.     
  284.     best.dist = bestdist;
  285.     return best;
  286. }
  287.  
  288. byte *Scumm::getBoxMatrixBaseAddr() {
  289.     byte *ptr = getResourceAddress(rtMatrix, 1) + 8;
  290.     if (*ptr==0xFF) ptr++;
  291.     return ptr;
  292. }
  293.  
  294. int Scumm::getPathToDestBox(int from, int to) {
  295.     byte *boxm;
  296.     int i;
  297.  
  298.     if (from==to)
  299.         return to;
  300.     
  301.     boxm = getBoxMatrixBaseAddr();
  302.  
  303.     i=0;
  304.     while (i != from) {
  305.         while (*boxm != 0xFF)
  306.             boxm += 3;
  307.         i++;
  308.         boxm++;
  309.     }
  310.  
  311.     while (boxm[0]!=0xFF) {
  312.         if (boxm[0] <= to && boxm[1]>=to)
  313.             return boxm[2];
  314.         boxm+=3;
  315.     }
  316.     return 0;
  317. }
  318.  
  319. int Scumm::findPathTowards(Actor *a, int box1, int box2, int box3) {
  320.     int upperLeftX, upperLeftY;
  321.     int upperRightX, upperRightY;
  322.     int lowerLeftX, lowerLeftY;
  323.     int lowerRightX, lowerRightY;
  324.     int i,j,m,n,p,q,r;
  325.     int tmp_x, tmp_y;
  326.     int tmp;
  327.     
  328.     getBoxCoordinates(box1);
  329.     upperLeftX = box.upperLeftX;
  330.     upperLeftY = box.upperLeftY;
  331.     upperRightX = box.upperRightX;
  332.     upperRightY = box.upperRightY;
  333.     lowerLeftX = box.lowerLeftX;
  334.     lowerLeftY = box.lowerLeftY;
  335.     lowerRightX = box.lowerRightX;
  336.     lowerRightY = box.lowerRightY;
  337.     getBoxCoordinates(box2);
  338.  
  339.     i = 0;
  340.     do {
  341.         if (i >= 4) goto ExitPos;
  342.         for (j=0; j<4; j++) {
  343.             if (upperRightX==upperLeftX &&
  344.                     box.upperLeftX==upperLeftX &&
  345.                     box.upperRightX==upperRightX) {
  346.                 
  347. ExitPos:;
  348.                 n = m = 0;
  349.                 if (upperRightY < upperLeftY) {
  350.                     m = 1;
  351.                     SWAP(upperRightY, upperLeftY);
  352.                 }
  353.                 if (box.upperRightY < box.upperLeftY) {
  354.                     n = 1;
  355.                     SWAP(box.upperRightY, box.upperLeftY);
  356.                 }
  357.                 if (box.upperRightY >= upperLeftY &&
  358.                         box.upperLeftY <= upperRightY &&
  359.                         (box.upperLeftY != upperRightY &&
  360.                          box.upperRightY!= upperLeftY ||
  361.                          upperRightY==upperLeftY ||
  362.                          box.upperRightY==box.upperLeftY)) {
  363.                     if (box2==box3) {
  364.                         m = a->walkdata.destx - a->x;
  365.                         p = a->walkdata.desty - a->y;
  366.                         tmp = upperLeftX - a->x;
  367.                         i = a->y;
  368.                         if (m) {
  369.                             q = tmp * p;
  370.                             r = q/m;
  371.                             if (r==0 && (q<=0 || m<=0) && (q>=0 || m>=0)) {
  372.                                 r = -1;
  373.                             }
  374.                             i += r;
  375.                         }
  376.                     } else {
  377.                         i = a->y;
  378.                     }
  379.                     q = i;
  380.                     if (q < box.upperLeftY)
  381.                         q = box.upperLeftY;
  382.                     if (q > box.upperRightY)
  383.                         q = box.upperRightY;
  384.                     if (q < upperLeftY)
  385.                         q = upperLeftY;
  386.                     if (q > upperRightY)
  387.                         q = upperRightY;
  388.                     if (q==i && box2==box3)
  389.                         return 1;
  390.                     _foundPathX = upperLeftX;
  391.                     _foundPathY = q;
  392.                     return 0;
  393.                 } else {
  394.                     if (m) {
  395.                         SWAP(upperRightY, upperLeftY);
  396.                     }
  397.                     if (n) {
  398.                         SWAP(box.upperRightY, box.upperLeftY);
  399.                     }
  400.                 }
  401.             }
  402.             if (upperLeftY==upperRightY &&
  403.                     box.upperLeftY==upperLeftY &&
  404.                     box.upperRightY==upperRightY) {
  405.                 n = m = 0;
  406.                 if(upperRightX < upperLeftX) {
  407.                     m = 1;
  408.                     SWAP(upperRightX, upperLeftX);
  409.                 }
  410.                 if (box.upperRightX < box.upperLeftX) {
  411.                     n = 1;
  412.                     SWAP(box.upperRightX, box.upperLeftX);
  413.                 }
  414.                 if (box.upperRightX >= upperLeftX &&
  415.                         box.upperLeftX <= upperRightX &&
  416.                         (box.upperLeftX != upperRightX &&
  417.                          box.upperRightX!= upperLeftX ||
  418.                          upperRightX==upperLeftX ||
  419.                          box.upperRightX==box.upperLeftX)) {
  420.                     if (box2==box3) {
  421.                         m = a->walkdata.destx - a->x;
  422.                         p = a->walkdata.desty - a->y;
  423.                         i = upperLeftY - a->y;
  424.                         tmp = a->x;
  425.                         if (p) {
  426.                             tmp += i * m / p;
  427.                         }
  428.                     } else {
  429.                         tmp = a->x;
  430.                     }
  431.                     q = tmp;
  432.                     if (q < box.upperLeftX)
  433.                         q = box.upperLeftX;
  434.                     if (q > box.upperRightX)
  435.                         q = box.upperRightX;
  436.                     if (q < upperLeftX)
  437.                         q = upperLeftX;
  438.                     if (q > upperRightX)
  439.                         q = upperRightX;
  440.                     if (tmp==q && box2==box3)
  441.                         return 1;
  442.                     _foundPathX = q;
  443.                     _foundPathY = upperLeftY;
  444.                     return 0;
  445.                 } else {
  446.                     if (m != 0) {
  447.                         SWAP(upperRightX, upperLeftX);
  448.                     }
  449.                     if (n != 0) {
  450.                         SWAP(box.upperRightX, box.upperLeftX);
  451.                     }
  452.                 }
  453.             }
  454.             tmp_x = upperLeftX;
  455.             tmp_y = upperLeftY;
  456.             upperLeftX = upperRightX;
  457.             upperLeftY = upperRightY;
  458.             upperRightX = lowerLeftX;
  459.             upperRightY = lowerLeftY;
  460.             lowerLeftX = lowerRightX;
  461.             lowerLeftY = lowerRightY;
  462.             lowerRightX = tmp_x;
  463.             lowerRightY = tmp_y;
  464.         }
  465.  
  466.         tmp_x = box.upperLeftX;
  467.         tmp_y = box.upperLeftY;
  468.         box.upperLeftX = box.upperRightX;
  469.         box.upperLeftY = box.upperRightY;
  470.         box.upperRightX = box.lowerLeftX;
  471.         box.upperRightY = box.lowerLeftY;
  472.         box.lowerLeftX = box.lowerRightX;
  473.         box.lowerLeftY = box.lowerRightY;
  474.         box.lowerRightX = tmp_x;
  475.         box.lowerRightY = tmp_y;
  476.         i++;        
  477.     } while (1);
  478. }
  479.  
  480.  
  481. void Scumm::setBoxFlags(int box, int val) {
  482.     Box *b = getBoxBaseAddr(box);
  483.     b->flags = val;
  484. }
  485.  
  486. void Scumm::setBoxScale(int box, int scale) {
  487.     Box *b = getBoxBaseAddr(box);
  488.     b->scale = scale;
  489. }
  490.  
  491. #define BOX_MATRIX_SIZE 2000
  492.  
  493. void Scumm::createBoxMatrix() {
  494.     byte *matrix_ptr;
  495.     int num,i,j;
  496.     byte flags;
  497.     int table_1[66],table_2[66];
  498.     int counter,val;
  499.     int code;
  500.  
  501.     PathVertex *vtx;
  502.     PathNode *node, *node2;
  503.  
  504.     _maxBoxVertexHeap = 1000;
  505.  
  506.     createResource(rtMatrix, 4, 1000);
  507.     createResource(rtMatrix, 3, 4160); //65 items of something of size 64
  508.     createResource(rtMatrix, 1, BOX_MATRIX_SIZE+8);
  509.  
  510.     matrix_ptr = getResourceAddress(rtMatrix, 1);
  511.  
  512.     /* endian & alignment safe */
  513.     ((uint32*)matrix_ptr)[1] = TO_BE_32(BOX_MATRIX_SIZE+8);
  514.     ((uint32*)matrix_ptr)[0] = MKID('BOXM');
  515.  
  516.     _boxMatrixPtr4 = getResourceAddress(rtMatrix, 4);
  517.     _boxMatrixPtr1 = getResourceAddress(rtMatrix, 1) + 8;
  518.     _boxMatrixPtr3 = getResourceAddress(rtMatrix, 3);
  519.  
  520.     _boxPathVertexHeapIndex = _boxMatrixItem = 0;
  521.     
  522.     num = getNumBoxes();
  523.  
  524.     for (i=0; i<num; i++) {
  525.         for (j=0; j<num; j++) {
  526.             if (i==j) {
  527.                 _boxMatrixPtr3[i*64+j] = 0;    
  528.             } else if (areBoxesNeighbours(i, j)) {
  529.                 _boxMatrixPtr3[i*64+j] = 1;
  530.             } else {
  531.                 _boxMatrixPtr3[i*64+j] = 250;
  532.             }
  533.         }
  534.     }
  535.  
  536.     for (j=0; j<num; j++) {
  537.         flags = getBoxFlags(j);
  538.         if (flags & 0x80) {
  539.             addToBoxMatrix(0xFF);
  540.             addToBoxMatrix(j);
  541.             addToBoxMatrix(j);
  542.             addToBoxMatrix(j);
  543.         } else {
  544.             vtx = addPathVertex();
  545.             for (i=0; i<num; i++) {
  546.                 flags = getBoxFlags(j);
  547.                 if (!(flags&0x80)) {
  548.                     node = unkMatrixProc2(vtx, i);
  549.                     if (i==j)
  550.                         node2 = node;
  551.                 }
  552.             }
  553.             table_1[j] = 0;
  554.             table_2[j] = j;
  555.             vtx = unkMatrixProc1(vtx, node2);
  556.             node = vtx ? vtx->left : NULL;
  557.  
  558.             counter = 250;
  559.             while (node) {
  560.                 val = _boxMatrixPtr3[j*64 + node->index];
  561.                 table_1[node->index] = val;
  562.                 if (val<counter) counter=val;
  563.                 
  564.                 if (table_1[node->index]!=250)
  565.                     table_2[node->index] = node->index;
  566.                 else
  567.                     table_2[node->index] = -1;
  568.  
  569.                 node = node->left;
  570.             }
  571.             
  572.             while (vtx) {
  573.                 counter = 250;
  574.                 node2 = node = vtx->left;
  575.  
  576.                 while (node) {
  577.                     if ( table_1[node->index] < counter ) {
  578.                         counter = table_1[node->index];
  579.                         node2 = node;
  580.                     }
  581.                     node = node->left;
  582.                 }
  583.                 vtx = unkMatrixProc1(vtx, node2);
  584.                 node = vtx ? vtx->left : NULL;
  585.                 while (node) {
  586.                     code = _boxMatrixPtr3[node2->index * 64 + node->index];
  587.                     code += table_1[node2->index];
  588.                     if (code < table_1[node->index]) {
  589.                         table_1[node->index] = code;
  590.                         table_2[node->index] = table_2[node2->index];
  591.                     }
  592.                     node = node->left;
  593.                 }
  594.             }
  595.  
  596.             addToBoxMatrix(0xFF);
  597.             for (i=1; i<num;) {
  598.                 if (table_2[i-1]!=-1) {
  599.                     addToBoxMatrix(i-1); /* lo */
  600.                     if (table_2[i-1] != table_2[i]) {
  601.                         addToBoxMatrix(i-1); /* hi */
  602.                         addToBoxMatrix(table_2[i-1]); /* dst */
  603.                     } else {
  604.                         while (table_2[i-1] == table_2[i]) {
  605.                             if (++i==num)
  606.                                 break;
  607.                         }
  608.                         addToBoxMatrix(i-1); /* hi */
  609.                         addToBoxMatrix(table_2[i-1]); /* dst */
  610.                     }
  611.                 }
  612.                 if (++i==num && table_2[i-1]!=-1) {
  613.                     addToBoxMatrix(i-1); /* lo */
  614.                     addToBoxMatrix(i-1); /* hi */
  615.                     addToBoxMatrix(table_2[i-1]); /* dest */
  616.                 }
  617.             }
  618.         }
  619.     }
  620.  
  621.     addToBoxMatrix(0xFF);
  622.     nukeResource(rtMatrix, 4);
  623.     nukeResource(rtMatrix, 3);
  624. }
  625.  
  626. PathVertex *Scumm::unkMatrixProc1(PathVertex *vtx, PathNode *node) {
  627.     if (node==NULL || vtx==NULL)
  628.         return NULL;
  629.  
  630.     if (!node->right) {
  631.         vtx->left = node->left;
  632.     } else {
  633.         node->right->left = node->left;
  634.     }
  635.  
  636.     if (!node->left) {
  637.         vtx->right = node->right;
  638.     } else {
  639.         node->left->right = node->right;
  640.     }
  641.  
  642.     if (vtx->left)
  643.         return vtx;
  644.  
  645.     return NULL;
  646. }
  647.  
  648. PathNode *Scumm::unkMatrixProc2(PathVertex *vtx, int i) {
  649.     PathNode *node;
  650.  
  651.     if (vtx==NULL)
  652.         return NULL;
  653.  
  654.     if (!vtx->right) {
  655.         node = (PathNode*)addToBoxVertexHeap(sizeof(PathNode));
  656.         vtx->left = vtx->right = node;
  657.  
  658.         node->index = i;
  659.         node->left = 0;
  660.         node->right = 0;
  661.     } else {
  662.         node = (PathNode*)addToBoxVertexHeap(sizeof(PathNode));    
  663.         vtx->right->left = node;
  664.         
  665.         node->right = vtx->right;
  666.         node->index = i;
  667.         node->left = 0;
  668.  
  669.         vtx->right = node;
  670.     }
  671.  
  672.     return vtx->right;
  673. }
  674.  
  675. /* Check if two boxes are neighbours */
  676. bool Scumm::areBoxesNeighbours(int box1, int box2) {
  677.     int upperLeftX, upperLeftY;
  678.     int upperRightX, upperRightY;
  679.     int lowerLeftX, lowerLeftY;
  680.     int lowerRightX, lowerRightY;
  681.     int j,k,m,n;
  682.     int tmp_x, tmp_y;
  683.     bool result;
  684.  
  685.     if (getBoxFlags(box1)&0x80 || getBoxFlags(box2)&0x80)
  686.         return false;
  687.  
  688.     getBoxCoordinates(box1);
  689.  
  690.     upperLeftX = box.upperLeftX;
  691.     upperLeftY = box.upperLeftY;
  692.     upperRightX = box.upperRightX;
  693.     upperRightY = box.upperRightY;
  694.     lowerLeftX = box.lowerLeftX;
  695.     lowerLeftY = box.lowerLeftY;
  696.     lowerRightX = box.lowerRightX;
  697.     lowerRightY = box.lowerRightY;
  698.  
  699.     getBoxCoordinates(box2);
  700.     
  701.     result = false;
  702.     j = 4;
  703.     
  704.     do {
  705.         k = 4;
  706.         do {
  707.             if (upperRightX == upperLeftX &&
  708.                   box.upperLeftX == upperLeftX &&
  709.                     box.upperRightX == upperRightX) {
  710.                 n = m = 0;
  711.                 if (upperRightY < upperLeftY) {
  712.                     n = 1;
  713.                     SWAP(upperRightY, upperLeftY);
  714.                 }
  715.                 if (box.upperRightY < box.upperLeftY) {
  716.                     m = 1;
  717.                     SWAP(box.upperRightY, box.upperLeftY);
  718.                 }
  719.                 if (box.upperRightY < upperLeftY ||
  720.                       box.upperLeftY > upperRightY ||
  721.                         (box.upperLeftY == upperRightY ||
  722.                          box.upperRightY==upperLeftY) &&
  723.                          upperRightY != upperLeftY &&
  724.                          box.upperLeftY!=box.upperRightY) {
  725.                     if (n) {
  726.                         SWAP(upperRightY, upperLeftY);
  727.                     }
  728.                     if (m) {
  729.                         SWAP(box.upperRightY, box.upperLeftY);
  730.                     }
  731.                 } else {
  732.                     if (n) {
  733.                         SWAP(upperRightY, upperLeftY);
  734.                     }
  735.                     if (m) {
  736.                         SWAP(box.upperRightY, box.upperLeftY);
  737.                     }
  738.                     result = true;
  739.                 }    
  740.             }
  741.  
  742.             if (upperRightY == upperLeftY && 
  743.                     box.upperLeftY == upperLeftY &&
  744.                     box.upperRightY == upperRightY) {
  745.                 n = m = 0;
  746.                 if (upperRightX < upperLeftX) {
  747.                     n = 1;
  748.                     SWAP(upperRightX, upperLeftX);
  749.                 }
  750.                 if (box.upperRightX < box.upperLeftX) {
  751.                     m = 1;
  752.                     SWAP(box.upperRightX, box.upperLeftX);
  753.                 }
  754.                 if (box.upperRightX < upperLeftX ||
  755.                       box.upperLeftX > upperRightX ||
  756.                         (box.upperLeftX == upperRightX ||
  757.                          box.upperRightX==upperLeftX) &&
  758.                          upperRightX != upperLeftX &&
  759.                          box.upperLeftX!=box.upperRightX) {
  760.  
  761.                     if (n) {
  762.                         SWAP(upperRightX, upperLeftX);
  763.                     }
  764.                     if (m) {
  765.                         SWAP(box.upperRightX, box.upperLeftX);
  766.                     }
  767.                 } else {
  768.                     if (n) {
  769.                         SWAP(upperRightX, upperLeftX);
  770.                     }
  771.                     if (m) {
  772.                         SWAP(box.upperRightX, box.upperLeftX);
  773.                     }
  774.                     result = true;
  775.                 }
  776.             }
  777.             
  778.             tmp_x = upperLeftX;
  779.             tmp_y = upperLeftY;
  780.             upperLeftX = upperRightX;
  781.             upperLeftY = upperRightY;
  782.             upperRightX = lowerLeftX;
  783.             upperRightY = lowerLeftY;
  784.             lowerLeftX = lowerRightX;
  785.             lowerLeftY = lowerRightY;
  786.             lowerRightX = tmp_x;
  787.             lowerRightY = tmp_y;
  788.         } while (--k);
  789.         
  790.         tmp_x = box.upperLeftX;
  791.         tmp_y = box.upperLeftY;
  792.         box.upperLeftX = box.upperRightX;
  793.         box.upperLeftY = box.upperRightY;
  794.         box.upperRightX = box.lowerLeftX;
  795.         box.upperRightY = box.lowerLeftY;
  796.         box.lowerLeftX = box.lowerRightX;
  797.         box.lowerLeftY = box.lowerRightY;
  798.         box.lowerRightX = tmp_x;
  799.         box.lowerRightY = tmp_y;
  800.     } while (--j);
  801.  
  802.     return result;
  803. }
  804.  
  805. void Scumm::addToBoxMatrix(byte b) {
  806.     if (++_boxMatrixItem > BOX_MATRIX_SIZE)
  807.         error("Box matrix overflow");
  808.     *_boxMatrixPtr1++ = b;
  809. }
  810.  
  811. void *Scumm::addToBoxVertexHeap(int size) {
  812.     byte *ptr = _boxMatrixPtr4;
  813.  
  814.     _boxMatrixPtr4 += size;
  815.     _boxPathVertexHeapIndex += size;
  816.  
  817.     if (_boxPathVertexHeapIndex >= _maxBoxVertexHeap)
  818.         error("Box path vertex heap overflow");
  819.  
  820.     return ptr;
  821. }
  822.  
  823. PathVertex *Scumm::addPathVertex() {
  824.     _boxMatrixPtr4 = getResourceAddress(rtMatrix, 4);
  825.     _boxPathVertexHeapIndex = 0;
  826.     return (PathVertex*)addToBoxVertexHeap(sizeof(PathVertex));
  827. }
  828.