Post by fcxiaopengyou

This is an improvement of 4120 frames, about 1 minute and 11 seconds, over [541] NES Boulder Dash by CtrlAltDestroy in 19:42.32. The improvement comes from creative new solutions, better manipulation of bugs, and an abuse of the Amoeba AI.

Uses a level password (724045, skips to level 19-1 which is the beginning of the 4th quest)
Plays on the hardest difficulty

Important note about the ROM:

Previous versions of this run, including the one this run obsoletes, use a common bad dump (b2 I believe). The bad dump appears to have no effect on the game except for adding two new tiles to level 21-1: an extra wall block, and an extra diamond, in the right chamber. I own the cartridge and I can confirm these two tiles do not exist. This run now uses the good dump (checksum 62fac46407453317683fcbdeffdb15ab) and could potentially be console verified now.

Intro

Boulder Dash was my favorite NES cartridge as a child. I always felt proud that I was able to do justice to the game by making the TAS over a decade ago. However, there was always one little thing that bugged me:

"The amoeba levels have long unavoidable waits, it is advised to fast-forward through these."

So, after over 10 years, I am back to get this disclaimer removed. It turns out that the waits weren't so unavoidable after all; 24-3 has been improved by over 35 seconds, and is now one of the highlights of the run!

The Story from the Manual (kind of)

On his deathbed, Rockford calls to his son, Rockford Jr., who likes to wear the color orange. He shows his son a map of secret caves all over the world, each filled with hidden treasures. “You must go and finish the quest I was never able to finish,” he tells his son with his dying breaths.

“You want me to visit these caves and collect all these diamonds?” Rockford Jr. asks.

“No,” his father says, coughing loudly. “You must go to Australia, to the Argyle Diamond Mine. There, you will find a secret tunnel that will lead you into an ancient volcano crater, the origin of all life on Earth. You must go there and destroy the amoebas once and for all, and get revenge for the misery they have caused me!” Moments later, Rockford dies of amoebic dysentery.

So Rockford Jr. spends the next ten years getting a PhD in microbiology. He learns that he needs to shorten his encounter with the amoebas by thirty-five seconds, lest he suffer the same fate as his father. He then visits secret diamond mines located in the Rocky Mountains in Colorado, Mt. Everest, the pyramids of Egypt, the Mariana Trench, and the Aztec ruins in South America, and sells the diamonds to pay off his student loans. Finally, he delves into the volcanic fissures in Australia, and he exacts his revenge on the amoebas by killing their ringleader and strangling the right-hand cohort.

Basic gameplay mechanics

To win each level, Rockford must collect the required diamond quota as indicated at the top left corner of the screen. Once the diamond count reaches 0, the exit will open. Rockford will die if he is hit by a falling object, touches a bug, gets caught in the explosion of a dying bug, or lets the time run out.

Gameplay takes place in intervals of 8 frames, which I will call “turns.” All actions in the game, whether it be the player’s movements, the enemy movements, or falling objects, happens according to these intervals. This makes TASing the game quite simple, as (most of the time) you don’t need to worry about things like momentum or subpixel position, and you can focus purely on puzzle solving. (I comfortably played most of the levels at 12% speed, and only needed to use frame advance on the menus.)

Diamonds and rocks have the same falling behavior, and both can kill Rockford by falling on him. If Rockford ends his turn directly beneath a falling object, he will die. However, it is safe to end a turn beneath a resting object, allowing Rockford to hold an object on his head.

Rocks and diamonds can topple sideways if they are resting on top of another rock, diamond, or wall, and if there is room to topple. They will try to topple to the left before trying to topple to the right. Rocks cannot topple off of dirt, Rockford, explosion stars, or the exit square.

By holding A and a direction, Rockford can dig a square of dirt, push a rock horizontally, or collect an adjacent diamond without moving. I call this “A-grabbing.”

Levels 20-4, 22-3, 22-4, and 24-2 have “magic walls” which will turn falling rocks into diamonds. The conversion will only work if there is empty space beneath the magic wall for the diamond to appear. If there is no empty space, the rock will simply rest on the wall, and will not fall through the wall even if space is cleared away later.

There are two types of enemies in the game, which I collectively call “bugs.” “Butterflies” follow the right-side wall, and will turn into 9 diamonds when crushed by a falling object. “Fireflies” follow the left-side wall, and do not give diamonds when crushed, only points. If a bug has no wall to follow, it will walk in circles. If the player ends a turn adjacent to a bug, the player will die.

When a butterfly explodes into diamonds, they aren't collectible right away. Generally, the diamonds will not be collectible for two turns. On the third turn, the right column becomes collectible, the middle column on the fourth, and the left column on the fifth. Rarely, due to unseen circumstances, there will be an "instant convert" and all the diamonds will become immediately collectible. This is very rare, and only happens once in the movie on level 22-2.

Many levels contain caged bugs following the inside edge of their cages until they are freed. They function as ”frame rules”, encouraging the TASer to wisely utilize the time spent waiting for the bug to cycle into the needed position. Sometimes just one spare turn when used wisely can save time later.

A bug will pause for one turn if it walks into an inside corner, and it will pause for 2 turns if it walks into a dead-end. By manipulating the path of the bugs, they can be sped up or slowed down so that they will arrive to their desired destination at the desired time.

Unlike the player, bugs cannot hold resting objects on top of their head; a resting rock or diamond can crush a bug.

When a bug is crushed, a 3x3 area of tiles around it will be deleted. This is a required trick to beat the game, as many diamonds and exits are sealed behind walls. Killing bugs can also open up many unconventional shortcuts in a TAS. Bugs caught in the explosion of another bug will not explode themselves, they will only be deleted. Only the exit and stage boundary tiles are immune to explosions.

Finally, there are amoebas in stages 20-3, 22-1, and 24-3. Amoebas will periodically multiply and spawn more amoebas in adjacent tiles. The algorithm Amoebas use to multiply is unintuitive, and I’ll get to it later. Amoebas can multiply into an empty space, or overwrite dirt, but can’t overwrite any other kind of tile. There are two ways to get diamonds from amoebas: the first way is to trap them completely so that no more amoebas can spawn, and they will all turn into diamonds. The second way is to make a butterfly try to walk into an amoeba, killing the butterfly and spawning 9 diamonds. This method is only possible on 22-1, since 20-3 and 24-3 contain no butterflies.

Tricks used

Catching objects on head:

During a turn when Rockford is walking, he exists in the destination tile. The previous space where he walked away from will contain a “placeholder,” which is an invisible, solid tile that will be removed on the next turn. If a falling object would kill Rockford on the next turn, Rockford can walk to another space, leaving a placeholder tile where he once was. The falling object will hit the placeholder and come to a rest. On the next turn, Rockford can walk back under the object, and it will not kill him because the object is now at rest.

Walking past bugs:

Rockford will die if he ends a turn adjacent to a bug. If he has correct parity with a bug, he can walk right past the bug because the bug will move past Rockford on the same turn, and he will never end a turn adjacent to the bug (think of opposite-color bishops on a chess board). This is easy to do in real-time. During casual gameplay, if you attempt to walk past a bug, you have a 50% chance of surviving.

Bugwalking:

Bugs follow either the left or right wall, and it is possible to use Rockford’s body as the wall which the bug follows. As long as Rockford’s movements have correct parity with the bug, and neither Rockford nor the bug stop moving, Rockford can freely move around the bug and make it walk in the direction he needs.

Pushwalking:

If you attempt to walk horizontally into a rock for about 4 turns straight, you will then push the rock and move into the space on the same turn. Although this is a game feature, this is rarely used because it is generally much faster to push the rock using A, then walk into the square on the next turn. However, it can be useful on very rare occasions, especially if you had to wait for more than 4 turns for something else to happen. Additionally, this feature seems glitchy, and the number of turns needed to push the rock seems to vary under mysterious circumstances.

Tower of Jenga trick:

The game is sometimes bad about updating tile graphics, and sometimes it will appear that there are more rocks than there actually are.

If you remove the base of a column of objects and then immediately walk upward, you can enter the tower at any point you wish with no waiting. The object you walk into will have just fallen away, and the object above you will still be at rest, so it will not kill you. This is also useful if a series of objects are falling on you: you can halt the first object on your head, then immediately walk around it and safely enter the pile at any point you wish.

The Timer

The in-game clock is based on 0x001E (the “global counter”) and ticks down once every 64 frames. (If (0x001E – 1) mod 64 = 0, the timer will tick down on the next frame).
The global counter keeps running even during menus, meaning the duration of the first “second” can be anything from 0 to 64 frames.
The global counter continues running if the game is paused, meaning that it’s possible to clock-stop by pausing the game around the frame the timer increments. (This is currently the only known way to get a “GOOD” rating on 19-2)
The global counter continues running during lag slowdown, meaning that lag can cause the timer to be lower at the end of the level, even if the same number of turns were taken.
For every second left on the timer, 2 frames are lost at the end of the level when the timer is drained.

Lag notes

Levels are timed in turns using the formula (Frame "GOOD" appears - frame Rockford appears - lag frames)/8.

Lag frames occasionally happen, and make a turn last longer than 8 frames. They seem to be completely random, and will sometimes happen even if the same level is played with the same input (if the past is different). If you’re unlucky, a level might last 10 extra frames due to lag, and there isn’t a lot you can do about it because 8 frames only gives you 1 extra turn to change your route and hopefully avoid the lag. Generally, it’s best to just solve the puzzle optimally and accept any lag frames you get.

There are two exceptions: 21-1 and 24-1, both of which are lag hell. In these stages, there is so much slowdown (often one lag frame per turn!) that an optimal solution to the puzzle using in-game time might be much slower than one which goes far out of the way to reduce lag.

To reduce lag:

Collect as many diamonds as possible, as fast as possible, to reduce the number of physics checks in the level.
Minimize the number of moving objects on the screen.
Minimize the movement of the camera.

How the Amoeba AI Works

You might notice that FCEUX now ships with a lua script that illustrates the amoeba AI. This is the work of AnS, to whom I owe massive thanks. In 2012 I begged him to help me understand how the amoebas multiplied, and he so kindly disassembled their behavior and wrote the lua script. Without him, 24-3 would have never gotten such a huge improvement, and this run would have never been finished.

At the beginning of an amoeba level, 0x00BD (the “amoeba counter”) is set to 255. On every turn, a tracer iterates through the inside edge of the amoeba blob, checking for possible places for a new amoeba to appear. It follows the inside of the amoeba blob in a clockwise pattern, very similar to the movement pattern of fireflies. Unlike bugs which move once per turn, the amoeba tracer moves over a hundred times per turn. Each time it finds a suitable place for a new amoeba to appear, the amoeba counter is decremented by one. When the counter is at 0, a new amoeba will (usually) be placed at the first free space the tracer finds. Thus, the more free space is around the amoeba swarm, the faster the amoebas will multiply.

When a new amoeba is placed, the amoeba counter is reset, but not to 255. It is reset to 4 lower than the last ceiling. Therefore, after the first placement, the counter will be set to 251, causing the next amoeba to be placed slightly faster. When the next amoeba is placed, it will be reset to 247, and so on. After the first 50 amoebas are placed, the amoebas will start to “boom” and rapidly multiply as the counter ceiling gets lowered to 50 and below, causing one amoeba to appear every turn, or every other turn. Once 65 amoebas have been spawned, the ceiling underflows and goes back to 255, causing amoeba multiplication to slow down again.

The location of the next amoeba to be spawned depends on where the tracer is on the turn where the counter hits 0. You can affect the location of the next amoeba simply by touching the amoeba blob with Rockford in different places at different times, or otherwise changing the number and placement of free spaces around the amoeba blob. If the number and location of free spaces around the amoeba blob doesn’t change, then the next amoeba will always appear in the same place. Most of the time, this makes it easy to manipulate the placement of the amoebas. When touching the amoebas to change their spawn pattern, walking next to them will affect them differently than standing still, since the placeholder Rockford leaves behind when moving counts as a second barrier.

During the “boom” period, it is difficult to control the amoebas since you have very limited turns between each new multiplication to affect the outcome of the following one, so it is best to manipulate the outcome of the entire boom period at once before it happens.

The tracer gets reset to the position of the original amoeba (whose Y and X coordinates are respectively stored at 0x00B8 and 0x00B9) every 4 turns, or every time a new amoeba is placed, whichever comes first. This means that new amoebas will be biased towards appearing in a specific region if they are not manipulated. If all four turns are used and the amoeba counter hasn’t decremented since the last time the tracer position was reset, then all the amoebas will turn into diamonds.

Improvements

Level	Improvement (Frames)	Improvement (Turns)
Boulder World
19-1	0	0
19-2	104	13
19-3	0	0
19-4	153	19
Ice World
20-1	1	0
20-2	0	0
20-3	87	11
20-4	-1	0
Sand World
21-1	83	-4
21-2	0	0
21-3	1	0
21-4	64	8
Ocean World
22-1	24	3
22-2	8	1
22-3	6	1
22-4	239	30
Relic World
23-1	-8	0
23-2	11	1
23-3	24	3
23-4	239	30
Volcano World
24-1	288	32
24-2	364	45
24-3	2127	269
24-4	308	37
Total	4262

Notes and Notable improvements

Color choice

Before entering a password, the game gives you the choice of color for Rockford. The menu accepts a D-pad press and A press at the same time. Therefore, there are three colors that can be picked without losing frames: tan, orange, and pink. I chose the orange suit for this run as a homage to TheMexicanRunner, who chose the same color when he played this game for NESMania. If I ever run this game again, I may choose the pink suit.

Boulder World

19-2

Shortly after finishing the previous TAS, I found a small improvement by killing a bug in one of the side rooms, saving a trip back to the main hallway. This saved about 5 turns. Since there are two bugs in this level, I wondered if the other one could also be used similarly, but it was very difficult to control the path of the bugs such that it would save time. During experimentation, I accidentally made both bugs collide in a hallway in such a way that one bug turned around, while the other one kept going straight, causing them to both go together. This was key in finding a strategy which used them both. After heavy micromanagement of the bugs’ routes, I found a strategy which destroys two walls with bugs and saves 13 turns.

19-4

A greater emphasis was placed on moving to the right while collecting diamonds. Most butterflies are now killed in horizontal patterns instead of vertical, and less diamonds are lost to deletion. 19 turns saved.

Ice World

20-3

I manipulated the amoebas to appear in a pattern which conserved empty spaces around them, making the amoeba counter drop faster and making them multiply faster. They multiplied so fast that I couldn’t reach them in time when the last one appeared! 11 turns saved.

Sand World

21-1

This is four turns slower than the previous TAS, but anti-lag strategies saved 115 lag frames, for a net gain of 83 frames.

21-3

Since this level has two unused bugs in my path, I thought for sure that I could use them to create some shortcuts. But the rock placement in this level is just so bad that it seems impossible to get the bugs anywhere safely without accidentally crushing them on the way. In the end, no improvement.

21-4

Fixed an embarrassing route error. In the previous video, I descend into a pit to collect a single diamond and then walk back out. This time, I realized that diamond is sitting on top of rocks that I can topple later, and I succeed in toppling the diamond directly into my path. 8 turns saved.

When I had finished the TAS, I noticed that this level contained a different, even more embarrassing mistake: The diamond at the top right corner of the map is collected sub-optimally. When I tried to use TAS Editor to hex in this change, I synced the run through 24-1 and noticed that I was now 12 frames behind due to new lag frames. Since the mistake only loses 8 frames, I left it in.

Ocean World

22-1

In the previous TAS, I realized I spent a long time waiting for the final jellyfish to return before crushing it and walking up to the exit. This time, I let some of the jellys go while I’m waiting, and they go all the way to the top of the map and kill themselves on the amoebas. This causes 3 more diamonds to be put directly in my path, where previously they were out of the way. 3 turns saved.

22-2

Collected diamonds more efficiently. 1 turn saved.

22-3

Collected diamonds more efficiently. 1 turn saved.

22-4

Big improvements here. The magic wall is blocked on both ends by walls. In this run, I destroy the pufferfish one turn later so that it destroys one of the wall blocks beneath the magic wall, freeing another space to drop rocks later. When pushing rocks, I dropped rocks on the edges of the rows to round off the ends, so pushed rocks would topple and let me turn around faster to get the next rock. And finally, I crush the final jellyfish in a much faster way. 30 turns saved.

Relic World

23-1

I lost 8 frames, an entire turn worth of time, to random lag.

23-2

The final pygmy has to walk all the way back to the beginning of the stage so that I can destroy it to collect the final diamonds and open the way to the exit. In this run, I shortened the distance the pygmy has to walk by 8 turns. But I failed to get an instant convert on him (which happened in the last movie), and the bugs surrounding the exit had a different placement which slowed me down. 1 turn saved, but hey, it’s something.

23-3

More efficiently killed the rightmost pygmies and collected their diamonds. 3 turns saved.

23-4

Another huge improvement. The bottleneck in this level is the bug in the central vertical column. In this level, I found a much faster way to open the horizontal vault of diamonds, and I beat the central bug by one cycle. I also had more diamonds at this point, so I could spend less time at the right side of the level. 46 turns saved!

Volcano World

24-1

Some outside-the-box strategies here, pushing the bug cycles to their limits. The key was to make 3 trips to the central vault, each time leaving a clear path for the next trip so that I could get to the bugs just in time to kill them. It just barely worked! 32 turns saved. Also, 32 lag frames saved, for a total of 288 frames saved.

24-2

I destroyed the first bug at a higher position so that I could get into the top chamber faster. In the final part of the level, there’s a very tight route change, and I only have to make two trips to the bug cages instead of three.

In the exit chamber, I not only had to reach the bug guarding the exit exactly on its cycle, but I also had to destroy it at precisely the right time so that the bug following me would run into its explosion stars, turn around, and go back the other way. This just barely worked. 45 turns saved.

24-3

Trying to trap the amoebas is far too slow, so I decided not to even try. Instead, I only trap the amoeba tracer, making it think the amoebas are completely surrounded when in fact they’re not.

First, I have to clear a path at the top of the level so that I can push a rock next to the amoeba blob. But in doing this, I have to dig a path to get to the top, which makes a hole in the dirt that I can't push the rock across. So then I have to manipulate the amoebas to curl around and plug the gap I created so that I can push the rock all the way to the left.

Next, I have to clear out the bottom area of the level. This will give the diamonds a place to fall in a neat row that will lead me right to the exit later. But while I’m busy clearing out the area, the amoebas are growing unchecked because I can’t touch them to change their growth pattern. So I have to make sure the growth pattern of the amoebas is favorable before I leave them alone for a long time.

Next, I have to wait for 83 amoebas to spawn, and I have to manipulate them not to obscure the area around the left side of the original amoeba. Once 83 amoebas have appeared, I have to free the bug and guide it to the original amoeba. Then I destroy the bug, which destroys the original amoeba and two more below it, leaving exactly 80 amoebas. Then I walk in the space where the original amoeba was. The amoeba tracer will get reset to the original amoeba, which is on top of Rockford. Then it will iterate to the right, where it will be trapped in a single space. 4 turns later, it has failed to decrement the amoeba counter, so all the amoebas turn into diamonds, even though only one amoeba was trapped!

A whopping 269 turns, or 35.45 seconds, was saved on this level, which is roughly half of the entire improvement of the movie. 25 frames were lost to new lag frames, as the falling diamonds lagged the game so much that the game just gave up trying to draw them correctly and left a lot of fake floating garbage on the screen.

24-4

By manually walking the first bug downward, I am able to beat the level after only making two trips to the top of the map to free more bugs. 37 turns saved.

Suggested publication notes

Frame 62193:

"Boulder Dash is a well known action-puzzle game where you must collect a quota of diamonds and reach the exit. This playthrough uses a password to skip to level 19-1, which begins the hardest set of levels.

Normally, standing under any falling object or just getting close to an enemy means instant death, but in this movie the player fearlessly dives through heaps of falling objects and walks past enemies without a scratch.

In this 71-second improvement to the previous movie, CtrlAltDestroy finds even faster solutions to many of the game's puzzles, and destroys the amoebas in record time by abusing their AI.

Special Thanks

I'd like to give my greatest thanks to AnS, the author of the lua script that ships with FCEUX now. Without discovering the trick to get the early conversion, I never would have been inspired to finish this run.
I'd also like to thank TheMexicanRunner for being a huge inspiration by playing all the NES games, especially this one, and inspiring me to be as dedicated to my own projects as he was with his.
Finally, I'd like to thank the entire TASVideos community. Boulder Dash was the first TAS I submitted to this site back in 2005 (Granted I didn't know what I was doing back then) and because of it, Boulder Dash will always remind me of the years of memories and entertainment this site has given me. I guess I just want to say, in a world where nearly the entire internet has been obsoleted by Facebook, Reddit, and Youtube, thanks for keeping your identity and keeping alive the spirit of the 2000s-era phpbb culture, and retro gaming, that defined my childhood.

feos: Accepting as an improvement over [541] NES Boulder Dash by CtrlAltDestroy in 19:42.32.

Fog: Processing.

Forum Published movies #5466: CtrlAltDestroy's NES Boulder Dash in 18:31.82