Digging into Escape from Monkey Island

In the scene fin Herman is told that he needs to go put some pants on. He does it, but to get there, he walks backwards towards his hiding spot. This pathfinding bug occurs throughout the game when played in ResidualVM. When NPCs walk through a scene, sometimes, they do it backwards. Another example of this behavior is in the town scenes, such as on Lucre Island, an NPC will mosey on through town backwards.

In fact, in this scene, Herman not only walks backwards, but continues walking behind the monkey leg instead of stopping to talk to Guybrush. So, this is really a simple issue, Actors don’t seem to stop when the stop_moving() method is run. A quick look at the stop_moving() method shows that it directly calls the Lua function ActorStopMoving. This is still a stubbed method, so this is why the actor doesn’t stop moving. And then, because he doesn’t stop moving, the next command tells Herman to turn, which happens while he’s still moving, resulting in him walking backwards.

While further work might need to be done to get this function just right, a simple fix has been submitted in PR #884.

Continued from the previous entry

In the previous entry, we found that the sector being selected for positioning the camera was incorrect in ResidualVM in the case of the set pph. Specifically, the setup pph_closer was incorrectly using the sector information for the setup pph_close. When the camera view is changed, the actor is asked for the CAMERA type sector the actor is in by calling the Lua engine function GetActorSector.

In GetActorSector, we get the actor’s world coordinates, then use the findPointSector method to get the current Sector, filtered by the desired sector type. This function simply iterates through the sectors in the set to find the one containing the actor’s coordinates. I tested with gdb and found that the correct sector was being identified. A bit puzzled, I went back to ResidualVM and ran the Lua script that updated the camera position:

In the set pph, Guybrush walks towards Pegnose Pete’s house when he hears voices through the window. Unfortunately, it’s impossible for Guybrush to leave the scene after this unless you can solve the puzzle. In the retail version, this isn’t the case, Guybrush is free to go get any missing puzzle items he needs. Clearly, a bug!

In EMI, each area that you visit is represented by a set. I’ve added a list of sets to the ResidualVM Wiki, and you can switch between them using the following Lua command:

• switch_to_set(“set”)

It’s really only appropriate to switch sets like this if you’re in the same act of the game with the appropriate inventory items, otherwise unexpected things can happen! To be sure, jump to the correct part of the story using the emi_jump command in ResidualVM. A list of the jump targets has also been added to the ResidualVM Wiki.

In each set, there’s at least one setup. A setup is the view used in the current set. For example, in Pegnose Pete’s House (the set pph, from file pph.lua) there are three setups representing the view of Guybrush paddling in, a closeup on the dock and the closeup of the house. There’s also an additional setup that’s a topdown view of the set, but it doesn’t appear to be used in the game and has no background. To switch between setups, use the following Lua command:

• set:current_setup(setup)

In the process of testing this, I found that ResidualVM crashed in the case where there is no background for a set instead of showing the default image. A pull request was submitted to fix this issue, and can be found here.

So, to get back to the problem: the trigger to move from one setup (the closeup of the house) to the next setup (the closeup of the dock) isn’t tripped when Guybrush walks away. Let’s first investigate how switching between these setups is supposed to work.

In EMI, the sets can be found in the local.m4b file. When extracted, they are the files ending with the .setb extension. Unlike Grim Fandango, these files are in a binary format. Luckily, ResidualVM provides a tool for converting from this binary format to the text format used in Grim Fandango. Let’s inspect the format of the sets, starting with the section tag. In each set, there are sections, which designate which part of the set is being described. These section tags are: colormaps, setups, lights and sectors. For this work, we’re mostly interested in the setups and sectors tags.

The setups section of a set describes each of the setups (or views) in the set. For instance, in the set pph there are four sets, as previously described: pph_wide, pph_close, pph_closer and pph_topdown. Each of these describes where the camera is placed when switching to the setup. This allows the game to leave the actor in the set, but change our perspective and background to the new camera angle.

The sectors section of a set describes areas of the set with specific behaviors, like the bounding box for each setup, objects to avoid for path finding and other information important to the scene.

So, what’s going wrong in the the scene pph when we try to leave the setup pph_closer? If we put a breakpoint in set.cpp, to break whenever the set setup changes, we find that the set change is triggered by a call to the function MakeCurrentSetup from the Lua scripts. Following its users and those functions, we ultimately find that there’s a Lua function that’s continuously running called TrackGuybrush.  This function, amongst other things, updates the camera position when Guybrush moves into a new setup. It does this by checking if the actor is in the current sector. If not, it forces a camera change. When in the scene shown above, we check the variable cameraman_box_name, and see that ResidualVM found that Guybrush is in the setup pph_close, but the retail version has him in the setup pph_closer. This would explain the bug! In the next post, I’ll discuss how to fix the issue.

It’s been a while, (sorry!) and I really need to post an update as to what I’ve been working on, so here it is! Unfortunately there aren’t any pictures this time.

After a few false starts, I’ve taken out the old Quaternion implementation and implemented an order agnostic version. This implementation implements basic Quaternion math, ignoring the complication of Euler Angle order. This makes the Quaternion class simpler, and moves the problem of Euler order to either the user or the Rotation3D class.

One approach the user can take is to convert the Euler Angles to Quaternions manually using the Axis-Angle representation for each rotation axis, then multiplying these Quaternions together. While this is easy to write, it may obfuscate the intention of the engine author, so this method isn’t my favorite.

A better idea would be to provide support for Euler Angles just like the original Quaternion implementation did. Due to the fact that the Rotation3D class has already implemented Euler Angle to Matrix conversions for a single Euler Angle Order, I decided that it would be a better idea to expand this for all possible Euler Angle Order representations. This code adds an order parameter for converting between Euler Angle rotations to a specific rotation order. By making this order explicit and supporting all of the available rotations, this approach should make the code more readable, while still providing the flexibility that supporting many 3D games requires.

With this capability added to the math libraries, I then wrote tests using the ResidualVM testing framework to ensure that I got the conversions correct. I also made a separate branch with both old and new Quaternion implementations to compare sequences to ensure that the new code matches the old code as closely as possible.

The git branch containing the new Quaternion and Rotation3D code can be found here, while the testing branch can be found here. There are a few bugs remaining in the usage of this code in ResidualVM (the LookAt for Grim looks like it’s Z Axis-inverted, some attachment bugs still), but I hope to have those fixed in the next few days.

Once this code is pushed into merge-able shape, my next task will be adding bugs to the ResidualVM bugs list for the open issues with EMI so that there’s less chance of duplicated effort.

I haven’t had a chance to finish my work on Quaternions, due to my end of semester responsibilities, but I did get a copy of Myst 3 and EMI for PS2. Awesome! Now I have all of the supported games in ResidualVM, for testing after large changes to the engine.

Continued from the previous entry.

In the previous entry, we identified a problem with attaching and detaching actors in a scene. In this post, we’ll look at the solution to the problem and then adapt the solution to the ResidualVM code.

In graphics, we usually think of posing an object as three rotations around the three axes, X, Y, and Z. These rotations are referred to as Euler Angles. Unfortunately, this isn’t always the best approach, because while this rotation is easy to conceptualize, the result is sometimes ambiguous depending on how those angles are interpreted. So, while the EMI engine uses Euler Angles when interacting with the user, internally, the engine uses Quaternions. While I won’t go into a discussion of Quaternions vs. Euler Angles, or the math behind them, understand that the output generated by the engine is going to involve the conversion of Euler Angles to Quaternions, some computation, then back into Euler Angles.

After examining the disassembled EMI source code and confirming that the engine did use Quaternions internally, I set up some test code using the Irrlicht Quaternion implementation because it was easy to use and easy to test different configurations with. The result of my testing can be found here. This implementation correctly computes the angles as reported by the EMI retail engine, as recorded in this spreadsheet (local copy can be found here).

Essentially, after some testing, I found that the EMI retail engine computes the new rotation angle by finding the Quaternion of the actor we’re attached to, finding the inverse, then multiplying that by the Quaternion of the actor that’s being attached. For detaching, the operation is reversed, where we take the attached actor’s Quaternion and multiply that by the inverse of the attached actor’s Quaternion.

So, what do we need to add to ResidualVM? In ResidualVM, the Quaternion implementation requires two new methods:

• getInverse() – Finds the Inverse of a Quaternion
• toEuler() – Returns the Euler Angles from a Quaternion

With these new methods, we can now implement the correct code for attaching and detaching actors in actor.cpp. However, I discovered that the ResidualVM Quaternion code wasn’t making much sense and the result was still incorrect. After discussing it with Botje, wjp, somaen and klusark on IRC, I decided to make the Quaternion implementation and usage consistent. This work will be described in the next entry.

 

After the Manatee’s Ride, I hoped that all of the attachment issues were fixed. Unfortunately, that’s not the case. Another, more complicated attachment situation presents itself when Guybrush is arriving at Pegnose Pete’s house. In this scene, Guybrush puts down the raft pole. Here, the pole is attached to Guybrush, who is in turn connected to the raft. When the pole is detached, the detached location doesn’t match the retail version, resulting in the scene below:

So, what’s the problem in ResidualVM? A series of scripts generating scenarios indicated that the current code for detaching actors was incorrect. Reversing the procedure that was worked out in the Manatee’s Ride resulted in the correct detached position for actors connected to another actor.

Great, now the above situation worked correctly right? Nope. It turns out that the situation is more complex when you’ve got a situation like the scene from the Mysts O’ Time with three actors attached. We’ll start by checking the values when everything is attached after Guybrush gets on the raft in the first setup of the scene “mot“:

swampraft	Retail	ResidualVM
getpos	(-0.109778, -0.12, -0.437341)	(-0.109778, -0.12, -0.437341)
getworldpos	(-0.109778, -0.12, -0.437341)	(-0.109778, -0.12, -0.437341)
getrot	(0,733,0)	(0,13,0)
guybrush	Retail	ResidualVM
getpos	(0.4, 0.25, 0.4)	(0.4, 0.25, 0.4)
getworldpos	(0.359951, 0.13, -0.137574)	(0.36995, 0.13, -0.137573)
getrot	(0,0.252186,0)	(0,0,0)
mot.pole	Retail	ResidualVM
getpos	(-0.0222, 0.0287, 0.147)	(-0.0222, 0.0287, 0.147)
getworldpos	(0.513002, 1.36408, 0.350046)	(0.510769, 1.36408, 0.350696)
getrot	(-13.8, -87.5, 0)	(-13.8, -87.5, 0)

While there are some differences, these results match up pretty well. Let’s detach the pole from guybrush and check the coordinates again:

mot.pole	Retail	ResidualVM
getpos	(0.513002, 1.36408, 0.350046)	(0.411437, 0.2787, 0.548226)
getworldpos	(0.513002, 1.36408, 0.350046)	(0.411437, 0.2787, 0.548226)
getrot	(129.963, -25.8091, 0.0515321)	(-13.8, -87.5, 0)

There’s a quick fix for the world position, using the result from getworldpos gives us our new coordinates. This makes sense as we don’t want to move when detached, so the world coordinates should become the new position. The rotation is more problematic, how did we get there? The resulting rotation seems to be the result of converting from providing the actor’s pose in the local reference basis to the world reference basis.

Interestingly, detaching all three actors, then re-attaching them results in an incorrect placement of the pole object, indicating that there’s probably some bugs in the original implementation. This appears to have been worked around by constantly setting the position and rotation in the game scripts.

To figure out exactly what was going on, I tested attaching three actors in different poses and recorded the final attached values. Then, I detached the third actor and recorded those values as well. The result of this experiment is recorded in this spreadsheet. Of interest, I found that the position of the actor does not change the resulting orientation, so the only values recorded are the rotation angles retrieved with the :getrot() method. In the next blog post, we’ll interpret these values and figure out how EMI actually calculated the attached and detached position angle.

ResidualVM comes with two tools we can use to modify scripts while running a game in the engine. These tools are diffr and patchr, and can be found in the residual-tools repository.

diffr takes two files, and prepares a binary difference patch between them, outputting the result into a .patchr file. patchr takes the original file and the patch, and outputs the patched file. Let’s say we’ve made a fix to the game logic that we’d like to ship with ResidualVM. In this example, I’m replacing the call to ReadRegistryValue in the EMI Demo so that instead of trying to read the value SfxVolume from a non-existent registry and segfaulting (remember that bug?) the script instead reads from system_prefs.cfg.sfxvolume, which is implemented properly in ResidualVM for EMI.

Once we have made the desired change to our script, the first step is to compile a new script. If we can, it’s desirable to base this script on the previous script to reduce the amount of binary changes for patchr. Note that the luac referenced here is the one distributed with residualvm-tools, a regular copy won’t work!

• luac -b <old compiled script> -o <new file output> <script to compile>

With the compiled script, we’ll now ask diffr to make a patchr file for us, describing the binary differences between the two files:

• diffr <old compiled script> <new compiled script> <patchr file>

Now, we need to add this to the file containing the patches used at runtime. In the source directory, there is a folder that contains the existing patches. It can be found here for EMI’s patches: dists/engine-data/patches/emi. Once we have generated a patchr file, move it into this directory. Then, from dists/engine-data we’ll generate a new copy of residualvm-emi-patch.m4b containing our patch:

• mklab –emi patches/emi residualvm-emi-patch.m4b

Now, what happens if someone has already made a patchr for the file we’d like to change? In this case, we’ll patch the binary file using patchr, then delua it like normal so we can make our changes:

• patchr <old file> <new output file> <patchr file>

Remember that when building the new file and generating the patchr file, the old file is the original file from EMI, not the one we generated using patchr.

In this way, we preserved the changes already made, and can safely overwrite the patchr file when making our modified residualvm-emi-patch.m4b.

As an added bonus, I’ve also written a script to let you get a regular old patch file from a patchr file. Simply pass the file to be patched and the patchr file, and the script will spit out a text patch that describes the changes made. Obviously, this only works if your patchr file is patching a Lua script. Here’s how to use it:

• patchr_diff _options.lua _options.lua_1.patchr

You know that feeling when you reach into a bowl of pretzels and munch down, enjoying that savory jerky flavor. Then, when you reach into the bowl again, you find that the old pretzel that you just ate is still stuck to your hand…

Okay, so it’s another bug! Looking into the script _props1.lua, we see the following sequence is run when Guybrush eats the pretzel:

• The pretzel is detached from the bowl
• The pretzel is attached to Guybrush @ wrist_l
• When the eating chore finishes, the pretzel has set_wear_chore(nil) run on it

It looks like the call to set_wear_chore(nil) makes the actor invisible. Let’s try it out on the retail copy, using the debug window. Let’s see if we can make the drunk vanish:

• drunk:set_wear_chore(nil)

So what is ResidualVM doing wrong? Let’s examine the Lua for set_wear_chore, a method of actor in _actors.lua. There’s a lot going on here, so I reset the scene and then started stepping through each command in set_wear_chore using the retail version until the drunk vanished again. Luckily, it turns out that it’s first action, the call to stop_all_chores, that makes the actor vanish!

This method is from the actor object as well, and the code for it is also in _actors.lua. Luckily, it’s just a simple call to the Lua function StopActorChores, which if we follow it through, simply calls the stop() method on every one of the actor’s chores. Before we get much further, let’s take a stop ourselves to review what Chores are.

Chores are instructions that describe what the actor is supposed to look like, or what the actor is supposed to do. As an example, you can make the drunk look like Meathook by doing the following from the console:

• drunk:set_wear_chore(“meathook.cos”)

They usually also contain rules for behaviors, like when Guybrush eats a pretzel (to use a topical example):

• guybrush:play_chore(“eat_pretzel”)

In the retail version, this runs the chore, but here, it doesn’t. This is probably another issue that needs to be looked into!

So, what have we learned? When the method set_wear_chore is called with nil, the actor’s costume is stopped as well, which results in the actor not being drawn. In ResidualVM, the actor’s costume is stored in a separate place from other chores and isn’t stopped when StopActorChores is called. How do we fix this?

I decided that it would be easiest to just store if the wearChore is active or not. I also added a check to see if the wearChore was active in the draw method in costume.cpp to prevent the object from being drawn if the wearChore is inactive. Finally, I added a method to allow setting and getting this state variable. This was pushed in PR #858.

We now have a pretty good idea of what the problem is. In all of the previous cases, when we apply rotation to the actor before attaching, we find that the actor position (and world position) are calculated incorrectly. We also found that the rotation was not applied to the attached actor, which resulted in incorrect rotation values as well. All of these issues were only present in the attached actor, the actor that we attached to was fine.

Here’s the patch I came up with to fix the problem, and an update that removes need to invert the position before saving it.

To fix attaching with rotation, I noticed that the current code didn’t actually transpose or rotate the actor’s position based on the rotation of the object we’re attaching to.

Why didn’t getWorldPos() do this? When getWorldPos() is called, the actors are not attached, so they just return their own position!

While this fixes the manatee and the candles and matches the output of getpos() in the retail engine, the rotation and world position components are still broken, as is detaching actors. These will need to be addressed in future posts, but for now, the bug is fixed!