aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--engines/draci/game.cpp19
-rw-r--r--engines/draci/game.h6
-rw-r--r--engines/draci/walking.cpp92
-rw-r--r--engines/draci/walking.h26
4 files changed, 102 insertions, 41 deletions
diff --git a/engines/draci/game.cpp b/engines/draci/game.cpp
index 079e2ebb55..3aad401ca2 100644
--- a/engines/draci/game.cpp
+++ b/engines/draci/game.cpp
@@ -950,7 +950,7 @@ void Game::playHeroAnimation(int anim_index) {
_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 @@ void Game::walkHero(int x, int y, SightDirection dir) {
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 @@ void Game::walkHero(int x, int y, SightDirection dir) {
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 @@ void Game::loadRoom(int roomNum) {
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);
diff --git a/engines/draci/game.h b/engines/draci/game.h
index 22f0bdf67f..670bb4bb01 100644
--- a/engines/draci/game.h
+++ b/engines/draci/game.h
@@ -329,7 +329,7 @@ private:
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 @@ private:
bool _inventoryExit;
Room _currentRoom;
- WalkingMap _walkingMap;
int _newRoom;
int _newGate;
int _previousRoom;
@@ -394,6 +393,9 @@ private:
bool _enableQuickHero;
bool _wantQuickHero;
bool _enableSpeedText;
+
+ WalkingMap _walkingMap;
+ WalkingState _walkingState;
};
} // End of namespace Draci
diff --git a/engines/draci/walking.cpp b/engines/draci/walking.cpp
index 5d48efabe6..8b748fcd6d 100644
--- a/engines/draci/walking.cpp
+++ b/engines/draci/walking.cpp
@@ -65,7 +65,7 @@ Sprite *WalkingMap::newOverlayFromMap(byte colour) const {
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 @@ Common::Point WalkingMap::findNearestWalkable(int startX, int startY, Common::Re
// 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 @@ bool WalkingMap::findShortestPath(Common::Point p1, Common::Point p2, Path *path
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 @@ void WalkingMap::obliquePath(const WalkingMap::Path& path, WalkingMap::Path *obl
// 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 @@ Sprite *WalkingMap::newOverlayFromPath(const WalkingMap::Path &path, byte colour
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 @@ Sprite *WalkingMap::newOverlayFromPath(const WalkingMap::Path &path, byte colour
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;
+}
+
}
diff --git a/engines/draci/walking.h b/engines/draci/walking.h
index 73030e79b8..07b0d3940c 100644
--- a/engines/draci/walking.h
+++ b/engines/draci/walking.h
@@ -33,6 +33,8 @@ namespace Draci {
class Sprite;
+typedef Common::Array<Common::Point> WalkingPath;
+
class WalkingMap {
public:
WalkingMap() : _realWidth(0), _realHeight(0), _deltaX(1), _deltaY(1),
@@ -46,10 +48,9 @@ public:
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 @@ private:
// 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 @@ enum Movement {
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
generated by cgit v1.2.3 (git 2.25.1) at 2024-09-30 17:05:33 +0000