Opened 8 years ago

Last modified 6 years ago

#7140 new defect

SCI: QFG3 - Incorrect Keyboard Movement

Reported by: OmerMor Owned by:
Priority: normal Component: Engine: SCI
Version: Keywords: pathfinding
Cc: Game: Quest for Glory 3

Description

ScummVM version: ScummVM 1.9.0git1868-gd35cdf5 (May 19 2016 09:14:40) Features compiled in: TAINTED Vorbis FLAC MP3 RGB zLib MPEG2 FluidSynth Theora AAC FreeType2 JPEG PNG

Details: In QFG3 (anthology version, English, no patches), room 750, when standing in the middle of the upper bridge, moving the character via the keyboard behaves incorrectly: Pressing the LEFT key moves the hero to the right.

In SSCI, the LEFT key moves the hero to the left, as expected.

Attaching save games for ScummVM and SSCI.

Plaftorm: Windows 10

Ticket imported from: bugs/7140.

Attachments (3)

GLORYSG.000​ (8.8 KB ) - added by OmerMor 8 years ago.
GLORYSG.DIR​ (18 bytes ) - added by OmerMor 8 years ago.
qfg3-vanilla.001​ (37.4 KB ) - added by OmerMor 8 years ago.

Download all attachments as: .zip

Change History (8)

by OmerMor, 8 years ago

Attachment: GLORYSG.DIR​ added

comment:1 by OmerMor, 8 years ago

Maybe this could help: When enabling Pathfinding debugflag, we get this output upon pressing the LEFT key:

[avoidpath] Pathfinding input: Start point: (218, 27) End point: (-31782, 27) Optimization level: 0 Polygons: 3: (262, 189) (272, 175) (265, 159) (235, 159) (221, 156) (201, 161) (191, 172) (128, 169) (38, 170) (64, 160) (137, 86) (127, 77) (135, 70) (164, 67) (184, 66) (204, 69) (224, 78) (228, 76) (187, 56) (133, 66) (116, 80) (128, 84) (57, 156) (32, 164) (21, 154) (48, 141) (33, 131) (57, 126) (0, 120) (0, 189) (262, 189); 3: (319, 88) (306, 85) (310, 74) (292, 70) (270, 69) (246, 78) (298, 78) (304, 81) (291, 90) (319, 90) (319, 88); 3: (319, 32) (282, 26) (204, 27) (183, 19) (135, 1) (130, 9) (202, 30) (284, 30) (319, 43) (319, 32);

Returning path: (218, 27) (284, 30);

The same problem also occurs when standing in the middle of the bottom plane (with the grass) and pressing the RIGHT key (the hero goes left):

[avoidpath] Pathfinding input: Start point: (127, 179) End point: (10793, 179) Optimization level: 0 Polygons: 3: (262, 189) (272, 175) (265, 159) (235, 159) (221, 156) (201, 161) (191, 172) (128, 169) (38, 170) (64, 160) (137, 86) (127, 77) (135, 70) (164, 67) (184, 66) (204, 69) (224, 78) (228, 76) (187, 56) (133, 66) (116, 80) (128, 84) (57, 156) (32, 164) (21, 154) (48, 141) (33, 131) (57, 126) (0, 120) (0, 189) (262, 189); 3: (319, 88) (306, 85) (310, 74) (292, 70) (270, 69) (246, 78) (298, 78) (304, 81) (291, 90) (319, 90) (319, 88); 3: (319, 32) (282, 26) (204, 27) (183, 19) (135, 1) (130, 9) (202, 30) (284, 30) (319, 43) (319, 32);

Returning path: (127, 179) (0, 179);

comment:2 by OmerMor, 8 years ago

I have a suspicion the problem has to with polygons of type POLY_CONTAINED_ACCESS (3).

I managed to reproduce this behavior also in room 380, when pressing LEFT (hero goes upper-left):

[avoidpath] Pathfinding input: Start point: (204, 135) End point: (-10462, 135) Optimization level: 0 Polygons: 3: (0, 92) (85, 92) (81, 103) (60, 109) (70, 115) (70, 136) (140, 179) (177, 184) (251, 184) (293, 152) (232, 110) (141, 96) (133, 87) (178, 80) (178, 76) (227, 76) (263, 69) (287, 71) (319, 53) (319, 1) (0, 1) (0, 92);

Returning path: (204, 135) (146, 97) (141, 96) (0, 1);

comment:3 by OmerMor, 8 years ago

I found that fixup_end_point() changes the endpoint from (-31782, 27) to (284, 30) which flips the direction from the hero's left to the hero's right side (the hero is at (233, 30)).

After this change it's clear why the pathfinding algorithm finds a path that moves the hero to the right. Still need to figure what goes wrong in fixup_end_point().

comment:4 by OmerMor, 8 years ago

Further analysis:

I've got this backtrace: 

    scummvm.exe!Common::Point::sqrDist(const Common::Point & p) Line 64 C++
    scummvm.exe!Sci::PathfindingState::findNearPoint(const Common::Point & p, Sci::Polygon * polygon, Common::Point * ret) Line 796 C++
    scummvm.exe!Sci::fixup_end_point(Sci::PathfindingState * s, const Common::Point & end) Line 1032    C++
    scummvm.exe!Sci::convert_polygon_set(Sci::EngineState * s, Sci::reg_t poly_list, Common::Point start, Common::Point end, int width, int height, int opt) Line 1234  C++

The end point is very far the to west (-31,782). // explain why fixup_end_point() tries to fix it to the closest point in the containing POLY_CONTAINED_ACCESS polygon. It does that in PathfindingState::findNearPoint() by iterating on the polygon's points and calculating comparing distances via Point::sqrDist(). The problem is that Point::sqrDist() only supports distance in each axis up to 4,096 (0x1000), When the distance is longer, it returns a constant 0xFFFFFF. As a consequence, the iteration in PathfindingState::findNearPoint() always calculates the same sqrDist from the end point, so the point it chooses is not the one with the minimal distance, but the ones that it happened to compare first with.

I don't know why Point::sqrDist() has these limits, but I'll try to find out.

comment:5 by OmerMor, 8 years ago

Following a discussion with waltervn, here's what we concluded: 1. Calling kAvoidPath due to keyboard event should not result in real pathfinding: it is called with optimizing level of 0, which means it should simply return a direct path until an obstacle is hit. This means fixup_end_point probaly should not be called in this case. Assuming this is correct - then this is the root cause of the bug. 2. Point::sqrDist() is capping the distance, and it's hard to tell why. This function goes back to the initial scummvm commit by Ludvig Strigeus from 2001. However since it's not the root cause - its not clear whether it should be fixed.

comment:6 by dafioram, 7 years ago

Keywords: pathfinding added
Summary: SCI: QFG3 - Incorrect Keyboard Movement → SCI: QFG3 - Incorrect Keyboard Movement
Note: See TracTickets for help on using tickets.