More on Sectors

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!

Why Are You Walking Backwards!?!

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.

A little late, but this is Herman walking 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.

Investigating Incorrect Sectors

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:

• pph:force_camerachange()

This correctly put guybrush into the right setup and updated the camera. I tried again with the only caller for this code, which is called from TrackGuybrush:

• pph:cameraman()

 I found that the camera wasn't being updated when called this way, so I went through each of the variables that might prevent a camera update, ultimately finding that the IsActorInSector method was using the substring of the setup name to identify the setup. Unfortunately, this won't work for the set pph because we have one setup that is a substring of the other: pph_close and pph_closer. Changing this check to an equality test fixes the issue, and Guybrush can now enter and leave the scene properly! The fix for this issue can be found in this PR.

Leaving Pegnose Pete's House

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!

You're welcome to enter the scene, but you can't leave!

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.

Quaternion Progress

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.