dev, computing and games

Short version: To disable collisions e.g., walk through walls in J. R. R. Tolkien's Lord of the Rings for SNES, use the following Pro Action Replay codes

80E0C780 (Disable horizontal collisions)
80E13480 (Disable vertical collisions)

Longer explanation below.


There are some areas in maps I wanted to look at in this game, and those areas are inaccessible playing the game normally. How can you look at inaccessible parts of the game?

One option: rip the map. That would work, although it's very hard. It would cascade into the problem of also ripping the tileset graphics and figuring out how the each map datum maps to which tile. I did this process once for a different game, Lagoon. Those maps are here. It was doable because I already did some other projects involving that game so I had some information about it. For games I'm less familiar with, like LotR, it will take longer, probably so long it's not worth it.

An easier option instead is to disable collisions. So I set out to do that.

The general sense I had was that this will be a code change to the collision logic in the game. Some code must take the player's position, do some comparisons on it, and permit you to move or not move based on the comparisons. But which code is doing this?

1. Where position is stored

Breaking the problem down, the first step is to find where your position is stored in memory. It's likely to be an X, Y position since what kind of a maniac would store it in polar.

So there's a number, somewhere in the program. Classic problem where we don't know where it is stored. But worse yet, we also don't know what the number is, what its value is.

When faced with this kind of problem I do something I'm calling "special diffing", you can call it whatever you want, basically you take 3 or more memory dumps.

  • For dump 0, you've got your character somewhere.
  • For dump 1, you move them a little bit to the right.
  • For dump 2, you move them a little bit more to the right.

And then write some code that opens the dumps, looking through each offset for some number that's increasing from dump 0 to 1, and 1 to 2. Want more confidence? Take more memory dumps to have more data points.

Why move horizontal and not vertical? Because there isn't a strong convention in computer graphics about whether up is positive or not. For horizontal there's a pretty strong convention.

Why move to the right, and not left? Convenience, we probably expect the position value to increase going to the right.

Why move just a little, and not a lot? So that you don't overflow the byte type (e.g., exceed 255) since that's a hassle to account for.

Using this diffing technique gave a few answers

  • 7E05D3
  • 7E0AE7
  • 7E0EF7
  • 7E1087
  • 7E128F <-- The answer
  • 7EFD46

It was a low enough number to rule out the false positives and find the answer:

7E128F

The other values corresponded to position too, but they were an output of it not an input. E.g., changing the value wouldn't stick, except for 7E128F.

2. What position is used for

The next obvious step is to break-on-write of position. We expect it to get hit whenever your character walks around, since it would get updated then. And moreover, we'd expect that code path to not get taken if you're hitting a wall.

Bad news here. The break-on-write will always fire regardless of whether you're moving or not-- the code is set up to always overwrite your position even if it doesn't need to. So that kind of breakpoint won't directly tell us which code paths fire or don't fire based on your hitting a wall.

For the record, it hits here:

$80/C88E 99 8F 12    STA $128F,y[$80:128F]   A:0100 X:0000 Y:0000 P:envmxdizc

That's okay. It will at least tell us something, when your position does get updated while moving, and we can still reason about what happens when it doesn't get updated.

And in particular, we can locally disassemble or CPU log to find the preceding operations

...

$80/C883 69 00 00    ADC #$0000              A:0000 X:0000 Y:0000 P:envmxdiZc
$80/C886 99 97 14    STA $1497,y[$80:1497]   A:0000 X:0000 Y:0000 P:envmxdiZc
$80/C889 AA          TAX                     A:0000 X:0000 Y:0000 P:envmxdiZc
$80/C88A 18          CLC                     A:0000 X:0000 Y:0000 P:envmxdiZc
$80/C88B 79 8F 12    ADC $128F,y[$80:128F]   A:0000 X:0000 Y:0000 P:envmxdiZc
$80/C88E 99 8F 12    STA $128F,y[$80:128F]   A:013A X:0000 Y:0000 P:envmxdizc

So some position-increment value gets saved to $80:1497, then increment the position by that number too. We can use this to work backwards and see a bunch of other fields updated as well.

Now we know the neighborhood of the collision code and can reason about the code path involved.

3. Finding the branch

There are a couple ways to proceed from here. There's a 'nice' option and a 'cheesy' option.

The 'nice' option is to take where we know the position is stored, and find the chain of operations done to its value. This works out if the control flow for controlling position is pretty localized-- say, if collision-checking and position-updating is all in one tidy function and they're right next to each other.

Unfortunately, the position-updating logic was messy. It was seemingly tangled up with the logic for checking for interact-ables (e.g., doors, NPCs). So while the 'nice' option is still an option, it's costly. Therefore there's the 'cheesy' option.

The cheesy option is to break on position change, using the information we found above, so we at least have some kind of frame delimiter and something to look for. Then enable CPU logging. Log:

  • one 'frame' where you can move, and
  • one 'frame' where you're obstructed.

Then strip out IRQs (they create noise), and put the result through a giant diff. I used Meld.

The diff isn't so crazy.

See there's data-divergence up until a certain point. After that, execution-divergence. It was a kind of thing where I scrolled through it and it caught my attention, so not a really thorough debugging experience, anyway the previous stuff to untangle where position is stored helped to understand the data-divergence and filter out noise in the diff.

And that ended up being the answer. The comparison

$80/E0C4 DD 41 E6    CMP $E641,x[$80:E643]   A:0010 X:0002 Y:00B2 P:envMxdizc
$80/E0C7 90 05       BCC $05    [$E0CE]      A:0010 X:0002 Y:00B2 P:envMxdiZC

will check if you're about to collide with a wall, or not. If you're free to move, you take the branch. If you're obstructed, you fall through. Therefore we can disable collisions by always taking the branch. So change

$80/E0C7 90 05       BCC $05    [$E0CE]

to

$80/E0C7 80 05       BRA $05    [$E0CE]

A quick test will show you this only covers horizontal collisions. Vertical goes down a completely separate code path. I guessed that they shared a common subroutine

$80/E0BD 20 22 D0    JSR $D022  [$80:D022]   A:00B2 X:0150 Y:00B2 P:envmxdizC

and this ended up being true. Setting a breakpoint on D022 ended up hitting for the vertical case:

$80/D022 DA          PHX                     A:0E05 X:016B Y:0095 P:envmxdizc
$80/D023 5A          PHY                     A:0E05 X:016B Y:0095 P:envmxdizc
$80/D024 8A          TXA                     A:0E05 X:016B Y:0095 P:envmxdizc
$80/D025 4A          LSR A                   A:016B X:016B Y:0095 P:envmxdizc
$80/D026 4A          LSR A                   A:00B5 X:016B Y:0095 
...
$80/D033 7A          PLY                     A:0000 X:0016 Y:026C P:envmxdiZc
$80/D034 FA          PLX                     A:0000 X:0016 Y:0095 P:envmxdizc
$80/D035 60          RTS                     A:0000 X:016B Y:0095 P:envmxdizc
$80/E12D E2 20       SEP #$20                A:0000 X:016B Y:0095 P:envmxdizc

at which point it's easy to step out 1 frame and see the caller. And it turns out the caller looks very similar to the horizontal case, with the same kind of branch. It has

$80/E131 D9 41 E6    CMP $E641,y[$80:E643]   A:0000 X:003F Y:0002 P:envMxdizc
$80/E134 90 05       BCC $05    [$E13B]      A:0000 X:003F Y:0002 P:eNvMxdizc

So you can do a similar thing, changing the branch on carry clear to a branch unconditional

$80/E134 80 05       BRA $05    [$E13B]    

Putting it all together, the two codes are

80E0C780 (Disable horizontal collisions)
80E13480 (Disable vertical collisions)

Here's a demo of it in action, successfully getting past a door.

Side thing, I also used the code to get above the door in Bree. That said, even when enabling collisions again, it didn't take me anywhere. So the door's either controlled by non-'physical' means or not implemented.

I was still left with this question of whether we can conclusively say the door is not implemented.

It's one thing to prove a positive, prove a program does something. Easy enough, you show it doing the thing.

It's another thing to prove a negative, to prove a computer program will never do a thing. Can you prove the door can never open? Not ever? You can't really, you can only reach levels of confidence. Can you prove White Hand is not in Pokemon? Can you prove Herobrine is not in Minecraft? Has anyone ever conclusively proven that the pendant in Dark Souls doesn't do anything? Well, see, they ran the program through a simulator and-- just kidding, they went low tech and asked the director, so then it's a social engineering problem of whether you believe him.

When people use formal or other methods to prove program behaviors or nonbehaviors, they exploit constraints in the programming language or execution environment. For example, a language like Haskell has a rich set of constraints which are helpful in proving behavior. Or if a computer is unplugged and has no battery, you have confidence it won't power on. But in our case we're talking about object code, not source code, and we're talking about something the hardware could do. The instruction set of the object code alone doesn't provide helpful constraints. Hell, we can't even universally statically disassemble programs on this platform (because the choice of instruction width is dynamically chosen). Statically prove nonbehavior?

I'm not trying to give credibility to conspiracy theories or the mindset behind that kind of thinking. I'm trying to explain why you might not find a conclusive answer when you might want one. Anyway, through this exercise I got a greater level of confidence that the door doesn't go anywhere.

Some details

  • You can use both codes or one at a time.
  • Disabling collisions means you also can't interact with objects like doors. If you want to pass through doors, re-enable collisions or enable them for one direction.
  • If collisions are disabled for you, they're also disabled for allies, NPCs, and enemies.
  • Disabling collisions will let you pass through 'physical' doors in the game, where you're obstructed simply by where you're allowed to walk. For example, the gate in Moria, and the fires on the steps by the Balrog. There can be other 'non-physical' doors, where you need to trigger the right game event (e.g., have a key) to open them.

I used password tricks to get to the end area with all events signaled in any case, and had collisions off. I got to freely walk around the area where you find Galadriel with the mirror.

It turns out, the area is an infinite plane!

It's for the best not to try and rip the level data. /j

August 19th, 2022 at 6:19 am | Comments & Trackbacks (0) | Permalink

J. R. R. Tolkien's Lord of the Rings for Super Nintendo shipped with a bug as you get toward the later parts of the game.

Short version: use these Pro Action Replay codes to un-glitch the late-game passwords.

81CBF10C
81A3900C
81A35C0C

Longer explanation below.

If you're in Moria past the entrance and the first part and request a password, the game will give you one. However, if you write down and try to use that same password later, the game won't accept it.

This is especially troublesome because

a) it's in the most tedious part of the game, a part you wouldn't ever want to re-do, and

b) even if you back-track to the Moria entrance, it won't go back to giving you valid passwords. The game's password system is basically cursed.

I investigated to understand this more. First, the password validation converts this character into a number.

The exact way it does this is described in an earlier post. So for here, L is 9, M would be 10, and so on.

Starting from there, I found out more by

  • typing a numerical garbage password like "023741" into the first six characters
  • taking memory dump of RAM
  • running a relative searcher on the memory dump, looking for a pattern like the one above
  • found one result. This was lucky in a bunch of ways. It was lucky how the number was indeed stored contiguously in RAM, not immediately over-written, the password characters' values are sequential (e.g., the value of password character '1' numerically comes right before '2') and that I had picked a unique enough number
  • Used that to get the RAM address of the character boxed in red above
  • Set a break-on-read of that RAM address in the debugger
  • Breakpoint hit when you press the button for password confirm. This also, was a bit lucky. The game only read the password back for initial graphics or when you hit 'confirm'. No reading it back continuously, no noisy breakpoints.
  • Stepped through in debugger to see what it did with the password character. When it copied the password character, set break-on-read of that too. This led to un-tangling the password characters from what I called the AreaNumbers below. I saved the code and marked it up with comments and labels.

Password validation calls this function

// Function: ReadPasswordLocationCode()
// Precondition: location code is stored at $81:039C
// Postcondition: result stored in 801CCB, 801CCD, 801CC9.
//   The result is what I'm calling an "AreaNumber"
//    plus positional information about
//    where in the world to load the player.
// 
//    Early-game AreaNumbers are high-numbered. 
//    Late-game ones are low.
//    Examples: 
//      Crossroads is 0x12A. 
//      Rivendell is 0x138. 
//      Moria Entrance is 0xEF. 
//      Moria 1 is 0x51. 
//      Moria 2 is 0x0C.

$81/CBEA B9 84 03    LDA $0384,y[$81:039C]   ; Load location code. E.g., the password 
                                             ; character 'M', which is 0xA

$81/CBED 29 1F 00    AND #$001F              ; Ignore upper bits 
$81/CBF0 C9 0A 00    CMP #$000A              						
$81/CBF3 90 02       BCC $02    [$CBF7]      ; If the password character is equal or greater than 
                                             ;'M' (0xA), fall through                                                                               
                                             ; to LocationCodeTooHigh.
                                             ; Otherwise, goto LocationCodeOk.

LocationCodeTooHigh:
$81/CBF5 38          SEC                     
$81/CBF6 6B          RTL                     ; Bail

LocationCodeOk:
$81/CBF7 85 90       STA $90    [$00:0090]   
$81/CBF9 A5 90       LDA $90    [$00:0090]   
$81/CBFB 0A          ASL A                  
$81/CBFC AA          TAX                     

// Write the output
$81/CBFD BF 18 CC 81 LDA $81CC18,x[$81:CC2A] 
$81/CC01 8F CB 1C 80 STA $801CCB[$80:1CCB]   
$81/CC05 BF 30 CC 81 LDA $81CC30,x[$81:CC42] 
$81/CC09 8F CD 1C 80 STA $801CCD[$80:1CCD]  
$81/CC0D BF 48 CC 81 LDA $81CC48,x[$81:CC5A] 
$81/CC11 8F C9 1C 80 STA $801CC9[$80:1CC9]   

$81/CC15 C8          INY                    
$81/CC16 18          CLC                     
$81/CC17 6B          RTL                     

It's pretty easy to see the problem. It validates your location code is too high if you specify 'M' or 'N', but those are codes the game gives you. It was clearly a mistake. Changing the line

$81/CBF0 C9 0A 00    CMP #$000A

to

$81/CBF0 C9 0C 00    CMP #$000C

will fix it, allowing through AreaNumbers up to N (since a password character N = 11 = 0xB), the maximum the game will give you.

This unblocks the password validation code. But, if you were to patch the above change and try it, you'd see the screen fade but hang there forever spinning in a long loop and hard locked not loading the level. So we're not out of the woods yet.

Terminology
Crashed, halted- the game's computer stopped executing instructions
Hard lock- the game's computer is executing instructions, but it appears unresponsive to inputs e.g., the screen is black
Soft lock- the game displays graphics and appears responsive but can not be won

The hang happens because we get past the password-validation and into level-loading yet there's parts of the level loading code that block out AreaNumbers belonging to Moria.

We get here

// Function: AreaLoadStaging()
// Preconditions: Location codes have been written to 801CCB, 801CCD 801CC9
// Expected behavior: Sanitize out bad location codes (e.g., bad
//   AreaNumbers) and call a common function AreaLoadHelper().
// AreaLoadHelper() is a common channel used during both password-based 
// loading and normal level loading as you move from one place to another 
// in the game.

$81/A377 E2 30       SEP #$30                
$81/A379 AF 0E 1D 80 LDA $801D0E   
$81/A37D CF 72 03 80 CMP $800372 
$81/A381 F0 76       BEQ $76     
$81/A383 AF 72 03 80 LDA $800372
$81/A387 30 70       BMI $70 
$81/A389 C2 20       REP #$20
$81/A38B AF C5 1C 80 LDA $801CC5          ; Load the area number.
										
$81/A38F C9 54 00    CMP #$0054   
$81/A392 B0 52       BCS $52    [$A3E6]   ; If area number < 54, fall through to 
                                          ; InvalidAreaNumber_TooLow.
                                          ; Otherwise, goto ValidAreaNumber.

InvalidAreaNumber_TooLow:
$81/A394 E2 20       SEP #$20              
$81/A396 AF 0E 1D 80 LDA $801D0E
$81/A39A C9 04       CMP #$04 
$81/A39C D0 0E       BNE $0E  
$81/A3AC E2 20       SEP #$20 
$81/A3AE A9 00       LDA #$00 
$81/A3B0 48          PHA     
$81/A3B1 AF 72 03 80 LDA $800372
$81/A3B5 48          PHA   
$81/A3B6 F4 06 00    PEA $0006 
$81/A3B9 22 02 80 81 JSL $818002
$81/A3BD 85 34       STA $34              ; Fall through into BadLoop

BadLoop:
$81/A3BF A9 00       LDA #$00 
$81/A3C1 48          PHA
$81/A3C2 AF 72 03 80 LDA $800372
$81/A3C6 48          PHA       
$81/A3C7 F4 06 00    PEA $0006  
$81/A3CA 22 02 80 81 JSL $818002
$81/A3CE C5 34       CMP $34   
$81/A3D0 F0 ED       BEQ $ED 
// This hangs forever :(

ValidAreaIndex:
$81/A3E6 E2 20       SEP #$20 
$81/A3E8 A9 00       LDA #$00 
//... clipped for brevity

This code snippet makes reference to another function I'm calling AreaLoadHelper. I'm not posting the code to AreaLoadHelper because it's veering a bit off topic. If you want to see the code for that, it's here. Look for 'Function: AreaLoadHelper() - 801D0D'.

Looking through, it's possible they originally intended for bad location codes to do something more elegant than a hang in this function (early out?). Or perhaps not, if they were sure this code wasn't reachable.

Anyway, changing

$81/A38F C9 54 00    CMP #$0054

to

$81/A38F C9 0C 00    CMP #$000C 

fixes it here. The AreaNumbers for the last two levels are 0051 and 000C, so 0C covers it. The fact that it's the same number as patched above is really a coincidence.

If you were to apply this change and run the game, you would still see the same symptom as before where the screen would fade to black yet no level would get loaded. This is because it gets further in the level-loading code before getting stuck again. It was a very loose spin. I had an unpleasant debugging experience. That's because if you break in the debugger while it's hanging, you're too late. The root cause of the hang was here

// Function: CallAreaLoadHelperArg4 ($81:A33A)
//  Preconditions: An AreaNumber is passed in through address $80:1CC5.
//  Expected result: Validate the AreaNumber.
//    If valid, push the argument '4' onto the stack and then call AreaLoadHelper(),
//    a common code path shared between password-loading usual traversal
//    through the game world.
$81/A33A E2 30       SEP #$30 
$81/A33C AF 0E 1D 80 LDA $801D0E
$81/A340 CF 72 03 80 CMP $800372
$81/A344 F0 2E       BEQ $2E 
$81/A346 AF 72 03 80 LDA $800372
$81/A34A 30 28       BMI $28 
$81/A34C C2 20       REP #$20 
$81/A34E AF C3 1C 80 LDA $801CC3
$81/A352 C9 EF 00    CMP #$00EF 
$81/A355 F0 09       BEQ $09
$81/A357 AF C5 1C 80 LDA $801CC5

$81/A35B C9 54 00    CMP #$0054            ; Load AreaNumber
$81/A35E 90 14       BCC $14    [$A374]    ; If too low, goto InvalidLocation. 
                                           ; If okay, fall through to ValidAreaNumber

ValidAreaNumber:
$81/A360 E2 20       SEP #$20  
$81/A362 A9 00       LDA #$00         
$81/A364 48          PHA           
$81/A365 AF 72 03 80 LDA $800372
$81/A369 48          PHA         
$81/A36A F4 00 01    PEA $0100  
$81/A36D F4 04 00    PEA $0004             ; Push args
$81/A370 22 02 80 81 JSL $818002[$81:8002] ; Call AreaLoadHelper()

InvalidLocation:
$81/A374 C2 30       REP #$30            
$81/A376 6B          RTL                  

Another place where the validation is on the wrong bounds.

So, change

$81/A35B C9 54 00    CMP #$0054 

to

$81/A35B C9 0C 00    CMP #$000C

allowing through both within-Moria area numbers, it works.

It is kind of good password-resuming the last two areas was something superficial like this, and not a deeper problem like a huge swath of level loading being actually not implemented. It turns out, the odds a "not implemented" is low anyway, since that part was written in a reasonable way- i.e., if you can visit an area, you can password-resume to it. They share the same code.

As for the fix since the total amount of changes is small, you could use a ROM patch, but it's even easier as a cheat code like a Pro Action Replay code. Expressing the above changes as SNES Pro Action Replay the codes are

81CBF10C
81A3900C
81A35C0C

These are value changes to ROM code (it is not self modified), so if you're applying cheats in an emulator you don't need to re-start the game to apply them.

Here is a demo of the codes in action

I was gonna post this to GameFaqs but they have this

oh well.

Anyway, you can use the cheat codes in a Pro Action Replay device for Super Nintendo, or any mainstream emulator (tested ZSNES, Snes9x) to unblock the game. Enjoy

April 6th, 2021 at 6:51 am | Comments & Trackbacks (4) | Permalink

This is an explanation of the formats of the password used in the game. I found this information by trying different passwords and seeing what is accepted by the game and what the effects were. Since this process didn't involve a debugger it could have been done on the console, but using an emulator sped this up a lot.

This game has a hugely long password (48 characters.)

Each alphanumeric character is one of

 .BCDFGHJKLMNPQRSTVWXYZ0123456789

That's a '.', the letters of the alphabet with no vowels plus the numbers 0 through 9. This gives 32 choices in total.

The general layout of the password is: (where '.' represents an alphanumeric character)

             Samwise   Merry           Frodo   Pippin    
            [       ][       ]       [       ][       ]  
             .  .  .  .  .  .         .  .  .  .  .  .   
                                                         
                                                         
                                                         
            Legolas   Aragorn          Gimli   Gandalf   
            [       ][       ]       [       ][       ]  
             .  .  .  .  .  .         .  .  .  .  .  .   
                                                         
                                                         
Spawn location              keys              Checksum   
            [ ][         and events          ][       ]  
             .  .  .  .  .  .         .  .  .  .  .  .   
                                                         
                                                         
                             Inventory                   
            [                                         ]  
             .  .  .  .  .  .         .  .  .  .  .  .   

As shown above there's

  • 3 characters for each of the 8 people in the fellowship (Boromir isn't joinable)
  • 1 character for your spawn location
  • 8 characters representing keys and events
  • 3 characters for checksum
  • and a 12-character inventory code at the bottom labeled 'INVENTORY CODE' in the password input screen.

Following goes into more detail for each of these.

Password characters

The alphanumeric password is a convenience (lol) for the user. Internally the game maps each character in a password to a number.
The mapping is this

Character | Value 
------------------
   .      |  0    
   B      |  1    
   C      |  2    
   D      |  3    
   F      |  4    
   G      |  5    
   H      |  6    
   J      |  7    
   K      |  8    
   L      |  9    
   M      |  10   
   N      |  11   
   P      |  12   
   Q      |  13   
   R      |  14   
   S      |  15   
   T      |  16   
   V      |  17   
   W      |  18   
   X      |  19   
   Y      |  20   
   Z      |  21   
   0      |  22   
   1      |  23   
   2      |  24   
   3      |  25   
   4      |  26   
   5      |  27   
   6      |  28   
   7      |  29   
   8      |  30   
   9      |  31  

In the sections that follow, these numerical representations of password characters get used and there is math done on them.

People in the fellowship

For each joinable person in the fellowship there's a three-character code that encodes their level and equipment.

Firstly, if the three character code is all '.' (value zeroes), that character is not in your party. Otherwise yes they are in your party.

The way in which the codes determine equipment is a bit convoluted and broken. The reason I say that is there are some
passwords that are accepted by the game but will either crash the game or cause corrruption while you're playing. The charts and things below describe passwords which are accepted and also don't crash or corrupt the game.

You can find situations (e.g., what if Code3, described below, is less than 16?) where the password gets accepted, the level gets loaded and things appear okay but corruption happens when you go into the menu for example. I reverse engineered what level/items you get in those cases too, and they're accounted for in the source code of my password editor. I'm leaving them out of this document so that these formulas stay neat and concise as they're specified, because those don't follow the rules listed below. If you want you can see source code here for more info on them

So anyway, each person in the fellowship gets a three-character code in the password. Call the three characters in the code
Code1, Code2, and Code3 in order.

For example if the password contained 'B89' then Code1=1, Code2=30, Code3=31 referring to the chart above. Yes, each of
Code1, Code2 and Code3 is a number between 0 and 31 inclusive.

Level is decided by the following:

if (Code1 < 10)
	Level = (Code2 mod 8) * 20 + Code1
else
	Level = (Code2 mod 8) * 20 + (Code1 mod 16) + 10

The 'mod' operator here is modulus. I.e., A mod B is the remainder when A is divided by B.

Armor is decided by the following:

 PW char 2  |     Code2      | Armor                          
--------------------------------------------------------------
. through F |  0 through 4   | If Code3 is even, Cloth Cloak. 
            |                | If Code3 is odd, Plate Mail.   
--------------------------------------------------------------
. through F |  0 through 4   | If Code3 is even, Cloth Cloak. 
            |                | If Code3 is odd, Plate Mail.   
--------------------------------------------------------------
K through P |  8 through 12  | If Code3 is even, Padded Armor.
            |                | If Code3 is odd, Mithril Armor 
--------------------------------------------------------------
T through Y |  16 through 20 | Leather Armor                  
--------------------------------------------------------------
2 through 6 |  24 through 28   Chain Mail                     

Weapons are decided by the following:

PW char 3| Code3 | Weapon        
 ----------------------------  
  T      |  16   | Old Dagger    
  V      |  17   | Old Dagger    
  W      |  18   | Dagger        
  X      |  19   | Dagger        
  Y      |  20   | Barrow Dagger  
  Z      |  21   | Barrow Dagger  
  0      |  22   | Troll Dagger  
  1      |  23   | Troll Dagger  
  2      |  24   | Elvish Dagger  
  3      |  25   | Elvish Dagger  
  4      |  26   | Sting         
  5      |  27   | Sting         
  6      |  28   | Light Sword   
  7      |  29   | Light Sword   
  8      |  30   | Sword         
  9      |  31   | Sword   

The password encoding for level, weapon and armor works the same for each of the 8 joinable characters.

Fun fact: if you enter an only-partially-valid password that includes some configuration for a character (e.g., the string is not all '.'), it permanently adds the character to your party until SNES reset. Even if the password is rejected. This leads to a well-known cheesy trick where you can enter a bad password, press start and hear the "invalid password" noise, then delete it and start the game with all the Fellowship unlocked.

Spawn Location

This is the place in the game world your party will be in after the password gets accepted.
It's a 1-character code.

PW char| Code | Location             
-------|------|------------          
  .    |  0   | Hobbiton             
  B    |  1   | Brandywine Bridge    
  C    |  2   | Farmer Maggot        
  D    |  3   | Ferry                
  F    |  4   | Crickhollow          
  G    |  5   | Tom Bombadil's House 
  H    |  6   | Barrow Downs Stones  
  J    |  7   | Crossroads           
  K    |  8   | Rivendell            
  L    |  9   | Moria entrance       
  M    |  10  | Moria 1 (glitched)   
  N    |  11  | Moria 2 (glitched) 

For the last two Moria locations, the game will include those location codes in the passwords it provides to you when you're in Moria.

However, it won't accept the passwords the next time you start the game 🙁 (Update: unless you have my bug fix described in this post)

Might want to keep a map of Moria, you definitely don't want to do it more than once if you can help it

Keys and events

These control the state of various unlockable doors and questlines. I haven't investigated which bits control what because it wasn't important to what I was trying to do.

Checksum

The checksum exists to stop you from trying random passwords and cheating. It's a way of making sure the only passwords accepted are ones the game has actually given to you, not ones you randomly made up yourself.

However, the checksum is pretty easy to understand if you look at the various passwords it gives you. For example, you'll see that leveling up or changing equipment only changes the first character. And using something in your inventory only changes the third character. And, you know how the password characters translate to character codes and there are 32 of them, and modulus kinds of operations are common and inexpensive for computing checksums.

The first character is the 'party checksum':
partySum = the sum of the character codes of the first two lines of the password
checksumCode = remainder when partySum is divided by 32. (For example, if partySum is 33, the checksumCode is 1.)

The second character is the 'event checksum':
eventSum = the sum of the character codes in the "spawn location" and "keys and events" part of the password
checksumCode = remainder when eventSum is divided by 32

The third character is the 'inventory checksum':
inventorySum = the sum of the character codes in the "inventory" part of the password
checksumCode = remainder when inventorySum is divided by 32

This gives you the first, second and third characters of the checksum in order.

I think they put the checksum in the middle of the password to obfuscate it a little bit.

If you're trying to troubleshoot, know that valid checksum doesn't necessarily mean the password will be accepted. The game sometimes rejects passwords for reasons other than invalid checksum. For example, if you specify an invalid location code like 'Z'.

Inventory

These character codes store your inventory state pretty compactly.
Each item corresponds to 1 bit within a byte. Not all the bits are used, which is why a full inventory's password code looks like "9S9S9S 9S9S9S" rather than all 9s (all 9s means all bits set).

There are 12 inventory code characters in all, which I'm calling code 0 through 11.

For readability the bit is written as a hexadecimal flag.

Item                |Code #| Bit      
--------------------------------    
Tomb Key            |  0   | 0x1      
Moria Key           |  0   | 0x2      
Red Gateway Gem     |  0   | 0x4      
Elvish Book         |  0   | 0x8      
Magic Rock          |  0   | 0x10     

Bottle              |  1   | 0x1      
Lost Amulet         |  1   | 0x2      
Maggot Note         |  1   | 0x4      
Scroll Of Floi      |  1   | 0x8      

Gate Key            |  2   | 0x1      
Moria Key           |  2   | 0x2      
Yellow Gateway Gem  |  2   | 0x4      
Book Of The Ages    |  2   | 0x8      
Gold Piece          |  2   | 0x10     

Jug Of Honey        |  3   | 0x1      
Lost Amulet         |  3   | 0x2      
Old Willow Note     |  3   | 0x4      
Scroll Of Oin       |  3   | 0x8      

Tomb Key            |  4   | 0x1      
Moria Key           |  4   | 0x2      
Gateway Keystone    |  4   | 0x4      
Book Of Mazarbul    |  4   | 0x8      
Gold Pieces         |  4   | 0x10     

Eye Glasses         |  5   | 0x1      
Lost Amulet         |  5   | 0x2      
Note From Gandalf   |  5   | 0x4      
Color Scoll         |  5   | 0x8      
Item                |Code #| Bit 
---------------------------------
Tomb Key            |  6   | 0x1 
Moria Key           |  6   | 0x2 
Green Gateway Gem   |  6   | 0x4 
Bilbo Diary         |  6   | 0x8 
Gold Pieces         |  6   | 0x10

Healing Moss        |  7   | 0x1 
Lost Amulet         |  7   | 0x2 
Letter To Elrond    |  7   | 0x4 
Keystone Scroll     |  7   | 0x8 

Tomb Key            |  8   | 0x1 
Boat Oar            |  8   | 0x2 
Purple Gateway Gem  |  8   | 0x4 
Jeweled Ring        |  8   | 0x8 
Gold Pieces         |  8   | 0x10

Athelas Major       |  9   | 0x1 
Lost Amulet         |  9   | 0x2 
Horn Of Boromir     |  9   | 0x4 
Long Bow            |  9   | 0x8 

Key To Bree         |  10  | 0x1 
Healing Mushroom    |  10  | 0x2 
Violet Gateway Gem  |  10  | 0x4 
The Ring            |  10  | 0x8 
Athelas Minor       |  10  | 0x10

Healing Fruit       |  11  | 0x1 
Lost Amulet         |  11  | 0x2 
Magic Fern          |  11  | 0x4 
Orb of Drexle       |  11  | 0x8 

The inventory codes come from bitwise OR-ing the corresponding bits together for each inventory item you have.

For example, suppose you have the first tomb key and the red gateway gem. This is bit '0x1' and '0x4'. When you bitwise-OR these, you get '5'. Code 5 corresponds to password code 'G', from the chart all the way at the top. So if those two are the only items you have, your inventory code in the password is 'G….. ……'.

For another example, suppose all you have is the first tomb key and the Orb of Drexle. This is bit '0x1' of the first code, and '0x8' of the last. So if those were the only two items you have, your inventory code in the password is 'B….. …..K'.

There's one special case- although there's an inventory bit allocated to the One Ring, the ring is always in your inventory regardless of whether it's encoded in the password or not.

Links

Hope you found this helpful

All this information is used in a password editor I made. That is here
https://github.com/clandrew/lotrpwcheck/

To view this post in text form, it's here
https://raw.githubusercontent.com/clandrew/lotrpwcheck/master/Format.txt

This post is following up from this one where I posted the editor, where someone asked about the information that the editor uses

March 31st, 2021 at 5:25 am | Comments & Trackbacks (1) | Permalink

Finished J.R.R. Tolkien's Lord of the Rings (SNES)

This is an action-RPG based on the book series, pre-Peter Jackson movie IP.

This game has some cool moments and good atmosphere and potential to be good. Still, it was held back by many technical problems. This game ended up being a rabbit hole into something else.

A couple weeks ago, I cleared the last boss, the Balrog using the full party (minus Gandalf, since having him in your party prevents you from beating the boss; also Boromir is E_NOTIMPL) and finished the game but didn't get such a good ending because Merry and Pippin died in the boss fight. They die really easily.
So last Saturday, I booted up the game with the intention to resume at the boss fight, attempt it again and keep them alive.

However the password I had written down was rejected by the game. I swear to goodness I wrote it down correctly. I went upstairs to my computer, reproduced the situation with an emulator. It turns out, the game will indeed give you invalid passwords and that's what happened here. So I went about trying to figure out how to "fix" my password.

The password system itself involves encoding a bunch of the game state in a certain way with a checksum. This game is a bit unusual in that there are no saves to the cartridge, it hashes together literally all the state into a 48-character-long password. It took a bit of effort, but I figured out how to derive the password. From there, how to un-glitch my password and preserve the progress I had (items, character stats, door open+close state) while letting it be accepted by the game. With this, I was able to re-attempt the boss fight and get the good ending!

After trying many different passwords looking for patterns, I cracked the password algorithm. It was not too much more work to put it into a program in case other people run into the same issues.

I posted the program to Github https://github.com/clandrew/lotrpwcheck/ .

As for the ending itself it was pretty cool, there is a scene where you meet Galadriel and she shows you the mirror. Although they never released a Vol II for SNES, I can see the next one picking up where this one left off.

September 5th, 2019 at 1:49 am | Comments & Trackbacks (4) | Permalink