OPENGL: Merged from trunk, from rev 52105 to 53396.

This includes an rather hacky attempt to merge all the recent gp2x backend
changes into the branch. I suppose the gp2x backend and probably all new
backends, i.e. gph, dingux etc., might not compile anymore.

Since I have no way of testing those it would be nice if porters could look
into getting those up to speed in this branch.

svn-id: r53399

1 files changed, 487 insertions, 0 deletions

diff --git a/engines/hugo/route.cpp b/engines/hugo/route.cpp
new file mode 100644
index 0000000000..2ba95fb7d7
--- /dev/null
+++ b/engines/hugo/route.cpp
@@ -0,0 +1,487 @@
+/* ScummVM - Graphic Adventure Engine
+ *
+ * ScummVM is the legal property of its developers, whose names
+ * are too numerous to list here. Please refer to the COPYRIGHT
+ * file distributed with this source distribution.
+ *
+ * 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$
+ *
+ */
+
+/*
+ * This code is based on original Hugo Trilogy source code
+ *
+ * Copyright (c) 1989-1995 David P. Gray
+ *
+ */
+
+// Find shortest route from hero to destination
+
+#include "common/system.h"
+
+#include "hugo/hugo.h"
+#include "hugo/game.h"
+#include "hugo/route.h"
+#include "hugo/global.h"
+
+namespace Hugo {
+Route::Route(HugoEngine &vm) : _vm(vm) {
+}
+
+// Face hero in new direction, based on cursor key input by user.
+void Route::setDirection(uint16 keyCode) {
+	debugC(1, kDebugRoute, "setDirection(%d)", keyCode);
+
+	object_t *obj = _vm._hero;                      // Pointer to hero object
+
+	// Set first image in sequence
+	switch (keyCode) {
+	case Common::KEYCODE_UP:
+		obj->currImagePtr = obj->seqList[_UP].seqPtr;
+		break;
+	case Common::KEYCODE_DOWN:
+		obj->currImagePtr = obj->seqList[DOWN].seqPtr;
+		break;
+	case Common::KEYCODE_LEFT:
+		obj->currImagePtr = obj->seqList[LEFT].seqPtr;
+		break;
+	case Common::KEYCODE_RIGHT:
+		obj->currImagePtr = obj->seqList[RIGHT].seqPtr;
+		break;
+	case Common::KEYCODE_HOME:
+		obj->currImagePtr = obj->seqList[LEFT].seqPtr;
+		break;
+	case Common::KEYCODE_END:
+		obj->currImagePtr = obj->seqList[LEFT].seqPtr;
+		break;
+	case Common::KEYCODE_PAGEUP:
+		obj->currImagePtr = obj->seqList[RIGHT].seqPtr;
+		break;
+	case Common::KEYCODE_PAGEDOWN:
+		obj->currImagePtr = obj->seqList[RIGHT].seqPtr;
+		break;
+	}
+}
+
+// Set hero walking, based on cursor key input by user.
+// Hitting same key twice will stop hero.
+void Route::setWalk(uint16 direction) {
+	debugC(1, kDebugRoute, "setWalk(%d)", direction);
+
+	static uint16 oldDirection = 0;                 // Last direction char
+	object_t *obj = _vm._hero;                      // Pointer to hero object
+
+	if (_vm.getGameStatus().storyModeFl || obj->pathType != USER)           // Make sure user has control
+		return;
+
+	if (!obj->vx && !obj->vy)
+		oldDirection = 0;                           // Fix for consistant restarts
+
+	if (direction != oldDirection) {
+		// Direction has changed
+		setDirection(direction);                    // Face new direction
+		obj->vx = obj->vy = 0;
+		switch (direction) {                        // And set correct velocity
+		case Common::KEYCODE_UP:
+			obj->vy = -DY;
+			break;
+		case Common::KEYCODE_DOWN:
+			obj->vy =  DY;
+			break;
+		case Common::KEYCODE_LEFT:
+			obj->vx = -DX;
+			break;
+		case Common::KEYCODE_RIGHT:
+			obj->vx =  DX;
+			break;
+		case Common::KEYCODE_HOME:
+			obj->vx = -DX;
+			// Note: in v1 Dos and v2 Dos, obj->vy is set to DY
+			obj->vy = -DY / 2;
+			break;
+		case Common::KEYCODE_END:
+			obj->vx = -DX;
+			// Note: in v1 Dos and v2 Dos, obj->vy is set to -DY
+			obj->vy =  DY / 2;
+			break;
+		case Common::KEYCODE_PAGEUP:
+			obj->vx =  DX;
+			// Note: in v1 Dos and v2 Dos, obj->vy is set to -DY
+			obj->vy = -DY / 2;
+			break;
+		case Common::KEYCODE_PAGEDOWN:
+			obj->vx =  DX;
+			// Note: in v1 Dos and v2 Dos, obj->vy is set to DY
+			obj->vy =  DY / 2;
+			break;
+		}
+		oldDirection = direction;
+		obj->cycling = CYCLE_FORWARD;
+	} else {
+		// Same key twice - halt hero
+		obj->vy = 0;
+		obj->vx = 0;
+		oldDirection = 0;
+		obj->cycling = NOT_CYCLING;
+	}
+}
+
+// Recursive algorithm!  Searches from hero to dest_x, dest_y
+// Find horizontal line segment about supplied point and recursively
+// find line segments for each point above and below that segment.
+// When destination point found in segment, start surfacing and leave
+// a trail in segment[] from destination back to hero.
+//
+// Note:  there is a bug which allows a route through a 1-pixel high
+// narrow gap if between 2 segments wide enough for hero.  To work
+// around this, make sure any narrow gaps are 2 or more pixels high.
+// An example of this was the blocking guard in Hugo1/Dead-End.
+void Route::segment(int16 x, int16 y) {
+	debugC(1, kDebugRoute, "segment(%d, %d)", x, y);
+
+// Note use of static - can't waste stack
+	static image_pt   p;                            // Ptr to _boundaryMap[y]
+	static segment_t *seg_p;                        // Ptr to segment
+
+	// Bomb out if stack exhausted
+	// Vinterstum: Is this just a safeguard, or actually used?
+	//_fullStackFl = _stackavail () < 256;
+	_fullStackFl = false;
+
+	// Find and fill on either side of point
+	p = _boundaryMap[y];
+	int16 x1, x2;                                   // Range of segment
+	for (x1 = x; x1 > 0; x1--) {
+		if (p[x1] == 0) {
+			p[x1] = kMapFill;
+		} else {
+			break;
+		}
+	}
+	for (x2 = x + 1; x2 < XPIX; x2++) {
+		if (p[x2] == 0) {
+			p[x2] = kMapFill;
+		} else {
+			break;
+		}
+	}
+	x1++;
+	x2--;
+
+	// Discard path if not wide enough for hero - dead end
+	if (_heroWidth > x2 - x1 + 1)
+		return;
+
+	// Have we found the destination yet?
+	if (y == _destY && x1 <= _destX && x2 >= _destX)
+		_routeFoundFl = true;
+
+	// Bounds check y in case no boundary around screen
+	if (y <= 0 || y >= YPIX - 1)
+		return;
+
+	if (_vm._hero->x < x1) {
+		// Hero x not in segment, search x1..x2
+		// Find all segments above current
+		for (x = x1; !(_routeFoundFl | _fullStackFl | _fullSegmentFl) && x <= x2; x++) {
+			if (_boundaryMap[y - 1][x] == 0)
+				segment(x, y - 1);
+		}
+
+		// Find all segments below current
+		for (x = x1; !(_routeFoundFl | _fullStackFl | _fullSegmentFl) && x <= x2; x++) {
+			if (_boundaryMap[y + 1][x] == 0)
+				segment(x, y + 1);
+		}
+	} else if (_vm._hero->x + HERO_MAX_WIDTH > x2) {
+		// Hero x not in segment, search x1..x2
+		// Find all segments above current
+		for (x = x2; !(_routeFoundFl | _fullStackFl | _fullSegmentFl) && x >= x1; x--) {
+			if (_boundaryMap[y - 1][x] == 0)
+				segment(x, y - 1);
+		}
+
+		// Find all segments below current
+		for (x = x2; !(_routeFoundFl | _fullStackFl | _fullSegmentFl) && x >= x1; x--) {
+			if (_boundaryMap[y + 1][x] == 0)
+				segment(x, y + 1);
+		}
+	} else {
+		// Organize search around hero x position - this gives
+		// better chance for more direct route.
+		for (x = _vm._hero->x; !(_routeFoundFl | _fullStackFl | _fullSegmentFl) && x <= x2; x++) {
+			if (_boundaryMap[y - 1][x] == 0)
+				segment(x, y - 1);
+		}
+
+		for (x = x1; !(_routeFoundFl | _fullStackFl | _fullSegmentFl) && x < _vm._hero->x; x++) {
+			if (_boundaryMap[y - 1][x] == 0)
+				segment(x, y - 1);
+		}
+
+		for (x = _vm._hero->x; !(_routeFoundFl | _fullStackFl | _fullSegmentFl) && x <= x2; x++) {
+			if (_boundaryMap[y + 1][x] == 0)
+				segment(x, y + 1);
+		}
+
+		for (x = x1; !(_routeFoundFl | _fullStackFl | _fullSegmentFl) && x < _vm._hero->x; x++) {
+			if (_boundaryMap[y + 1][x] == 0)
+				segment(x, y + 1);
+		}
+	}
+
+	// If found, surface, leaving trail back to hero
+	if (_routeFoundFl) {
+		// Bomb out if too many segments (leave one spare)
+		if (_segmentNumb >= kMaxSeg - 1) {
+			_fullSegmentFl = true;
+		} else {
+			// Create segment
+			seg_p = &_segment[_segmentNumb];
+			seg_p->y  = y;
+			seg_p->x1 = x1;
+			seg_p->x2 = x2;
+			_segmentNumb++;
+		}
+	}
+}
+
+// Create and return ptr to new node.  Initialize with previous node.
+// Returns 0 if MAX_NODES exceeded
+Point *Route::newNode() {
+	debugC(1, kDebugRoute, "newNode");
+
+	if (_routeListIndex >= kMaxNodes)               // Too many nodes
+		return 0;                                   // Incomplete route - failure
+	_routeListIndex++;
+	_route[_routeListIndex] = _route[_routeListIndex - 1];  // Initialize with previous node
+	return &_route[_routeListIndex];
+}
+
+// Construct route to cx, cy.  Return TRUE if successful.
+// 1.  Copy boundary bitmap to local byte map (include object bases)
+// 2.  Construct list of segments segment[] from hero to destination
+// 3.  Compress to shortest route in route[]
+bool Route::findRoute(int16 cx, int16 cy) {
+	debugC(1, kDebugRoute, "findRoute(%d, %d)", cx, cy);
+
+	// Initialize for search
+	_routeFoundFl  = false;                         // Path not found yet
+	_fullStackFl = false;                           // Stack not exhausted
+	_fullSegmentFl  = false;                        // Segments not exhausted
+	_segmentNumb = 0;                               // Segment index
+	_heroWidth = HERO_MIN_WIDTH;                    // Minimum width of hero
+	_destY = cy;                                    // Destination coords
+	_destX = cx;                                    // Destination coords
+
+	int16 herox1 = _vm._hero->x + _vm._hero->currImagePtr->x1;        // Hero baseline
+	int16 herox2 = _vm._hero->x + _vm._hero->currImagePtr->x2;        // Hero baseline
+	int16 heroy  = _vm._hero->y + _vm._hero->currImagePtr->y2;        // Hero baseline
+
+	// Store all object baselines into objbound (except hero's = [0])
+	object_t  *obj;                                 // Ptr to object
+	int i;
+	for (i = 1, obj = &_vm._objects[i]; i < _vm._numObj; i++, obj++) {
+		if ((obj->screenIndex == *_vm._screen_p) && (obj->cycling != INVISIBLE) && (obj->priority == FLOATING))
+			_vm.storeBoundary(obj->oldx + obj->currImagePtr->x1, obj->oldx + obj->currImagePtr->x2, obj->oldy + obj->currImagePtr->y2);
+	}
+
+	// Combine objbound and boundary bitmaps to local byte map
+	for (int16 y = 0; y < YPIX; y++) {
+		for (int16 x = 0; x < XBYTES; x++) {
+			for (i = 0; i < 8; i++)
+				_boundaryMap[y][x * 8 + i] = ((_vm.getObjectBoundaryOverlay()[y * XBYTES + x] | _vm.getBoundaryOverlay()[y * XBYTES + x]) & (0x80 >> i)) ? kMapBound : 0;
+		}
+	}
+	
+	// Clear all object baselines from objbound
+	for (i = 0, obj = _vm._objects; i < _vm._numObj; i++, obj++) {
+		if ((obj->screenIndex == *_vm._screen_p) && (obj->cycling != INVISIBLE) && (obj->priority == FLOATING))
+			_vm.clearBoundary(obj->oldx + obj->currImagePtr->x1, obj->oldx + obj->currImagePtr->x2, obj->oldy + obj->currImagePtr->y2);
+	}
+	
+	// Search from hero to destination
+	segment(herox1, heroy);
+
+	// Not found or not enough stack or MAX_SEG exceeded
+	if (!_routeFoundFl || _fullStackFl || _fullSegmentFl) {
+		return false;
+	}
+
+	// Now find the route of nodes from destination back to hero
+	// Assign first node as destination
+	_route[0].x = _destX;
+	_route[0].y = _destY;
+
+	// Make a final segment for hero's base (we left a spare)
+	_segment[_segmentNumb].y  = heroy;
+	_segment[_segmentNumb].x1 = herox1;
+	_segment[_segmentNumb].x2 = herox2;
+	_segmentNumb++;
+
+	Point     *routeNode;                           // Ptr to route node
+	// Look in segments[] for straight lines from destination to hero
+	for (i = 0, _routeListIndex = 0; i < _segmentNumb - 1; i++) {
+		if ((routeNode = newNode()) == 0)           // New node for new segment
+			return false;                           // Too many nodes
+		routeNode->y = _segment[i].y;
+
+		// Look ahead for furthest straight line
+		for (int16 j = i + 1; j < _segmentNumb; j++) {
+			segment_t *seg_p = &_segment[j];
+			// Can we get to this segment from previous node?
+			if (seg_p->x1 <= routeNode->x && seg_p->x2 >= routeNode->x + _heroWidth - 1) {
+				routeNode->y = seg_p->y;            // Yes, keep updating node
+			} else {
+				// No, create another node on previous segment to reach it
+				if ((routeNode = newNode()) == 0)   // Add new route node
+					return false;                   // Too many nodes
+
+				// Find overlap between old and new segments
+				int16 x1 = MAX(_segment[j - 1].x1, seg_p->x1);
+				int16 x2 = MIN(_segment[j - 1].x2, seg_p->x2);
+
+				// If room, add a little offset to reduce staircase effect
+				int16 dx = HERO_MAX_WIDTH >> 1;
+				if (x2 - x1 < _heroWidth + dx)
+					dx = 0;
+
+				// Bear toward final hero position
+				if (j == _segmentNumb - 1)
+					routeNode->x = herox1;
+				else if (herox1 < x1)
+					routeNode->x = x1 + dx;
+				else if (herox1 > x2 - _heroWidth + 1)
+					routeNode->x = x2 - _heroWidth - dx;
+				else
+					routeNode->x = herox1;
+				i = j - 2;                          // Restart segment (-1 to offset auto increment)
+				break;
+			}
+		}
+
+		// Terminate loop if we've reached hero
+		if (routeNode->x == herox1 && routeNode->y == heroy)
+			break;
+	}
+	return true;
+}
+
+// Process hero in route mode - called from Move_objects()
+void Route::processRoute() {
+	debugC(1, kDebugRoute, "processRoute");
+
+	static bool turnedFl = false;                   // Used to get extra cylce for turning
+
+	// Current hero position
+	int16 herox = _vm._hero->x + _vm._hero->currImagePtr->x1;
+	int16 heroy = _vm._hero->y + _vm._hero->currImagePtr->y2;
+	status_t &gameStatus = _vm.getGameStatus();
+	Point *routeNode = &_route[gameStatus.routeIndex];
+
+	// Arrived at node?
+	if (abs(herox - routeNode->x) < DX + 1 && abs(heroy - routeNode->y) < DY) {
+		// DX too low
+		// Close enough - position hero exactly
+		_vm._hero->x = _vm._hero->oldx = routeNode->x - _vm._hero->currImagePtr->x1;
+		_vm._hero->y = _vm._hero->oldy = routeNode->y - _vm._hero->currImagePtr->y2;
+		_vm._hero->vx = _vm._hero->vy = 0;
+		_vm._hero->cycling = NOT_CYCLING;
+
+		// Arrived at final node?
+		if (--gameStatus.routeIndex < 0) {
+			// See why we walked here
+			switch (gameStatus.go_for) {
+			case GO_EXIT:                           // Walked to an exit, proceed into it
+				setWalk(_vm._hotspots[gameStatus.go_id].direction);
+				break;
+			case GO_LOOK:                           // Look at an object
+				if (turnedFl) {
+					_vm.lookObject(&_vm._objects[gameStatus.go_id]);
+					turnedFl = false;
+				} else {
+					setDirection(_vm._objects[gameStatus.go_id].direction);
+					gameStatus.routeIndex++;        // Come round again
+					turnedFl = true;
+				}
+				break;
+			case GO_GET:                            // Get (or use) an object
+				if (turnedFl) {
+					_vm.useObject(gameStatus.go_id);
+					turnedFl = false;
+				} else {
+					setDirection(_vm._objects[gameStatus.go_id].direction);
+					gameStatus.routeIndex++;        // Come round again
+					turnedFl = true;
+				}
+				break;
+			case GO_SPACE:
+				warning("Unhandled gameStatus.go_for GO_STATUS");
+				break;
+			}
+		}
+	} else if (_vm._hero->vx == 0 && _vm._hero->vy == 0) {
+		// Set direction of travel if at a node
+		// Note realignment when changing to (thinner) up/down sprite,
+		// otherwise hero could bump into boundaries along route.
+		if (herox < routeNode->x) {
+			setWalk(Common::KEYCODE_RIGHT);
+		} else if (herox > routeNode->x) {
+			setWalk(Common::KEYCODE_LEFT);
+		} else if (heroy < routeNode->y) {
+			setWalk(Common::KEYCODE_DOWN);
+			_vm._hero->x = _vm._hero->oldx = routeNode->x - _vm._hero->currImagePtr->x1;
+		} else if (heroy > routeNode->y) {
+			setWalk(Common::KEYCODE_UP);
+			_vm._hero->x = _vm._hero->oldx = routeNode->x - _vm._hero->currImagePtr->x1;
+		}
+	}
+}
+
+// Start a new route from hero to cx, cy
+// go_for is the purpose, id indexes the exit or object to walk to
+// Returns FALSE if route not found
+bool Route::startRoute(go_t go_for, int16 id, int16 cx, int16 cy) {
+	debugC(1, kDebugRoute, "startRoute(%d, %d, %d, %d)", go_for, id, cx, cy);
+
+	// Don't attempt to walk if user does not have control
+	if (_vm._hero->pathType != USER)
+		return false;
+
+	status_t &gameStatus = _vm.getGameStatus();
+	// if inventory showing, make it go away
+	if (gameStatus.inventoryState != I_OFF)
+		gameStatus.inventoryState = I_UP;
+
+	gameStatus.go_for = go_for;                     // Purpose of trip
+	gameStatus.go_id  = id;                         // Index of exit/object
+
+	// Adjust destination to center hero if walking to cursor
+	if (gameStatus.go_for == GO_SPACE)
+		cx -= HERO_MIN_WIDTH / 2;
+
+	bool foundFl = false;                           // TRUE if route found ok
+	if ((foundFl = findRoute(cx, cy))) {            // Found a route?
+		gameStatus.routeIndex = _routeListIndex;    // Node index
+		_vm._hero->vx = _vm._hero->vy = 0;      // Stop manual motion
+	}
+
+	return foundFl;
+}
+
+} // End of namespace Hugo