1 2
Posted: 5/11/2018 12:33 AM
(Edited: 2/9/2020 1:06 PM)
Quote
Alyosha
He/Him
Editor, Emulator Coder, Expert player (3821)
Joined: 11/30/2014
Posts: 2832
Location: US
GBA TASer of 2023 Homebrew TAS of 2023 Gameboy TASer of 2022 NES TASer of 2015
http://tasvideos.org/userfiles/info/47030679356753062 Here is 3-10 in 422 steps (4 better then Nitrodon's improvement to 426.) That's probably about all the effort I'm going to put into this game. If GBHawk becomes acceptable in the next BizHawk release I'll likely just submit what I have.
Posted: 5/11/2018 5:52 AM
Quote
thommy3
Joined: 12/10/2006
Posts: 118
Great work. I'll be exited to watch it.
Posted: 6/26/2018 9:04 PM
Quote
ZenicReverie
Player (6)
Joined: 11/26/2007
Posts: 43
Neat, nice to see some work done on the TAS. I was thinking about updating this with the time savings I found a few months ago, but didn't know if anyone would be interested in them. I posted the ILs to speedrun.com, check out my runs there for 2-1 (41), 2-2 (197), 2-3 (98), 2-6 (105), 2-7 (237), and 2-9 (118). Those are all the ones with fewer steps than the currently posted TAS. I stopped checking at 3-4 and on since they were so long. In case you missed these: https://www.speedrun.com/Kwirk/individual_levels Looking forward to the improvements.
Posted: 6/26/2018 11:24 PM
Quote
Alyosha
He/Him
Editor, Emulator Coder, Expert player (3821)
Joined: 11/30/2014
Posts: 2832
Location: US
GBA TASer of 2023 Homebrew TAS of 2023 Gameboy TASer of 2022 NES TASer of 2015
Woah nice work on 2-2 and 2-9, I would never have thought of those! 2-1, 2-3, and 2-6 are in the current WIP. If you are interested 2-4 can be improved 2 steps to 241 and 2-7 can be improved to 236.
Posted: 6/28/2018 1:52 AM
(Edited: 2/9/2020 1:06 PM)
Quote
Alyosha
He/Him
Editor, Emulator Coder, Expert player (3821)
Joined: 11/30/2014
Posts: 2832
Location: US
GBA TASer of 2023 Homebrew TAS of 2023 Gameboy TASer of 2022 NES TASer of 2015
Seeing those improvements in stage 2 gave me some fresh motivation to look for other improvements. I found a pretty significant improvement in 3-4, I haven't optimized it yet but looks like it will be around 12 steps. http://tasvideos.org/userfiles/info/48107498757978657 Here is a new file with ZenicReverie's improvements in 2-2 and 2-9 as well as my new 3-4 in 324 moves (-14 steps) EDIT: 3-4 improved further to 322.
Posted: 7/1/2018 6:28 AM
Quote
Nitrodon
Active player (287)
Joined: 3/4/2006
Posts: 341
This is probably too late, but 3-10 can be improved to 418 steps. The trick is to push the 2x1 block last. EDIT: 416 steps.
Posted: 10/5/2019 12:26 AM
Quote
Alyosha
He/Him
Editor, Emulator Coder, Expert player (3821)
Joined: 11/30/2014
Posts: 2832
Location: US
GBA TASer of 2023 Homebrew TAS of 2023 Gameboy TASer of 2022 NES TASer of 2015
Looks like Kwirk isn't quite done yet. I realized I made a mistake in 2-7 pushing a block unnecessarily, then I noticed that I could also saves 4 steps with a pretty obvious oversight. I don't think there are any other improvements before 2-7, but I'm going over everything again. EDIT: 3-4 improved by one move and one unnecessary push. 3-7 improved by 2 unnecessary moves. 3-9 improved 4 unnecessary moves (my goodness I made a lot of oversights.)
Posted: 2/23/2024 4:05 AM
(Edited: 5/7/2024 4:33 PM)
Post subject: Heading Out?
Quote
Sand
He/Him
Player (143)
Joined: 6/26/2018
Posts: 175
Exciting news today with #8905: Nitrodon, ZenicReverie, CyberShadow, Sand, Alyosha & Deadcode's GB Kwirk "Going Up?" in 15:15.89 and most of the "Going Up?" levels being bot-optimized. I've been thinking a bit about the "Heading Out?" game mode a bit as well. In that mode, you play a sequence of up to 99 random mini-floors in a row, in one of three skill levels. RTA runners have categories for 10 floors and 99 floors in each of the three skill levels. There's a different number of distinct floors in each skill level: 30 in Easy, 50 in Average, and 40 in Hard. When you play 99 floors, you are guaranteed to get repeats. Internally the game numbers floors thus:
  • 0–29: Going Up?
  • 30–59: Heading Out? Easy
  • 60–109: Heading Out? Average
  • 110–149: Heading Out? Hard
I reverse engineered the Kwirk RNG. The RNG is only used in "Heading Out?" mode. It's seeded from a frame counter mod 60, so there are at most 60 different random floor schedules in each skill level. (The schedules are in fact all distinct, so there are exactly 60 for each skill.) The RNG is used once at the beginning of the run to generate the floor schedule, and then called once when starting each new floor for a 50% chance of flipping the floor layout vertically. There's no way to manipulate the RNG while playing, so which floors get flipped can also be considered an immutable part of the floor schedule. Vertical flips don't change anything really: if you have a solution already, just change all Up moves to Down and vice versa. One idea would be to make a TAS that does 99 "Heading Out?" floors in each of the three skill levels. Pre-solve every floor in the selection pool, and choose an RNG seed that produces the schedule of 99 levels that is fastest to solve. "Heading Out?" floors are smaller (maximum 8×6) than "Going Up?" floors and probably easier to solve. But another idea I had is an "all unique floors" TAS. This would mean playing until you've finished all 30 distinct Easy floors, all 50 distinct Average floors, and all 40 distinct Hard floors (ignoring vertical flips). This would allow you to choose any number of floors, and play the same skill level more than once. For example, you might play a run of 40 floors in Hard to hit 36 distinct floors, then start a new run with a different seed to play 12 more floors and collect the remaining 4 floors. (These numbers are made up.) It adds an additional dimension to the optimization: not only solving each floor as fast as possible, but choosing a good route through seeds in each skill level in order to see all the distinct floors as fast as possible. There's a "magic" seed, 40 42, in the Easy skill level that hits all 30 distinct floors in the first 30 levels. There's no such one-shot seed for Average and Hard. Without restarting, the seed that hits all distinct floors in Average in the least number of floors is seed 20, requiring 88 floors to see 50 distinct. In Hard, the seed that hits all distinct floors without restarting in the least number of floors is seed 34, requiring 60 floors to see 40 distinct. These could likely be done faster with judicious restarts. Caveat: I haven't carefully checked my reverse engineered floor schedule generator for accuracy, so these specific numbers may be inaccurate.
Posted: 2/25/2024 3:19 AM
Quote
Sand
He/Him
Player (143)
Joined: 6/26/2018
Posts: 175
Sand wrote:
I've been thinking a bit about the "Heading Out?" game mode a bit as well. In that mode, you play a sequence of up to 99 random mini-floors in a row, in one of three skill levels.
These are my Kwirk TAS utilities: 
git clone https://www.bamsoftware.com/git/kwirk.git
I reverse engineered how floors are stored in the ROM. The rip-floors script extracts floor layouts and writes them to a file. The floors/ directory has all the floor layouts, including both non-inverted and inverted versions of the "Heading Out?" floors. The solver/ directory contains my optimizer. It can't solve all the "Going Up?" floors, but the "Heading Out?" floors are easier. I posted solutions for all 120 floors (non-inverted and inverted) at Wiki: GameResources/GB/Kwirk#HeadingOut. Caveat: I haven't actually tried these in an emulator. My thought is that we can also try solving them with DDD-Kwirk as a check against error. The total frame count for each floor may be off by a constant, because I just hacked in an exit staircase at the left side of each floor. I was slightly incorrect in Post #527972 when I said that inverting doesn't affect the time to complete a floor. It's true that the central portion of the floor is equivalent, but the entrance/exit passages are carved out after the central part is inverted, and therefore may change length when the floor is inverted. For example, these are the non-inverted and inverted versions of floor 31. (# = wall, 1 = player, . = empty, a = block, ~ = hole.) Note how there is an extra bend in the entrance/exit passages in the inverted version: 
31
####################
####################
####################
####################
####################
####################
######........######
######........######
......~.####......1#
######..####..######
######.a......######
######.#......######
####################
####################
####################
####################
####################
####################
31i
####################
####################
####################
####################
####################
####################
######.#......######
######.a......######
....##..####..##..1#
###...~.####.....###
######........######
######........######
####################
####################
####################
####################
####################
####################
The solutions are therefore of different lengths. 
31   429 frames  44 steps  WWWWWNWWWWWWSSWSEEEEESENNNENWWWWWWNWSSWWWWWW
31i  447 frames  46 steps  WWSWWWWSWWWWWNNWNEEEEENESSSESWWWWWWSWNNWWWNWWW
Posted: 2/27/2024 6:43 AM
Post subject: Heading Out? routing
Quote
Sand
He/Him
Player (143)
Joined: 6/26/2018
Posts: 175
Sand wrote:
But another idea I had is an "all unique floors" TAS. This would mean playing until you've finished all 30 distinct Easy floors, all 50 distinct Average floors, and all 40 distinct Hard floors (ignoring vertical flips). This would allow you to choose any number of floors, and play the same skill level more than once. For example, you might play a run of 40 floors in Hard to hit 36 distinct floors, then start a new run with a different seed to play 12 more floors and collect the remaining 4 floors. (These numbers are made up.) It adds an additional dimension to the optimization: not only solving each floor as fast as possible, but choosing a good route through seeds in each skill level in order to see all the distinct floors as fast as possible.
A route in Heading Out? mode is a set of RNG seeds, paired with a number of floors to play in each seed before bailing out and starting the next seed. Optimizing a route is equivalent to solving an instance of the weighted set cover problem, except for a few minor details like menuing. The decision version of set cover is NP-complete, but there are few enough seeds and floors involved that solving it for Kwirk is tractable. Below I'll show routes I computed, based on optimized frame counts per floor and some quick measurements I did of the time between levels and seeds. Let's take Hard for an example. The universe U is the set of 40 distinct floors we need to cover: {110, 111, 112, …, 149}. We have 60×99 = 5,940 sets to work with, where each set represents a seed (0–60) and a number of floors to play in that seed (1–99). For example, S0,5 = {121, 122, 124, 130, 148}, because those are the distinct floors you cover if you play the first 5 floors of seed 0. (Refer to the floor schedules.) We need to find a collection of Sseed,n sets whose union is U. The optimization part is that each Sseed,n has an associated weight Wseed,n, which represents the number of frames needed to restart a run and play the specified number of floors into the seed, taking into account the time needed to actually solve the floors, as well as the animated transitions between them. The collection of sets must not only cover U but also have minimum combined weight. To solve it, we can represent the instance of weighted set cover as an integer program. (I got the idea from these lecture notes.) A is a 5940×40 matrix, where 5,940 is the number of Sseed,n sets and 40 is the size of U (the number of distinct floors in Hard). Each column of A is a 0–1 vector that indicates what floors are covered by the corresponding set. For example, the fifth column of A, corresponding to S0,5, has a 1 in the positions for 121, 122, 124, 130, and 148, and a 0 in all other positions. c is a 5,940-vector of weights for each set. The integer program is: minimize: cTx subject to: Ax ≥ 1, x integer, 0 ≤ x ≤ 1 What this means is: all the elements of the solution vector x have to be either 1 or 0 (we either include a set or we don't). The matrix product Ax tells us how many times each floor gets played for a given solution vector x; all elements of this product must be at least 1 (we have to cover every floor). And finally, the x we find that satisfies these constraints should minimize the total weight cTx. I thought I might have to settle for approximation, but I threw the matrices and vectors into scipy.optimize.milp and it found exact solutions without any problem. The program to do this is headingoutroute in my repository. In order to know the weight of each seed+n combination, we need to know not only how long it takes to play each floor, but also how long it takes to transition between floors on the same seed, and how long it takes to end a run, navigate the menus, and start a new seed. I timed two floor transitions at 222 and 224 frames, so I estimated 223 as an average cost. I timed a run restart at about 646 frames total: 209 frames to play the victory jingle, 109 frames to navigate menus and change the number of floors, and 328 frames to play the entrance jingle. These estimates don't include time waiting for the next seed, but that's at most 59 frames each time we have to do it, and we have some flexibility because we can play the seeds in any order. The estimates also don't account for varying menuing times to change the number of floors between runs, but I am treating those differences as negligible. Here are the optimized routes. Unsurprisingly, the optimizer found the "magic" seed 42 in Easy that covers all floors with no restarts. In Average and Hard, it manages to cover all the floors with just one repeated floor (underlined) in each case. Easy: total frames 17,085, total floors 30
Seed# FloorsFloors
423032i, 35i, 55i, 46, 59, 45i, 49i, 58, 56, 33, 30i, 57, 48i, 31i, 47i, 51i, 37, 41, 38, 44i, 50i, 34i, 42i, 53, 43, 54i, 40i, 36, 52i, 39i
Average: total frames 38,210, total floors 51
Seed# FloorsFloors
114109i, 100i, 62, 83
125105i, 94, 104, 77i, 99i
172567i, 78, 84i, 69, 75, 61, 79, 88, 72, 85, 81, 70i, 66, 92, 86, 98, 73i, 71i, 108i, 106, 65, 63i, 107i, 64i, 80i
321102
36260, 101i
45490, 103, 87, 76i
52474i, 89, 93i, 68i
54682, 91, 97, 78, 96, 95i
Hard: total frames 39,113, total floors 41
Seed# FloorsFloors
214125, 134, 114i, 145i
263137i, 140i, 130i
3428120, 133i, 138i, 110i, 118i, 123, 139, 119i, 113i, 146, 148i, 111i, 144, 143i, 140, 131i, 142i, 136i, 149, 116, 112, 147i, 121i, 129i, 127i, 141, 135, 115i
352124i, 117
584128i, 132, 122i, 126
If the frame count estimates are accurate, a full "Heading Out?, all unique floors" run will take about 26m13s.
Posted: 3/19/2024 9:46 AM
Post subject: Heading Out? WIP (Easy floors)
Quote
Sand
He/Him
Player (143)
Joined: 6/26/2018
Posts: 175
Here's a WIP draft of Heading Out? mode, the 30 floors of Easy only. It navigates the opening menus, waits for RNG seed 42, then plays each floor using precomputed solutions. Link to video BizHawk file With this TAS I'm trying something new (at least for me). All the inputs for the movie are generated by a Lua script. The main code block looks like this: 
Language: lua
savestate = run_until_exec(savestate, nil, TITLE_SCREEN_ADDR)
console.log("title screen")
savestate = earliest_effective_frame(savestate, function (s)
	return savestate_joypad_set(s, {Start = true})
end, function (s)
	return run_until_exec(s, 32, MENU_ADDR)
end)

console.log("select game")
savestate = select_menu_item(savestate, 1) -- Heading Out?

console.log("select skill")
savestate = select_menu_item(savestate, 0) -- Easy

console.log("select course")
savestate = select_num_floors(savestate, 30)

console.log("select display")
savestate = select_menu_item(savestate, 1) -- Bird's-eye View

console.log("heading out confirm")
savestate = earliest_effective_frame(savestate, function (s)
	return savestate_joypad_set(s, {[menu_confirm_button(s)] = true}) -- Start
end, function (s)
	return run_until_u8_is(s, 100, RNG_SEED_ADDR, 42)
end, true)
console.log(string.format("rng seed %d", savestate_read_u8(savestate, RNG_SEED_ADDR)))
assert(savestate_read_u8(savestate, RNG_SEED_ADDR) == 42)

for _, floor in ipairs{"32i", "35i", "55i", "46", "59", "45i", "49i", "58", "56", "33", "30i", "57", "48i", "31i", "47i", "51i", "37", "41", "38", "44i", "50i", "34i", "42i", "53", "43", "54i", "40i", "36", "52i", "39i"} do
	console.log("floor", floor)
	local solution = SOLUTIONS[floor]
	savestate = play_floor(savestate, solution.moves)
end
The core feature of the script is a function that finds the earliest frame at which an input has an effect. You give it a function to execute that enters the input, and another function to test whether the input had an effect. The function tries the input at the current frame, then runs the emulator ahead for a few frames to see if anything changed. If not, it rewinds to before it tried the input, advances one frame, and tries again. The first stanza of code is an example. function (s) return savestate_joypad_set(s, {Start = true}) end tells the function to try pressing the Start button. function (s) return run_until_exec(s, 32, MENU_ADDR) end means to try running up to 32 frames ahead, checking to see if the emulator executes the main menu subroutine. Other functions, like select_menu_item and play_floor, are implemented similarly, finding the earliest frames for menu inputs and player movements respectively. Here's a video of the Lua script running in BizHawk at 400% speed. It's super jittery because of the repeated advancing and rewinding to find the earliest frame for every input. Link to video
Posted: 3/20/2024 12:55 AM
(Edited: 3/20/2024 1:40 AM)
Post subject: 27 frames to push a block into a hole, not 28
Quote
Sand
He/Him
Player (143)
Joined: 6/26/2018
Posts: 175
EDIT: This was incorrect, see Post #528398. The execution Lua script doesn't have move costs hardcoded. After making a move, it tries the next move at multiple offsets to find the earliest frame where an input has effect. It finds the move costs that are already known, e.g. 9 frames for a move into an empty square, 10 to push a block, 12 to push a turnstile, with one exception. Pushing a block into a hole consistently takes 27 frames total, not the 28 frames reported at Post #527986. For example, applying this patch to the Lua script to log move costs: 
Language: diff
diff --git a/tas.lua b/tas.lua
index 1886e26..19aa575 100644
--- a/tas.lua
+++ b/tas.lua
@@ -717,6 +717,7 @@ end
 local function play_floor(savestate, schedule)
 	console.log("executing schedule", schedule)
 	savestate = run_until_exec(savestate, nil, SWITCH_PLAYERS_ADDR)
+	local prev_frames
 	for i = 1, string.len(schedule) do
 		local code = string.sub(schedule, i, i)
 		local button = ({
@@ -732,6 +733,11 @@ local function play_floor(savestate, schedule)
 		end, function (s)
 			return run_until_player1_moves(s, 16)
 		end, true)
+		local frames = savestate_frame_count(savestate)
+		if prev_frames ~= nil then
+			console.log("exec", code, frames - prev_frames)
+		end
+		prev_frames = frames
 	end
 	return savestate
 end
results in this log for floor 56: 
floor	56
executing schedule	WWWWWWWNWENEESWWWWSNWWWSWWWWWW
exec	W	9
exec	W	9
exec	W	9
exec	W	9
exec	W	9
exec	W	9
exec	N	9
exec	W	12
exec	E	9
exec	N	9
exec	E	9
exec	E	9
exec	S	9
exec	W	10
exec	W	10
exec	W	10
exec	W	27
exec	S	12
exec	N	9
exec	W	12
exec	W	9
exec	W	9
exec	S	9
exec	W	9
exec	W	9
exec	W	9
exec	W	9
exec	W	9
exec	W	9
Despite the thread for #8905: Nitrodon, ZenicReverie, CyberShadow, Sand, Alyosha & Deadcode's GB Kwirk "Going Up?" in 15:15.89 saying 28 frames, I checked the input file and it actually uses 27 frames. I didn't see anything to improve there. I re-ran both the per-floor and route optimizers. The frame count for a few floors decreases slightly, but the solutions don't change in any significant ways. The RNG seed segments remain the same.
Posted: 3/20/2024 1:38 AM
Post subject: Re: 27 frames to push a block into a hole, not 28
Quote
Sand
He/Him
Player (143)
Joined: 6/26/2018
Posts: 175
Sand wrote:
Pushing a block into a hole consistently takes 27 frames total, not the 28 frames reported at Post #527986.
Never mind, I was mistaken. The inputs are still spaced 28 frames apart in the movie file. It was an artifact of the way the script counts frames and how the script decides when an input has taken effect. In floor 56, for example, the 4 W moves in the middle have 2× block push, 1× hole fill, 1× step, the costs of which we think of as 
exec	W	10
exec	W	10
exec	W	28
exec	W	9
But the script considers a move accomplished (and starts looking for the first possible frame for the next move) when Kwirk's position in memory changes, not when the hole is completely filled. So it ends up being the same total number of frames, just subdivided differently: 
exec	W	10
exec	W	10
exec	W	10
exec	W	27
The script was just attributing the 18 frames to fill the hole to the next move, rather than the current move. The 27 comes from 18+9 (fill hole and take a step), not 10+17 (push block and fill hole).
Posted: 3/22/2024 7:08 PM
Post subject: Left + Select cheat code
Quote
Sand
He/Him
Player (143)
Joined: 6/26/2018
Posts: 175
I just learned there's a cheat code in Heading Out? mode. If you hold the Left and Select buttons while confirming the "Select Display" menu, then the floor schedule will be overwritten to play all the floors in the chosen skill level, exactly once and in order. Each floor may still be inverted or not, but the cheat code skips seeding the RNG, so the inversion schedule is always the same as well. (Unless you've played an earlier round to set the seed.) This cheat code would obviously be the fastest way to play all floors in Heading Out? mode, but I'm not planning to use it in the TAS, because it would take away the fun of RNG seed routing. Also, while reverse engineering, I discovered a feature that I couldn't find documented. If you hold the B Button while playing, it disables movement auto-repeat. You have to release and press the D-Pad for each step. It's probably not useful for a speedrun.
Posted: 5/7/2024 7:55 PM
Post subject: Timing transitions between segments
Quote
Sand
He/Him
Player (143)
Joined: 6/26/2018
Posts: 175
Now that we have a list of 14 segments that together cover all unique floors, we have to decide what order to play them in. The order matters for two reasons. First, menuing. Settings carry over between segments, so transitioning from one Average segment to another Average segment, for example, is faster than transitioning from an Average to a Hard, because you don't have to go as deep into the menus. Second: RNG. Recall that the RNG seed is a frame counter mod 60. Depending on where we are in the RNG seed cycle after finishing a segment, we have to wait longer for some seeds that others. (At the same time, forced RNG waiting may make some extra menuing "free", as long as it doesn't come at the expense of something even faster.) I wrote a script to automatically measure the time to transition between each pair of segments. For each segment, it gets into the segment from the title screen (to find the transition cost if that segment happens to be chosen as the first segment), plays through the segment and records the time at the end, then (starting from a savestate immediately after solving the segment), measures how long it takes to get into every other segment. There are two ways to go through the menus and change settings between segments, and the script tries both. It also does every segment in both Diagonal and Bird's-eye views. It also measures the time to complete each floor and transition between floors within a segment. After running for about 9 hours, it outputs a table of 29×28×2 segment transition costs and 122 floor transition costs (there are 120 unique floors, 2 of which get played twice). These are segments.csv and floors.csv in the repository. Here's a sample of segments.csv. It says: from boot, it takes 524 frames to get into the (easy, birdseye, 30, 42) segment (earliest frame that gives the desired RNG seed). At the end of that segment, 17030 total frames have elapsed. To complete the (easy, birdseye, 30, 43) segment and transition into the (average, birdseye, 4, 11) segment takes 17417 frames if you use the B Button to traverse menus, or 17416 if you use the END menu. To complete the (easy, birdseye, 30, 43) segment and transition into the (hard, birdseye, 28, 34) segment takes 17440 and 17379 frames respectively for the B Button and END menu respectively.
from_skillfrom_displayfrom_num_floorsfrom_seedto_skillto_displayto_num_floorsto_seedreconfigureframes
easybirdseye3042524
easybirdseye304217030
easybirdseye3042averagebirdseye411b17417
easybirdseye3042averagebirdseye411menu17416
easybirdseye3042hardbirdseye2834b17440
easybirdseye3042hardbirdseye2834menu17379
Why test every segment in both Diagonal and Bird's-eye views? We know from #8905: Nitrodon, ZenicReverie, CyberShadow, Sand, Alyosha & Deadcode's GB Kwirk "Going Up?" in 15:15.89 that Bird's-eye view is preferable during gameplay, because pushing a block into a hole is 8 frames faster. In addition, Bird's-eye saves around 16 frames before the first floor, and between each pair of floors in a segment, as you can see in this excerpt from floors.csv (compare corresponding transition_frames between display=diagonal and display=birdseye):
prev_floorfloordisplayseednum_floorsfloor_seqtransition_framesfloor_frames
109idiagonal11413361101
109i100idiagonal1142230523
100i62diagonal1143229585
6283diagonal1144229259
109ibirdseye11413211101
109i100ibirdseye1142214499
100i62birdseye1143213585
6283birdseye1144213259
The only advantage of Diagonal is that it is 1 frame faster to choose at the SELECT DISPLAY menu—which might be enough to save an RNG cycle and therefore 60 frames. Of course, 16 frames of that gets immediately erased on entering the first floor in a segment, and the segment cannot be too long, or else the rest of the gain will be eaten up by longer floor transitions. (And of course, the segment cannot involve many instances of pushing a block into a hole.) It's unlikely, but possible, that using Diagonal display in some of the shortest segments could save time. In between segments, you have to go through the menus to change the settings for the next segment. The settings you may have to change are the skill level (Easy, Average, or Hard), number of floors, and view (Diagonal or Bird's-eye). How much time you spend in the menus depends on how many settings you have to change. In the special case where the skill level, number of floors, and view are the same in two consecutive segments, you don't have to enter the menus at all, you only have to wait for the right RNG seed. But there are two ways to navigate the menu. You can back up screen by screen using the B Button, or you can directly choose a screen to go to using the END menu. In either case, you then can only advance linearly through the rest of the screens. This is what the possible menu transitions look like graphically: The difference in time between the END menu and the B Button depends on how far back you have to go in the menu sequence:
If you need to change the skill level (SELECT SKILL menu),the END menu is 1 or 61 frames faster than the B Button
If you need to change the number of floors (SELECT COURSE menu),the END menu is 0 or 60 frames faster than the B Button
If you need to change the view (SELECT DISPLAY menu),the END menu is 2 or 62 frames slower than the B Button
I was surprised at seeing the numbers 1, 2, 61, and 62. It seems like every difference should always be a multiple of 60, because of the RNG seed cycle. Either the difference between the END menu and the B Button is small enough to hit the same cycle, or else one is one cycle slower. That is true, but as it turns out, the RNG seed variable is not an exact frame counter. It can fail to count vblanks in some situations, and moving between menus is one of them. This is why the END menu is usually faster than the B Button, because there are fewer total menu transitions. Only in the special case of having to visit only the final menu (SELECT DISPLAY) can it be faster to use the B Button. The next step is to load the segment transition costs into a traveling salesman solver to optimize the order of segments, in each case using whichever of the B Button or END menu gives the fastest transition between consecutive segments, and keeping the option of doing each segment in either Diagonal or Bird's-eye view.
Posted: 5/14/2024 5:13 AM
Post subject: Optimized segment order – and a plot twist
Quote
Sand
He/Him
Player (143)
Joined: 6/26/2018
Posts: 175
I found approximately optimal orderings of the 14 segments. But I had overlooked something initially in the way random floor schedules are generated. The schedules are not independent, but are affected by schedules that have already been executed. In light of this new knowledge, optimizing the route through RNG seeds is going to require different techniques. I put the segment transition costs from Post #529194 into traveling salesman solvers, with the simplifying assumption of using Bird's-eye view only. This would forego potential minor time savings of using Diagonal view for some segments. I tried the LK solver and GenericGraph.traveling_salesman_problem from Sage. (I also tried algorithms.approximation.traveling_salesman.traveling_salesman_problem from NetworkX, but even with a reduced graph of 7 segments, it was still running after 2 hours, while the other two solvers took only a few seconds. There must be a bug, because 7! is only 5,040, small enough to solve quickly even by brute force.) LK and Sage gave me different routes with equal cost:
FramesSkillSeed# FloorsFloors
17379Easy423032i, 35i, 55i, 46, 59, 45i, 49i, 58, 56, 33, 30i, 57, 48i, 31i, 47i, 51i, 37, 41, 38, 44i, 50i, 34i, 42i, 53, 43, 54i, 40i, 36, 52i, 39i
42681Hard3428120, 133i, 138i, 110i, 118i, 123, 139, 119i, 113i, 146, 148i, 111i, 144, 143i, 140[, 131i, 142i, 136i, 149, 116, 112, 147i, 121i, 129i, 127i, 141, 135, 115i
46056Hard263137i, 140i, 130i
49567Hard584128i, 132, 122i, 126
54155Hard214125, 134, 114i, 145i
57988Average125105i, 94, 104, 77i, 99i
60217Average36260, 101i
64304Average54682, 91, 97, 78, 96, 95i
67084Average52474i, 89, 93i, 68i
70738Average114109i, 100i, 62, 83
73845Average45490, 103, 87, 76i
75257Average321102
91869Average172567i, 78, 84i, 69, 75, 61, 79, 88, 72, 85, 81, 70i, 66, 92, 86, 98, 73i, 71i, 108i, 106, 65, 63i, 107i, 64i, 80i
93520Hard352124i, 117
FramesSkillSeed# FloorsFloors
17379Easy423032i, 35i, 55i, 46, 59, 45i, 49i, 58, 56, 33, 30i, 57, 48i, 31i, 47i, 51i, 37, 41, 38, 44i, 50i, 34i, 42i, 53, 43, 54i, 40i, 36, 52i, 39i
42681Hard3428120, 133i, 138i, 110i, 118i, 123, 139, 119i, 113i, 146, 148i, 111i, 144, 143i, 140, 131i, 142i, 136i, 149, 116, 112, 147i, 121i, 129i, 127i, 141, 135, 115i
46076Hard263137i, 140i, 130i
62664Average172567i, 78, 84i, 69, 75, 61, 79, 88, 72, 85, 81, 70i, 66, 92, 86, 98, 73i, 71i, 108i, 106, 65, 63i, 107i, 64i, 80i
66497Average125105i, 94, 104, 77i, 99i
68726Average36260, 101i
72813Average54682, 91, 97, 78, 96, 95i
75593Average52474i, 89, 93i, 68i
79247Average114109i, 100i, 62, 83
82354Average45490, 103, 87, 76i
83771Average321102
88276Hard214125, 134, 114i, 145i
91869Hard584128i, 132, 122i, 126
93520Hard352124i, 117
But when I entered one of the schedules into the Lua script to have it executed, it desynced after the first segment. There was an error in my understanding of how the random floor schedule generation algorithm works. I understood that the algorithm does not allow repeating a floor if that same floor was already played within the most recent 20 floors of a schedule. What I did not understand is that this 20-floor history carries over across schedules, too. The first floor in a schedule cannot be the same as any of the most recent 20 floors played in previous runs, then the window shifts by 1 for the second floor, and so on. (The equality that matters for this purpose is the relative floor number; that is, the floor's index number minus the index of the first floor in the skill level. So floor 35 (index 5 in Easy) will block not only 35, but also 65 (index 5 in Average) and 115 (index 5 in Hard). This is the code that I initially misinterpreted: 
generate_random_floor_schedule:
        31e7    1111c3  ld      de, heading_out_floor_schedule
                        ; Seed the RNG.
        31ea    fa77c3  ld      a, [frame_counter_copy]
        31ed    ea28cf  ld      [rng_state_a], a
        31f0    ea29cf  ld      [rng_state_b], a
        31f3    ea2acf  ld      [rng_state_c], a
        31f6    ea2bcf  ld      [rng_state_d], a
        31f9    0e63    ld      c, 99           ; Always generate a full schedule of 99 rooms.
next_random:
        31fb    cd5432  call    rng_next        ; Get a random 8-bit integer.
        31fe    6f      ld      l, a
        31ff    2600    ld      h, 0
        3201    cdc93e  call    heading_out_num_floors_for_skill_level
        3204    78      ld      a, b
        3205    cd2b1f  call    remainder_16b   ; Reduce the random number mod the number of floors in the skill level.
        3208    c61e    add     30              ; Add 30 to skip over Going Up? floors.
        320a    cd3c32  call    check_for_recent_duplicate_floors
        320d    feab    cp      0xab            ; 0xab is a sentinel that means a duplicate was found.
        320f    28ea    jr      Z, next_random
        3211    12      ld      [de], a         ; Assign next slot in heading_out_num_floors.
        3212    13      inc     de
        3213    0d      dec     c               ; Are we done with all 99 floors yet?
        3214    20e5    jr      nZ, next_random
        3216    fab9c2  ld      a, [heading_out_num_floors]
        3219    47      ld      b, a
        321a    fab8c2  ld      a, [game_mode]
        321d    fe01    cp      0x01
        321f    2808    jr      Z, copy_last_20_into_history
        3221    fabac2  ld      a, [heading_out_num_floors_remaining]
        3224    4f      ld      c, a
        3225    90      sub     b
        3226    3801    jr      C, copy_last_20_into_history
        3228    41      ld      b, c
copy_last_20_into_history:
        3229    78      ld      a, b
        322a    21fdc2  ld      hl, heading_out_floor_schedule - 20
        322d    cd6b24  call    add_16b         ; Add the selected number of floors to hl.
        3230    0614    ld      b, 20
        3232    11fdc2  ld      de, heading_out_floor_schedule - 20
                        ; Copy 20 bytes from heading_out_floor_schedule - 20 + num_floors
                        ; into the history buffer at heading_out_floor_schedule - 20.
copy_loop:
        3235    2a      ldi     a, [hl]
        3236    12      ld      [de], a
        3237    13      inc     de
        3238    05      dec     b
        3239    20fa    jr      nZ, copy_loop
        323b    c9      ret

check_for_recent_duplicate_floors:
        323c    d5      push    de
        323d    c5      push    bc
        323e    0614    ld      b, 20
        3240    4f      ld      c, a
        3241    1b      dec     de
check_loop:
        3242    1a      ld      a, [de]
        3243    b9      cp      c
        3244    2806    jr      Z, dup_found    ; Duplicate found, bail out.
        3246    1b      dec     de
        3247    05      dec     b               ; Done with all 20 yet?
        3248    20f8    jr      nZ, check_loop
        324a    1804    jr      no_dups         ; Finished all 20, no duplicates.
dup_found:
        324c    3eab    ld      a, 0xab         ; 0xab is a sentinel indicating a duplicate.
        324e    1801    jr      done
no_dups:
        3250    79      ld      a, c            ; Restore the caller's a register.
done:
        3251    c1      pop     bc
        3252    d1      pop     de
        3253    c9      ret
The important part is the copy_last_20_into_history label at the end of generate_random_floor_schedule. There is an array of 99 bytes at 0xc311 that I call heading_out_floor_schedule, which holds the randomly generated floor schedule. There is also a buffer that starts 20 bytes before heading_out_floor_schedule, which I'll call the "history" buffer. Initially, the history buffer is filled with 0xee, which is unequal to any floor number. I thought the purpose of this buffer was just to simplify the code of check_for_recent_duplicate_floors, allowing it to unconditionally look 20 bytes back, even when that goes before the beginning of heading_out_floor_schedule. But the loop at copy_last_20_into_history copies the 20 floors at the end of the schedule into the history buffer. (It's the 20 floors at the end of the schedule only up to the player's chosen number of floors, which may be less than 99.) So on the second and subsequent runs, the history buffer is no longer filled with 0xee, but contains floor numbers from the previous schedule, which affects the subsequent generation of floors, because of the no-repeat rule. It is not the case that there are only 60 possible schedules in each skill level, one for each seed, as was claimed in Post #527972. That's true for the first run, but after that each of the 60 seeds in each skill level will yield a slightly different random sequence of floors than it would have the first time. This is both good and bad. It will likely be possible to visit all unique floors in fewer than the 13 restarts that I had previously computed, because there are more opportunities to affect the RNG sequence. But the search space is greatly increased – we're no longer looking at just 180 basically static schedules – so it may not be possible to find a route that is definitely minimal.
Posted: 6/2/2024 6:34 AM
Post subject: A complete route for Heading Out?, all floors
Quote
Sand
He/Him
Player (143)
Joined: 6/26/2018
Posts: 175
I've been working on the all-floors route since correcting my understanding of how RNG is affected by previously completed floors. As I suspected, it is a harder overall than the set cover / traveling salesman I had envisioned before. But while the larger search space makes solutions harder to find, solutions also have the potential to be faster, with fewer segments and fewer repeated floors. I found a working route for "Heading Out? all unique floors" that hits all 120 floors in 10 segments with no repeats. It's 90741 frames in length. You can find it in User movie #638529018325843149, and I'll say more about it below. I'm planning to try running a few more variations through the route optimizer to see if I can find a faster route. The route optimizer I wrote is the usual uniform cost search kind of thing. It treats the game states (skill, floor schedule, number of unique floors completed) as vertices in a graph. Being at a certain vertex means you have just completed a floor, and you now have the option of playing the next floor in the schedule, or starting a new segment with a new skill and RNG seed. We're trying to find a shortest path from the origin vertex to a vertex that has all floors completed. To make the problem more tractable, I've imposed some simplifying restrictions:
  1. Optimize only one skill level at a time (Easy, Average, or Hard). This means when we follow a "restart" edge, we only have to consider up to 60 seeds in the current skill, not up to 180 seeds across all skills. This restriction could cause the optimizer to ignore some possibilities; for example, suppose there is a route where you play a few segments in Hard, which lines up the RNG just right to solve Average, which then lines up the RNG to finish the rest of Hard.
  2. Don't follow edges ("next floor" or "restart") that would have us repeat a floor that has already been done. This one is actually not much of a restriction, because we expect an optimum route not to have any repeats anyway.
  3. Only consider "restart" edges when "next floor" is impossible because it would cause a repeat. This means that every segment is as long as possible without a repeat. The optimizer will ignore opportunities to restart a segment earlier. Since every "restart" choice means adding up to 60 new vertices to the candidate list (which in turn can add 60 of its own, and so on), this restriction is important for keeping the size of the candidate vertex set manageable.
The Easy and Hard skill levels are not too hard to deal with. Easy has only 30 floors, and we already know that seed 42 works from boot to cover all 30 perfectly. The optimizer finds that single-segment route for Easy instantly. Hard has 40 floors, which makes the optimizer work more, but is still not too bad. Hard can be done after Easy in just 3 segments. The difficult part is Average skill, with its 50 floors. The most progress I have been able to make in Average, so far, is 48 floors. That's with giving it several hours of computation and about 150 GB of space to work with. I tried optimizing the skill levels in the order Easy, Hard, Average. It got to 118 floors before running out of space. The unfinished floors were 76 and 105. I tried restarting the optimizer with just those two floors, and it found a way to cover them with one additional segment each. This is probably suboptimal (even with the restrictions listed above) because it's not a global optimization: we optimized the problem in two parts and glued them together. But it is at least a functional route that can serve as a basis of comparison. Here is the route. The movie file for it is User movie #638529018325843149. The tas.lua script that executes the route is available at commit 32c435cca14ae486f42be4b261a3fa5a061e0c82 in my repo.
SkillSeed# FloorsFloors
Easy423032i, 35i, 55i, 46, 59, 45i, 49i, 58, 56, 33, 30i, 57, 48i, 31i, 47i, 51i, 37, 41, 38, 44i, 50i, 34i, 42i, 53, 43, 54i, 40i, 36, 52i, 39i
Hard3423138i, 110i, 139, 113i, 146, 148i, 111i, 144i, 143, 140, 131, 142i, 136i, 149i, 112i, 147, 121, 129i, 127i, 141, 135i, 115i, 118
Hard2210128, 123i, 145i, 117i, 114, 125i, 119, 120, 133, 137
Hard587132, 122, 126i, 124i, 134i, 130, 116
Average22989i, 98, 90, 108, 71i, 94, 102, 86i, 106, 92i, 103i, 60, 104, 63, 91i, 97i, 64i, 62, 68, 88i, 93, 65i, 74i, 107, 73, 109, 72, 84, 78
Average17967, 69, 75i, 61, 79, 85, 81, 70i, 66i
Average26587, 80i, 77, 82i, 95i
Average13583, 100i, 101i, 99i, 96
Average101105i
Average5176
I'm planning to try a few more experiments with route optimization, but not take it too far. Finding routes with fewer restarts, or more favorable floor inversions, can be left as an opportunity for future improvements.
Posted: 7/10/2024 7:27 AM
(Edited: 8/30/2024 3:53 PM)
Post subject: A route in 90570 frames
Quote
Sand
He/Him
Player (143)
Joined: 6/26/2018
Posts: 175
It was surprisingly difficult to find a route faster than the 90741-frame one I posted as a point of comparison in Post #529667. Long story short, the best route I've found is 90570 frames long, about 2.8 seconds faster. Link to video BizHawk file This route has 8 segments, compared to Post #529667's 10 segments. It has one repeated floor, floor 90 in Average skill, but repeating the floor is faster than restarting with additional segments.
SkillSeed# FloorsFloors
Easy423032i, 35i, 55i, 46, 59, 45i, 49i, 58, 56, 33, 30i, 57, 48i, 31i, 47i, 51i, 37, 41, 38, 44i, 50i, 34i, 42i, 53, 43, 54i, 40i, 36, 52i, 39i
Hard3422138i, 110i, 139, 113i, 146, 148i, 111i, 144i, 143, 140, 131, 142i, 136i, 149i, 112i, 147, 121, 129i, 127i, 141, 135i, 115i
Hard2210128i, 123i, 145i, 117, 114i, 125, 119, 120, 133, 137
Hard588132, 122i, 126, 124i, 134i, 130, 118, 116
Average3712109i, 100, 106, 104i, 98i, 65i, 63i, 93, 90, 73i, 95i, 96
Average21589i, 108, 71, 94, 87i, 102, 86, 92i, 80, 103i, 60i, 91, 97, 64, 62i
Average41568, 82i, 83i, 74i, 99, 70i, 76, 84i, 101, 77, 67, 90, 69, 107, 105i
Average17978, 75, 61i, 79, 88, 72, 85, 81i, 66i
I started using an abbreviated notation to describe routes. The above route is E42x30-H34x22-H22x10-H58x8-A37x12-A02x15-A04x15-A17x9. Here are other routes I discovered and tested over the past month:
RouteSegmentsRepeatsFramesComment
E42x30-H34x23-H22x10-H58x7-A26x2-A21x16-A45x17-A04x8-A17x99291644
E42x30-H34x22-H22x10-H58x8-A21x3-A21x12-A45x16-A03x3-A04x8-A17x910191528
E42x30-H34x22-H22x10-H58x8-A21x5-A37x13-A45x7-A04x14-A17x10-A53x110090930
E42x30-H34x23-H22x10-H58x7-A21x6-A37x11-A45x13-A04x12-A48x2-A17x610090904
E42x30-H34x23-H22x10-H58x7-A21x6-A37x12-A45x13-A04x11-A53x1-A17x710090902
E42x30-H34x23-H22x10-H58x7-A26x2-A21x22-A17x10-A19x5-A04x8-A45x310090896
E42x30-H34x23-H22x10-H58x7-A02x29-A17x9-A26x5-A10x1-A14x3-A13x310090873Best with UCS
E42x30-H44x8-H41x15-H22x5-H07x4-H58x8-A45x3-A25x1-A23x2-A48x4410090786
E42x30-H44x8-H41x17-H22x4-H07x4-H58x7-A22x1-A45x3-A25x4-A48x4210090743
E42x30-H34x23-H22x10-H58x7-A02x29-A17x9-A26x5-A13x5-A10x1-A05x110090741Post #529667
E42x30-H34x22-H22x10-H58x8-A37x12-A02x14-A04x16-A17x98190578
E42x30-H34x22-H22x10-H58x8-A37x12-A02x13-A04x17-A17x98190577
E42x30-H34x22-H22x10-H58x8-A37x12-A02x15-A04x15-A17x98190570This post
I let the uniform cost search optimizer from Post #529667 keep running for a week or so. It did eventually find an exact solution, E42x30-H34x23-H22x10-H58x7-A02x29-A17x9-A26x5-A10x1-A14x3-A13x3. The optimizer doesn't take into account the fact that the time to restart a new segment is variable (mainly because of the time to wait for the next RNG seed), because that it too hard to simulate. So the idea was to get some fast route candidates, then get precise frame counts for them by executing the routes in the emulator. (Because the TAS is automated using a Lua script, testing candidate routes doesn't require manual TASing.) The optimizer estimates that E42x30-H34x23-H22x10-H58x7-A02x29-A17x9-A26x5-A10x1-A14x3-A13x3 is 18 frames faster than the E42x30-H34x23-H22x10-H58x7-A02x29-A17x9-A26x5-A13x5-A10x1-A05x1 of Post #529667, but when actually played out, it's actually 183 frames slower. If allowed to continue, the optimizer would eventually have gotten to E42x30-H34x23-H22x10-H58x7-A02x29-A17x9-A26x5-A13x5-A10x1-A05x1 and competitive routes, but here I decided to try something different, a genetic algorithm. The genetic algorithm has the advantage that is is not bound by the simplifying restrictions introduced to make the problem more tractable. In particular, it's allowed to repeat floors, and start a new segment even when the current segment is not just about to hit a repeat. The tradeoff, of course, is that there's no guarantee of optimality. The first breakthrough was when the genetic algorithm found the solution H34x22-H22x10-H58x8 for the Hard floors. This is very similar to how Hard was solved in Post #529667, H34x23-H22x10-H58x7, just moving one floor from the seed 58 segment to the seed 34 segment, but its slightly different history buffer of recently played levels clears the way for a faster clear of Average. I ran the genetic optimizer several thousand times and tested the best routes it found. Ultimately the best one is the one you see in the video above. The tas.lua script to execute it is in commit 78a676ebcde7f6885d99b751ac27d3f1683df17f in my repo.
Posted: 8/30/2024 5:22 PM
(Edited: 8/30/2024 5:23 PM)
Post subject: 90570-frame route submitted.
Quote
Sand
He/Him
Player (143)
Joined: 6/26/2018
Posts: 175
Sand wrote:
It was surprisingly difficult to find a route faster than the 90741-frame one I posted as a point of comparison in Post #529667. Long story short, the best route I've found is 90570 frames long, about 2.8 seconds faster.
I've submitted the 90570-frame route E42x30-H34x22-H22x10-H58x8-A37x12-A02x15-A04x15-A17x9: #9257: Sand's GB Kwirk "Heading Out?, all floors" in 25:15.19. The video encode has a tracker on the side that shows what floors have been completed. It also shows the frame counter used to seed the RNG, and the RNG seed for the current segment. Link to video
Posted: 9/1/2024 4:57 AM
(Edited: 9/1/2024 5:02 AM)
Post subject: Video using cheat code
Quote
Sand
He/Him
Player (143)
Joined: 6/26/2018
Posts: 175
Sand wrote:
I just learned there's a cheat code in Heading Out? mode. If you hold the Left and Select buttons while confirming the "Select Display" menu, then the floor schedule will be overwritten to play all the floors in the chosen skill level, exactly once and in order. Each floor may still be inverted or not, but the cheat code skips seeding the RNG, so the inversion schedule is always the same as well. (Unless you've played an earlier round to set the seed.) This cheat code would obviously be the fastest way to play all floors in Heading Out? mode, but I'm not planning to use it in the TAS, because it would take away the fun of RNG seed routing.
Out of curiosity, and because I wanted to make a speedrunning guide, I hacked the tas.lua script to use the cheat code and play all the floors in order, in 3 segments. The total time is 87537 frames and 24:25.128. That's 3033 frames and 50.071 seconds faster than the 90570 frames and 25:15.195 of Post #530388, with its 10 segments. That tracks with the estimate of each restart costing about 8 seconds. Using the cheat code, it might be possible to get a slightly lower time by playing the difficulty levels in a different order. The floors would be the same, but they would be inverted differently.
SkillSeed# FloorsFloors
EasyN/A3030, 31i, 32, 33, 34, 35, 36i, 37i, 38i, 39, 40, 41, 42i, 43, 44, 45, 46, 47, 48, 49, 50, 51i, 52, 53i, 54, 55, 56, 57i, 58, 59i
AverageN/A5060i, 61i, 62, 63, 64i, 65, 66, 67i, 68, 69i, 70i, 71, 72, 73, 74i, 75i, 76i, 77, 78, 79i, 80i, 81, 82, 83, 84, 85, 86, 87i, 88, 89i, 90i, 91, 92i, 93i, 94i, 95, 96, 97, 98i, 99, 100, 101, 102, 103, 104, 105, 106, 107i, 108, 109i
HardN/A40110i, 111, 112, 113, 114, 115, 116i, 117i, 118, 119, 120i, 121, 122, 123i, 124, 125i, 126i, 127, 128, 129i, 130i, 131, 132, 133, 134i, 135, 136i, 137, 138, 139, 140, 141, 142, 143i, 144, 145i, 146i, 147, 148, 149
Link to video
1 2