Opened 8 years ago

Last modified 6 years ago

#7155 new defect

SCI: Differences in the pathfinding algorithm

Reported by: SF/boneosaurusrex Owned by:
Priority: normal Component: Engine: SCI
Version: Keywords: pathfinding has-pull-request
Cc: Game: Space Quest 5


When entering (returning to) the goliath drive bay room from the hallway room, clicking Walk almost anywhere causes Roger to walk halfway down the platform then turn around and automatically leave the room, returning to the hallway room. This only happens in ScummVM, walking behaves as expected in the original game.

To reproduce, enter the drive bay room from the hallway. Click Walk on the lower left platform. Roger will start to walk towards it but around the halfway point the hallway door will open and Roger will turn around and walk back and leave through it. The expected result is that Roger will just walk down the platform. It's possible to work around this by clicking Walk just barely in front of Roger and continue doing that to advance down the platform, but that took a lot of trial and error to figure out. The hallway door normally only opens as soon as Roger walks up to it or an enemy guard enters the room.

I don't know if this is relevant but in both the original and ScummVM if you enter the drive bay room through the hallway and just stand there and wait, the enemy guard enters the room behind you, walks through you, does his sweep and leaves through you again without detecting you. So... this room has edge cases.

Attached are save games from SQ5 1.04 English using ScummVM nightly and dosbox. Both of them are in the hallway with Roger standing next to the door to the drive room.

Ticket imported from: bugs/7155.

Attachments (3)

SQ5SG.003 (9.6 KB ) - added by SF/boneosaurusrex 8 years ago.
sq5.010 (41.8 KB ) - added by SF/boneosaurusrex 8 years ago.
sq5.096 (41.4 KB ) - added by SF/captainjei 8 years ago.

Download all attachments as: .zip

Change History (14)

by SF/boneosaurusrex, 8 years ago

Attachment: sq5.010 added

comment:1 by m-kiewitz, 8 years ago

This may be a pathfinding issue. We do not use the exact pathfinding algo that Sierra used because of patent issues.

by SF/captainjei, 8 years ago

Attachment: sq5.096 added

comment:2 by SF/captainjei, 8 years ago

I'm experiencing a walking bug in the Space Bar. I try to go into the brig area, and Roger just stops at the edge of the screen, and I'm unable to progress in the game. I'll attach a save.

comment:3 by SF/captainjei, 8 years ago

I'm going to open a separate ticket for the Space Bar issue since I'm not positive it's related.

comment:4 by dafioram, 7 years ago

Keywords: pathfinding added

comment:5 by sluicebox, 6 years ago

Script patch:

This issue is due to the pathfinding algorithm differences. Adjusting ego's initial position by a few pixels works around the problem.

comment:6 by m-kiewitz, 6 years ago

I don't really like patching things like this out.
The actual problem here as you have also said is the pathfinding algo.

I'm on my way rewriting that plus making it so that it actually works like the original.
It's rather time consuming and complicated, so it will take some time.

Originally another algo was used because of patent infringement (and that algo is primarily from FreeSCI - really interesting if you want to read about it - see ).

comment:7 by sluicebox, 6 years ago

That's great news that the pathfinding rewrite is in progress. Sounds hard! I guess the question is how long that will take. Right now navigation in this room is pretty difficult and this patch, along with the existing pathfinding workarounds, can just be removed once new pathfinding is in place.

comment:8 by m-kiewitz, 6 years ago

Hmmmm, okay.

But this bug definitely must NOT be closed.
It must stay open, otherwise we may miss it.

Please add the following to the script patch documentation:

WORKAROUND: Should only be needed until pathfinding algorithm has been rewritten.
Should be removed when this has taken place.

comment:9 by bluegr, 6 years ago

I agree witm m_kiewitz. We should use the script patch as a workaround, and then remove it, together with many more script patches like this one, once we have a pathfinding implementation that is like what SSCI did.

I remember that wjp was looking into Sierra’s pathfinding algorithm some time ago, when he was working on MergePoly, but I can’t find any relevant branch in his scummvm git fork

comment:10 by digitall, 6 years ago

Keywords: has-pull-request added

comment:11 by bluegr, 6 years ago

Summary: SCI: SQ5: Walking bug in Goliath Drive BaySCI: Differences in the pathfinding algorithm

I've added the patch for this, together with the other pathfinding related pull requests, and will mark these and any other pathfinding related script patches we already have as workarounds.

I'll keep this bug open, so that it won't be forgotten, until the SCI pathfinding algorithm is rewritten.

comment:12 by sluicebox, 6 years ago

How would you like future scummvm sci pathfinding bugs reported? Separate issues or added onto this one?

I tripped a Longbow one where the scummvm pathfinding sends ego backwards into an obstacle and locks up the game. It's not a scene that occurs unless you're playing badly, or accidentally click in the wrong spot like I did, so I don't think it's worth a temporary workaround. It will make a good test case though for testing your new pathfinding. I'm so happy to hear that's a work in progress!

Note: See TracTickets for help on using tickets.