aboutsummaryrefslogtreecommitdiff
path: root/sky
diff options
context:
space:
mode:
Diffstat (limited to 'sky')
-rw-r--r--sky/autoroute.cpp346
-rw-r--r--sky/autoroute.h43
-rw-r--r--sky/grid.cpp5
-rw-r--r--sky/grid.h2
4 files changed, 396 insertions, 0 deletions
diff --git a/sky/autoroute.cpp b/sky/autoroute.cpp
new file mode 100644
index 0000000000..2ce96dfb20
--- /dev/null
+++ b/sky/autoroute.cpp
@@ -0,0 +1,346 @@
+/* ScummVM - Scumm Interpreter
+ * Copyright (C) 2003 The ScummVM project
+ * Copyright (C) 2003 Robert "LavosSpawn" Goeffringmann
+ *
+ * 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 "autoroute.h"
+
+#define ROUTE_GRID_WIDTH ((GAME_SCREEN_WIDTH/8)+2)
+#define ROUTE_GRID_HEIGHT ((GAME_SCREEN_HEIGHT/8)+2)
+#define ROUTE_GRID_SIZE (ROUTE_GRID_WIDTH*ROUTE_GRID_HEIGHT*2)
+#define WALK_JUMP 8 // walk in blocks of 8
+
+SkyAutoRoute::SkyAutoRoute(SkyGrid *pGrid) {
+
+ _grid = pGrid;
+ _routeGrid = (uint16*)malloc(ROUTE_GRID_SIZE);
+}
+
+SkyAutoRoute::~SkyAutoRoute(void) {
+
+ free(_routeGrid);
+}
+
+uint16 SkyAutoRoute::checkBlock(uint16 *blockPos) {
+
+ uint16 fieldVal, retVal = 0;
+ fieldVal = blockPos[1]; // field to the right
+ if ((!(fieldVal & 0x8000)) && (fieldVal != 0)) retVal = fieldVal;
+ fieldVal = (blockPos - 1)[0]; // field to the left
+ if ((!(fieldVal & 0x8000)) && (fieldVal != 0) && (fieldVal > retVal)) retVal = fieldVal;
+ fieldVal = (blockPos + ROUTE_GRID_WIDTH)[0]; // upper field
+ if ((!(fieldVal & 0x8000)) && (fieldVal != 0) && (fieldVal > retVal)) retVal = fieldVal;
+ fieldVal = (blockPos - ROUTE_GRID_WIDTH)[0]; // upper field
+ if ((!(fieldVal & 0x8000)) && (fieldVal != 0) && (fieldVal > retVal)) retVal = fieldVal;
+ return retVal;
+}
+
+uint16 SkyAutoRoute::autoRoute(Compact *cpt) {
+
+ if (!cpt->extCompact)
+ error("SkyAutoRoute::autoRoute: fatal error. cpt->extCompact == NULL!\n");
+ uint16* routeData = (uint16*)cpt->extCompact->animScratch;
+ uint8* screenGrid = _grid->giveGrid(cpt->screen) - 4;
+ // ^^ this is actually a pointer to the last dword of the grid
+ uint16* routeCalc = _routeGrid + (ROUTE_GRID_SIZE >> 1) - 1;
+
+ uint8 stretch1, stretch2; // bl / bh
+ stretch1 = 0;
+ //FIXME: don't know if this is uint16 or uint32 (endian problem)
+ stretch2 = (uint8)*(uint32 *)SkyCompact::getCompactElem(cpt, C_GRID_WIDTH + cpt->extCompact->megaSet);
+
+ uint16 cnt;
+ //First clear the bottom line and right hand edge of next line
+ for (cnt = 0; cnt < ROUTE_GRID_WIDTH + 1; cnt++)
+ _routeGrid[(ROUTE_GRID_SIZE>>1) - 1 - cnt] = 0;
+
+ uint16 gridCntX = ROUTE_GRID_WIDTH-2; // ch
+ uint16 gridCntY = ROUTE_GRID_HEIGHT-2; // ebp
+ uint16 bitsLeft = 32;
+ uint32 gridData = screenGrid[0] | (screenGrid[1] << 8) |
+ (screenGrid[2] << 16) | (screenGrid[3] << 24);
+ screenGrid -= 4;
+ do {
+ //stretch:
+ uint8 shiftBit = (uint8)gridData&1;
+ gridData >>= 1;
+ if (shiftBit) {
+ //bit_set:
+ routeCalc[0] = 0xFFFF;
+ stretch1 = stretch2; // set up stretch factor
+ } else {
+ if (stretch1) {
+ //still_stretching:
+ stretch1--;
+ routeCalc[0] = 0xFFFF;
+ } else {
+ routeCalc[0] = 0; // this block is free
+ }
+ }
+ // next_stretch:
+ routeCalc--;
+ bitsLeft--;
+ if (!bitsLeft) {
+ gridData = screenGrid[0] | (screenGrid[1] << 8) |
+ (screenGrid[2] << 16) | (screenGrid[3] << 24);
+ screenGrid -= 4;
+ bitsLeft = 32;
+ }
+ // still bits:
+ gridCntX--;
+ if (gridCntX == 0) {
+ routeCalc--;
+ routeCalc[0] = routeCalc[1] = 0; // do edges
+ routeCalc--;
+ gridCntX = ROUTE_GRID_WIDTH-2;
+ stretch1 = 0; // clear stretch factor
+ gridCntY--;
+ }
+ } while(gridCntX || gridCntY);
+ for (cnt = 0; cnt < ROUTE_GRID_WIDTH-1; cnt++)
+ _routeGrid[cnt] = 0; // clear top line (right hand edge already done
+
+ // the grid has been initialised
+
+ // calculate start and end points
+ int16 initX = 0, initY = 0, postX = 0, postY = 0;
+ uint8 initBlockY; // bh
+ uint8 initBlockX; // bl
+ uint8 postBlockY; // ch
+ uint8 postBlockX; // cl
+
+ if (cpt->ycood < TOP_LEFT_Y) {
+ initY = cpt->ycood - TOP_LEFT_Y;
+ initBlockY = 0;
+ } else if (cpt->ycood - TOP_LEFT_Y >= GAME_SCREEN_HEIGHT) { // no_init_y1
+ initY = cpt->ycood - TOP_LEFT_Y - GAME_SCREEN_HEIGHT;
+ initBlockY = (GAME_SCREEN_HEIGHT - 1) >> 3; // convert to blocks
+ } else { // no_init_y2
+ initBlockY = (cpt->ycood - TOP_LEFT_Y) >> 3; // convert to blocks
+ }
+
+ if (cpt->xcood < TOP_LEFT_X) {
+ initX = cpt->xcood - TOP_LEFT_X;
+ initBlockY = 0;
+ } else if (cpt->xcood - TOP_LEFT_X >= GAME_SCREEN_WIDTH) { // no_init_x1
+ initX = cpt->xcood - TOP_LEFT_X - (GAME_SCREEN_WIDTH - 1); // -1 to match amiga
+ initBlockX = (GAME_SCREEN_WIDTH - 1) >> 3;
+ } else { // no_init_x2
+ initBlockX = (cpt->xcood - TOP_LEFT_X) >> 3;
+ }
+
+ // destination coords:
+
+ if (cpt->extCompact->arTargetY < TOP_LEFT_Y) {
+ postY = cpt->extCompact->arTargetY - TOP_LEFT_Y;
+ postBlockY = 0;
+ } else if (cpt->extCompact->arTargetY - TOP_LEFT_Y >= GAME_SCREEN_HEIGHT) { // no_post_y1
+ postY = cpt->extCompact->arTargetY - TOP_LEFT_Y - (GAME_SCREEN_HEIGHT - 1);
+ postBlockY = (GAME_SCREEN_HEIGHT - 1) >> 3;
+ } else { // no_post_y2
+ postBlockY = (cpt->extCompact->arTargetY - TOP_LEFT_Y) >> 3;
+ }
+
+ if (cpt->extCompact->arTargetX < TOP_LEFT_X) {
+ postX = cpt->extCompact->arTargetX - TOP_LEFT_X;
+ postBlockX = 0;
+ } else if (cpt->extCompact->arTargetX - TOP_LEFT_X >= GAME_SCREEN_WIDTH) {
+ postX = cpt->extCompact->arTargetX - TOP_LEFT_X - (GAME_SCREEN_WIDTH - 1);
+ postBlockX = (GAME_SCREEN_WIDTH - 1) >> 3;
+ } else {
+ postBlockX = (cpt->extCompact->arTargetX - TOP_LEFT_X) >> 3;
+ }
+ if ((postBlockX == initBlockX) && (postBlockY == initBlockY)) {
+ // empty route
+ routeData[0] = 0;
+ return 1;
+ }
+
+ int32 directionX, directionY;
+ uint8 numLines, numCols; // number of lines / columns to go
+ if (initBlockY > postBlockY) {
+ directionY = -ROUTE_GRID_WIDTH;
+ numLines = initBlockY;
+ } else { // go_down:
+ directionY = ROUTE_GRID_WIDTH;
+ numLines = (ROUTE_GRID_HEIGHT-1)-initBlockY;
+ }
+ if (initBlockX > postBlockX) {
+ directionX = -1;
+ numCols = initBlockX+2;
+ } else {
+ directionX = 1;
+ numCols = (ROUTE_GRID_WIDTH - 1) - initBlockX;
+ }
+ // calculate destination address
+ //postBlockX <<= 1; postBlockY <<= 1; // multiply by 2
+ uint16 *routeDestCalc;
+ routeDestCalc = postBlockY * ROUTE_GRID_WIDTH + postBlockX + _routeGrid;
+ routeDestCalc += ROUTE_GRID_WIDTH+1; // skip blank edges (what?)
+
+ //initBlockX <<= 1; initBlockY <<= 1;
+ uint16 *routeSrcCalc;
+ routeSrcCalc = initBlockY * ROUTE_GRID_WIDTH + initBlockX + _routeGrid;
+ routeSrcCalc += ROUTE_GRID_WIDTH+1; // skip blank edges
+ routeSrcCalc[0] = 1; //start this one off
+ // means: mark the block we start from as accessible
+
+ // if we are on the edge, move diagonally from start
+ if (numLines < ROUTE_GRID_HEIGHT-3)
+ routeSrcCalc -= directionY;
+
+ if (numCols < ROUTE_GRID_WIDTH-2)
+ routeSrcCalc -= directionX;
+
+ if (routeDestCalc[0]) {
+ // If destination is a wall then we have no route
+ // By the way, we could improve this algorithm by moving as close to the
+ // wall as possible. The original pathfinding of SKY sucked, if I remember correctly
+ return 2;
+ }
+ uint8 cnty; // ch
+ uint8 cntx; // cl
+ // numLines = dh, numCols = dl
+ uint16 blockRet;
+ bool gridChanged, foundRoute;
+ do { // wallow_y
+ gridChanged = false;
+ cnty = numLines;
+ uint16 *yPushedSrc = routeSrcCalc;
+ do { // wallow_x
+ cntx = numCols;
+ uint16 *xPushedSrc = routeSrcCalc;
+ do { // wallow
+ if (!routeSrcCalc[0]) {
+ // block wasn't yet done
+ blockRet = checkBlock(routeSrcCalc);
+ if (blockRet > 0) {
+ // this block is accessible
+ routeSrcCalc[0] = blockRet;
+ gridChanged = true;
+ }
+ }
+ routeSrcCalc += directionX;
+ cntx--;
+ } while (cntx);
+ routeSrcCalc = xPushedSrc + directionY;
+ cnty--;
+ } while (cnty);
+ routeSrcCalc = yPushedSrc;
+
+ foundRoute = false;
+ if (!routeDestCalc[0]) {
+ // we have done a section, see if we want to shift backwards (what?)
+ if (numLines < ROUTE_GRID_HEIGHT-4) {
+ routeSrcCalc -= directionY;
+ numLines++;
+ }
+ if (numCols < ROUTE_GRID_WIDTH-4) {
+ routeSrcCalc -= directionX;
+ numCols++;
+ }
+ } else foundRoute = true;
+ } while ((!foundRoute) && gridChanged);
+
+ if (!routeDestCalc[0]) {
+ // no route exists from routeSrc to routeDest
+ return 2;
+ }
+ // ok, we know now that it's possible to get from the start position to the desired
+ // destination. Let's see how.
+ uint16 *saveRoute = routeData+(ROUTE_SPACE >> 1)-1; // route_space is given in bytes so >> 1
+ saveRoute[0] = 0; // route is null terminated
+ uint16 lastVal;
+ lastVal = routeDestCalc[0];
+ lastVal--;
+ bool routeDone = false;
+ do {
+ // check_dir:
+ if (lastVal == (routeDestCalc-1)[0]) {
+ // look_left
+ saveRoute -= 2;
+ saveRoute[1] = RIGHTY;
+ saveRoute[0] = 0;
+ while ((lastVal == (routeDestCalc-1)[0]) && (!routeDone)) {
+ lastVal--;
+ if (lastVal == 0) routeDone = true;
+ else {
+ routeDestCalc--; // keep checking left
+ saveRoute[0] += WALK_JUMP;
+ }
+ }
+ } else if (lastVal == routeDestCalc[1]) {
+ // look_right
+ saveRoute -= 2;
+ saveRoute[1] = LEFTY;
+ saveRoute[0] = 0;
+ while ((lastVal == routeDestCalc[1]) && (!routeDone)) {
+ lastVal--;
+ if (lastVal == 0) routeDone = true;
+ else {
+ routeDestCalc++; // keep checking right
+ saveRoute[0] += WALK_JUMP;
+ }
+ }
+ } else if (lastVal == (routeDestCalc - ROUTE_GRID_WIDTH)[0]) {
+ // look_up
+ saveRoute -= 2;
+ saveRoute[1] = DOWNY;
+ saveRoute[0] = 0;
+ while ((lastVal == (routeDestCalc - ROUTE_GRID_WIDTH)[0]) && (!routeDone)) {
+ lastVal--;
+ if (lastVal == 0) routeDone = true;
+ else {
+ routeDestCalc -= ROUTE_GRID_WIDTH; // keep checking up
+ saveRoute[0] += WALK_JUMP;
+ }
+ }
+ } else if (lastVal == (routeDestCalc + ROUTE_GRID_WIDTH)[0]) {
+ // look_down
+ saveRoute -= 2;
+ saveRoute[1] = UPY;
+ saveRoute[0] = 0;
+ while ((lastVal == (routeDestCalc + ROUTE_GRID_WIDTH)[0]) && (!routeDone)) {
+ lastVal--;
+ if (lastVal == 0) routeDone = true;
+ else {
+ routeDestCalc += ROUTE_GRID_WIDTH; // keep checking right
+ saveRoute[0] += WALK_JUMP;
+ }
+ }
+ } else {
+ error("AutoRoute:: Can't find way backwards through _routeGrid");
+ }
+ } while (!routeDone);
+ // the route is done. if there was an initial x/y movement tag it onto the start
+ if (initX < 0) {
+ saveRoute -= 4;
+ saveRoute[1] = RIGHTY;
+ saveRoute[0] = ((-initX)+7)&0xFFF8;
+ } else if (initX > 0) {
+ saveRoute -= 4;
+ saveRoute[1] = LEFTY;
+ saveRoute[0] = (initX+7)&0xFFF8;
+ }
+ // I wonder why initY isn't checked
+ // saveRoute should now point to routeData
+ if (routeData > saveRoute) error("Autoroute: Internal pointer error! routeData overflow.");
+ return 1;
+} \ No newline at end of file
diff --git a/sky/autoroute.h b/sky/autoroute.h
new file mode 100644
index 0000000000..9a3936bf78
--- /dev/null
+++ b/sky/autoroute.h
@@ -0,0 +1,43 @@
+/* ScummVM - Scumm Interpreter
+ * Copyright (C) 2003 The ScummVM project
+ * Copyright (C) 2003 Robert "LavosSpawn" Goeffringmann
+ *
+ * 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$
+ *
+ */
+
+#ifndef __AutoRoute__
+#define __AutoRoute__
+
+#include "stdafx.h"
+#include "struc.h"
+#include "compact.h"
+#include "grid.h"
+#include "skydefs.h"
+
+class SkyAutoRoute {
+public:
+ SkyAutoRoute(SkyGrid *pGrid);
+ ~SkyAutoRoute(void);
+ uint16 autoRoute(Compact *cpt);
+private:
+ uint16 checkBlock(uint16 *blockPos);
+ SkyGrid *_grid;
+ uint16 *_routeGrid;
+};
+
+#endif // __AutoRoute \ No newline at end of file
diff --git a/sky/grid.cpp b/sky/grid.cpp
index fff6dc4fec..998f8b1685 100644
--- a/sky/grid.cpp
+++ b/sky/grid.cpp
@@ -235,3 +235,8 @@ void SkyGrid::removeGrid(uint32 x, uint32 y, uint32 width, Compact *cpt) {
if (getGridValues(x, y, width, cpt, &resBitPos, &resWidth))
removeObjectFromWalk(resBitPos, resWidth);
}
+
+uint8 *SkyGrid::giveGrid(uint32 pScreen)
+{
+ return _gameGrids + GRID_SIZE * _gridConvertTable[pScreen];
+}
diff --git a/sky/grid.h b/sky/grid.h
index 6566925ab9..a594caf632 100644
--- a/sky/grid.h
+++ b/sky/grid.h
@@ -48,6 +48,8 @@ public:
void plotGrid(uint32 x, uint32 y, uint32 width, Compact *cpt);
// same here, it's basically the same as removeObjectFromWalk
void removeGrid(uint32 x, uint32 y, uint32 width, Compact *cpt);
+ // note that this function actually returns the byte after the end of the requested grid
+ uint8 *giveGrid(uint32 pScreen);
private:
static int8 _gridConvertTable[];
generated by cgit v1.2.3 (git 2.25.1) at 2025-11-04 07:22:27 +0000