Tree Warp

Tree warp, or Dynamic Sprite Spawn Overflow (DSSO) for the glitch in general, is a strong contender for the coolest glitch. I've explained it before using the Agahnim 2 stal, but for this explanation, I'll be focusing on tree warp.

Sprite spawning

There's a lot to discuss with how sprites spawn, but let's focus on the basics for this. The basics are all we really need. There are 16 active sprite slots in WRAM, and there are 3 ways to spawn sprites:

Static spawning

is how sprites are spawned in the underworld. Every room has a list of up to 16 sprites, and they are all loaded into the active sprites array when the room is loaded.

Semi-static spawning

is how sprites are spawned on the overworld. Every overworld area has a list of sprites, but it doesn't have the same 16 sprite limit in ROM that the underworld does. Instead, sprite references are first loaded into a buffer where they don't actually run code. When you get close to where a sprite is placed, then it is pulled out of the buffer and put into the active sprites array, assuming there's room. If there's no room, it just doesn't spawn.

Dynamic spawning

covers everything else. When some routine wants to spawn a sprite when an area has already loaded or under specific circumstances, the sprite's ID is fed to the routine SpawnSpriteDynamically.

When a sprite is spawned, no matter what method, it undergoes certain preparations to set its coordinates, AI pointers, etc. This happens exactly once, but who performs this prep depends on the method the sprite is spawned with.

Dinomaniac spawning

As mentioned before, there are only 16 slots for active sprites to be in. To make sure there's room, SpawnSpriteDynamically starts a search at slot 15 for a sprite that is totally inactive and dead. If it finds such a slot, it branches ahead to set the spawned sprite's properties and cache some information from the spawner to be used later.

If there was no room, then our index register hits −1, which for an 8-bit two's-complement is $FF, equivalent to the unsigned value 255. If we go negative, the search loop is broken and the CPU returns with this value. And that's all the spawn routine does when there's no room. Handling the case of "there's no room, buster" is left to the whatever wanted the sprite to spawn in the first place.

And handle that they do. For the most part. Almost every call to this routine is followed by the instruction BMI, which means, in some sense, "Go here if the last number we saw was negative, otherwise just ignore me." A couple are followed by the opposite, BPL, which means to follow where it's pointing when the number is not negative. It's the Master Sword, okay. The Master Sword, scourge of evil, was programmed by a got dang intern. But at least that intern had the sense to include the failsafe used everywhere else.

Arbor Day 2019

The same can't be said for whatever intern coded the talking tree sprite. These guys break so many rules. First off, they use 3 sprite slots. 1 for the mouth, 2 for the eyes. Secondly, they have the persistence bit set. You see, on the overworld, when most sprites go off screen, they have the decency to deactivate themselves and return to the buffer. This frees up space for other sprites to spawn. Not talking trees. Once those 3 sprites are in their slots, they grasp onto them until you transition. If you visit both trees in the Village of Outcasts, you now have tree rudely hogging 40% of the slots.

And finally (for the sake of time), trees spawn their eyeballs recklessly. Only the mouth is a semi-static spawn. When it's spawned into the main list, its prep routine performs 2 calls of SpawnSpriteDynamically, one for each eye. What it doesn't do is check for success. Talking trees are of a small handful of sprites that assume that there will always be a free sprite slot. Of that group, it's probably also the most careless to have made that assumption.

Tree warp specifically happens when there is exactly 1 free sprite slot; i.e. the mouth takes the last available slot, leaving no space for either of the eyeballs.

The Overflow

What exactly happens when this assumption is made depends on where it was made, but in every case, just spawning a sprite is not good enough. Now that the sprite is spawned, subsequent routines continue prepping it in whatever ways are needed. There's just one itsy-bitsy problem: our index is out of whack. Remember: failure is indicated by an index of $FF; that means we're waaaay out of bounds, and whatever we do will be operating on the invalid sprite slot 255.

That failsafe is important. Most sprite data is near other sprite data, so a value intended for one property, if using an out-of-bounds index, will be written to an unrelated property. These are mostly inconsequential places, really. Mostly. Offsetting 255 into most of the properties gives us a write to some timer, or the stripes DMA buffer. You might cause a jerk in some sprite's behavior, but nothing that big. The DMA buffer is just going to be updated before it's needed, so it doesn't cause any issues whatsoever.

The interesting write we care about is the X-coordinate low byte, which writes to the array at $0D30. With an index of $FF, this ends up at $0E2F. That's the Fth sprite slot!

The X-coordinate is loaded from the address $01. When successful, the dynamic spawn routine will have set this address and several others with a copy of important properties of the sprite or overlord that spawned it. But when the spawn fails, it takes some investigative work to see what last modified these addresses.

Tracing backwards, the last time these were modified was during the sprite prep routine for the tree's mouth. It took the sprite ID and called JumpTableLocal. In short, this routine uses a value to pick from a list of routines and finds the appropriate one. In doing so, it puts the 24-bit address of the routine we requested in $00.

In the case of tree warp, the routine we jumped to is SpritePrep_TalkingTree, located at $06:904A. So we have $4A in address $00, $90 in $01, and $06 in $02. There's also, get this: Link's layer in $03.

You're getting grabby

We are writing $90, the sprite ID for wallmasters, into memory that holds a sprite's ID. It doesn't matter what sprite was in that slot before, it is now a wallmaster. It's really hard to pinpoint why the wallmaster grabs you right away and instantly fades to black, but the most common scenario seems to, once again, involve the tree. This time, it has to do with how trees never go inactive.

Let's quickly explain how wallmaster grabbing works: If the wallmaster is alive, it doesn't let go of Link. If it's active, it can execute its code. If the address $0D9x is nonzero, then Link is considered grabbed. Got it? Good.

Simply by how overworld spawning works, it is very likely that a tree will be in sprite slot 15. This means sprite slot 15 will already be set as active, permanently at that. For some reason that I'm too scared to learn, the routine outlined above also stores each coordinate in another address. In the case of the X-coordinate, this address is $0D9x, the same array of values used by wallmasters to indicate that they have grabbed Link.

So that means we're not just spawning a wallmaster. We are spawning a super wallmaster. One from which there is no escape.

In cases where there is not an eyeball as the last sprite, it seems the wallmaster just behaves normally. If it's offscreen, it will despawn to free up space, but, being a dynamically spawned bastard, it will find no home in the buffer. If it's onscreen, you may catch a glimpse of it flying away. I've seen it only once, but it was a magical moment.

When things go terribly wrong

Tree warp works when only 1 sprite slot is free before spawning the mouth. When 2 slots are free, things go really really wrong and the game crashes.

This crash is purely bad luck with ROM data. If 2 slots are free, that means the mouth takes one and eyeball 0 takes the other. So eyeball 0 spawns successfully, in the correct slot, and due to the prep that happens in SpawnSpriteDynamically, we now have a new value in $01: 3. Eyeball 1 ends up overflowing, writing 3 to the last sprite slot.

When it comes to sprite IDs, 3 is particularly evil. There isn't actually a sprite with that ID. That slot in the sprite routines table just contains a pointer to $0000. That's the same $00 we were storing scratch data in, but now we are executing it as code. And because it's consistent from the previous routines, I can tell you exactly what the CPU is doing:

And that's where Mr. Smith hits the fan. BRK is an instruction inherited from the WDC 65c816, which the SNES's Ricoh 5A22 is based on. The instruction is meant to be used in a debugging environment on a computer's operating system to track down bugs and errors. That obviously is of no use for a cartridge game running on a console, so the developers replaced the break vector with $FFFF, just a filler value. The CPU doesn't know that though, so it follows it blindly. The byte at $00:FFFF is $82, which is the byte for a branch long instruction (BRL). But this is the end of the bank, so the operand of this instruction is read by wrapping around back to $0000. Data we executed as code is now being used as a relative pointer for the CPU to follow. It's telling us to branch forward $0368 bytes and resume execution at $036A. This address is related to lifting tiles, and it will hold a value based on the last liftable tile you touched. Long story short, there's no predicting what happens next.

What else can we spawn?

You're in for a challenge if you want to overflow any of your other spawns. I will cover the ones that are reasonably doable.

In the Village of Outcasts, where the most famous trees reside, you can spawn a vulture by pulling the Thieves' Town gate with every sprite slot filled. This one may be slightly easier than tree warp, but all it spawns is a really ugly bird.

The next easiest DSSO to perform is the digging game. Not even a perfect TAS can dig up enough prizes fast enough to fill the sprite list unassisted. I've tried. Although, with a little help from Qirn, you can bring a cucco down to the digging game and smack it silly until it summons a swarm. For this DSSO, the sprite spawned is based on your X-coordinate. You'll get sprite $00 (crow) on the west half of the screen and sprite $01 (vulture) on the east half.

With perfect timing, you can mess with the clone animations in the Agahnim 2 fight and have them fill every slot. If the main Agahnim spawns the phantom Ganon then, he'll end up creating a hopping bush stal instead (sprite $D3). This is the original DSSO discovered, during the making of the 100% Glitched TAS.

I've not actually seen it done, but it should be possible to bring enough sprites on screen on Death Mountain so that when the old man tagalong turns into a sprite, he DSSOs himself. In this case, you just softlock your game. The old man sprite is what gives you control of Link by ending the cutscene. It's sort of like returning him in the rain state without an overlord, but slightly less funny, because there's no geezer wandering off into infinity.

Was it really that stupid?

Except for the tree warp, everywhere else that a dynamic sprite spawn overflow can occur is pretty difficult to pull off. For the most part, it's a fair assumption that there would be room somewhere. After all, if that assumption were bad, it wouldn't have taken 27 years for this glitch to be discovered. Actually it was just under 27 years. I found this on 12 November 2018, 9 days before LTTP's birthday. It also only happened during trial and error optimization of a TAS, and it was difficult to reproduce at first.

Summary

For some stupid reason, the talking tree is composed of 3 permanently active sprites—1 mouth, 2 eyes. The eyes are spawned dynamically by the mouth. When spawning sprites dynamically, the caller of the routine is left with the responsibility for adding a failsafe when all slots are full. Trees don't.

If the mouth spawns into the last available sprite slot, the eyes will end up in slot $FF. Part of these invalid writes loads a value from scratch space to use for the X-coordinate. The value it loads ends up being part of the tree's spawn routine address ($90), and it gets written to the last slot in sprite ID. This is the ID for a wallmaster, which ends up inheriting the properties of whatever sprite was in that slot. In the consistent set ups, this sprite is part of the other talking tree in Village of Outcasts, so the wallmaster is always active. And by sheer coincidence, it spawns immediately in the "grabbed player" mode.