aboutsummaryrefslogtreecommitdiff
path: root/engines/draci
diff options
context:
space:
mode:
Diffstat (limited to 'engines/draci')
-rw-r--r--engines/draci/game.cpp10
-rw-r--r--engines/draci/game.h2
-rw-r--r--engines/draci/walking.cpp122
-rw-r--r--engines/draci/walking.h6
4 files changed, 59 insertions, 81 deletions
diff --git a/engines/draci/game.cpp b/engines/draci/game.cpp
index 53ada6ace4..0336dd4320 100644
--- a/engines/draci/game.cpp
+++ b/engines/draci/game.cpp
@@ -973,18 +973,18 @@ void Game::setHeroPosition(const Common::Point &p) {
_hero = p;
}
-Common::Point Game::findNearestWalkable(int x, int y) const {
- Surface *surface = _vm->_screen->getSurface();
- return _walkingMap.findNearestWalkable(x, y, surface->getDimensions());
-}
-
void Game::walkHero(int x, int y, SightDirection dir) {
if (!_currentRoom._heroOn) {
// Nothing to do. Happens for example in the map.
return;
}
+ // Find the closest walkable point.
Common::Point target = findNearestWalkable(x, y);
+ if (target.x < 0 || target.y < 0) {
+ debug(1, "The is no walkable point on the map");
+ return;
+ }
// Compute the shortest and obliqued path.
WalkingPath shortestPath, obliquePath;
diff --git a/engines/draci/game.h b/engines/draci/game.h
index 8d219850d2..6e71088ae0 100644
--- a/engines/draci/game.h
+++ b/engines/draci/game.h
@@ -207,7 +207,7 @@ public:
return n;
}
- Common::Point findNearestWalkable(int x, int y) const;
+ Common::Point findNearestWalkable(int x, int y) const { return _walkingMap.findNearestWalkable(x, y); }
void heroAnimationFinished() { _walkingState.heroAnimationFinished(); }
void stopWalking() { _walkingState.stopWalking(); } // and clear callback
void walkHero(int x, int y, SightDirection dir); // start walking and leave callback as is
diff --git a/engines/draci/walking.cpp b/engines/draci/walking.cpp
index 7998126699..14e7153de2 100644
--- a/engines/draci/walking.cpp
+++ b/engines/draci/walking.cpp
@@ -54,9 +54,9 @@ bool WalkingMap::getPixel(int x, int y) const {
return *pMapByte & (1 << x % 8);
}
-bool WalkingMap::isWalkable(int x, int y) const {
+bool WalkingMap::isWalkable(const Common::Point &p) const {
// Convert to map pixels
- return getPixel(x / _deltaX, y / _deltaY);
+ return getPixel(p.x / _deltaX, p.y / _deltaY);
}
Sprite *WalkingMap::newOverlayFromMap(byte colour) const {
@@ -85,107 +85,82 @@ Sprite *WalkingMap::newOverlayFromMap(byte colour) const {
* @param startY y coordinate of the point
*
* @return A Common::Point representing the nearest walkable point
- *
- * The algorithm was copied from the original engine for exactness.
- * TODO: Study this algorithm in more detail so it can be documented properly and
- * possibly improved / simplified.
*/
-Common::Point WalkingMap::findNearestWalkable(int startX, int startY, Common::Rect searchRect) const {
- // If the starting point is walkable, just return that
- if (searchRect.contains(startX, startY) && isWalkable(startX, startY)) {
- return Common::Point(startX, startY);
- }
-
- int signs[] = { 1, -1 };
- const uint kSignsNum = 2;
-
- int radius = 0;
- int x, y;
- int dx, dy;
- int prediction;
+Common::Point WalkingMap::findNearestWalkable(int startX, int startY) const {
+ // The dimension of the screen.
+ const Common::Rect searchRect(0, 0, _realWidth, _realHeight);
- // The place where, eventually, the result coordinates will be stored
- int finalX, finalY;
+ // Consider circles with radii gradually rising from 0 to the length of
+ // the longest edge on the screen. For each radius, probe all points
+ // on the circle and return the first walkable one. Go through angles
+ // [0, 45 degrees] and probe all 8 reflections of each point.
+ for (int radius = 0; radius < searchRect.width() + searchRect.height(); radius += _deltaX) {
- // The algorithm appears to start off with an ellipse with the minor radius equal to
- // zero and the major radius equal to the walking map delta (the number of pixels
- // one map pixel represents). It then uses a heuristic to gradually reshape it into
- // a circle (by shortening the major radius and lengthening the minor one). At each
- // such resizing step, it checks some select points on the ellipse for walkability.
- // It also does the same check for the ellipse perpendicular to it (rotated by 90 degrees).
+ // The position of the point on the circle.
+ int x = 0;
+ int y = radius;
- while (1) {
- // The default major radius
- radius += _deltaX;
+ // Variables for computing the points on the circle
+ int prediction = 1 - radius;
+ int dx = 3;
+ int dy = 2 * radius - 2;
- // The ellipse radii (minor, major) that get resized
- x = 0;
- y = radius;
+ // Walk until we reach the 45-degree angle.
+ while (x <= y) {
- // Heuristic variables
- prediction = 1 - radius;
- dx = 3;
- dy = 2 * radius - 2;
+ // The place where, eventually, the result coordinates will be stored
+ Common::Point final;
- do {
- // The following two loops serve the purpose of checking the points on the two
- // ellipses for walkability. The signs[] array is there to obliterate the need
- // of writing out all combinations manually.
+ // Auxilliary array of multiplicative coefficients for reflecting points.
+ static const int kSigns[] = { 1, -1 };
- for (uint i = 0; i < kSignsNum; ++i) {
- finalY = startY + y * signs[i];
+ // Check all 8 reflections of the basic point.
+ for (uint i = 0; i < 2; ++i) {
+ final.y = startY + y * kSigns[i];
- for (uint j = 0; j < kSignsNum; ++j) {
- finalX = startX + x * signs[j];
+ for (uint j = 0; j < 2; ++j) {
+ final.x = startX + x * kSigns[j];
// If the current point is walkable, return it
- if (searchRect.contains(finalX, finalY) && isWalkable(finalX, finalY)) {
- return Common::Point(finalX, finalY);
+ if (searchRect.contains(final.x, final.y) && isWalkable(final)) {
+ return final;
}
}
}
+ for (uint i = 0; i < 2; ++i) {
+ final.y = startY + x * kSigns[i];
- if (x == y) {
- // If the starting point is walkable, just return that
- if (searchRect.contains(finalX, finalY) && isWalkable(finalX, finalY)) {
- return Common::Point(finalX, finalY);
- }
- }
-
- for (uint i = 0; i < kSignsNum; ++i) {
- finalY = startY + x * signs[i];
-
- for (uint j = 0; j < kSignsNum; ++j) {
- finalX = startX + y * signs[j];
+ for (uint j = 0; j < 2; ++j) {
+ final.x = startX + y * kSigns[j];
// If the current point is walkable, return it
- if (searchRect.contains(finalX, finalY) && isWalkable(finalX, finalY)) {
- return Common::Point(finalX, finalY);
+ if (searchRect.contains(final.x, final.y) && isWalkable(final)) {
+ return final;
}
}
}
- // If prediction is non-negative, we need to decrease the major radius of the
- // ellipse
+ // Walk along the circle to the next point: the
+ // X-coordinate moves to the right, and the
+ // Y-coordinate may move to the bottom if the predictor
+ // says so.
if (prediction >= 0) {
prediction -= dy;
dy -= 2 * _deltaX;
y -= _deltaX;
}
-
- // Increase the minor radius of the ellipse and update heuristic variables
prediction += dx;
dx += 2 * _deltaX;
x += _deltaX;
-
- // If the current ellipse has been reshaped into a circle,
- // end this loop and enlarge the radius
- } while (x <= y);
+ }
}
+
+ // The destination point is unreachable.
+ return Common::Point(-1, -1);
}
// We don't use Common::Point due to using static initialization.
-int WalkingMap::kDirections[][2] = { {0, -1}, {0, +1}, {-1, 0}, {+1, 0} };
+const int WalkingMap::kDirections[][2] = { {0, -1}, {0, +1}, {-1, 0}, {+1, 0} };
bool WalkingMap::findShortestPath(Common::Point p1, Common::Point p2, WalkingPath *path) const {
// Round the positions to map squares.
@@ -632,6 +607,11 @@ bool WalkingState::turnForTheNextSegment() {
void WalkingState::heroAnimationFinished() {
debugC(2, kDraciWalkingDebugLevel, "Turning callback called");
_turningFinished = true;
+
+ // We don't need to clear the callback to safer doNothing, because
+ // nobody ever plays this animation directly. It is only played by
+ // turnForTheNextSegment() and then the same callback needs to be
+ // activated again.
}
bool WalkingState::walkOnNextEdge() {
@@ -648,8 +628,6 @@ bool WalkingState::walkOnNextEdge() {
Movement nextAnim = directionForNextPhase();
_lastAnimPhase = _vm->_game->playHeroAnimation(nextAnim);
- // TODO: do we need to clear the callback for the turning animation?
-
debugC(2, kDraciWalkingDebugLevel, "Turned for edge %d, starting animation %d with phase %d", _segment, nextAnim, _lastAnimPhase);
if (++_segment < _path.size()) {
diff --git a/engines/draci/walking.h b/engines/draci/walking.h
index eb165b2c6f..e21ed710b8 100644
--- a/engines/draci/walking.h
+++ b/engines/draci/walking.h
@@ -43,10 +43,10 @@ public:
void load(const byte *data, uint length);
bool getPixel(int x, int y) const;
- bool isWalkable(int x, int y) const;
+ bool isWalkable(const Common::Point &p) const;
Sprite *newOverlayFromMap(byte colour) const;
- Common::Point findNearestWalkable(int x, int y, Common::Rect searchRect) const;
+ Common::Point findNearestWalkable(int x, int y) const;
bool findShortestPath(Common::Point p1, Common::Point p2, WalkingPath *path) const;
void obliquePath(const WalkingPath& path, WalkingPath *obliquedPath);
@@ -66,7 +66,7 @@ private:
const byte *_data;
// 4 possible directions to walk from a pixel.
- static int kDirections[][2];
+ static const int kDirections[][2];
void drawOverlayRectangle(const Common::Point &p, byte colour, byte *buf) const;
bool lineIsCovered(const Common::Point &p1, const Common::Point &p2) const;