Opened 19 years ago

Closed 19 years ago

Last modified 19 years ago

#1864 closed defect (fixed)

FT: Incorrect actor drawing order

Reported by: salty-horse Owned by: cyxx
Priority: normal Component: Engine: SCUMM
Version: 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 19 years ago.
Taken from original interpreter
actors-scummvm.png (29.7 KB ) - added by salty-horse 19 years ago.
Taken from ScummVM
ft_1093867.diff (1.6 KB ) - added by cyxx 19 years ago.
ft_processActors.txt (2.5 KB ) - added by cyxx 19 years ago.

Download all attachments as: .zip

Change History (19)

by salty-horse, 19 years ago

Attachment: actors-original.png added

Taken from original interpreter

comment:1 by salty-horse, 19 years ago

Component: Engine: SCUMM
Game: Full Throttle

by salty-horse, 19 years ago

Attachment: actors-scummvm.png added

Taken from ScummVM

comment:2 by fingolfin, 19 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, 19 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, 19 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, 19 years ago

Attachment: ft_1093867.diff added

by cyxx, 19 years ago

Attachment: ft_processActors.txt added

comment:5 by fingolfin, 19 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, 19 years ago

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

comment:7 by cyxx, 19 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, 19 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, 19 years ago

Owner: set to cyxx

comment:10 by fingolfin, 19 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, 19 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, 19 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, 19 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, 19 years ago

Resolution: fixed
Status: newclosed

comment:15 by cyxx, 19 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.