My Super Bomberman speedrun introduces new strategies compared to the previous two runs of the game that allow me to complete the game faster than before, so I thought this overview of the speedrun and the techniques used in it could be interesting.
Randomness
Before diving into the speedrun itself, we first need to discuss how Super Bomberman generates random numbers. The game actually has two different random number generators – one is faster than the second, while the second provides better entropy.
1. The slow generator has 15 bits of state. Each call takes the state as a 16-bit number, bitwise ORs it with 1 (rather than adding 1, which reduce it to 15-bits of state), and multiplies it by 899. It takes the result and saves it as the new 16-bit state value. Then, the new state is multiplied by a caller-provided value N and divided by 0x10000 to cap the value to the range [0, N-1].
2. The fast generator is actually a bit more complicated, but since it doesn't use complex arithmetic it's a lot faster. It has around ~10.4 bits of state (fractional bits due to no utilizing all possible states).
The slow generator is the one that's used for level generation, while the fast generator is used for some enemy and boss movements. We only really care about the slow generator, the only time I had to care about the fast generator is when I revisited already recorded levels, and wanted to keep the final value of the fast generator the same so it does not change how enemies behave in future levels, forcing me to needlessly re-record them.
The slow generator's initial state comes from numbers of frames spent on the title screen. However, since the slow generator is normally only used for level generator (which the player can't influence), once the initial seed is set by pressing Start on the title screen, the layout of every stage becomes deterministic.
Levels 1-1 to 1-4
I start the run with the same random seed as the previous run by Ryuto. It's a generally very nice seed that allows relatively speedy completion of the first few levels. The major difference between the runs here is that while Ryuto balances the Fire Up bonuses between both players, I let the Black Bomberman take all of them while leaving the White Bomberman with a zero bomb radius. This is seemingly illogical, but the rationale will make sense once we reach level 1-5.
Manipulating Level Generation
I previously mentioned that normally, level layouts are deterministic after the initial seed has been set, but there's a little known aspect of this game that also uses the slow RNG, and can be used to pick different, more favorable seeds for the upcoming levels. Sometimes, seemingly randomly, special bonuses that can't be found anywhere else, will just spawn out of nowhere during story mode. But as I described in a 2013 video (
https://www.youtube.com/watch?v=OrKehQ3DXAY), they don't appear randomly. There are several level-specific conditions that will cause them to appear once they're met:
1. Bombing the exit (Levels 1-2 and 3-7)
2. Getting a combo of 3 enemies (Levels 1-3 and 4-4)
3. Standing on the exit for 1280 frames (Levels 1-4 and 4-7)
4. Placing a bomb at least once in each of the four corners of the level (Levels 1-5 and 4-1)
5. Don't move for 1280 frames (Level 1-7)
6. Open the pause menu (Levels 2-2 and 6-7)
7. Find every regular bonus, and the exit, without taking or destroying any of them (Level 2-4)
8. Use the Punching Glove bonus 5 times (Levels 2-7 and 6-5)
9. Let the last digits of a player's score be "20" (Levels 3-3 and 6-4)
10. Have a player reach 0 lives (Levels 3-4, 4-5)
11. Have one player place 6 bombs at the same time (Level 3-6)
12. Get hit by a punched bomb (Level 6-2)
Some of these are not practical for a TAS:
* 1 is possible but usually not practical, bombing the exit will respawn a defeated enemy with several seconds of invincibility, and it can't be done while the end-of-level jingle is playing, so it's too slow for a TAS. If someone happens to have the exit exposed before defeating an enemy it's possible to utilize this, but it's very unlikely and it's probably not worth to plan a run around this.
* 2 is possible but hard to control in a TAS scenario, because placing a bomb into a tile with an active explosion breaks the current combo, so you have to plan the entire level around this bonus, which might be too slow.
* 3 and 5 are hugely impractical, 1280 frames are over 21 seconds and wasting so much time on a single level makes no sense in a TAS.
* 4 is quite time consuming, however for a reason I'll describe later I still use it on Level 1-5.
* 6 is actually free! Turns out you can press Start while the end-of-level jingle plays and it'll spawn the bonus without actually opening a menu and wasting a precious second on the menu animation. Keep in mind, however, that 6-7 is the last randomly-generated level, so triggering a bonus there isn't too helpful.
* 8 is also free. If a player has the Punching Glove bonus, pressing the Y button 5 times (no need to actually punch a bomb) will fulfill the condition.
* It's hard to plan ahead for 9 in Level 3-3, as the only bonus that alters the second digit of the score is the Extra Bomb bonus and there aren't too many of these to spare or give up on. However, there are more than enough Extra Bomb bonuses until level 6-4 making the hidden bonus in this level very plausible.
* 10 is hugely impractical, by the time a speedrunner reaches level 3-4 they should already have 9 lives, and losing all 9 will take ages with the super long invincibility. They'd also lose most of the power ups which is a major set-back.
* 12 is also impractical, as you can't get hit by a punched bomb while having the invincibility on. Waiting for it to wear off takes too much time.
* Finally, 7 and 11 are both quite easy.
So out of 20 levels that have hidden bonuses, there are 7 levels we can use to manipulate RNG: 1-5, 2-2, 2-4, 2-7, 3-6, 6-4 and 6-5. (Although a few others, such as 1-3, 4-4 and 4-1 could be possible if you manage to find a lucky seed that makes them plausible)
Now, the way hidden bonuses work is as follows – once the conditions have been met, the game will try to generate the level-defined hidden bonus every frame until it succeeds. It will generate two random numbers from the slow RNG – one for the X position and one for the Y position. If it lands on an empty tile on the game grid, it'll place the bonus. Otherwise, it will try again the next frame with newly generated X and Y positions.
This allows us the force the game to continuously generate as many numbers as we'd like by occupying the tiles that are about to be randomly selected with a player character or a bomb until we land on a seed that generates a favorable level. There are two more factors that make manipulations even easier:
1. The fact that the process is done on a frame-by-frame basis means we can move things around between frames to gain even finer control.
2. For the purpose of bonus placements, empty tiles that are "in-check" (i.e. within the range of a set bomb's explosion) will be considered occupied, so we can "occupy" several tiles by placing a single bomb.
Level 1-5
Level 1-5 is where I activate my first hidden bonus. I take a major detour compared to Ryuto's run by placing a bomb in each of the four corners, but I'm not actually doing this to affect the next level's seed. Level 1-5's hidden bonus is a very special one – it's the Question Mark bonus. When a player takes the Question Mark bonus, a random value is generated from the slow RNG to pick a different, random bonus, and that bonus is the one that takes effect. This allows us to obtain a power up that is normally available only until much later.
I place several other bombs before setting our final corner bomb to force a specific RNG seed, and generate a Question Mark bonus that turns out to be the golden Full Fire bonus, instantly maximizing White Bomberman's bomb radius from zero to max. This bonus is normally not available before level 3-3! This is the rationale behind letting Black Bomberman take all of the Fire Up bonuses until now.
Since I've manipulated the RNG, this level marks the divergence point between this run's and Ryuto's run's seeds. My Level 1-6's layout will end up different from the layout in Ryuto's run.
Level 2-2
Level 2-2 is the second time I activate a hidden bonus. After Black Bomberman enters the exit, White Bomberman checks a few tiles by placing two bombs, then the Start button is pressed to "open the menu", which doesn't actually open because the level was already completed. But that's enough to trigger the bonus item and generate the Onigiri bonus and adjust the RNG seed in my favor.
Level 2-4
Level 2-4 is the home of the second Question Mark bonus, which appears when all bonuses and the exit are revealed. It happens in just a few frames so it's hard to notice, but just a few frames after the Wall Pass bonus is revealed (and fulfills this level's conditions), the Black Bomberman takes the Invincibility Vest bonus and immediately moves a single pixel to the right to free that tile. Then, the Question Mark bonus is generated into the exact same tile that had the Vest, which the Black Bomberman immediately takes. This time the Black Bomberman is gifted a Red Bombs bonus, normally first available in Level 3-1, that lets bomb explosions pass through walls.
Level 2-7
Level 2-7 has a hidden bonus that is activated after using the Punching Glove 5 times. I spread several bombs before spawning the Heart bonus to generate a lovely seed for Level 3-1 that will follow the upcoming boss fight. I let White Bomberman take the Heart bonus for a minor cosmetic effect on the final boss fight on Level 6-8.
Levels 3-1 to 3-3
Over the course of these few levels I gained a Red Bombs bonus for White Bomberman and a Punching Glove (which I skipped earlier) and Full Fire bonus for Black Bomberman, essentially maximizing both players power-ups. On a run that doesn't use and manipulate Question Mark bonuses this usually done only at around the middle of World 4 (Depending on how the Fire Up bonuses are divided). From now on, I no longer have to worry about power ups.
Level 3-6
I didn't particularly aim for a specific seed here, merely placing 6 bombs arbitrarily in this level generated a nicer seed for level 3-7 compared to the seed I had before generating the hidden bonus here.
World 5 and Level 6-1
World 4 didn't have any hidden bonus I could use to manipulate the RNG, so let's skip to World 5. World 5 is very different when it comes to RNG manipulation – there is no level to generate as the arena remains empty of soft blocks, randomly-placed enemies and additional hard blocks, and there are no hidden bonuses here. However, there are random bonuses that appear once in a while on the arena. They operate very similarly to how hidden bonuses work, and can be manipulated in the exact same ways:
* Once the random bonus timer reaches zero, the game will try to place a random bonus each frame
* If the tile is occupied or "in-check", the game will try again the next frame
* Otherwise, it'll generate another random number from the slow RNG the decide which bonus to spawn, and spawn it
There isn't much point manipulating more than one bonus in World 5 because there won't be any randomly generated level until World 6, I only manipulate the bonus that is scheduled to appear after defeating the two Gold Bombermen. Because I have a very long time between the defeat of these two and the actual end of the level, I have a very wide range of Level 6-1 seeds available to me. Additionally, there's a Poison Bonus available on the arena at this point. Taking this bonus will generate
another number from the slow RNG to pick the effect of the poison. Not only taking this will affect the seed, the timing I take it also affects the positions the game tries for the random bonus, making even more 6-1 seeds available.
There's one aspect of level generation I need to discuss here – the key RNG primitive used by the level generator is one that generates a random position on the grid, which is done by generating two numbers from the slow RNG. This means randomly generated numbers are generated in pairs, one for the X position and one for the Y position. No matter where the random bonus ends, it'll always generate an odd number of numbers before we reach Level 6-1 – an even number for the positions and one more number for the bonus type. This means that X positions generated during the level generation will always come from "even" seeds while Y positions come from "odd" seeds. By taking the Poison bonus and generating a single random number, the game essentially swaps the seeds that are used to generate X positions with the seeds used to generate Y positions, making seeds where I take the Poison bonus radically different from the seeds where I don't.
I ended up trying several dozens of variations of Level 6-1 before I settled on this final seed, which is my second-best run for Level 6-1 and a very speedy run for Level 6-2 (the fastest 6-1 seed ended up with a fairly slow 6-2 layout, and it was only 2 frames faster). This seed also happens to generate a Bomb Up bonus, letting White Bomberman's score end with "10", which will prove helpful in Level 6-4.
Levels 6-4 and 6-5
Before taking the Bomb Up bonus and letting White Bomberman's score end with "20" (Thanks Level 5-8!) I do the usual ritual of spreading bombs in specific locations in the level to force the hidden Apple bonus to generate a favorable seed for Level 6-5. In Level 6-5 I use the Punching Glove 5 times to generate a favorable seed for the remaining two randomly generated levels.
Level 6-7
After finishing the level, I press the Start button and take the second hidden Heart bonus available for this run with Black Bomberman. This bonus only affects the bombs Spiderer randomly tosses in the next boss level, but the reason I take it is mostly cosmetic.
Level 6-8
The two bosses in this level are handled pretty much the same way as the two previous attempts of this game, but there's a minor cosmetic difference here – because both players have taken a Heart bonus, they can withstand a hit after their invincibility had ended without losing a life, making the run end without any of them dying after the last input.
Final Words
I hope you enjoyed this TAS and this overview, and hope this overview will help future runners improve times for this game even further. It's very likely that better initial seeds can generate better layouts for the first two worlds, which are the most timing critical; especially Level 1-5 which is significantly slower than other runs.