Digging into Escape from Monkey Island

I’ve been having a hard time trying to reconcile approaches that seem mathematically correct with the actual output from the Retail version of EMI. To figure out exactly what was going wrong, I decided to go back to the debugger and probe the internal values generated by the Retail version of EMI to compare with the results that are being produced by ResidualVM.

To begin with, I needed to figure out how the Retail version maintained the actor’s position. To find this out, I investigated the Lua entry point for SetActorRot to find where in memory the rotation information was stored. After some inspection, it turns out that in EMI, the rotation information is converted from the Euler Angles that were passed in from the Lua to a rotation matrix located 0xA0 bytes from the beginning of the allocated Actor. How do we know where the start of the allocated Actor is? For C++, the X86 ABI uses the convention that the object being referenced is passed in the ECX register when calling an object method. We can be fairly certain that in this case, it is the Actor object because the Lua/C++ interface passes in the actor handle as the first parameter, and when that actor’s handle is used to retrieve the Actor object, the return value is saved into the ECX register.

How did I know that the rotation was stored in a rotation matrix? I observed that after the Euler Angles were passed in, a series of floating point operations occurred, resulting in writing to nine values in the Actor object. Writing nine values was likely to be a 3×3 matrix, so I checked these values for Guybrush in the set wed by setting the debugger to break when SetActorRot is called and the actor handle matched the integer stored in hActor for Guybrush, which seems to always be 4.  To be sure that this was Guybrush, I also checked the actor’s position at offset 0x94, which matched with the results from guybrush:getpos().

Here’s the rotation matrix for Guybrush in the scene wed, before any movement, in the Retail version:

This rotation matrix was created by setrot(0, 110, 0). So, I then tested and found that there were multiple Euler Angle Orders that can reproduce this matrix. This is because there’s only one rotation axis that’s being changed, so there is ambiguity between the other two.

So, lets investigate the more complex attaching and detaching scenario that I outlined in the previous post. We’ll start with only the first actor, and check that rotation matrix first. First, I needed to identify the actor handle ID, so I ran the rotation script and checked the value of hActor for at1, at2 and at3. The actor handles for each, after running the script for the first time in the set wed, are: 106, 107 and 108, respectively. Recall that the first actor is rotated with the call setrot(5, 15, 25). This results in this matrix in the Retail version:

In this case, there should be no ambiguity, with only one rotation that produces the correct result because each of the rotations are different. The rotation that produces the correct result in ResidualVM is:

     Math::Matrix4 m;
     m.buildFromXYZ(getRoll(), getYaw(), getPitch(), Math::EO_ZYX);
     m.transpose();

With this approach now reproducing the same results, in the next post, we’ll examine attaching again with the extra information we’ve learned here.

Continued from the previous entry.

It turns out that the Euler Angle Order changes from the last blog post had a bug, causing the heads in Grim Fandango to not point in the right direction. This was odd because I had shown that the output was the same with both the original approach and the new Rotation3D approach, so what was the bug? After some time in my debugger, it turns out that the original implementation maintains the values in the matrix for position (the last column in the 4×4 rotation matrix) when building a new rotation. My new code simply discarded these values. With this changed in PR #944, the heads rotate properly in Grim Fandango again! Sorry about that oversight!

With Euler Angle Order taken care of by the changes in the Rotation3D class, I then focused on finishing the new Quaternion implementation without the added complexity of Euler Angles. The few remaining uses for Quaternions are largely in the EMI portions of the engine, which helps to reduce the impact that this patch has on the other supported games.

In the change set for improving Quaternions, I removed the direct implementation of conversion from Euler Angles to Quaternions. I then replaced it by creating a rotation matrix from the angles using the  new functionality we added to Rotation3D and then converting that to a Quaternion. Using this approach, there is only one implementation of Euler Angle conversion instead of the two (different!) versions that were in ResidualVM previously. I also added new functionality useful for Quaternion work and cleaned up the Quaternion class by improving the comments and fixing style issues. This work is in PR #943.

With a working Quaternion implementation, we can now finally work on fixing attaching and detaching for good! From the work before, I had thought that the position was computed properly. Things seemed to be positioned properly, Guybrush rode the manatee and there was no problem, right?

Well, testing with more complicated position vectors has shown that the code here isn’t exactly right! Why didn’t I notice the problem before? The examples that we used to demonstrate attaching/detaching like the candles, the raft and the manatee all have one attached part that’s zeros or have values that are the same, hiding the problem.

So, what’s a good vector for testing? Instead of using something from the game, we’ll test with a vector that has different components for all of the vector elements. The following table shows the three actors we’ll be testing, with the position and rotation vector for each:

It would be easy to write a script that sets up this scenario, but instead, I’ve made it so that tests can be run on objects from the GRIM engine in ResidualVM, as discussed in the previous post. In the tables below, I’ve attached these actors, with actor3 attached to actor2, who is attached to actor1.

Due to the influence that the rotation of the actor has on the position, I decided to fix the rotation first, then investigate if the position code needed to be modified further. In this next table, the actors’ rotation is checked between the Retail version and ResidualVM:

So, what does this tell us? Well, we need to change the rotation from a global rotation (the original angles) to a relative one (relative to the rotation of the parent object). How do we do this? By removing the rotation of the parent from the child. With Quaternions, there’s no subtraction operator. Instead, we invert the rotation we want to remove, then combine it with the current by multiplying both rotations to find the difference.
This difference is our new rotation. Unfortunately, it was still wrong! After some testing and checking against the retail version, I found that the Euler Order was incorrect. Changing the Euler Order to XZY and swapping the input parameters around gets us here:

Well, it’s an improvement. The angle is now calculated properly for the first and second actors. So, why didn’t the third attached actor come out correctly? For quaternions, the order of multiplication is not commutative. As it turns out, the order that the parent rotations were being applied was backwards, resulting in an incorrect rotation quaternion. After fixing this, the result matches the retail version. This was submitted as part of PR #948. In the next post, I’ll discuss fixing the position and the changes required to make it work correctly.

Just a short update here! I ran into some problems with the new Quaternion code, I’ll detail those in a later post. As part of getting that to work, I got sick of having to start the game over and over again. To alleviate this tedium, I implemented unit testing for the Actor methods related to the Quaternion work in the Grim Engine. Neat, but why was that interesting?

To get this working, I needed to solve a few problems:

• Some methods depend on a working, initialized GameEngine
• Linking all of the parts of ResidualVM into the test binary

In some of the methods, the engine depends on being initialized, with all of the correct settings. An obvious example of this is the check to see which game is being run by calling the getGameType() method. So, to fix this, I have written the minimum required code to start the main engine from the tests.

With that fixed, the next problem was that linking together the test binary was not as simple as before. If you just add the libgrim.a object, there will be quite a few missing objects in the final linked binary. To fix this, I found all of the .a files generated by the compiler and added them to the module.mk file for the testing build. Just adding them will not solve all of the dependency issues because the linker will search in order through the .a files to find the required symbols. If the objects containing those symbols haven’t been passed to the linker yet when encountered, the symbols will still be unresolved. So, you must order the objects so that all of the symbols can be found. Additionally, I added some extra code to the module.mk file so that when (for instance) support for Grim isn’t built and only Myst3 support is, the associated tests are not run.

I don’t think this will get submitted to ResidualVM, but it was an interesting exercise. This work can be found in my GitHub here. You must configure with –enable-text-console for this tree to work as it skips some GUI initialization that way.

Continued from the previous entry.

After a long hiatus, I’m working on completing the rotation and quaternion changes that arose as a part of fixing attaching and dettaching actors. To begin, I needed to rebase my old changes so that they applied to the current git master. With all of the progress that has been made since the start of GSoC, the patchset was out of date and doesn’t address all of the current uses of Quaternions and Rotation3d.

In order to make this patchset easier to accept into ResidualVM, I’m splitting the work up into three distinct parts:

1. Rework of Rotation3d to support the various Euler Angle orders
2. The final expanded Quaternion implementation
3. The completed attaching and detaching code

The reasoning behind this approach is that a large portion of the current Quaternion usage is simply to convert from Euler Angles to a Matrix. By removing this extra step, the resulting code will be easier to read and more straightforward. After applying my previous changes to the Rotation3d class, I created tests to check that the code was capable of converting from Euler Angles to a Rotation Matrix, and back again. In this implmentation, the user can specify the Euler Angle order by using the enum EulerOrder values, and building the Rotation Matrix with the member function buildFromXYZ or using the constructor that takes three angles and the EulerOrder.

Let’s take a brief detour here for a moment to explain how to add tests to ResidualVM’s test suite. ResidualVM uses CxxTest as the framework to build unit tests. All of the tests can be found in the directory test, with a directory inside that for each of the ResidualVM components tested. Currently, there are tests for the audio subsystem and the common functionality. In this changeset, I’ve created a new directory, math and added a new file, rotation3d.h which contains the unit tests for the Rotation3d class.

Unit tests are implemented by writing classes that contain the tests and CxxTest automatically generates the rest of the code to run the tests. So, to add a new test, we first include a header from CxxTest that defines the TestSuite class. We then define a class that inherits from this base class and then implement our tests with each unit test as a public member of our class. Each of these unit test functions return no value and have no parameters. To actually test a value, CxxTest provides assertions which should be used to report the test result.

Since math isn’t already a part of the testing structure, we’ll need to add a new directory to the unit test build system. To do this, you must add the test header files to the build by adding them to the module.mk file in the test root. So, to add our new math tests to the unit tests to be built, I modified the TEST variable with the text in red:

• TESTS := $(srcdir)/test/common/*.h $(srcdir)/test/audio/*.h $(srcdir)/test/math/*.h

I also needed to link the actual math library implementation to the unit test build, so I added the following to the TEST_LIBS variable:

• TEST_LIBS := audio/libaudio.a math/libmath.a common/libcommon.a

And that’s it! To build and run our tests, from your build directory, simply run:

• make test

The output will look like this (assuming I didn’t break anything!):

And failures will look like this when something does break, depending on the assertion type used:

And that’s it for testing! It’s very straightforward to add additional tests, so I’ll try to add code that performs testing in the future for applicable changes.

Back to Rotation3d! In this incarnation of the updated Rotation3d code, I decided to return the rotation direction to the “left handed” DirectX direction of rotation that was previously in Rotation3d. This will remove the necessity for all of the transpose() calls that I had previously needed to insert to produce the same result as before.

In addition to the basic assertions, I had previously created a test that compared the original implementation of Rotation3d to my new version for each of the uses in ResidualVM. I adapted these tests for the new implementation, but won’t submit them for inclusion because they duplicate a lot of code. The branch containing these tests can be found here, while the Rotation3d changes can be found in PR #936.

In the next post, we’ll look at the Quaternion implementation and finish working on attaching and dettaching.

In a previous post, I commented on a texturing problem with the lava in the scene lav. As I indicated in that post, while the work around that I submitted did fix the problem for the scenes with issues, the workaround itself was sort of a hack. I had assumed that if a texture was larger than 128 pixels on a side, then that texture should be clamped at the edges. Clamping prevents the OpenGL renderer from repeating the texture over the surface, resulting in lines when the textures don’t repeat cleanly. So why not just always use clamping? Well, in many cases we DO want the texture to repeat. Think of a typical grass pattern or a sandy beach texture, or in this case, the lava!

Although my approach did fix the problem, the solution was a hack. There’s nothing that really indicates that that is a cutoff for which approach to take. To investigate possible solutions, I used apitrace, a tool that records OpenGL state information, allowing you to replay, investigate and examine what OpenGL calls a program is executing to render the screen.

To capture a trace, we’ll use this command with the retail version:

• apitrace trace -o retail.trace wine ./Monkey4.exe -gl -w

And this with ResidualVM:

• apitrace trace -o residual.trace residualvm

Of note, to trace 32-bit Windows applications in wine, you will need a 32-bit version of apitrace.

To view the traces, I used the program qapitrace, a GUI viewer for replaying traces from apitrace. To run qapitrace on an existing trace:

• qapitrace retail.trace

With these traces in hand and in the viewer, I took a look at the size of the textures and when the glTexParameteri function was used on them in the retail version. To make the trace more manageable, I filtered the results for Texture Events using Trace->Options and configuring it like shown below.

After some investigation, I found that there were definitely textures that used clamping when the size was lower than 128 pixels and repeating when greater. Rats, that approach definitely was wrong!

It was at this point that Akz- suggested that I try clamping sprites, which are generally images painted on top of the scene (such as the candles’ flame or the Dainty at dock on Lucre Island) and repeat all other textures. This approach seemed to work well, also resolving all of the issues resolved by the previous patch. For this approach, I had originally thought of passing a texture parameter to the Material (which loads the texture) using an enum, but I ran into the issue of having to predeclare the enum when used in places that had also predeclared the Material class. In C++, unlike C, the enum has a variable storage size and isn’t assumed to be int. In C++11, there is support for predeclaring the type, but ResidualVM targets the C++03 standard, which doesn’t include this feature.

In the end, I realized that the retail version only used GL_CLAMP_TO_EDGE and GL_REPEAT, so instead of using an enum, I replaced it with a bool indicating that the texture should be clamped when true. The completed patch for this work can be found in PR #910. It fixes both the lava, as shown in the previous post, with a repeating texture, and the Dainty at the dock on Lucre Island, where the texture needed to be clamped to remove the lines as shown below. Note that in these pictures, they’re not exactly in the same place because the Dainty texture moves to simulate waves.

In the next post, I will get back to collisions and the actual lava puzzle issues.

On Monkey Island, there’s a puzzle involving a lava flume ride:

Unfortunately, the first thing that’s immediately obvious is that the lava texture is rendered improperly. After bisecting, it turns out that this is due to this recent commit to fix the lines in the intro bitmaps. After testing the retail version in a debugger, I found that it used both GL_CLAMP and GL_REPEAT. I’m not sure if the approach is correct, but it looked like only textures that were smaller than 128×128 used GL_REPEAT, while larger textures seemed to use GL_CLAMP. An implementation of this was submitted as PR #910. Here’s what the Lava Puzzle looks like now:

This puzzle is configured from the set lav, which starts a separate Lua script: lava_flume2.lua. This script contains the logic for building the puzzle and controlling the raft, separate from the normal game controls and logic. This is all contained in the variable flume. In this puzzle, the locations of the logs can be in 1 of 4 different orientations, appearing at different stopping locations. There are always four logs. In the game script, the paths that Guybrush might take are represented as a graph of connected nodes, with each node containing information as to whether the node is blocked with a log, the node’s coordinates, etc. As you can see in the screen shot above, Guybrush does not collide with the stuck logs, he just passes through them instead of bumping them into the lava stream.

So, why doesn’t Guybrush collide with the stuck logs? In the script, it appears that the collisions are detected by turning on the collision mode to COLLISION_SPHERE. This in turn calls into ResidualVM using the functions SetActorCollisionMode and SetActorCollisionScale, which configure collision detection between the actor and other actors. When these collision modes are active, the collision check between actors occurs in the ResidualVM function handeCollisionWith in actor.cpp. I commented this function to see what collisions were being checked and got no print outs during the lava puzzle. I did get some collisions with Timmy the Monkey on the beach in the set mib though, which provides an easier testing location than the lava puzzle and also displays broken behavior. In this scene, Timmy is randomly running around, including through the legs of Guybrush, when he should stop by colliding with Guybrush. Using a debugger, I discovered the call in the retail version for determining a collision and found that Timmy does register a collision whenever he’s close to Guybrush. In ResidualVM, this doesn’t happen. This is likely the root cause of the bug.

There are also other problems with the lava puzzle as well, such as the boat bouncing back and forth the second time through the puzzle, and being able to see through the bottom of Guybrush’s boat. The second problem is likely related to the issue with doors

Since this blog entry is getting long, in the next entries, I’ll discuss fixing these issues.

Continued from the previous entry

In the previous entry, we identified the reason why it’s hard to start a conversation with Herman Toothrot in the set toc. To debug this issue, I took a look at the set gpt because it has a variety of sectors, many with the same name. This results in sectors that are easy to move between, but transition in the wrong place. For example, the transition between gpt_village (sector 4) and gpt_starbuck (sector 5) happens at a different position in the retail version of EMI and ResidualVM, as shown below:

Let’s take a look at the sector map for the camera sectors for the set gpt:

In this picture, we can see that the two sectors overlap, resulting in the glitchy behavior we see in the example above. In the retail version, it appears that the higher ID sector takes precedence over a lower sector ID.

As another test, let’s move Guybrush into the sector marked 4 and check what the result of IsActorInSector(guybrush.hActor, “gpt_village”) is. We would expect this function to return “4” because this sector is named gpt_village, but in fact, we are told that Guybrush isn’t in the sector gpt_village. However, if we move Guybrush into the sector marked 16, which is another sector named gpt_village, we find that the same command returns 16, indicating that Guybrush is in the sector!

So, it appears that IsActorInSector() should only return the sector ID if the name matches the requested name and the ID is the highest of all of the sectors where the name matches. A patch that implements this is found in an update to PR #883.

When Guybrush enters Herman Toothrot’s camp (the set toc) for the first time, Guybrush should be able to trigger a conversation with Herman by walking up towards him. In ResidualVM, this conversation is never triggered! Let’s find out why.

In this scene, there’s a function to control the setup changes, including the closeup for the conversation Herman. This function checks if Guybrush is in the setup toc_log and if the conversation has already happened. So, why doesn’t the standard “Talk to Herman” come up when we approach? In this script, the range for this pop-up is reduced to 0, which prevents it from coming up. Setting it with:

• toc.herman_obj.range = 4.3

Makes this behavior work as intended, and indeed, the script does this after Guybrush has the initial conversation with Herman. We can also check the state of the conversation, just to make sure this isn’t the problem either (using my pop up lua injector):

• dd = glob.herman_talk_status

And as expected, it has the correct value, 0. Let’s check Guybrush’s current setup now:

• dd = toc:current_setup()

Which returns 1, the ID for toc_wide. So it seems that Guybrush never enters the setup toc_log, which is required to trigger the conversation.

First of all, are we sure that the setup_change function is being run? Yes! We can prove this by checking the range on Herman’s note in this scene. If we check from the setup toc_wide, the interaction range for the note is 0, but when we change to the setup toc_close, the interaction range is changed to 1.8. This change is implemented in the setup_change function, so it’s certainly being run.

How about if we force the current setup to toc_log?

• toc:current_setup(toc_log)

That works, and we’re treated to the conversation with Herman. So, it seems that Guybrush isn’t moving into the setup toc_log. As with the previous bug at Pegnose Pete’s House, there is a problem moving between setups, but this time, it’s impossible to move into the setup toc_log.

Let’s check to see what sector Guybrush is in with find_sector_type:

• system.currentActor:find_sector_type(CAMERA)

We find that the sector reported when we’re near the log is actually toc_log.

How about IsActorInSector()? Both toc_wide and toc_log both are matched as valid setups when Guybrush is near the log. However, in the retail version, only toc_log matches, with IsActorInSector(ActorHandle, “toc_wide”) returning a nil, even when the setup toc_wide is showing! Trying this test again with the set gpt also resulted in nil values for IsActorInSector when in setups gtp_arial and gpt_dock, while ResidualVM reported that Guybrush was in the sectors of the same name.

First, let’s see if the sectors actually overlap. To visualize the sectors in a set, I rewrote a utility in perl from residualvm-tools to work with EMI and GRIM. This new version can be found here. The input of this tool is a text based set (so you’ll have to convert binary sets with setb2set first), and the output is a fig file, compatible with xfig. I also added the ability to filter by sector type.

For the set toc, I filtered by type camera, which is the type used to pick the view and got the following result:

From this, we can easily see that the sector toc_log (sector 19), overlaps one of the toc_wide (sector 0) sectors. After going through all of the sets, I found that this set is the only set in which the camera sector is almost completely overlapped, aside from the set cpt. In the set cpt, the two overlapping sectors have the same name.

So, why does this bug arise? When the camera change function is called, it checks to see if Guybrush is still in the same sector by calling IsActorInSector(). This call succeeds when it should fail because the sectors are overlapped, so the camera change function thinks Guybrush hasn’t left the sector.

This post is going on a bit long, so in the next post, we’ll come up with a solution to this problem.

Continued from the previous entry

Continued from the previous entry

Sorry, no pictures for this one!

With the previous patch for equality when checking if an actor was in a sector, I thought the work was completed. Unfortunately, it was pointed out that in the original engine for Grim Fandango, the sector check is done using strstr to check the sector name by substring. Also, with some help from the #ResidualVM IRC channel, I found out that ResidualVM originally DID use equality, but it was changed to a substring check due to a bug in GRIM. Uh oh!

First, I took a look at the problematic scenes in EMI and GRIM to figure out why this bug is happening exactly. Next, the source for EMI needed to be checked to see what its behavior was when running the Lua command IsActorInSector, which is where the broken behavior was. And finally, I needed to resolve the issue for both games.

In the sets themselves, I identified the original problem as returning the incorrect sector when picking the sector by name, with pph_close and pph_closer as the example of two colliding sectors. So, out of curiosity, how often does this happen in EMI? As it turns out, really often! There’s cases where different sectors even have the same name! How did I find this? I started by first converting the binary set information to text:

• mkdir artAll
• cd artAll
• unlab ../artAll.m4b
• mkdir Sets
• cd Sets
• for i in *.setb; do n=$(basename $i | cut -f1 -d.); setb2set $i > $n.set; done

With the converted sets, I could now inspect the sectors that they used:

• grep sector *.set | grep -v section: | grep -v numsectors > ../sectorlist && mv ../sectorlist .

With this information and this script, I collected some statistics:

• GRIM (3142 total sectors):
  • None of the sectors have duplicate names
  • 605 of the sectors are substrings of another (including duplicates)

• EMI (2228 total sectors):
  • 140 of the sectors have duplicate names
  • 506 of the sectors are substrings of another (including duplicates)

Well, that’s interesting. Both games have sectors that are named so that some sectors are substrings of other sectors! However, this bug is specifically about changing between setups when the actor triggers the setup change by changing sectors. So, I also checked all of the setups for substrings and found:

• GRIM (384 total setups):
  • 1 of the setups has duplicate names
  • 2 of the setups are substrings of another (including duplicates)

• EMI (326 total setups):
  • 0 of the setups have duplicate names
  • 28 of the setups are substrings of another (including duplicates)

It’s important to note that in the case of the bug, only the camera sectors are checked, so let’s run the same test, but filtering for only camera sectors:

• GRIM (210 total camera sectors)
  •  0 of the camera sectors are substrings

• EMI (182 total camera sectors)
  • 73 of the camera sectors are substrings

I also checked the setups more closely in EMI, and it turns out that while there are plenty of setups named with substrings, the only setups that the player who is controlling Guybrush can walk between are in the set pph (i.e. pph_close and pph_closer). All of the other setups are unused or switched to by the Lua directly (as in the set pla with pla_judges and pla_judges_close).

So, I’ve identified that there’s really quite a bit of overlap, but not much in GRIM when it comes to camera sectors, while there are a lot of overlaps in EMI’s camera sectors which is causing this bug. However, I’ve shown that the only scene in EMI that this effects is the set pph.

In the next post, I’ll discuss the original binaries and the solution to this problem, this post is getting long enough!