diff options
-rw-r--r-- | engines/draci/game.cpp | 10 | ||||
-rw-r--r-- | engines/draci/game.h | 2 | ||||
-rw-r--r-- | engines/draci/walking.cpp | 122 | ||||
-rw-r--r-- | engines/draci/walking.h | 6 |
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; |