Post by happy_mario

Introduction

After my ACE TAS I was looking for something more straight-forward as a change of pace, more optimizing and saving frames rather than storyboarding and assembly programming. I settled on Super Mario Bros. because it was an entirely different problem, different platform, different genre, and different kinds of optimizations where every frame's input is important (compared to games like Pokémon which are about overall routing and luck manipulation but individual inputs are not precise). It is also known to be very well optimized already, so it's a good benchmark for how well you're doing in your optimizations.

The run I ended up saving 45 frames compared to the current one, saving 21 frames in World 1 using a better power-up route, another 21 frames in 4-4 by optimizing the wall clip and making an earlier frame rule, and 3 frames in 6-4 which the current movie lost to lag frames. There are many more small optimizations in this run, but none of them ended up saving anything due to the frame rule.

Tools

The first thing I noticed was that my optimization methods used for previous submissions (i.e. running several parallel game states at each point to ensure some of them always have favorable RNG) just won't work here, movement optimizations in SMB are too variable and have a large fanout. So I needed to devise a new set of tools, specifically for this game: Instead of running the game in an emulator, I analyzed the code (using Doppelganger's disassembly) and extracted a simplified model of Mario's movement. It only tracks relevant values for Mario's movement in relation to the static elements of the level (all enemies are ignored), and allows for a simplified but way faster emulation. With this simplified model, you can do an exhaustive search over all possible movements to determine how to get to a desired goal state optimally. E.g. it can determine what the optimal sequence of inputs is to get up to speed from a standing position, how to clip into a wall optimally or how to perform the flagpole glitch. It can't just solve entire levels start-to-finish though, the search space is just too large, plus enemies might get in your way. TAS game play of SMB naturally consists of small sections of precise movements, with large sections of cruising along at running speed in-between, and the tool is good for optimizing these precise movements individually.

Memory consumption really is the biggest limiting factor with this approach, even with each state only taking up ~10 bytes, it's hard to fit more than a billion states into the memory of your standard home computer. Of course you could upgrade your memory or buy cloud computing resources, but that only gets you so far as the number of states tends to grow exponentially. A way more effective strategy is to put more smarts into the software instead, only considering relevant states in the first place using heuristics. Using some precomputation go create fairly accurate heuristics, I managed to fit most optimization problems into memory.

You can find the source on GitHub. Usual caveats apply, I wrote it purely for myself to use and it may be rough around the edges.

Optimizations

The second thing I soon realized was just how well optimized SMB really is already. In the majority of cases, the optimal movement I computed was only slightly faster than the movement in the current TAS, or exactly the same. On the one hand this was useful, it helped validate the model I used for Mario's movement and I discovered some bugs by comparing my results to it as a reference. On the other hand, it meant that there will be not much of an improvement possible, especially since SMB's 21 frame rule will nullify virtually all individual frames saved through better movement. The reason this submission is a warpless run and not any% is that as far as I could see, there is nowhere to save even a single frame compared to the current any% run. Does this mean the current any% TAS is perfect and will never be beaten? No, it's always possible to discover new strats which nobody has found so far; it only means that you can't improve it by pure optimization without coming up with something new. So big props to HappyLee for achieving incredible levels of optimization with what I presume is manual inputs and deep knowledge of the game mechanics.

A note to HappyLee

Creating this run has led me to really appreciate the amazing job you've done in the current SMB TASes. I only learned about that you're also working on a warpless TAS a few weeks ago in the comments of the recent "all items" movie, when I was almost done with this run. I was not planning to preempt you with this in any way, and the fact that this run contains improvements also hinted at in the "all items" TAS is a case of multiple discovery. In fact I'm happy to hear that you have more improvements up your sleeve, and I'm looking forward to seeing your submission and specifically the improvement in 8-4 you were hinting at. At least I'm fairly confident the improvement in 4-4 is new to you (considering it's not in the "all items" TAS), and I'm glad this submission will contribute to even faster runs in this way if nothing else.

Detailed Game Mechanics

During the creation of this run, I learned a lot about the inner workings of SMB, which I couldn't really find explained anywhere, so here are some notes for posterity.

General Movement

SMB uses an acceleration-based movement model, where the player inputs control the direction of the acceleration acting on Mario, which in turn changes his velocity. The magnitude of acceleration has three possible values, mostly depending on how fast Mario is already moving. Additionally, acceleration is doubled when Mario is not looking in the direction he is moving. This is likely done to allow faster deceleration, but can be abused for acceleration as well. Mario has a max speed with applies to moving both left and right, for running (2.5 pixels/frame),walking/swimming (1.5 pixels/frame) and walking underwater (1 pixel/frame). Acceleration, velocity and position all have fractional amounts ("subpixels") to make Mario's movement appear smoother and allow for finer control.

Interval Timers and Frame Rules

The 21 frame rule is one of the most infamous features of SMB when it comes to speedrunning, but only few people know why it exists (I for one didn't before looking into it). It is born from the solution SMB chose for how to do timers. Timers are fairly simple, you set a timer, it ticks down by one every frame, and you check when it reaches zero to perform a timed action. The problem is that the NES is an 8-bit system, so your timer can only count 255 frames (~4.25 seconds) before overflowing, but you want to be able to have delays longer than that. The solution SMB chose are interval timers: the timer only ticks down every 21 frames (this is controlled using an ordinary timer), which allows to measure far longer durations. The number 21 itself is arbitrary and was likely tweaked during development to achieve the desired pacing of the game. Interval timers are used in many places throughout the game:

Time until an enemy does certain actions (like a Koopa shell coming back to life)
Time until a multi-coin brick runs out of coins (it's not actually a fixed amount, you get more if you hit it quicker)
The amount of time Mario is invincible after being hit
The amount of time Mario has star invincibility
The amount of time a level intro or game over screen is shown for
Time until the title screen demo starts playing
The amount of time after the level ending cutscene until transition to the next level starts

Most of these are irrelevant for a speedrun, except the last one. The next level starts based on the interval timer, which means that depending on when the next tick of the interval timer is when you finish the stage, you may need to wait for a longer or shorter amount of time. This is commonly known as the "frame rule" of SMB: time can only be lost or gained in multiples of 21 frames in each level. Improvements only make a difference if you manage to reach an earlier interval timer tick, otherwise you end up just waiting longer at the end and begin the next level at the exact same time. Some events don't follow the frame rule though, notably:

Collecting powerups or taking damage stops all timers from ticking for the duration of the animation
The timers don't run during lag frames, so they are not affected by the frame rule; any lag frame costs a frame no matter where it occurs
Since the movie ends before the interval timer comes into play for the very last level, 8-4 is the only level where individual frames matter

Screen Scrolling and Loading

The screen generally scrolls as Mario moves right trying to keep Mario in the center of the screen, but it can be manipulated using certain actions. In SMB, the screen can never scroll left, only ever right. When a level starts, the entire level is not loaded into memory at once, instead only the first part is loaded, and new parts are loaded as the screen scrolls right. The screen position also determines when level objects (like enemies or event triggers) spawn, so manipulating the screen position can be used to spawn objects sooner or later. Some common ways to manipulate the screen position are:

Colliding with a block: in addition to nullifying your speed, it also disables screen scrolling for 16 frames, allowing you to adjust your relative position for a brief moment.
Being pushed out by blocks directly changes Mario's position, effectively changing the relative screen position. This is what happens during wall clips.
Moving left will not scroll the screen left, therefore changing the relative screen position.

New chunks of level are loaded every 32 pixels of screen scroll, loading 2 columns of blocks at a time. The load itself happens in 8 phases, spread out over 8 frames to avoid lag spikes while loading. The loading of enemies and events is largely independent from loading the blocks of the level, but they can influence each other's timing slightly. One of the phases of loading level blocks (phase 7) is special, as it stops objects from being processed, so it can delay object spawns for an extra frame when aligned so that new columns are loaded the frame before the enemies would load. Additionally, collecting coins stops the processing for a frame, can be used to extend phase 7 for an extra frame and delay enemy spawns even more.

The Flagpole Glitch

The flagpole glitch is a well-known time saving trick in SMB during the end-of-level cutscene. At the end of each (non-bowser) level, a cutscene plays which has multiple stages, in this order:

Mario slides down the flagpole
Mario enters the castle
The remaining time counts down and adds points to your score
the flag is raised (even for large castles where you usually can't see it)
fireworks go off
the next level begins

Each of these phases has conditions when to switch to the next phase, and the flagpole glitch abuses these to trigger faster by setting up Mario's position when hitting the flag. One of the end conditions for the flagpole slide is (that is never used in normal gameplay) is that if Mario's Y position is at least 0xa2, the phase ends immediately. My assumption is that this exists because the flagpole slide was supposed to look differently initially, where the flag is only raised while Mario is sliding down, so it may end up in different places depending on where Mario hit the pole, but they either changed their minds later or messed up the implementation. The Y position 0xa2 is partially inside the base block and therefore hard to get to (for non-TAS runs), but it skips the flag lowering animation altogether and saves significant time.

For even more time savings, the second phase where Mario walks into the castle can be cut short as well. The end trigger for that phase is very simple, it ends as soon as Mario collides with something on the right. One of the blocks of the castle is actually solid, and that is what Mario usually collides with when entering the castle. However, by hitting the flagpole at a height of at least 0xa5, Mario collides with the base block instead, ending both the first and second phase immediately and saving even more time. This is also sometimes called the "full" flagpole glitch (as opposed to the "half" flagpole glitch where only the first phase is skipped). However, due to how jump heights happen to align, it's not actually possible to hit the flagpole at the right height when just standing in front of it, it needs additional help or trickery. These tricks that can make the full flagpole glitch work come in three main varieties:

Using an enemy to bounce off of to hit the right height
Clipping into the ground and therefore jumping from a lower-than-normally-possible position
Scrolling the screen far enough to the left to cause Mario to screen wrap and collide with a block on the left side of the screen instead

All these options can only be used effectively in specific situations, and setting these situations up is one of the main aspects of an SMB TAS.

Level Comments

1-1

The first level is special in that it is the only level where going through a sub-world actually saves time.

It is also infamous for antagonizing TASers by being exactly 1 frame off a faster frame rule, with no hope in sight for ever getting it.

1-2

The current run movie collects a power-up at the start of 1-2, but it turns out collecting it later is actually faster and saves 21 frames over the course of World 1.

During the underground section, I intentionally slowed down twice for entertainment purposes, so the section is 2 frames slower than it could by just holding right.

Fun fact: When stomping on two Goombas on the same frame, you'd expect to get 100 ad 200 points, but you actually get 100 and 400 points. The reason is that in addition to the counter that awards progressively more points, there's also a timer that awards even more points if you hit them in quick succession. However, that timer is only ever increased by one frame for each bounce, so unless you hit multiple enemies at the same time you'll not see it. I suspect it's a remnant from an earlier design of how stomp chains work which they ultimately replaced by the simple counter method.

Whether you bounce on or get hit by an enemy only depends on your vertical speed (in most cases, I'll get to that later): if you go downwards (with at least 1 px/frame), you bounce. It doesn't matter how your hitboxes intersect. This allows bouncing on enemies from seemingly impossible positions like the Koopa at the end of 1-2, and is used to do floor clips in future stages.

Fun trivia: The end of this level (and all other underground or water levels) is literally the end of 1-1, as in it actually loads 1-1's level data. If you're wondering where the piranha plant comes from since that's not part of 1-1, it actually is, all pipes have piranhas in them, only that 1-1 specially prevents any from spawning.

1-3

You collide with moving platforms from the bottom only when you hit the bottom of their hitbox, if you align your jump right and skip this window, you can just go right through them.

The power-up is conveniently located to collect it without slowing down much by grabbing it through the block from below.

It's important to not collide during the power-up collection, as it would change the screen position and make the Koopa for the floor clip spawn later.

Bouncing on Koopa Paratroopas is different from most enemies, in that for one you can bounce off of them while moving upwards as long as you hit it at the top (this is not possible with normal Koopas and most other enemies), and bouncing on them doesn't increase your bounce counter, so subsequent bounces won't give you any more points.

The Koopa floor clip is surprisingly precise: you need to be low enough to not land on top of the floor, but at the same time high enough to have wiggle room to do a successful wall clip into the floor. There are only exactly 2 jump heights that allow the clip: pressing A for 15 or 22 frames from a standing position.

In this specific case, the floor clip actually ends up a frame slower than just running to the end and doing the half flag pole glitch. Which one is faster depends on alignment and parity rules and is hard to predict in the general case, but it looks nice and doesn't cost a frame rule.

1-4

Again, the power-up here is more conveniently located than the one in 1-2 and faster to collect. However, collecting it in a way that allows to clear the lava pit while maintaining running speed is fairly precise. It abuses the fact that after collecting a power-up, Mario is actually considered to be on the ground for a frame, allowing to jump mid-air and gain more height and distance than a normal jump could. It was concurrently discovered and shown off in the "all items" TAS as well.

Fun fact: the lava in the pits does nothing, it's just a texture on top of an ordinary pit.

Fun fact: all the protruding blocks along the way are supposed to have firebars attached, but they're only active in 6-4 which uses the same map as 1-4.

Bowser's flames have surprisingly small hitboxes. That, combined with the fact that the game only checks for player-to-enemy collisions every second frame, means Mario can appear to just jump right through them without taking any damage.

The reason to collect power-ups and get Fire Mario is solely to fight Bowser. When hitting the axe without defeating Bowser first, an animation plays where the bridge retracts and Bowser falls into the lava, costing multiple seconds. The time spent collecting the power-ups is easily regained skipping these animations.

The ending cutscene after Bowser fights depends on the screen scroll position, the length can differ by up to 2 frames depending on the alignment. It can actually be faster to slow down before Bowser for a better alignment.

Fun fact: the axe can only be activated when colliding with Mario's feet, and is surprisingly solid when approached from the side.

2-1

A clip through the pipe is used to scroll the screen far enough to the right to delay the spawn of the Koopa Paratroopa later. Additionally, by aligning the screen position with when new sections of the level are loaded, the spawn is delayed by 2 additional frames.

I'm using a different pipe to clip through than the current run, which is better for optimization, saving 2 frames in the end.

When a Paratroopa spawns, its vertical speed is not reset, so it keeps whatever speed the last enemy in its slot had when it despawned. By manipulating the last enemy, the vertical speed is set to 0. This exploits another quirk with Paratroopas, where floor collisions are only checked when it is moving downwards with at least 1px/frame. That means that for the first few frames, the Koopa slowly sinks into the ground until it hits the floor from the side and turns around, making it move to the right, in an ideal position to clip into the ground.

2-2

You can swim while ducking just like duck-jumping, which doesn't change Mario's sprite but does change his hitbox. This is shown off on the initial Blooper, Mario appears to be both inside the Blooper and the wall.

The whirlpools directly change Mario's horizontal position every second frame, to the right in the first half and to the left in the second half. By slowing down to align when this switch happens, you can actually gain some distance compared to just holding right. It is not enough to gain a frame though.

2-3

SMB's RNG is entirely frame-based, random events only depend on the number of (non-lag) frames that passed so far. The Cheep-Cheep frenzy starts and ends based on an invisible element that is loaded in at specific parts of the level. When Cheep-Cheeps spawn and their initial horizontal speed and relative position is random, but there are only 4 different combinations of speed and relative position possible while in motion. Additionally, new Cheep-Cheeps can only spawn on frames divisible by 8 relative to the start of the frenzy, so the ideal fish for the clip can't be controlled precisely. The fish used in this run is the latest you can spawn one before the frenzy ends, and a fish spawned 8 frames earlier wouldn't quite make it to a position to bounce off of. Some fish are left alive, to manipulate the RNG (whether or not a fish spawns depends on how many still live, and this can influence future fish), to get the fish for the floor clip.

3-1

Again a pipe clip is used to scroll the screen and delay enemy spawns, this time for a shell at the end of the level. Some intentional slow-down is necessary at the end to avoid fireworks, bleeding off 6 frames.

3-2

This stage follows a similar scheme as 1-3: The Koopa is spawned as soon as possible, and with a precise bounce Mario clips into the ground. Unlike 1-3, even though the Koopa needs to walk the same distance, this clip is actually significantly faster than just running through. This is because here you can do the clip with running speed instead of from a standing position.

3-3

The platforms that fall at the end can be used to once more clip into the ground. The vertical subpixel position of where the platform spawns is important, and can be manipulated using the previous enemy that occupied the same enemy slot. It needs to be between 0x75 and 0xb6 to align the vertical position when jumping off correctly for the floor clip. That last enemy turns out to be the flying Koopa Paratroopa, when shooting it right when it leaves the screen, it happens to end up with a value of 0x99.

4-3

The ending cutscene continues as soon as the last firework was launched without waiting for it to explode, so ending with a single firework only costs 1 extra frame and it's usually not worth waiting for another timer tick. For 3 or 6 fireworks however, it is significantly better to wait.

4-4

Very precise optimizations allowed for the second major time improvement in this run, saving another frame rule in 4-4. Unlike most movement optimizations which end up not saving any time due to the frame rule, this one happens to save just enough to make the earlier cycle. This one has not been shown in the latest "all items" movie, and I'm not surprised considering it required optimizations down to a single subpixel to save the frame for the frame rule. It is a combination of the correct amount of screen scroll (0x92) saving 2 frames in the ending cutscene, and starting the firebar after the clip a frame earlier, which is the limiting factor to how fast you can reach Bowser.

Firebars are special in that they don't start spinning right when they spawn, but only when you get close enough to them. Also they don't have a fixed initial position, but rather take the value from whatever enemy occupied their slot before, so your previous interactions can affect the position of later firebars.

Another way firebars are special is their collision detection, which is not based on the same hitboxes as normal enemy collisions, but rather the player's distance to each of the flames, and is checked every frame instead of only every other frame. That is why their hitbox can behave in unexpected ways and hit Mario when you wouldn't expect it, or miss him when it looks like it hit, as shown here.

5-3

This is the first repeat of a level, the exact same level as 1-3, just with some random Bullet Bills throughout. They actually can mess with the usual spawning in the level and make the level impossible by blocking all enemy slots and preventing the platforms from spawning. As mentioned in 1-3, the Koopa floor clip does not save time over just finishing the level normally, so this time around I decided to forgo the clip.

5-4

This is another repeat level, this time of 2-4. Bowser is actually represented by two enemy slots with individual hitboxes. If a fireball hits both at the same frame, both do damage to Bowser. This is shown in this Bowser fight, which uses only 4 fireballs to deal the 5 damage necessary to defeat Bowser.

6-2

The vine glitch is used in this level to teleport Mario forwards, thereby changing the relative screen scroll position and allowing a bounce on the Koopa at the end of the level. The vine glitch works because the developers didn't account for the ability to press left and right simultaneously. The game tries to look up where Mario should be placed relative to the vine depending on where Mario is looking, and by pressing both left and right the game ends up some random value instead, which happens to move Mario 0x90 to the right. The trick by itself is not useful to save time as the setup costs more than the teleport gains, but it is the fastest way to change the relative screen position.

By hitting the vine block a frame early, this run saves 2 frames compared to the current movie.

6-3

Hitting the flag is intentionally delayed by 9 frames in order to avoid 6 fireworks.

6-4

This is another repeat level, of 1-4. It is also the first time Bowser starts throwing hammers at Mario, which have the nasty tendency to cause lag frames when too much is going on at once. The best way to avoid lag frames is to not shoot fireballs, but that's not super helpful when you need to defeat Bowser. By using the trick described in 5-4 for dealing 2 damage per fireball and shooting some early before Bowser starts throwing hammers, I managed to avoid all lag frames, saving 3 frames over the current run.

7-1

Another level where screen scroll can be abused to use and enemy at the end of the level to perform the flagpole glitch. The screen needs to be scrolled to near the maximum amount, requiring at least three individual pipe clips to prepare.

7-2

This is another repeat level, of 2-2, just with some more Bloopers.

7-3

Again a repeat, of 2-3, with some Koopas sprinkled in. The same Cheep-Cheep-based floor clip as described in 2-3 applies. The fish used here is 8 frames slower than the optimal fish used in 2-3, but ends up not costing any time.

7-4

7-4 is another maze level like 4-4 which requires Mario to take a certain path. This is done by checking at very specific points whether Mario is standing on the floor and has the correct Y position.

8-2

Like Cheep-Cheeps, Bullet Bill cannons are random in nature, but they work differently internally. There can be at most 6 cannons active at once in the game's memory, after that it starts overwriting them. For each frame and each free enemy slot of the first 3 slots, a random number is chosen (0-15 for levels until 5-3, 0-7 afterwards), and if it happens to be a valid active cannon slot (0-5), its timer is decreased (the timer starts at 15). When the timer reaches zero, the corresponding cannon will create a Bullet Bill enemy in preparation of firing it. On the next frame, the Bullet Bill decides whether to actually fire, based on whether it is off-screen or too close to Mario, and either starts moving or vanishes again.

As mentioned before, the random numbers in SMB only depend on which frame you're on and can't be manipulated. What can be manipulated though is which random numbers are used when, by controlling which enemy slots are free and which are occupied. That means by killing enemies at the right times, you can influence the occupancy of the enemy slots and therefore indirectly manipulate when the cannons will fire. So if it looks weird that some of the enemies are left alive in this run which could have easily been killed, it's actually because of RNG manipulation.

The Bullet Bill in this run is the best possible spawn, saving 4 frames over the current run.

8-3

Due to how the game timer aligns, hitting the flagpole normally is roughly as fast as waiting and doing the flag pole glitch (the flag pole glitch would still be 2 frames faster). Since this is the only opportunity to do it in this run, I hit the flagpole normally.

8-4

Since the input ends as soon as Mario hits the axe, the frame rule doesn't come into play in this level and every frame counts. Because of this and the fact that it is present in any% as well, 8-4 is insanely well optimized already. While the movements used in the current run were not perfect and I could save some subpixels, they were good enough to not lose a frame anywhere. The pipe entry after the wall clip was particularly frustrating, as it only lacks a single subpixel to enter the pipe a frame early, but alas. I also had other wild ideas, including intentionally taking damage at the turn-around pipe entry, so the screen scrolls to the right and loads the correct loading zone without actually needing to move there, but it turns out the screen just doesn't scroll quite far enough to make it work.

Fun fact, the pipe you start from in the underground section actually has a piranha plant in it, it's just not visible, but it can still damage Mario and can be killed as shown here.

For the final Bowser fight, defeating Bowser is optional as the Bridge collapse happens after the movie ends, but I decided to do it anyway. Mario is getting up close and personal with Bowser, dealing two damage each with two fireballs.

Nach: This is a nice improvement over the existing run. Audience response was mostly not directed at this run, but what was directed to it was positive. Accepting to Moons.

Spikestuff: Publishing.