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

Finished Arcana (SNES).

Play as Rooks, an orphaned magic card user who needs to stop an evil empress vying to take over the kingdom. Rooks also wants to live up to his late father's legacy.

Turn-based JRPG, Wizardry-like, with "cards" being a prominent visual motif and somewhat gameplay motif. Unique qualities: no backtracking, death of anyone in your party == game over

The use of cards in the gameplay would lead you to think the game has a combat system way more evolved than the old "Fight Magic Item Flee". It does not.

There is a rock-paper-scissors-style elemental system. The game is balanced such that you can ignore it. There are also four pokemon ("Spirits") which act like party members except disposable and only their magic is any good.

Pop quiz: magic spell called "Attribute 6". What does it do, take a guess? Bonus: how it is different from Attribute 5.

I think people might not play this game any more because of the enemy system. What enemy system? Random encounters. How many? A lot. It has one of the worst grinds. Find enclosed: random encounters every two steps in the map, or on simply a 90 degree turn. If not for the in-game map it would have been a big problem. Although there's items and spells to hightail it out of a dungeon, you always enter a dungeon from the very beginning.

Lack of checkpointing is a problem for one of the largest areas called "Stavery Tower", a twelve-floor maze. You can't save while in a dungeon, not even a save-to-be-deleted-on-resume (those are not popular on SNES platform anyway). So you will need to book one to three hours per game session. Alternatively, you can leave your SNES on and hope there isn't a power outage, or use a piece of technology which rhymes with asdflemulator.

Still, the first 5 minutes and the last 30 minutes were Awesome. This game has a great soundtrack and visual style with a lot of character. The final boss concept is extremely cool. This game, you can tell what they were going for.

June 2nd, 2020 at 2:20 am | Comments & Trackbacks (0) | Permalink

Finished Final Fantasy Legend (GB)

This is a spin-off to the Final Fantasy series and related to the Sa-Ga series made by Square Enix.

The whole thing with Legend is it's "a lot more epic than it seems like it should be". See the games I remember Game Boy original were fairly light in subject matter, emotional power and how the story is delivered. But, this game:
• Levels with a scary unkillable monster
• Real actual character death
• An ending sequence where you fight the creator of the universe
Confirmed the creator of the universe is wearing a top hat
It turns out the composer for this game is also Nobuo Uematsu the same as mainline Final Fantasy series except for XIII. If you listen carefully you can hear similarities to the rest of the series' music.

For the gameplay, you have the flexibility of choosing all characters in your party and their type (Human, Mutant, Monster). The game suffers from some balancing issues which make certain bossfights far, far disproportionally harder than others.

There is apparently an homage to Legend in Final Fantasy XIII where (spoiler) Orphan can be killed instantly by Vanille's Death spell. It is not 100% guarantee but there is a chance particularly if staggered. In the Final Fantasy XIII Scenario Ultimania book it says outright this was an intentional reference to Legend.

November 22nd, 2018 at 9:24 am | Comments & Trackbacks (0) | Permalink

After a couple repairs and lots of futzing with cables... life!
This is the SHARP x68000, a vintage computer from Japan.

If the name sounds familiar- it runs on a Motorola 68000 processor. This vintage computer was never sold outside of Japan due to very strict export regulations in the 1980s which included this system. Inside Japan, there were many notable video game franchises that debuted and/or gained prominence on this platform

It has an OS very much like DOS.

Sadly my Lagoon system disk needs to be replaced, but this is it booting up "Xak: The Art of Visual Stage".

September 26th, 2016 at 7:59 pm | Comments & Trackbacks (0) | Permalink