Debugged computation and displaying of optimal walking paths

svn-id: r45597

7 files changed, 76 insertions, 28 deletions

diff --git a/engines/draci/animation.cpp b/engines/draci/animation.cpp
index a0f983100b..560f03ffcf 100644
--- a/engines/draci/animation.cpp
+++ b/engines/draci/animation.cpp
@@ -163,6 +163,11 @@ void Animation::addFrame(Drawable *frame, const SoundSample *sample) {
 	_samples.push_back(sample);
 }
 
+void Animation::replaceFrame(int i, Drawable *frame, const SoundSample *sample) {
+	_frames[i] = frame;
+	_samples[i] = sample;
+}
+
 Drawable *Animation::getCurrentFrame() {
 	// If there are no frames stored, return NULL
 	return _frames.size() > 0 ? _frames[_currentFrame] : NULL;
diff --git a/engines/draci/animation.h b/engines/draci/animation.h
index 6805822640..11cdc3d414 100644
--- a/engines/draci/animation.h
+++ b/engines/draci/animation.h
@@ -38,12 +38,14 @@ namespace Draci {
 enum {
 	kOverlayImage = -1,
 	kWalkingMapOverlay = -2,
-	kTitleText = -3,
-	kSpeechText = -4,
-	kInventorySprite = -5,
-	kDialogueLinesID = -6,
-	kUnused = -10,
-	kInventoryItemsID = -11
+	kWalkingShortestPathOverlay = -3,
+	kWalkingObliquePathOverlay = -4,
+	kTitleText = -5,
+	kSpeechText = -6,
+	kInventorySprite = -7,
+	kDialogueLinesID = -8,
+	kUnused = -12,
+	kInventoryItemsID = -13
 };
 
 /**
@@ -72,6 +74,7 @@ public:
 	void drawFrame(Surface *surface);
 
 	void addFrame(Drawable *frame, const SoundSample *sample);
+	void replaceFrame(int i, Drawable *frame, const SoundSample *sample);
 	Drawable *getCurrentFrame();
 	Drawable *getFrame(int frameNum);
 	void setCurrentFrame(uint frame);
diff --git a/engines/draci/draci.cpp b/engines/draci/draci.cpp
index 6f99a38830..fec53392d6 100644
--- a/engines/draci/draci.cpp
+++ b/engines/draci/draci.cpp
@@ -263,6 +263,15 @@ void DraciEngine::handleEvents() {
 			case Common::KEYCODE_w:
 				// Show walking map toggle
 				_showWalkingMap = !_showWalkingMap;
+				if (_showWalkingMap) {
+					_anims->play(kWalkingMapOverlay);
+					_anims->play(kWalkingShortestPathOverlay);
+					_anims->play(kWalkingObliquePathOverlay);
+				} else {
+					_anims->stop(kWalkingMapOverlay);
+					_anims->stop(kWalkingShortestPathOverlay);
+					_anims->stop(kWalkingObliquePathOverlay);
+				}
 				break;
 			case Common::KEYCODE_q:
 				_game->setWantQuickHero(!_game->getWantQuickHero());
@@ -286,15 +295,6 @@ void DraciEngine::handleEvents() {
 			_mouse->handleEvent(event);
 		}
 	}
-
-	// Show walking map overlay
-	// If the walking map overlay is already in the wanted state don't
-	// start / stop it constantly
-	if (_showWalkingMap && !_anims->getAnimation(kWalkingMapOverlay)->isPlaying()) {
-		_anims->play(kWalkingMapOverlay);
-	} else if (!_showWalkingMap && _anims->getAnimation(kWalkingMapOverlay)->isPlaying()) {
-		_anims->stop(kWalkingMapOverlay);
-	}
 }
 
 DraciEngine::~DraciEngine() {
diff --git a/engines/draci/game.cpp b/engines/draci/game.cpp
index 9f15a1e7fc..89622beff1 100644
--- a/engines/draci/game.cpp
+++ b/engines/draci/game.cpp
@@ -39,6 +39,12 @@ static const Common::String dialoguePath("ROZH");
 
 static double real_to_double(byte real[6]);
 
+enum {
+	kWalkingMapOverlayColour = 2,
+	kWalkingShortestPathOverlayColour = 120,
+	kWalkingObliquePathOverlayColour = 73
+};
+
 Game::Game(DraciEngine *vm) : _vm(vm) {
 	uint i;
 
@@ -932,6 +938,14 @@ void Game::playHeroAnimation(int anim_index) {
 	_vm->_anims->play(animID);
 }
 
+void Game::redrawWalkingPath(int id, byte colour, const WalkingMap::Path &path) {
+	Animation *anim = _vm->_anims->getAnimation(id);
+	Sprite *ov = _walkingMap.newOverlayFromPath(path, colour);
+	delete anim->getFrame(0);
+	anim->replaceFrame(0, ov, NULL);
+	anim->markDirtyRect(_vm->_screen->getSurface());
+}
+
 void Game::walkHero(int x, int y, SightDirection dir) {
 	// Needed for the map room with empty walking map.  For some reason,
 	// findNearestWalkable() takes several seconds with 100% CPU to finish
@@ -939,11 +953,20 @@ void Game::walkHero(int x, int y, SightDirection dir) {
 	if (!_currentRoom._heroOn)
 		return;
 
+	Common::Point oldHero = _hero;
 	Surface *surface = _vm->_screen->getSurface();
 	_hero = _walkingMap.findNearestWalkable(x, y, surface->getDimensions());
 	debugC(3, kDraciLogicDebugLevel, "Walk to x: %d y: %d", _hero.x, _hero.y);
 	// FIXME: Need to add proper walking (this only warps the dragon to position)
 
+	// Compute the shortest and obliqued path.
+	WalkingMap::Path shortestPath, obliquePath;
+	_walkingMap.findShortestPath(oldHero.x, oldHero.y, _hero.x, _hero.y, &shortestPath);
+	_walkingMap.obliquePath(shortestPath, &obliquePath);
+
+	redrawWalkingPath(kWalkingShortestPathOverlay, kWalkingShortestPathOverlayColour, shortestPath);
+	redrawWalkingPath(kWalkingObliquePathOverlay, kWalkingObliquePathOverlayColour, obliquePath);
+
 	Movement movement = kStopRight;
 	switch (dir) {
 	case kDirectionLeft:
@@ -1060,6 +1083,19 @@ void Game::loadRoom(int roomNum) {
 	// Load the walking map
 	loadWalkingMap(getMapID());
 
+	// Add overlays for the walking map and shortest/obliqued paths.
+	Animation *map = _vm->_anims->addAnimation(kWalkingMapOverlay, 256, _vm->_showWalkingMap);
+	Sprite *ov = _walkingMap.newOverlayFromMap(kWalkingMapOverlayColour);
+	map->addFrame(ov, NULL);
+
+	Animation *sPath = _vm->_anims->addAnimation(kWalkingShortestPathOverlay, 257, _vm->_showWalkingMap);
+	Animation *oPath = _vm->_anims->addAnimation(kWalkingObliquePathOverlay, 258, _vm->_showWalkingMap);
+	WalkingMap::Path emptyPath;
+	ov = _walkingMap.newOverlayFromPath(emptyPath, 0);
+	sPath->addFrame(ov, NULL);
+	ov = _walkingMap.newOverlayFromPath(emptyPath, 0);
+	oPath->addFrame(ov, NULL);
+
 	// Load the room's objects
 	for (uint i = 0; i < _info._numObjects; ++i) {
 		debugC(7, kDraciLogicDebugLevel,
@@ -1095,10 +1131,6 @@ void Game::loadRoom(int roomNum) {
 	// Set room palette
 	f = _vm->_paletteArchive->getFile(_currentRoom._palette);
 	_vm->_screen->setPalette(f->_data, 0, kNumColours);
-
-	Animation *map = _vm->_anims->addAnimation(kWalkingMapOverlay, 255, false);
-	Sprite *ov = _walkingMap.newOverlayFromMap();
-	map->addFrame(ov, NULL);
 }
 
 int Game::loadAnimation(uint animNum, uint z) {
@@ -1284,6 +1316,8 @@ void Game::enterNewRoom(bool force_reload) {
 
 	// Delete walking map testing overlay
 	_vm->_anims->deleteAnimation(kWalkingMapOverlay);
+	_vm->_anims->deleteAnimation(kWalkingShortestPathOverlay);
+	_vm->_anims->deleteAnimation(kWalkingObliquePathOverlay);
 
 	// TODO: Make objects capable of stopping their own animations
 	const GameObject *dragon = getObject(kDragonObject);
diff --git a/engines/draci/game.h b/engines/draci/game.h
index d8155dbcae..3ac27a2997 100644
--- a/engines/draci/game.h
+++ b/engines/draci/game.h
@@ -321,6 +321,7 @@ private:
 	void enterNewRoom(bool force_reload);
 	void loadRoom(int roomNum);
 	void runGateProgram(int gate);
+	void redrawWalkingPath(int id, byte colour, const WalkingMap::Path &path);
 
 	DraciEngine *_vm;
 
diff --git a/engines/draci/walking.cpp b/engines/draci/walking.cpp
index c08e97346c..ad1642132e 100644
--- a/engines/draci/walking.cpp
+++ b/engines/draci/walking.cpp
@@ -57,7 +57,7 @@ bool WalkingMap::isWalkable(int x, int y) const {
 	return getPixel(x / _deltaX, y / _deltaY);
 }
 
-Sprite *WalkingMap::newOverlayFromMap() const {
+Sprite *WalkingMap::newOverlayFromMap(byte colour) const {
 	// HACK: Create a visible overlay from the walking map so we can test it
 	byte *wlk = new byte[_realWidth * _realHeight];
 	memset(wlk, 255, _realWidth * _realHeight);
@@ -65,7 +65,7 @@ Sprite *WalkingMap::newOverlayFromMap() const {
 	for (int i = 0; i < _mapWidth; ++i) {
 		for (int j = 0; j < _mapHeight; ++j) {
 			if (getPixel(i, j)) {
-				drawOverlayRectangle(i, j, 2, wlk);
+				drawOverlayRectangle(i, j, colour, wlk);
 			}
 		}
 	}
@@ -274,6 +274,9 @@ bool WalkingMap::findShortestPath(int x1, int y1, int x2, int y2, WalkingMap::Pa
 void WalkingMap::obliquePath(const WalkingMap::Path& path, WalkingMap::Path *obliquedPath) const {
 	// Prune the path to only contain vertices where the direction is changing.
 	obliquedPath->clear();
+	if (path.empty()) {
+		return;
+	}
 	obliquedPath->push_back(path[0]);
 	uint index = 1;
 	while (index < path.size()) {
@@ -315,8 +318,8 @@ void WalkingMap::obliquePath(const WalkingMap::Path& path, WalkingMap::Path *obl
 		bool allPointsOk = true;
 		// Testing only points between (i.e., without the end-points) is OK.
 		for (int step = 1; step < steps; ++step) {
-			const int x = (v1.x * (steps-step) + v3.x * step) / steps;
-			const int y = (v1.y * (steps-step) + v3.y * step) / steps;
+			const int x = (v1.x * (steps-step) + v3.x * step + steps/2) / steps;
+			const int y = (v1.y * (steps-step) + v3.y * step + steps/2) / steps;
 			if (!getPixel(x, y)) {
 				allPointsOk = false;
 				break;
@@ -340,15 +343,17 @@ Sprite *WalkingMap::newOverlayFromPath(const WalkingMap::Path &path, byte colour
 		// Draw only points in the interval [v1, v2).  These half-open
 		// half-closed intervals connect all the way to the last point.
 		for (int step = 0; step < steps; ++step) {
-			const int x = (v1.x * (steps-step) + v2.x * step) / steps;
-			const int y = (v1.y * (steps-step) + v2.y * step) / steps;
+			const int x = (v1.x * (steps-step) + v2.x * step + steps/2) / steps;
+			const int y = (v1.y * (steps-step) + v2.y * step + steps/2) / steps;
 			drawOverlayRectangle(x, y, colour, wlk);
 		}
 	}
 	// Draw the last point.  This works also when the path has no segment,
 	// but just one point.
-	const PathVertex &vLast = path[path.size()-1];
-	drawOverlayRectangle(vLast.x, vLast.y, colour, wlk);
+	if (path.size() > 0) {
+		const PathVertex &vLast = path[path.size()-1];
+		drawOverlayRectangle(vLast.x, vLast.y, colour, wlk);
+	}
 
 	Sprite *ov = new Sprite(_realWidth, _realHeight, wlk, 0, 0, false);
 	// ov has taken the ownership of wlk.
diff --git a/engines/draci/walking.h b/engines/draci/walking.h
index ed6d95ca85..161f16d441 100644
--- a/engines/draci/walking.h
+++ b/engines/draci/walking.h
@@ -49,7 +49,7 @@ public:
 	bool getPixel(int x, int y) const;
 	bool isWalkable(int x, int y) const;
 
-	Sprite *newOverlayFromMap() const;
+	Sprite *newOverlayFromMap(byte colour) const;
 	Common::Point findNearestWalkable(int x, int y, Common::Rect searchRect) const;
 
 	typedef Common::Array<PathVertex> Path;