AGDQ "Mew under the truck" Writeup

Mew under the truck
=============================
Save file (didn't release early because lazy): https://mega.nz/file/U9V2zZrA#9P-ehDdHExkZQFAnLmKFOIxNuGXcsnDrOSDA_RCbc7U

Pre-ramble
=============================
The idea first started about a year ago. I posted the idea and my initial code on the GCLF forums (http://forums.glitchcity.info/index.php/topic,6638.msg197210.html#msg197210), but I scrapped the project away and began working on other things.

A year later, I thought it would be cool to show it off at a big event like AGDQ. My initial plan was to have the save start at the truck, but then Shenanagans_ suggested showing how to get back on the S.S. Anne, then preceeding with pushing the truck to reveal Mew. This made the code a bit harder, but it was worth it in the end.

Technical Terms
=============================
First off, if you don't know other numeric bases, then read something up on that (specifically binary and hexadecimal).

This explanation will use many technical terms. To clear things up, here are quick explanations of them:
- $: $ will indicate a hexadecimal value. (0x is the standard notation for a hexadecimal value, but $ is used in the RGBDS (Rednex Game Boy Development System) compiler)
- Byte: (Partially copied from Wikipedia) A byte is a unit of measurement of the size of information on a computer or other electronic device. It is composed of 8 bits, and can hold values from $00 to $ff.
- Address: A memory location in the GameBoy indicated by one 16-bit value, or two bytes. An address can be for ROM, or the many types of RAM.
- Pointer: A set of two bytes which tell the game the address of the data to use. For example, the game would use a pointer to the move data in order to find the attack power of a move.
- Tile: A 8x8 square composed of pixels. Tiles are stored in memory like a grid.
- Metatile: A cluster of tiles used to create a bigger tile in the game's memory. For example, the Pokemon Center sign is a metatile composed of 2x2 tiles.
- Block: Composed of a 4x4 metatile, this is the building block for overworld maps.
- Video RAM/VRAM: A special portion of memory in the GameBoy that handles data related to the display, such as the internal tilemap and the tile data.



Before I go on about how the setup works, there are three portions of memory that I'd like to explain in simple terms. They are:
- Map Script Pointer: Every overworld frame (2 frames while in the overworld without any menus open), the game will run code at whatever this value is. This handles stuff like trainer engaging, or special scripts like the Oak Cutscene in Pallet Town. By setting this to a value that points to WRAM (Work RAM), one could run custom code every overworld frame. This is the foundation of the whole setup; without this, it would have been much harder to create this.
- Map Text Pointer: In short, this tells the game where the text for NPCs and signs on the current map is located in ROM. Like the Map Script Pointer, one could create a custom text box for an NPC. Because there are multiple NPC and signs, the text pointer points to a table of multiple pointers, where the game uses the internal sprite ID to find which text to print.
- Bit 7 of the Tileset: This bit is completely unrelated to the tileset. It's used as a flag to determine if the game is entering a map from the CONTINUE option on the screen, to avoid re-loading map data when it's unnecessary. In the setup, this is used in order to keep the Map Script from being re-written upon changing maps.

Explanation
=============================
The save starts out in Vermillion City, near the Sailor guy. Right now, our map script pointer is set to an address in WRAM, to allow for later exploits.

(Technical note: The reason I can't set an invalid value to Vermillion Dock's Cur Script is because it flat out doesn't exist. For Vermillion Dock's Script, the game uses event flags to control scripts such as the boat leaving)

Our first goal is to get on Vermillion Dock without losing the custom map script. As mentioned earlier, setting bit 7 of the Tileset would prevent new map data from loading, allowing us to enter the Vermillion Dock and continue on with the exploit. However, there are some problems with that. The biggest problem is the game thinks that we're on tileset $80, which is obviously an invalid tileset (the game doesn't load garbage to Video RAM because the tiles are loaded using a pointer in WRAM, and not the value of the tileset). Here is a list of the uses of the current tileset relevant to the setup, and the problems caused with an invalid tileset:
- Determine if surfing is allowed.
	- Problem caused: As the current tileset isn't in a tileset with water, we can't surf.
- Determine which function to use for checking for map warps. There are two functions:
		- Function 1: Check if the player is standing on a warp tile (like a door tile) before looking if the player coordinates match a warp entry.
		- Function 2: Check if we're facing the edge of the map.
	- Problem caused: While the overworld (outside) tileset uses function 1, most other tilesets default to function 2. This requires us to adjust the map height in order to trick the game that warping is possible. However, by setting the Map Height too soon, upon loading the game, the bottom row of blocks won't be drawn on screen.

To solve these two problems, the custom map script will only modify the tileset and the map height if the player is surfing. This solves the surfing problem as it allows surfing, and solves the map height problem as the blocks have been already loaded in memory, so the map would look perfectly normal.

After surfing, the player enters Vermillion Dock. Because bit 7 of the tileset is set, the game will only load the internal map ID without loading other necessary map data. This is a problem, since the map would look like a bunch of garbage, and bear no resemblance to Vermillion Dock. Luckily, we can fix this with our custom map script. This is done with these steps:
- Check if the current map ID is Vermillion Dock.
	- If it isn't, run the Vermillion City Script.
	- Otherwise, continue running the custom code.
- Firstly, black the screen palette so the garbage map wouldn't be shown
- Secondly, load the actual map data for Vermillion Dock
- Thirdly, write the new map script pointer relevant to the Mew Code
- Finally, run the rest of the "EnterMap" code, which will run additional code and then execute the overworld loop

Now, to an unknowing viewer, this seems perfectly normal. However, the custom map script is secretly running in the background, doing the following checks in order before moving the truck:
- Check if Strength was used
- Check if the player coordinates match either the left side or right side of the truck
- Check if the bottom-left tile of the 2x2 metatile in front of the player matches the tile if the player was facing the truck
- Check if we've moved after all the above checks have been succeeded (this is to prevent pushing the truck by simply moving to the correct location)
- Check if we're facing the direction that would have the player face the truck

Once all those checks have been fulfilled, then comes the actual moving of the truck, with the following steps:
- Create a copy of the truck in the section of VRAM designated to sprites
- Change the player's sprite picture to the "moving" picture to simulate the player in a pushing motion, then wait one frame for it to be shown on the screen
- Disable overworld sprite updating to freeze the player sprite in the pushing motion
- Write data to the game's sprite buffer (which is copied to actual sprite data every frame) which will make the truck appear on the same spot as the truck on the map:
- Copy a "blank" tile to sprite VRAM. This is necessary as one of the four colours a sprite can have is transparent, so we need to copy an additional set of blank sprites under the truck in order to make the truck look "normal"
- Write more data to the game's sprite buffer which will write the blank tiles directly under the truck
- Adjust the truck's position on screen if the player is facing right
- Modify the sprite palette so the truck doesn't appear different from the one on the map
- (Temporarily) remove the truck block on the map
- Play the Boulder sound and animate the truck moving left/right, depending on the facing direction
	- (Technical note: the reason the truck moves two tiles instead of one is because there isn't a block with only half a truck, and another block with the other half of the truck)
- Save the player's facing direction when the truck was moved for later, as well as the address of the truck block on screen
- Redraw the truck block on screen, relative to where the truck was pushed
- Hide the truck sprite

Now, we need to show Mew on screen. Unfortunately, the reasons for some of the stuff I did is all fuzzy, so I can't really explain much here. I know that the code could be optimized but I didn't want to mess with the code after it was done.

So, after the truck is pushed, the Mew sprite is created with the following steps:
- Create a copy of the generic monster sprite into the VRAM slot reserved for sprites that have only one facing picture (like item balls). This was necessary at the time, as I couldn't figure out how to make a sprite look in a set direction like trainers do, and if Mew were to face another direction, it would turn into another sprite as Vermillion Dock was never meant to have a generic monster sprite on screen (the reason it's located in VRAM is that it's a remnant of previously loaded sprite data.
- Enable overworld sprite updating (actually irrevelant and doesn't do anything)
- Write the number of non-player overworld map sprites to one (so the game will handle Mew's sprite)
- Write the sprite ID to overworld sprite data (overworld sprite data is a section of memory that handles various attributes of overworld map sprites. It is converted to internal sprite data every frame and copied to actual sprite data)
- Write the coordinates of the Mew sprite
- Prevent Mew from moving
- Set the "sprite slot" of the Mew sprite to a non-facing sprite to prevent turning.

Now, we have to animate the boulder dust:
- Disable sprite updating (enabled earlier)
- Modify the player's absolute x coord (pixel-wise) so that the boulder dust will appear to come from the end of the truck
- Run some code which does the boulder dust
- Fix the player's absolute x coord to what it was before animating boulder dust
- Enable sprite updating

Finally, we modify the map text pointer so that it runs custom text, and the script pointer so that it does nothing.

The player will then talk to Mew. The custom text will print the "Mew!" text, then run some custom code:
- Write Mew's internal index number to a special variable which will start a battle with the index number of the Pokémon contained in it
- Play and wait for Mew's cry
- Set the level of the Mew to be 5
- Write another map script pointer, which points to more custom code that will clean up after the battle is finished.
- Set bit 7 of the tileset to prevent the map script from being overwritten

The battle starts with Mew, and it is finished in any way possible. However, the map has refreshed to its original state, which means we have to fix the overworld map so that the truck stays where it was pushed. Since the custom map script is still in memory, it is executed to:
- Clear the Mew sprite from memory
- Write the truck block to where it was pushed. The address of the truck block that was saved earlier is used here.
- Clear the address of where the truck block would normally be. The saved player facing direction is used here to determine the location of the normal truck block, relative to the location where the truck block was moved.
- Finally, set the Map Script Pointer to the regular Vermillion Dock script.

Doing this setup at home.
=============================
Unfortunately, I didn't create a setup to store this code in memory. stump (twitch.tv/stumpdotio) had a save flasher which he used in order to flash the save which had the code stored on using an emulator. If I have the motivation, I may create a setup so you could fool your friends (Kappa), but for now there isn't a setup.

Special Thanks
=============================
The people who worked on the pokered disassembly - Without the amount of documentation they wrote, I wouldn't have been able to create this code
stump - for having a save flasher so I didn't have to create a bootstrap to write the code