Experienced Forum User, Published Author, Player
(125)
Joined: 6/26/2018
Posts: 154
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.
Experienced Forum User, Published Author, Player
(125)
Joined: 6/26/2018
Posts: 154
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).
Experienced Forum User, Published Author, Player
(125)
Joined: 6/26/2018
Posts: 154
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
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
Experienced Forum User, Published Author, Player
(125)
Joined: 6/26/2018
Posts: 154
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 videoBizHawk 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
Experienced Forum User, Published Author, Player
(125)
Joined: 6/26/2018
Posts: 154
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
Experienced Forum User, Published Author, Player
(125)
Joined: 6/26/2018
Posts: 154
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.
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:
Experienced Forum User, Published Author, Player
(125)
Joined: 6/26/2018
Posts: 154
Deadcode wrote:
Sand wrote:
But now I suppose that I really had correctly measured 28 frames when I tested it myself the first time. Unfortunately I don't have movie files, but if I had to guess, I probably would have been testing frame timings with the 2×3 in 1-4 or the 1×1 in 1-5.
So does that mean you were doing your test runs in Bird's-eye View even though I hadn't submitted my TAS yet?
Correct, I was using bird's-eye. Besides finding bird's-eye easier to read, I found a post at speedrun.com that says "you want to make sure that you use bird eye as view mode, this mode alows you to move faster after a cutscene."
I should mention that I tested the timing of a couple of level transitions in diagonal and bird's-eye, and I didn't find a difference. I'm not sure what I was doing wrong/differently. I may have only timed the flashing "exit" animation and the stripes "enter" animation; does the lag happen in the "You did it!" screen? I regret not saving the recordings, but anyway here are excerpts from my notes:
Birds-eye level transition
10295 -> 10296 -> 10518 223
11370 -> 11593
11907 -> 12129 222
16094 -> 16316 222
16550 -> 16774 224
17041 -> 17265 224
17731 -> 17955 224
Diagonal timings
1-1 in 1146 -> 1317 171
1-1 out 1527 -> 1725 198
1-2 in 1781 -> 1952 171
1-2 out 2118 -> 2316 198
intra-level frame count is as predicted, for 1-1 and 1-2 at least
Birds-eye timings
1-1 in 1180 -> 1351 171
1-1 out 1561 -> 1759 198
1-2 in 1814 -> 1985 171
1-2 out 2151 -> 2349 198
intra-level frame count is as predicted, for 1-1 and 1-2 at least
Experienced Forum User, Published Author, Player
(125)
Joined: 6/26/2018
Posts: 154
Deadcode wrote:
It assumes that a push-fill always takes 10 frames to push and 26 frames to fill. But with your demonstration, it appears that sometimes it only takes 28 frames total.
That explains something for me. When I posted the comparison in Post #527971, at first not all my frame count predictions matched the ones in this submission. Some of mine were faster in multiples of 8: e.g., 8 frames faster, 56 frames faster, 16 frames faster. I deduced that the mismatches were in levels in which blocks were pushed into holes, and the reason was that in my solver, I had coded the cost of pushing a block into a hole as a flat 28 frames. After I edited my program to make pushing blocks into holes cost 10+26 frames, all my frame count predictions matched up, so I assumed I had just made a careless mistake when first measuring the cost myself. (I also found Post #215759 which corroborated 10+26.) But now I suppose that I really had correctly measured 28 frames when I tested it myself the first time. Unfortunately I don't have movie files, but if I had to guess, I probably would have been testing frame timings with the 2×3 in 1-4 or the 1×1 in 1-5.
Experienced Forum User, Published Author, Player
(125)
Joined: 6/26/2018
Posts: 154
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.
Experienced Forum User, Published Author, Player
(125)
Joined: 6/26/2018
Posts: 154
This is absolutely amazing! Brilliant work.
Coincidentally I started working on a Kwirk solver about a month ago, not being aware of the ongoing DDD work. This is way beyond what I was able to do. I was only able to find solutions for 19 of the 30 levels. (The easy ones: most of those can be solved in 10 seconds or less using just RAM as storage.) The only improvement I had found over [4105] GB Kwirk "Going Up?" by Nitrodon, ZenicReverie, Alyosha in 15:46.03 was 100 steps in 3-1, same as this submission.
I didn't get as far as starting to TAS the levels in an emulator, but I can confirm that your frame/step counts match my predicted ones for the levels I was able to solve: 1-1, 1-2, 1-3, 1-4, 1-5, 1-6, 1-7, 1-8, 1-9, 1-10, 2-1, 2-3, 2-4, 2-5, 2-10, 3-1, 3-2, 3-3, 3-5.
I see DDD-Kwirk takes into account that in multi-player levels, a "Switch" move immediately after another "Switch" is 2 frames slower. I think you can save 2 frames in 2-9 by reordering moves to break up an instance of consecutive "Switch" moves. Starting at frame 24745, the sequence goes:
(playing Pete) Left Down Up (Switch to Kwirk) (Switch to Eddie) Right Right Up Up (Switch to Pete) Left Left Down Left Left Down (Switch to Kwirk) Up Up
You can move one of Kwirk's later "Up" moves to be in between the first two "Switch"es, without interfering with the rest of the sequence:
(playing Pete) Left Down Up (Switch to Kwirk) Up (Switch to Eddie) Right Right Up Up (Switch to Pete) Left Left Down Left Left Down (Switch to Kwirk) Up
The only other level where this could matter (levels with 3 or 4 players) is 3-8, and it looks like that one is already free of consecutive "Switch".