Opened 5 years ago

Closed 5 years ago

Last modified 5 years ago

#10858 closed defect (fixed)

QFG4: Pathfinding in forest 1S from town, south entry

Reported by: tomasz89 Owned by: bluegr
Priority: normal Component: Engine: SCI
Version: Keywords: SCI32 has-pull-request
Cc: Game: Quest for Glory 4


The room south of town has an odd pathing route when entering from south; the Hero walks NE then SW rather than simply entering the room.

Attachments (3)

qfg4-cd-gog.018 (88.5 KB ) - added by tomasz89 5 years ago.
Polygons - Room 563.png (42.4 KB ) - added by Vhati 5 years ago.
Polygon - Room 563 Bush.png (39.3 KB ) - added by Vhati 5 years ago.

Download all attachments as: .zip

Change History (12)

by tomasz89, 5 years ago

Attachment: qfg4-cd-gog.018 added

comment:1 by Vhati, 5 years ago

Room 563, 1S from town entrance

  • Entering from south (564) is handled by enterRoomScr in script 50.

script 563 - rm563::init()

(self setRegions: 50)

That Room method invokes forest::init() in script 50, which schedules enterRoomScr on the room.

by Vhati, 5 years ago

Attachment: Polygons - Room 563.png added

comment:2 by Vhati, 5 years ago

I can reproduce this in both CD and floppy editions under ScummVM.
It does not occur in the original interpreters.

Or rather, under ScummVM, hero makes a much wider turn when running around the bush.

QFG4 CD (English)

File - 5kb MD5 - Full MD5
RESOURCE.000 - 263dce4aa34c49d3ad29bec889007b1c - 1364ba69e3c0abb68cc0170650a56692
RESOURCE.AUD - c39521bffb1d8b19a57394866184a0ca - 71098b9e97e20c8941c0e4812d5f906f
RESOURCE.MAP - aba367f2102e81782d961b14fbe3d630 - 801a04cc6aa5d437681a2dd0b6545248
RESOURCE.SFX - 3cf95e09dab8b11d675e0537e18b499a - 7c858d7253f86dab4cc6066013c5ecec

QFG4 Floppy 1.1a + note patch (English)

File - 5kb MD5 - Full MD5
RESOURCE.000 - f64fd6aa3977939a86ff30783dd677e1 - ff42260a665995a85aeb277ad80aac8a
RESOURCE.MAP - d10a4cc177d2091d744e2ad8c049b0ae - 3695b1b0a1d15f3d324ea9f0cc325245
RESOURCE.SFX - 3cf95e09dab8b11d675e0537e18b499a - 7c858d7253f86dab4cc6066013c5ecec

comment:3 by Vhati, 5 years ago

Keywords: SCI32 added
Summary: QFG4 path north results in walking NE then SWQFG4: Pathfinding in forest 1S from town, south entry

comment:4 by Vhati, 5 years ago

From the hand decompiled code attached to #10857...

script 50 - forest::init()

(switch myPrevRoomNum
# ...
	((g2_myCurrentRoom south?)
		(g0_hero posn: 160 240 setHeading: 0)
		(= loc1 160)
		(= loc2
				(if g365_myFoeScriptNum 1 else 21)
		(g2_myCurrentRoom setScript: enterRoomScr)
# ...

loc1 and loc2 are x,y coords that hero is moved to by enterRoomScr::changeState(1).

In this case, hero starts at (160,240) and is sent to (160,161).

Last edited 5 years ago by Vhati (previous) (diff)

by Vhati, 5 years ago

Attachment: Polygon - Room 563 Bush.png added

comment:5 by Vhati, 5 years ago

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.

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;

(Modern ticket number for the QFG1VGA bug is #6140.)

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.

Last edited 5 years ago by Vhati (previous) (diff)

comment:6 by Vhati, 5 years ago

Keywords: has-pull-request added

Pull Request: SCI32: Fix QFG4 forest pathfinding

comment:7 by bluegr, 5 years ago

Owner: set to bluegr
Resolution: fixed
Status: newclosed

comment:8 by Filippos Karapetis <bluegr@…>, 5 years ago

In aac5ed1c:

SCI32: Fix QFG4 forest pathfinding

Adds workarounds for odd detours during entry, bugs #10857, #10858

comment:9 by tomasz89, 5 years ago

Confirmed fixed.

Note: See TracTickets for help on using tickets.