Opened 15 years ago

Closed 15 years ago

Last modified 15 years ago

#1864 closed defect (fixed)

FT: Incorrect actor drawing order

Reported by: salty-horse Owned by: cyxx
Priority: normal Component: Engine: SCUMM
Keywords: Cc:
Game: Full Throttle

Description

During the Corley murder sequence, Miranda is drawn
behind Ripburger. She should be drawn in front of him.
See included screenshots.

I am using current CVS, with the english talkie version
B of the game, on Win32

Steps to reproduce:
1) Load FT with bootparam 400
2) Wait until you reach the room in the picture (room
33), where Miranda is struggling to get free.

Analysis:
Looking at the room script for room 31, which directs
the sequence:

[0849] (9D) actorOps.setCurActor(6)
[084E] (9D) actorOps.setCostume(0)

Miranda is actor 6.
Since she has no costume, ScummEngine::processActors()
in scumm/actor.cpp doesn't include her in the actor
array, and doesn't sort the draw order.
It's worthy to note that the "actors" debug command
shows her data since she's in the room.

Her y-value is lower than Ripburger's.

Adding costume=0 actors to the array isn't so trivial
because there are some costume functions called
afterwards that assert on costume 0.

Ticket imported from: #1093867. Ticket imported from: bugs/1864.

Attachments (4)

actors-original.png (12.3 KB ) - added by salty-horse 15 years ago.
Taken from original interpreter
actors-scummvm.png (29.7 KB ) - added by salty-horse 15 years ago.
Taken from ScummVM
ft_1093867.diff (1.6 KB ) - added by cyxx 15 years ago.
ft_processActors.txt (2.5 KB ) - added by cyxx 15 years ago.

Download all attachments as: .zip

Change History (19)

by salty-horse, 15 years ago

Attachment: actors-original.png added

Taken from original interpreter

comment:1 by salty-horse, 15 years ago

Component: Engine: SCUMM
Game: Full Throttle

by salty-horse, 15 years ago

Attachment: actors-scummvm.png added

Taken from ScummVM

comment:2 by fingolfin, 15 years ago

Well, yeah... costume 0 ordinarily means: "don't draw anything".
So, yes, Miranda doesn't get sorted. I don't quite see your
point, though -- even if we sorted her, she isn't drawn that way,
so it doesn't matter.

Actor 6 is only placed for the sake of the voice over text. The
animation of Miranda is really a part of actor 2.

Both actor 2 and actor 4 (ripburger) have the same position
(135,199) and the same elevation (0), and hence they are drawn in
the order determined by their actor IDs, which in this case
causes the wrong thing to happen.

I haven't yet looked into the reasons of that, though. Maybe in
FT the actors should actually be drawn "the other way around",
i.e. from highest number to lowest? That would also fix bug
#775097, but is a pure guess, and if wrong, would likely cause
many other regressions. Best to verify this with disassembly, I
guess.

comment:3 by SF/benshadwick, 15 years ago

I'm using the 0.8.0CVS Feb 20 2005 11:25:04 Win32 daily
build, and I just noticed the same problem. Game files are
from the PC DOS CD-ROM version (I don't think there is a
floppy version - just a Mac version AFAIK); I haven't tested
with the official SCUMM interpreter included with the game
to see how it behaves in this scene of the game.

I have a save file near this part of the game, but
apparently I can't attach files to existing bug reports (?).
I guess anyone who is interested will have to email me or
whatever.

fingolfin: If ScummVM is drawing the actors in the opposite
order from the way they're suposed to, wouldn't the problem
be a lot more noticable? Maybe overlapping actors don't
occur as much as I'd expect.

Also, I see the following actor data in the debug console:
2: x=135, y=199, w=24, elev=0, cos=139, box=0, mov=0, zp=0,
frm=6, scl=255, dir=180, cls=$00
4: x=135, y=199, w=24, elev=0, cos=140, box=0, mov=0, zp=0,
frm=1, scl=255, dir=180, cls=$00
6: x=119, y=188, w=24, elev=0, cos=0, box=1, mov=0, zp=100,
frm=5, scl=255, dir=180, cls=$00

What is the frm attribute for? I don't know anything about
SCUMM :) Perhaps a different ordering on actor #, costume #,
and/or "frm" is required?

In any case, someone should probably verify that this "bug"
only occurs in ScummVM and not the official SCUMM version
bundled with this game.

comment:4 by cyxx, 15 years ago

I checked disassembly of processActors in FT and there are
some "interesting" side effects. There are two differences
with the scummvm implementation :
- the original doesn't exclude actors without a costume in
the first loop
- the original uses bubble sort to perform the actual sorting

So, in this sequence, under scummvm, at the end of the first
loop, we have :
_sortedActors[0] == &_actor[2] (y=199 layer=0)
_sortedActors[1] == &_actor[4] (y=199 layer=0)

The qsort() doesn't do anything as both actors have the same
y coordinate and the same layer. So the drawing order is :
_actor[2].drawActorCostume
_actor[4].drawActorCostume

... which leads to the glitch described here.

If we execute the processActors of the original, we have at
the end of the first loop :
_sortedActors[0] == &_actor[2] (y=199 layer=0)
_sortedActors[1] == &_actor[4] (y=199 layer=0)
_sortedActors[2] == &_actor[6] (y=188 layer=0 no costume)

After that, the bubble sort:
end of loop 1:
_sortedActors[0] == &_actors[2]
_sortedActors[1] == &_actors[4]
_sortedActors[2] == &_actors[6]

end of loop 2:
_sortedActors[0] == &_actors[2]
_sortedActors[1] == &_actors[4]
_sortedActors[2] == &_actors[6]

end of loop 3:
_sortedActors[0] == &_actors[6] // has the lower y
coordinate, hence moving to the beginning and because of the
algorithm used, 4 and 2 are swapped too
_sortedActors[1] == &_actors[4]
_sortedActors[2] == &_actors[2]

The drawing order ends with :
_actor[6].drawActorCostume (will be skipped, no costume)
_actor[4].drawActorCostume
_actor[2].drawActorCostume

... which draw the actors correctly for the sequence.

I hope I have been clear :/.
So, what how can we fix that ? To me, I don't see a way to
"emulate" with our qsort() method. Maybe we could just get
rid of the qsort() thing and switch the "method" used by the
original interpreters (we'll have to verify this) ? I know
bubble sort is the worst sorting algorithm but afterall,
there aren't that much actors, aren't they ?

Anyway, this is not the kind of thing we should get
committed as-is... So if anybody as remarks...

To finish, I've attached a patch which implement the
original method.

by cyxx, 15 years ago

Attachment: ft_1093867.diff added

by cyxx, 15 years ago

Attachment: ft_processActors.txt added

comment:5 by fingolfin, 15 years ago

Bubble sort is a stable sort -- so whatever algorithm you implemented
there, it can't be bubble sort if it does behave in the way you described
here.

In particular, we have code in compareDrawOrder() to ensure a stable sort
even when using qsort (which in the C spec is not guranteed to be stable,
and indeed, if it is implemented via quicksort, isn't stable; although many
C libs these days use another algorithm). That was added to fix bug
#758167. So before anything is changed, at the very least, the problem
described in that older bug should be re-checked.

comment:6 by fingolfin, 15 years ago

Oh and of course also bug #775097 would need to be rechecked. And
compareDrawOrder() would be removed.

comment:7 by cyxx, 15 years ago

Indeed, this isn't bubble sort... But anyway, you get my
point :). And sure, compareDrawOrder() can be removed ; I
just patched this quickly.

I checked bug #758167 with the 'new' processActors()
function and I haven't noticed any glitches. Dumping the
drawing order here gives :

_actor[8].drawActorCostume y=48
_actor[4].drawActorCostume y=167
_actor[2].drawActorCostume y=170
_actor[10].drawActorCostume y=170
_actor[3].drawActorCostume y=173
_actor[7].drawActorCostume y=208
_actor[9].drawActorCostume y=221

... which seems ok.

As of bug #775097, I don't have an english talkie of DOTT,
so I can't test. It would be nice if someone could do it.
But by looking at the processActors() disassembly attached
to that bug report, it seems the sort algorithm used in DOTT
is very similar (if not identical if you ignore the _layer
field) to the one used in FT.

It may be nice to check the processActors() of other games
too, to prevent 'future' bug reports... For example, looking
at revision 1.121 of actor.cpp, I see that the sorting was
achieved slightly differently.

comment:8 by cyxx, 15 years ago

I just checked COMI disasm. The processActors() is very
similar to FT. In fact, the only difference, if you don't
take into account the layer < 0 thing, is that actors
without costume are excluded in the first loop (as it is in
scummvm now...).

comment:9 by fingolfin, 15 years ago

Owner: set to cyxx

comment:10 by fingolfin, 15 years ago

I just checked Monkey Island EGA -- it also uses the same
sorting method you employ, and not the one found in older
versions of actor.cpp
For reference, your code does this (pseudo code):
for i = 0...numActors do
for j = 0..numActors do
if (a[i] < a[j]) swap(a[i],a[j])

This is precisely what MI EGA does, and also what the
earliest versions of ScummVM did (which were based on MI2).
At a later point this was optimized by various people,
including me. At one point it looked like this:

for i = 0...numActors do
for j = 0..i do
if (a[i] < a[j]) swap(a[i],a[j])

And then later was changed to use qsort.

Well, what we didn't realize was that apparently quite some
games rely on this particular sorting algorithm in subtle
ways (and I am pretty sure the game authors didn't really
realize this either ;-)

Furthermore, all versions of the code I checked also include
actors w/o a costume in the list, and only filter them in
the drawing phase, just like your patch does.

As a conclusion, I think what your patch does is exactly
what is "correct". So please commit it (after cleaning it
up, of course). You might want to include a comment which
explains that the algorithm has to stay and shouldn't be
"optimized" again by anybody (maybe also include the various
bug numbers in the comment). Or, if you prefer, I can do it.

comment:11 by fingolfin, 15 years ago

To correct myself, the second form of the sorting code used to be like this:

for j = numActors..0 do
for i = 0..j do
if (a[i] > a[i+1]) swap(a[i],a[i+1])

Not that it really matters, it was wrong anyway :-)

comment:12 by cyxx, 15 years ago

Yeah, I also think the game authors weren't aware of the
side effects caused by this particular algorithm.

And as you suggest, I would prefer that you commit it. I am
sure you'll be able to write a better comment for it than me :)

comment:13 by fingolfin, 15 years ago

OK, done. Good work, cyx.

One question:
a[j]->_pos.y - a[j]->_layer * 2000;
-> where is that "* 2000" bit from ? Looking at the asm code you attached,
I interpret it as:
a[j]->_pos.y - a[j]->_layer;
Either I interpret the asm wrong; or their layer value differs from ours
(maybe the premultiply it); or your translation is wrong?
Also, in old revisions of actor.cpp, we did something similiar, only we didn't
multiply by 2000 but rather shifted left by 11 (i.e. multiplied by 2048).

comment:14 by fingolfin, 15 years ago

Resolution: fixed
Status: newclosed

comment:15 by cyxx, 15 years ago

The _layer field of the actor is multiplied by 2000 in
subopcode 227 of o6_actorOps in FT_disasm :

case_227: ; CODE XREF: o_actorSet+5Dj
call pop
imul edx, eax, 2000
mov eax, _curActor
mov actor_layer[eax*4], edx

Here is where it comes from.

Note: See TracTickets for help on using tickets.