STARTREK: Pathfinding

8 files changed, 256 insertions, 17 deletions

diff --git a/engines/startrek/awaymission.cpp b/engines/startrek/awaymission.cpp
index 77576d295c..16ce842eb7 100644
--- a/engines/startrek/awaymission.cpp
+++ b/engines/startrek/awaymission.cpp
@@ -20,6 +20,7 @@
  *
  */
 
+#include "startrek/iwfile.h"
 #include "startrek/startrek.h"
 
 namespace StarTrek {
@@ -89,13 +90,13 @@ void StarTrekEngine::loadRoom(const Common::String &missionName, int roomIndex)
 	_awayMission.mapFileLoaded = 1;
 	_mapFilename = _screenName;
 	_mapFile = loadFile(_mapFilename + ".map");
-	// loadIWFile(_mapFilename);
+	_iwFile = SharedPtr<IWFile>(new IWFile(this, _mapFilename + ".iw"));
 
 	objectFunc1();
 	initObjects();
 
-	double num = _room->readRdfWord(0x0c) - _room->readRdfWord(0x0a);
-	double den = _room->readRdfWord(0x06) - _room->readRdfWord(0x08) + 1;
+	double num = _room->getVar0c() - _room->getVar0a();
+	double den = _room->getVar06() - _room->getVar08() + 1;
 	_playerObjectScale = (int32)(num * 256 / den);
 
 	// TODO: RDF vars 1e/1f and 20/21; relates to BAN files?
@@ -239,6 +240,8 @@ void StarTrekEngine::runAwayMissionCycle() {
  * when that position is solid.
  */
 bool StarTrekEngine::isPositionSolid(int16 x, int16 y) {
+	assert(x >= 0 && x < SCREEN_WIDTH && y >= 0 && y < SCREEN_HEIGHT);
+
 	_mapFile->seek((y * SCREEN_WIDTH + x) / 8, SEEK_SET);
 	return _mapFile->readByte() & (0x80 >> (x % 8));
 }
diff --git a/engines/startrek/common.h b/engines/startrek/common.h
index 4598085a27..c84b9c4e43 100644
--- a/engines/startrek/common.h
+++ b/engines/startrek/common.h
@@ -34,6 +34,10 @@ T max(T a, T b) { return a > b ? a : b; }
 
 Common::Rect getRectEncompassing(Common::Rect r1, Common::Rect r2);
 
+
+// Fixed-point (16.16) number
+typedef int32 FixedInt;
+
 }
 
 #endif
diff --git a/engines/startrek/iwfile.cpp b/engines/startrek/iwfile.cpp
new file mode 100644
index 0000000000..830cb78855
--- /dev/null
+++ b/engines/startrek/iwfile.cpp
@@ -0,0 +1,82 @@
+
+/* 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.
+ *
+ */
+
+#include "startrek/iwfile.h"
+
+namespace StarTrek {
+
+IWFile::IWFile(StarTrekEngine *vm, const Common::String &filename) {
+	debug(6, "IW File: %s", filename.c_str());
+
+	_vm = vm;
+
+	SharedPtr<FileStream> file = _vm->loadFile(filename);
+	_numEntries = file->readUint16();
+
+	assert(_numEntries < MAX_KEY_POSITIONS);
+
+	for (int i = 0; i < MAX_KEY_POSITIONS; i++) {
+		int16 x = file->readUint16();
+		int16 y = file->readUint16();
+		_keyPositions[i] = Common::Point(x, y);
+	}
+
+	for (int i = 0; i < _numEntries; i++) {
+		file->read(_iwEntries[i], _numEntries);
+	}
+}
+
+// FIXME: same issue with sorting as with "compareSpritesByLayer" in graphics.cpp.
+bool iwSorter(const Common::Point &p1, const Common::Point &p2) {
+	return p1.y < p2.y;
+}
+
+/**
+ * Returns the index of the nearest "key position" in the room that an object can walk to
+ * (in a straight line) from a given position.
+ */
+int IWFile::getClosestKeyPosition(int16 x, int16 y) {
+	// This is a sorted list of indices from 0 to _numEntries-1.
+	// The index is stored in Point.x, and the "cost" (distance from position) is stored
+	// in Point.y for sorting purposes.
+	Common::Point sortedIndices[MAX_KEY_POSITIONS];
+
+	for (int i = 0; i < _numEntries; i++) {
+		sortedIndices[i].x = i;
+		sortedIndices[i].y = sqrt(_keyPositions[i].sqrDist(Common::Point(x, y)));
+	}
+
+	sort(sortedIndices, sortedIndices + _numEntries, &iwSorter);
+
+	// Iterate through positions from closest to furthest
+	for (int i = 0; i < _numEntries; i++) {
+		int index = sortedIndices[i].x;
+		Common::Point dest = _keyPositions[index];
+		if (_vm->directPathExists(x, y, dest.x, dest.y))
+			return index;
+	}
+
+	return -1;
+}
+
+}
diff --git a/engines/startrek/iwfile.h b/engines/startrek/iwfile.h
new file mode 100644
index 0000000000..ffc5467a6b
--- /dev/null
+++ b/engines/startrek/iwfile.h
@@ -0,0 +1,59 @@
+
+/* 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.
+ *
+ */
+
+#ifndef STARTREK_IWFILE_H
+#define STARTREK_IWFILE_H
+
+#include "startrek/startrek.h"
+
+/**
+ * Files with the ".iw" extension define a set of "key points" through a room used for
+ * pathing. This is a basic interface for that.
+ */
+namespace StarTrek {
+
+const int MAX_KEY_POSITIONS = 32;
+
+class IWFile {
+public:
+	IWFile(StarTrekEngine *vm, const Common::String &filename);
+
+	int getNumEntries() { return _numEntries; }
+	int getClosestKeyPosition(int16 x, int16 y);
+
+	///< List of "key positions" used for pathing.
+	Common::Point _keyPositions[MAX_KEY_POSITIONS];
+
+	///< _iwEntries[i][j] is the index of the next key position to move to, when one is
+	///   already at key position "i" and is trying to get to key position "j".
+	byte _iwEntries[MAX_KEY_POSITIONS][MAX_KEY_POSITIONS];
+
+private:
+	StarTrekEngine *_vm;
+
+	uint16 _numEntries;
+};
+
+}
+
+#endif
diff --git a/engines/startrek/module.mk b/engines/startrek/module.mk
index b79126a794..04f2c7c53a 100644
--- a/engines/startrek/module.mk
+++ b/engines/startrek/module.mk
@@ -8,6 +8,7 @@ MODULE_OBJS = \
 	events.o \
 	filestream.o \
 	font.o \
+	iwfile.o \
 	lzss.o \
 	graphics.o \
 	object.o \
diff --git a/engines/startrek/object.h b/engines/startrek/object.h
index d1cd8fb649..eb0f3dacad 100644
--- a/engines/startrek/object.h
+++ b/engines/startrek/object.h
@@ -23,6 +23,7 @@
 #ifndef STARTREK_OBJECT_H
 #define STARTREK_OBJECT_H
 
+#include "startrek/common.h"
 #include "startrek/sprite.h"
 
 #include "common/scummsys.h"
@@ -58,12 +59,12 @@ struct Object {
 	int16 iwDestPosition;
 
 	// Fixed-point position values (16.16) used while walking.
-	uint32 granularPosX;
-	uint32 granularPosY;
+	FixedInt granularPosX;
+	FixedInt granularPosY;
 
 	// Fixed-point speed values (16.16).
-	uint32 speedX;
-	uint32 speedY;
+	FixedInt speedX;
+	FixedInt speedY;
 
 	Common::Point dest; // Position object is walking toward
 	uint16 field90;
diff --git a/engines/startrek/startrek.cpp b/engines/startrek/startrek.cpp
index 9cafd44365..15c991e227 100644
--- a/engines/startrek/startrek.cpp
+++ b/engines/startrek/startrek.cpp
@@ -34,6 +34,7 @@
 #include "video/qt_decoder.h"
 
 #include "startrek/filestream.h"
+#include "startrek/iwfile.h"
 #include "startrek/lzss.h"
 #include "startrek/startrek.h"
 
@@ -412,10 +413,32 @@ bool StarTrekEngine::objectWalkToPosition(int objectIndex, const Common::String
 	object->iwDestPosition = -1;
 	object->iwSrcPosition = -1;
 
-	// TODO: if (directPathExists(srcX, srcY, destX, destY)) {
+	if (directPathExists(srcX, srcY, destX, destY)) {
+		chooseObjectDirectionForWalking(object, srcX, srcY, destX, destY);
+		updateObjectPositionWhileWalking(object, (object->granularPosX + 0x8000) >> 16, (object->granularPosY + 0x8000) >> 16);
+		return true;
+	}
+	else {
+		object->iwSrcPosition = _iwFile->getClosestKeyPosition(srcX, srcY);
+		object->iwDestPosition = _iwFile->getClosestKeyPosition(destX, destY);
+
+		if (object->iwSrcPosition == -1 || object->iwDestPosition == -1) {
+			// No path exists; face south by default.
+			strcat(object->animationString2, "S");
+			object->direction = 'S';
 
-	chooseObjectDirectionForWalking(object, srcX, srcY, destX, destY);
-	updateObjectPositionWhileWalking(object, (object->granularPosX + 0x8000) >> 16, (object->granularPosY + 0x8000) >> 16);
+			updateObjectPositionWhileWalking(object, srcX, srcY);
+			initStandAnim(objectIndex);
+
+			return false;
+		}
+		else {
+			Common::Point iwSrc = _iwFile->_keyPositions[object->iwSrcPosition];
+			chooseObjectDirectionForWalking(object, srcX, srcY, iwSrc.x, iwSrc.y);
+			updateObjectPositionWhileWalking(object, (object->granularPosX + 0x8000) >> 16, (object->granularPosY + 0x8000) >> 16);
+			return true;
+		}
+	}
 }
 
 void StarTrekEngine::updateObjectAnimations() {
@@ -432,8 +455,6 @@ void StarTrekEngine::updateObjectAnimations() {
 				object->animFile->seek(18 + nextAnimIndex + object->animFrame * 22, SEEK_SET);
 				byte nextAnimFrame = object->animFile->readByte();
 
-				debugC(7, kDebugGraphics, "Object %d animation frame %d", i, nextAnimFrame);
-
 				if (object->animFrame != nextAnimFrame) {
 					if (nextAnimFrame == object->numAnimFrames - 1) {
 						object->field62++;
@@ -511,7 +532,7 @@ void StarTrekEngine::updateObjectAnimations() {
 				if (object->iwSrcPosition == -1) {
 					if (object->field64 != 0) {
 						object->field64 = 0;
-						//addCommand(COMMAND_12, object->field66 & 0xff, 0, 0);
+						//addCommand(COMMAND_12, object->field66 & 0xff, 0, 0); // TODO
 					}
 
 					object->sprite.bitmap.reset();
@@ -523,10 +544,14 @@ void StarTrekEngine::updateObjectAnimations() {
 						object->animationString2[strlen(object->animationString2) - 1] = '\0';
 						object->iwDestPosition = -1;
 						object->iwSrcPosition = -1;
-						// sub_11677(object->pos.x, object->pos.y, object->dest.x, object->dest.y);
+						chooseObjectDirectionForWalking(object, object->pos.x, object->pos.y, object->dest.x, object->dest.y);
 					}
 					else {
-
+						int index = _iwFile->_iwEntries[object->iwSrcPosition][object->iwDestPosition];
+						object->iwSrcPosition = index;
+						Common::Point dest = _iwFile->_keyPositions[object->iwSrcPosition];
+						object->animationString2[strlen(object->animationString2) - 1] = '\0';
+						chooseObjectDirectionForWalking(object, object->pos.x, object->pos.y, dest.x, dest.y);
 					}
 				}
 			}
@@ -618,8 +643,8 @@ void StarTrekEngine::releaseAnim(Object *object) {
 		object->sprite.bitmap.reset();
 		object->animFile.reset();
 		break;
-	case 1: // TODO
-		warning("Unimplemented anim type %d", object->animType);
+	case 1:
+		object->sprite.bitmap.reset();
 		break;
 	default:
 		error("Invalid anim type");
@@ -740,6 +765,67 @@ void StarTrekEngine::chooseObjectDirectionForWalking(Object *object, int16 srcX,
 	}
 }
 
+/**
+ * Returns true if an object can walk directly from a source position to a destination
+ * position without running into unwalkable terrain.
+ */
+bool StarTrekEngine::directPathExists(int16 srcX, int16 srcY, int16 destX, int16 destY) {
+	int32 distX = destX - srcX;
+	int32 distY = destY - srcY;
+
+	int32 absDistX = abs(distX);
+	int32 absDistY = abs(distY);
+
+	int32 distCounter;
+	FixedInt speedX, speedY;
+
+	if (absDistX > absDistY) {
+		distCounter = absDistX;
+
+		if (distCounter == 0)
+			return true;
+
+		speedY = (distY << 16) / absDistX;
+
+		if (distX > 0)
+			speedX = 1 << 16;
+		else
+			speedX = -1 << 16;
+	}
+	else { // absDistX <= absDistY
+		distCounter = absDistY;
+
+		if (distCounter == 0)
+			return true;
+
+		speedX = (distX << 16) / absDistY;
+
+		if (distY > 0)
+			speedY = 1 << 16;
+		else
+			speedY = -1 << 16;
+	}
+
+	FixedInt fixedX = srcX << 16;
+	FixedInt fixedY = srcY << 16;
+
+	if (isPositionSolid((fixedX + 0x8000) >> 16, (fixedY + 0x8000) >> 16))
+		return false;
+
+	while (distCounter-- > 0) {
+		fixedX += speedX;
+		fixedY += speedY;
+
+		if (isPositionSolid((fixedX + 0x8000) >> 16, (fixedY + 0x8000) >> 16))
+			return false;
+	}
+
+	return true;
+}
+
+/**
+ * Loads a bitmap for the animation frame with the given scale.
+ */
 SharedPtr<Bitmap> StarTrekEngine::loadAnimationFrame(const Common::String &filename, uint16 scale) {
 	SharedPtr<Bitmap> bitmapToReturn;
 
diff --git a/engines/startrek/startrek.h b/engines/startrek/startrek.h
index 68a9d51218..0c3273f394 100644
--- a/engines/startrek/startrek.h
+++ b/engines/startrek/startrek.h
@@ -114,6 +114,7 @@ const int MAX_OBJECTS = 0x20;
 
 struct StarTrekGameDescription;
 class Graphics;
+class IWFile;
 class Sound;
 
 class StarTrekEngine : public ::Engine {
@@ -165,6 +166,7 @@ public:
 	void initStandAnim(int objectIndex);
 	void updateObjectPositionWhileWalking(Object *object, int16 x, int16 y);
 	void chooseObjectDirectionForWalking(Object *object, int16 srcX, int16 srcY, int16 destX, int16 destY);
+	bool directPathExists(int16 srcX, int16 srcY, int16 destX, int16 destY);
 
 	SharedPtr<Bitmap> loadAnimationFrame(const Common::String &filename, uint16 arg2);
 	Common::String getCrewmanAnimFilename(int objectIndex, const Common::String &basename);
@@ -270,6 +272,7 @@ public:
 private:
 	Common::MacResManager *_macResFork;
 	Room *_room;
+	SharedPtr<IWFile> _iwFile;
 };
 
 } // End of namespace StarTrek