[Scummvm-tracker] [ScummVM] #10858: QFG4: Pathfinding in forest 1S from town, south entry

[ScummVM]

#10858: QFG4: Pathfinding in forest 1S from town, south entry
--------------------------------+-------------------------
  Reporter:  tomasz89           |      Owner:  (none)
      Type:  defect             |     Status:  new
  Priority:  normal             |  Component:  Engine: SCI
Resolution:                     |   Keywords:  SCI32
      Game:  Quest for Glory 4  |
--------------------------------+-------------------------

Comment (by Vhati):

 The SW poly represents a stream and bush that extends across the center of
 the screen.

 ScummVM's pathfinding *REALLY* doesn't want to make the sharp turn around
 that point at the end.
 \\
 \\
 I tried moving the point left, so the angle wouldn't be so acute. I tried
 moving the polygon up, away from the edge. No luck.
 \\
 \\
 Finally, I looked at the pathfinding code.

 [https://github.com/scummvm/scummvm/blob/df74a209ca8496f08283285337181ea73a69b78f/engines/sci/engine/kpathing.cpp#L1400
 Source]: kpathing.cpp - AStar()
 {{{
 new_dist = vertex_min->costG +
 (uint32)sqrt((float)vertex_min->v.sqrDist(vertex->v));

 // When travelling to a vertex on the screen edge, we
 // add a penalty score to make this path less appealing.
 // NOTE: If an obstacle has only one vertex on a screen edge,
 // later SSCI pathfinders will treat that vertex like any
 // other, while we apply a penalty to paths traversing it.
 // This difference might lead to problems, but none are
 // known at the time of writing.

 // WORKAROUND: This check fails in QFG1VGA, room 81 (bug report #3568452).
 // However, it is needed in other SCI1.1 games, such as LB2. Therefore, we
 // add this workaround for that scene in QFG1VGA, until our algorithm
 matches
 // better what SSCI is doing. With this workaround, QFG1VGA no longer
 freezes
 // in that scene.
 bool qfg1VgaWorkaround = (g_sci->getGameId() == GID_QFG1VGA &&
 g_sci->getEngineState()->currentRoomNumber() == 81);

 if (s->pointOnScreenBorder(vertex->v) && !qfg1VgaWorkaround)
         new_dist += 10000;
 }}}
 \\
 \\
 Speculation: Hero is starting off-screen and needs to stop at that point
 on the edge to pivot. ScummVM penalizes routes with that waypoint. Hero
 instead passes *through* the point in a straight line... to some arbitrary
 spot on the screen... then navigates to the destination from there.
 \\
 \\
 When I added a QFG4 exemption for this room, hero entered properly.

-- 
Ticket URL: <https://bugs.scummvm.org/ticket/10858#comment:5>
ScummVM <https://bugs.scummvm.org>
ScummVM