Cave Story in 49:57.16

What this is

A tool-assisted speedrun (TAS) is a list of button presses, one entry per frame, built with savestates and search tools instead of human reflexes. Played back into the game, it beats the game as fast as the inputs allow. The goal here is Cave Story's Best Ending, the longest route: it rescues Curly, collects what the true ending needs, and clears Sacred Ground (the hell levels) and its final boss.

The bar was high. nitsuja's 2011 run is the TASVideos publication for this category and stood for 15 years. It already takes damage boosts, manipulates luck and kills bosses with frame-tight timing. Finding 657 frames in it meant shaving 1–30 frames off dozens of rooms, plus two big pieces: a route idea from periwinkle (below) and a way to drown faster in the Core.

Not ours, mostly. Every frame below is colored by where its button presses came from. It's a bit like gene editing: the run is nitsuja's genome with one big graft and many small edits.

periwinkle, a Cave Story speedrunner, left a work-in-progress TAS on TASVideos in 2022. It reaches the first Egg Corridor and has one huge idea: in the Graveyard, take a hit from a Pignon (the mushroom enemy) at the right moment and the knockback launches Quote up the shaft. That room alone drops from 907 to 646 frames. The new run's first 10,470 frames (3½ minutes) are his inputs, unchanged.

The catch: nobody could attach his opening to nitsuja's run. Cave Story has a single random-number stream, and the Graveyard line draws 532 more random numbers than nitsuja's. Every enemy, drop and boss pattern after that comes out differently, and nitsuja's later inputs fall apart. Worse, under the new luck the Grasstown enemies left the Missile Launcher at level 2 instead of 3 for the Balfrog fight, which measured at roughly 700–845 frames slower. The bridge that finally worked is described under "Why you can't just cut a frame".

nitsuja's inputs make up most of the rest. Once the luck lines up again at a door, his movie can be replayed from that point, frame for frame, to the end of the game.

Say you find a way through a room that's 2 frames faster. You can't just splice it in. Cave Story pulls its randomness from one generator, the C library's rand(): seed = seed × 214013 + 2531011. Many rooms draw from it every frame (Start Point's water drips take 2 per frame). Two fewer frames means 4 fewer draws. Every later random event shifts along the stream: which enemy drops a heart, where a boss jumps. The rest of nitsuja's inputs then play against a different world and die.

The key insight is about doors. When Quote enters a room, the game reloads all of its enemies from the map file. So at a door, the whole world reduces to three things: Quote, the carried state (HP, weapons, ammo, flags, two hidden animation and weapon timers), and the RNG seed. Match all three to nitsuja's at some door and his inputs replay from there, frame for frame. So the frames you saved are only banked once the run walks through a door in sync with his.

To get back in sync you burn random numbers. A head bonk on a ceiling spawns two little particles and costs exactly 4 draws. A Machine Gun shot costs 1, a splash 32–500. Or you skip draws: kill an enemy sooner, avoid triggering one, fire one fewer missile. Try it:

That's how periwinkle's Graveyard finally joined nitsuja's run. A GPU luck search re-solved Grasstown so that the RNG at the door into Santa's House (room 41) matched nitsuja's exactly, and from there his inputs replay to the end. At first that needed a detour of nearly 60 frames to refill health at Santa's house. A later search found a line that picks up one more heart and skips the refill, worth 53 frames. The full-run records keep using this "converge at a door" trick: about 100 frames came from luck re-solves and burns.

After the Core boss, the story has Quote run out of air. So the run wants to drown as early as possible. The drown comes exactly 1,000 frames after Quote's last dive, plus 972 frames of scripts that freeze the game. Diving earlier means drowning earlier, as long as the boss is dead in time and Quote never surfaces in between.

The water isn't still. Its level is a little machine that ignores Quote: every frame, it accelerates 4/512 pixel per frame² toward its rest line. That makes a fixed oscillation of ±16 px with a 256-frame period, the same on every attempt. An agent built an exact model of it (0 mismatches over 1,366 frames) and planned the fight around the tide: dive while the floor is dry and only the pit is underwater, and keep enough missiles for the rest of the game. The first tide line dove 24 frames earlier. The second, a dive-first line, went 46 frames earlier. After paying for the luck repairs, they banked 24 and 16 frames, and the first one took the run under 50:00.

How it was found

The short version (the long one is on How it works):

• A bit-exact twin of the game. CSE2, a community decompilation of Cave Story, patched for headless replay and savestates, was checked against the original exe running under Wine with a fake DirectInput DLL feeding it the inputs. nitsuja's whole movie matches on all 149,311 frames, down to the RNG seed.
• The game on a GPU. First Quote's movement and collision (10 billion player-frames per second on an RTX 4090), then the whole world: enemies, scripts, weapons and luck (1.8 million world-frames per second).
• Search, a lot of it. Evolution strategies over short input windows, exact breadth-first search, luck planners that steer the RNG to a target seed at a door, boss-fight optimizers, a value network, Monte Carlo tree search. Each idea was tried. The "how it works" page also covers the ones that failed.
• A paranoid banking rule. A record only counts after a full replay to the ending, a check of every story flag and item, a frame-by-frame match on the original exe, and a room-by-room diff against the previous record. That last check was added after one record quietly lost 2 frames elsewhere.

From the lab

Clips recorded during the hunt for tricks and glitches. Most of them didn't make it into the run, which is the point: this is what "everything was tried" looks like. Clips marked cheat edit the game state to show what would happen. They aren't legal in the run.

The last mile

Once the big ideas were banked, the record moved a frame or two at a time. Three things kept it moving.

• Rooms nobody had touched since 2011. A boss-fight agent, comparing every room with nitsuja's movie, noticed that about a third of the run was still his inputs, byte for byte. Our searches mostly edited the last few hundred frames before each exit, so the middles of long rooms had never been searched at all. Whole-room and long-window passes over those rooms found frames in Labyrinth I and Grasstown within hours.
• Longer windows. Letting the search rewrite up to 600 frames before a window, not just the window itself, let it reshape a whole approach (jump earlier so a later climb lines up). Outer Wall, Labyrinth I and Grasstown each gave up frames that shorter windows had missed.
• A fresh seed is a fresh look. Re-running the same room with a new random seed explores a different corner of the same search space. Several records came from the 8th to 13th seed on a room that earlier seeds had called dry.
• Keeping near misses. The search used to throw away any faster exit that wasn't byte-identical to the record. Some were off by a booster-fuel count or a few weapon EXP that heal on their own a few hundred frames later. Keeping those and replaying each one to the end turned up four records in the last two days.
• Spending the luck in the next room. A faster exit that leaves the random numbers off usually ruins the next room. But re-solving the next room for the new random state sometimes absorbs the whole difference: the exit from Balfrog's room got 6 frames faster this way, in two steps.
• Faster searching. Moving the mutation step onto the GPU, refilling idle GPU lanes and running six windows at once made each GPU about 8 times faster on the last day than the day before.

One night the home internet went out. The laptop moved to a phone hotspot, the cloud GPUs kept searching, and the laptop itself became the original-exe checker (a 15-minute Wine replay instead of the usual 3). Nine records were banked before the internet came back.

Checked, measured, dead

Ideas that sound like they should work, and the reason each one doesn't. Every verdict here comes from a measurement, not a hunch.

• Avoiding a music change. Each one costs about 4 frames of real-hardware lag, 302 times per run. All 302 were read against the script that triggers them: the game only skips a change to the song already playing, and every remaining change sits on a required story path. None can be avoided.
• Skipping an optional item. The Fireball comes inside a conversation the story needs. The missiles do 53 to 98% of the damage in seven boss fights. Without the Life Capsule, 8 of the run's hits would kill Quote, starting with the Graveyard boost. Skipping the Super Missile upgrade is possible on paper, but plain missiles deal only 40 to 78% of its damage in the late fights: an estimated net loss of about 150 frames.
• Misery's "wasted" frames. The record waits 14 to 17 frames in each of her rounds. Those waits buy the burst that closes the round: her 500 HP has to come out of capped rounds plus bursts, and every faster round found left more HP than the last round can take.
• A faster Ironhead. Quote can only fire forward and Ironhead swims in from behind, so when they meet is fixed. The one faster kill costs a Super Missile the run needs later, and there's no missile to buy back on the way.
• No sound card. Without an audio device the original game skips every music stall (24 seconds!). It also skips the sound setup that seeds the random numbers, so every random event in the game would change: a different run entirely, and probably not a legal one.

How much is left?

Probably half a second to two seconds on this route, spread thin. One agent hunted for route-level skips worth hundreds or thousands of frames (sequence breaks, death and reset tricks, a developer warp in Hell, wall clips, knockback launches like the Graveyard's) and found every one blocked for a structural reason, not a search-effort one. Splitting the run's time three ways:

• About 69,700 frames of scripts, cutscenes and music lag: fixed by the story.
• About 16,200 frames of boss fights: maybe 0 to 30 more, almost all behind the missile budget.
• About 64,000 frames of everything else: maybe 20 to 80 more, a frame or two at a time.

That puts this route's floor somewhere around 49:55 to 49:57. Some of the run is proven optimal outright: an exact GPU breadth-first search shows nitsuja's own inputs can't be beaten on 153 short segments (280 with one extra assumption about pushing into corners). But proofs cover only about a tenth of the time Quote is under control, so "solved" here means "close to the limit", not "proven".

The search is paused, not finished: records were still arriving about once an hour when we stopped. Every search's state, coverage and best open leads are written down, so it can pick up where it left off.

Credits

• nitsuja: the 2011 Best Ending TAS (TASVideos 1917M) that this run is built on, and the Hourglass tool it was made with. About two-thirds of these inputs are his.
• periwinkle: the 2022 WIP with the Graveyard damage boost, the run's first 3½ minutes.
• The CSE2 decompilation project, which made a bit-exact, searchable copy of the game possible.
• zoan: the idea, the direction, the hardware and the cloud bill, and many "crazy ideas" that became real searches.
• Claude (Claude Opus 5.5 in Claude Code): a main session plus dozens of parallel agents that wrote the tools, ran the searches, verified and banked every record, and wrote this page. OpenAI Codex finished the full-world GPU port.

Cave Story is by Daisuke "Pixel" Amaya / Studio Pixel. The maps and clips on this page are rendered from the Japanese freeware release; its graphics and music are his.