The autoroute stuff (completely untested)

svn-id: r7154

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[];