diff options
| -rw-r--r-- | engines/draci/walking.cpp | 105 | ||||
| -rw-r--r-- | engines/draci/walking.h | 3 |
2 files changed, 61 insertions, 47 deletions
diff --git a/engines/draci/walking.cpp b/engines/draci/walking.cpp index 8b748fcd6d..372901e5f7 100644 --- a/engines/draci/walking.cpp +++ b/engines/draci/walking.cpp @@ -303,53 +303,10 @@ void WalkingMap::obliquePath(const WalkingPath& path, WalkingPath *obliquedPath) } } - // 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. 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 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 (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); - } - } + // Repeatedly oblique the path until it cannot be improved. This + // process is finite, because after each success the number of vertices + // goes down. + while (managedToOblique(obliquedPath)) {} } Sprite *WalkingMap::newOverlayFromPath(const WalkingPath &path, byte colour) const { @@ -409,4 +366,58 @@ bool WalkingMap::lineIsCovered(const Common::Point &p1, const Common::Point &p2) return true; } +bool WalkingMap::managedToOblique(WalkingPath *path) const { + bool improved = false; + + // 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. 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 < path->size(); ++head) { + const Common::Point &v1 = (*path)[head-2]; + const Common::Point &v2 = (*path)[head-1]; + const Common::Point &v3 = (*path)[head]; + 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 (first12 == 0) { + // Can completely remove the vertex. Head stays the + // same after -- and ++. + path->remove_at(--head); + improved = true; + 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. + (*path)[head-1] = interpolate(v1, v2, first12, points12); + // After replacing the 2nd vertex, let head move on. + } else if (first32 < points32) { + (*path)[head-1] = interpolate(v3, v2, first32, points32); + } + } + return improved; +} + } diff --git a/engines/draci/walking.h b/engines/draci/walking.h index 07b0d3940c..247f57b4c9 100644 --- a/engines/draci/walking.h +++ b/engines/draci/walking.h @@ -68,6 +68,9 @@ private: 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; + + // Returns true if the number of vertices on the path was decreased. + bool managedToOblique(WalkingPath *path) const; }; /* |