[Scummvm-cvs-logs] SF.net SVN: scummvm:[45622] scummvm/trunk/engines/draci

spalek at users.sourceforge.net spalek at users.sourceforge.net
Tue Nov 3 04:24:59 CET 2009


Revision: 45622
          http://scummvm.svn.sourceforge.net/scummvm/?rev=45622&view=rev
Author:   spalek
Date:     2009-11-03 03:24:59 +0000 (Tue, 03 Nov 2009)

Log Message:
-----------
Greatly improved the quality of obliqueing the shortest path.

The current algorithm is much better than the original player'ss one and it
find really nice curved paths.

Also, started preparing interface for actually walking along this path.

Modified Paths:
--------------
    scummvm/trunk/engines/draci/game.cpp
    scummvm/trunk/engines/draci/game.h
    scummvm/trunk/engines/draci/walking.cpp
    scummvm/trunk/engines/draci/walking.h

Modified: scummvm/trunk/engines/draci/game.cpp
===================================================================
--- scummvm/trunk/engines/draci/game.cpp	2009-11-02 23:48:21 UTC (rev 45621)
+++ scummvm/trunk/engines/draci/game.cpp	2009-11-03 03:24:59 UTC (rev 45622)
@@ -950,7 +950,7 @@
 	_vm->_anims->play(animID);
 }
 
-void Game::redrawWalkingPath(int id, byte colour, const WalkingMap::Path &path) {
+void Game::redrawWalkingPath(int id, byte colour, const WalkingPath &path) {
 	Animation *anim = _vm->_anims->getAnimation(id);
 	Sprite *ov = _walkingMap.newOverlayFromPath(path, colour);
 	delete anim->getFrame(0);
@@ -965,15 +965,14 @@
 	if (!_currentRoom._heroOn)
 		return;
 
-	Common::Point oldHero = _hero;
+	Common::Point target;
 	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)
+	target = _walkingMap.findNearestWalkable(x, y, surface->getDimensions());
+	debugC(3, kDraciLogicDebugLevel, "Walk to x: %d y: %d", target.x, target.y);
 
 	// Compute the shortest and obliqued path.
-	WalkingMap::Path shortestPath, obliquePath;
-	_walkingMap.findShortestPath(oldHero, _hero, &shortestPath);
+	WalkingPath shortestPath, obliquePath;
+	_walkingMap.findShortestPath(_hero, target, &shortestPath);
 	// TODO: test reachability and react
 	_walkingMap.obliquePath(shortestPath, &obliquePath);
 	if (_vm->_showWalkingMap) {
@@ -981,6 +980,10 @@
 		redrawWalkingPath(kWalkingObliquePathOverlay, kWalkingObliquePathOverlayColour, obliquePath);
 	}
 
+	_walkingState.setPath(obliquePath);
+
+	// FIXME: Need to add proper walking (this only warps the dragon to position)
+	_hero = target;
 	Movement movement = kStopRight;
 	switch (dir) {
 	case kDirectionLeft:
@@ -1104,7 +1107,7 @@
 
 	Animation *sPath = _vm->_anims->addAnimation(kWalkingShortestPathOverlay, 257, _vm->_showWalkingMap);
 	Animation *oPath = _vm->_anims->addAnimation(kWalkingObliquePathOverlay, 258, _vm->_showWalkingMap);
-	WalkingMap::Path emptyPath;
+	WalkingPath emptyPath;
 	ov = _walkingMap.newOverlayFromPath(emptyPath, 0);
 	sPath->addFrame(ov, NULL);
 	ov = _walkingMap.newOverlayFromPath(emptyPath, 0);

Modified: scummvm/trunk/engines/draci/game.h
===================================================================
--- scummvm/trunk/engines/draci/game.h	2009-11-02 23:48:21 UTC (rev 45621)
+++ scummvm/trunk/engines/draci/game.h	2009-11-03 03:24:59 UTC (rev 45622)
@@ -329,7 +329,7 @@
 	bool enterNewRoom();	// Returns false if another room change has been triggered and therefore loop() shouldn't be called yet.
 	void loadRoom(int roomNum);
 	void runGateProgram(int gate);
-	void redrawWalkingPath(int id, byte colour, const WalkingMap::Path &path);
+	void redrawWalkingPath(int id, byte colour, const WalkingPath &path);
 
 	DraciEngine *_vm;
 
@@ -350,7 +350,6 @@
 	bool _inventoryExit;
 
 	Room _currentRoom;
-	WalkingMap _walkingMap;
 	int _newRoom;
 	int _newGate;
 	int _previousRoom;
@@ -394,6 +393,9 @@
 	bool _enableQuickHero;
 	bool _wantQuickHero;
 	bool _enableSpeedText;
+
+	WalkingMap _walkingMap;
+	WalkingState _walkingState;
 };
 
 } // End of namespace Draci

Modified: scummvm/trunk/engines/draci/walking.cpp
===================================================================
--- scummvm/trunk/engines/draci/walking.cpp	2009-11-02 23:48:21 UTC (rev 45621)
+++ scummvm/trunk/engines/draci/walking.cpp	2009-11-03 03:24:59 UTC (rev 45622)
@@ -65,7 +65,7 @@
 	for (int i = 0; i < _mapWidth; ++i) {
 		for (int j = 0; j < _mapHeight; ++j) {
 			if (getPixel(i, j)) {
-				drawOverlayRectangle(i, j, colour, wlk);
+				drawOverlayRectangle(Common::Point(i, j), colour, wlk);
 			}
 		}
 	}
@@ -185,7 +185,7 @@
 // We don't use Common::Point due to using static initialization.
 int WalkingMap::kDirections[][2] = { {0, -1}, {0, +1}, {-1, 0}, {+1, 0} };
 
-bool WalkingMap::findShortestPath(Common::Point p1, Common::Point p2, Path *path) const {
+bool WalkingMap::findShortestPath(Common::Point p1, Common::Point p2, WalkingPath *path) const {
 	// Round the positions to map squares.
 	p1.x /= _deltaX;
 	p2.x /= _deltaX;
@@ -271,7 +271,7 @@
 	return true;
 }
 
-void WalkingMap::obliquePath(const WalkingMap::Path& path, WalkingMap::Path *obliquedPath) const {
+void WalkingMap::obliquePath(const WalkingPath& path, WalkingPath *obliquedPath) {
 	// Prune the path to only contain vertices where the direction is changing.
 	obliquedPath->clear();
 	if (path.empty()) {
@@ -305,33 +305,54 @@
 
 	// Making the path oblique works as follows.  If the path has at least
 	// 3 remaining vertices, we try to oblique the L-shaped path between
-	// them.  If this can be done (i.e., all points on the line between the
-	// 1st and 3rd point are walkable), we remove the 2nd vertex (now the
-	// path will go directly from the 1st vertex to the 3rd one), and
-	// continue obliqueing from the same index, otherwise we leave the
-	// first edge (going from the 1st vertex to the 2nd one) as is, move
-	// the index to the 2nd vertex, and continue.
+	// them.  First we try to connect the 1st and 3rd vertex directly (if
+	// all points on the line between them are walkable) and then we try to
+	// walk on both edges towards the 2nd vertex in parallel and try to
+	// find a shortcut (replacing the 2nd vertex by this mid-point).  If
+	// either of those attempts succeeds, we have shortned the path.  We
+	// update the path vertices and continue with the next segment.
 	for (uint head = 2; head < obliquedPath->size(); ++head) {
 		const Common::Point &v1 = (*obliquedPath)[head-2];
+		const Common::Point &v2 = (*obliquedPath)[head-1];
 		const Common::Point &v3 = (*obliquedPath)[head];
-		const int steps = MAX(abs(v3.x - v1.x), abs(v3.y - v1.y));
-		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/2) / steps;
-			const int y = (v1.y * (steps-step) + v3.y * step + steps/2) / steps;
-			if (!getPixel(x, y)) {
-				allPointsOk = false;
+		const int points12 = pointsBetween(v1, v2);
+		const int points32 = pointsBetween(v3, v2);
+		// Find the first point p on each edge [v1, v2] and [v3, v2]
+		// such that the edge [p, the third vertex] is covered.
+		// Ideally we would like p \in {v1, v3} and the closer the
+		// better.  The last point p = v2 should always succeed.
+		int first12, first32;
+		for (first12 = 0; first12 < points12; ++first12) {
+			Common::Point midPoint = interpolate(v1, v2, first12, points12);
+			if (lineIsCovered(midPoint, v3)) {
 				break;
 			}
 		}
-		if (allPointsOk) {
+		if (first12 == 0) {
+			// Can completely remove the vertex.  Head stays the
+			// same after -- and ++.
 			obliquedPath->remove_at(--head);
+			continue;
 		}
+		for (first32 = 0; first32 < points32; ++first32) {
+			Common::Point midPoint = interpolate(v3, v2, first32, points32);
+			if (lineIsCovered(midPoint, v1)) {
+				break;
+			}
+		}
+		if (first12 < points12 && first32 >= points32 + MIN(first12 - points12, 0)) {
+			// There is such a point on the first edge and the
+			// second edge has either not succeeded or we gain more
+			// by cutting this edge than the other one.
+			(*obliquedPath)[head-1] = interpolate(v1, v2, first12, points12);
+			// After replacing the 2nd vertex, let head move on.
+		} else if (first32 < points32) {
+			(*obliquedPath)[head-1] = interpolate(v3, v2, first32, points32);
+		}
 	}
 }
 
-Sprite *WalkingMap::newOverlayFromPath(const WalkingMap::Path &path, byte colour) const {
+Sprite *WalkingMap::newOverlayFromPath(const WalkingPath &path, 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);
@@ -339,20 +360,18 @@
 	for (uint segment = 1; segment < path.size(); ++segment) {
 		const Common::Point &v1 = path[segment-1];
 		const Common::Point &v2 = path[segment];
-		const int steps = MAX(abs(v2.x - v1.x), abs(v2.y - v1.y));
+		const int steps = pointsBetween(v1, v2);
 		// 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/2) / steps;
-			const int y = (v1.y * (steps-step) + v2.y * step + steps/2) / steps;
-			drawOverlayRectangle(x, y, colour, wlk);
+			drawOverlayRectangle(interpolate(v1, v2, step, steps), colour, wlk);
 		}
 	}
 	// Draw the last point.  This works also when the path has no segment,
 	// but just one point.
 	if (path.size() > 0) {
 		const Common::Point &vLast = path[path.size()-1];
-		drawOverlayRectangle(vLast.x, vLast.y, colour, wlk);
+		drawOverlayRectangle(vLast, colour, wlk);
 	}
 
 	Sprite *ov = new Sprite(_realWidth, _realHeight, wlk, 0, 0, false);
@@ -361,12 +380,33 @@
 	return ov;
 }
 
-void WalkingMap::drawOverlayRectangle(int x, int y, byte colour, byte *buf) const {
+void WalkingMap::drawOverlayRectangle(const Common::Point &p, byte colour, byte *buf) const {
 	for (int i = 0; i < _deltaX; ++i) {
 		for (int j = 0; j < _deltaY; ++j) {
-			buf[(y * _deltaY + j) * _realWidth + (x * _deltaX + i)] = colour;
+			buf[(p.y * _deltaY + j) * _realWidth + (p.x * _deltaX + i)] = colour;
 		}
 	}
 }
 
+int WalkingMap::pointsBetween(const Common::Point &p1, const Common::Point &p2) const {
+	return MAX(abs(p2.x - p1.x), abs(p2.y - p1.y));
 }
+
+Common::Point WalkingMap::interpolate(const Common::Point &p1, const Common::Point &p2, int i, int n) const {
+	const int x = (p1.x * (n-i) + p2.x * i + n/2) / n;
+	const int y = (p1.y * (n-i) + p2.y * i + n/2) / n;
+	return Common::Point(x, y);
+}
+
+bool WalkingMap::lineIsCovered(const Common::Point &p1, const Common::Point &p2) const {
+	const int steps = pointsBetween(p1, p2);
+	for (int step = 0; step <= steps; ++step) {
+		Common::Point p = interpolate(p1, p2, step, steps);
+		if (!getPixel(p.x, p.y)) {
+			return false;
+		}
+	}
+	return true;
+}
+
+}

Modified: scummvm/trunk/engines/draci/walking.h
===================================================================
--- scummvm/trunk/engines/draci/walking.h	2009-11-02 23:48:21 UTC (rev 45621)
+++ scummvm/trunk/engines/draci/walking.h	2009-11-03 03:24:59 UTC (rev 45622)
@@ -33,6 +33,8 @@
 
 class Sprite;
 
+typedef Common::Array<Common::Point> WalkingPath;
+
 class WalkingMap {
 public:
 	WalkingMap() : _realWidth(0), _realHeight(0), _deltaX(1), _deltaY(1),
@@ -46,10 +48,9 @@
 	Sprite *newOverlayFromMap(byte colour) const;
 	Common::Point findNearestWalkable(int x, int y, Common::Rect searchRect) const;
 
-	typedef Common::Array<Common::Point> Path;
-	bool findShortestPath(Common::Point p1, Common::Point p2, Path *path) const;
-	void obliquePath(const Path& path, Path *obliquedPath) const;
-	Sprite *newOverlayFromPath(const Path &path, byte colour) const;
+	bool findShortestPath(Common::Point p1, Common::Point p2, WalkingPath *path) const;
+	void obliquePath(const WalkingPath& path, WalkingPath *obliquedPath);
+	Sprite *newOverlayFromPath(const WalkingPath &path, byte colour) const;
 
 private:
 	int _realWidth, _realHeight;
@@ -63,7 +64,10 @@
 	// 4 possible directions to walk from a pixel.
 	static int kDirections[][2];
 
-	void drawOverlayRectangle(int x, int y, byte colour, byte *buf) const;
+	void drawOverlayRectangle(const Common::Point &p, byte colour, byte *buf) const;
+	int pointsBetween(const Common::Point &p1, const Common::Point &p2) const;
+	Common::Point interpolate(const Common::Point &p1, const Common::Point &p2, int i, int n) const;
+	bool lineIsCovered(const Common::Point &p1, const Common::Point &p2) const;
 };
 
 /*
@@ -86,6 +90,18 @@
 	kSpeakRight, kSpeakLeft, kStopRight, kStopLeft
 };
 
+class WalkingState {
+public:
+	WalkingState() : _path() {}
+	~WalkingState() {}
+
+	void setPath(const WalkingPath& path) { _path = path; }
+	const WalkingPath& getPath() const { return _path; }
+
+private:
+	WalkingPath _path;
+};
+
 } // End of namespace Draci
 
 #endif // DRACI_WALKING_H


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.




More information about the Scummvm-git-logs mailing list