aboutsummaryrefslogtreecommitdiff
path: root/engines/hugo/route.cpp
diff options
context:
space:
mode:
authorJohannes Schickel2010-10-13 03:57:44 +0000
committerJohannes Schickel2010-10-13 03:57:44 +0000
commit75e8452b6e6a2bf4fb2f588aa00b428a60d873b5 (patch)
treef29541d55309487a94bd1d38e8b53bb3dde9aec6 /engines/hugo/route.cpp
parent48ee83b88957dab86bc763e9ef21a70179fa8679 (diff)
parente9f50882ea5b6beeefa994040be9d3bab6a1f107 (diff)
downloadscummvm-rg350-75e8452b6e6a2bf4fb2f588aa00b428a60d873b5.tar.gz
scummvm-rg350-75e8452b6e6a2bf4fb2f588aa00b428a60d873b5.tar.bz2
scummvm-rg350-75e8452b6e6a2bf4fb2f588aa00b428a60d873b5.zip
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
Diffstat (limited to 'engines/hugo/route.cpp')
-rw-r--r--engines/hugo/route.cpp487
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