Kwirk is a block-pushing puzzle game for Game Boy.
This is a speedrun of the game's "Heading Out?" mode,
which is a time attack of small puzzles, drawn randomly.
The goal of this run is to clear all 120 unique floors of this mode as fast as possible.
Besides solving each individual floor quickly,
this requires manipulating RNG to access unplayed floors.
Game objectives
- Emulator used: BizHawk 2.9.1
- Clears every floor in Heading Out? mode at least once
- Aims for fastest real time
- Manipulates luck
Suggested screenshot: frame 21507
Kwirk has two game modes.
Going Up? mode is the "adventure mode":
you play 30 full-size floors in a fixed order
across three difficulty levels, Easy, Average, and Hard.
Heading Out? mode is the "time attack mode":
you choose a difficulty level and a number of floors,
and the game gives you that many mini-floors to play,
with time-based scoring.
The floors in Heading Out? mode are drawn randomly
from a pool of 120,
distributed over the three difficulty levels:
30 in Easy, 50 in Average, and 40 in Hard.
That still leaves Heading Out? mode, which does not have a published TAS.
The puzzles in Heading Out? are smaller, enough that
my relatively simple solver could find
optimal solutions for all of them.
While the floors are smaller, there are more of them:
120 compared to 30 in Going Up? mode.
And while you can choose the difficulty and number of floors (from 1 to 99),
the actual floors you get are randomly selected by the game.
RTA runners play Heading Out? in
a single segment of 10 or 99 floors,
taking whatever floors the RNG gives them.
(Which entails playing some floors more than once, in the 99-floor case.)
For the TAS I decided to do something different:
clear all 120 floors at least once,
over multiple segments (allowing to re-seed the RNG between segments, at the cost of time).
This is a new, invented category,
but one I think is well-suited to a TAS.
It adds another dimension to the optimization,
because in addition to playing each floor optimally,
you have to coax the RNG into giving you floors you haven't seen yet.
The video encode attached to this submission has a tracker
that shows which floors have been cleared so far.
Floor solver
The solver for individual floors is nothing very special.
It is the typical breadth-first,
uniform cost search
kind of thing,
with a reimplementation of the game rules
and knowledge of
the cost in frames of each action, such as:
9 frames to step into an empty tile,
28 frames to push a block into a hole,
12 frames to rotate a turnstile.
As there is no randomness within floors,
all solutions can be pre-computed as
fixed move sequences.
I am confident the per-floor solutions are optimal.
The game counts "steps" as well as frames.
This run tries to minimize real time (frames),
not steps or in-game time.
Random floor scheduling
The floors in Heading Out? are
internally numbered
30–59 for Easy,
60–109 for Average, and
110–149 for Hard.
Floor numbers 0–29 are used for Going Up? mode.
The
RNG is seeded,
at the start of each segment,
with a frame counter mod 60.
This means the only possible seeds are 0–59,
and you can get any seed you want
by waiting at the confirmation menu for up to 1 second.
A complete schedule of floors is
generated
as soon as you hit Start.
There is no way to affect the RNG while playing a segment,
only between segments.
In the video encode attached to this submission,
you can see the constantly updating frame counter that is used to set the RNG seed (in gray),
and the seed used for the current segment (in white).
Each floor has a 50% random chance of being
inverted (flipped vertically).
This does not have much of an effect on gameplay or routing.
The inverted version of a floor has essentially the same solution as the normal version,
but it may be slightly faster or slower to solve,
because inversion affects the shape of the passages
into and out of the central puzzle area.
It might seem that there are only 60 possible floor schedules
per difficulty level,
which is
what I thought at first.
But there's an important complication.
The game keeps track of the 20 most recently played floors,
and will never repeat a floor that is in that set.
This filter remains in effect across segments
and even across difficulty levels,
because the set of recently played floors is indexed
relative to the start of the difficulty level.
This means, for example, that if you have just cleared floor 35 (which is index 5 in Easy)
and started a new segment,
none of the next 20 floors can be
35 (index 5 in Easy),
65 (index 5 in Average), or
115 (index 5 in Hard).
Massaging the random floor generation algorithm
with this cross-segment carryover
is critical for getting long sequences of
not-yet-played floors.
But it's not simple to optimize.
(If you think of it as a graph search problem,
the
branching factor is about 181,
because after clearing a floor you have the option of
continuing in the current segment,
or starting a new segment in one of 3 difficulty levels and one of 60 random seeds.)
The route used in this run is the result of a computer search.
In the end I turned to a
genetic algorithm
to find the segment route shown below,
which has 8 segments and 1 repeated floor.
I am pretty happy with this route,
but it has no proof of optimality.
It may be possible to improve on this route,
whether by using fewer segments,
repeating no floors,
repeating a
shorter floor,
getting more favorable inverted floors,
or spending less time waiting for RNG seeds to roll around.
Seed 42 in the Easy difficulty level is extremely lucky.
On a freshly started game,
seed 42 hits all 30 floors exactly once with no repeats.
The route starts there, because it's hard to beat for efficiency.
It only works when it's the first segment,
and the history of recently played floors is empty.
If you've already played a segment,
the recently played floors filter will cause you to get
a different sequence of floors
that no longer covers all 30 possibilities cleanly.
The route
The route consists of 8 segments.
Only 1 floor is repeated, floor 90 in the Average difficulty level.
An "i" suffix means the inverted version of a floor.
| Skill | Seed | # Floors | Floors |
|---|
| Easy | 42 | 30 | 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 |
| Hard | 34 | 22 | 138i, 110i, 139, 113i, 146, 148i, 111i, 144i, 143, 140, 131, 142i, 136i, 149i, 112i, 147, 121, 129i, 127i, 141, 135i, 115i |
| Hard | 22 | 10 | 128i, 123i, 145i, 117, 114i, 125, 119, 120, 133, 137 |
| Hard | 58 | 8 | 132, 122i, 126, 124i, 134i, 130, 118, 116 |
| Average | 37 | 12 | 109i, 100, 106, 104i, 98i, 65i, 63i, 93, 90, 73i, 95i, 96 |
| Average | 2 | 15 | 89i, 108, 71, 94, 87i, 102, 86, 92i, 80, 103i, 60i, 91, 97, 64, 62i |
| Average | 4 | 15 | 68, 82i, 83i, 74i, 99, 70i, 76, 84i, 101, 77, 67, 90, 69, 107, 105i |
| Average | 17 | 9 | 78, 75, 61i, 79, 88, 72, 85, 81i, 66i |
There are
routes with no repeats,
but they are slower overall,
because they require more segments.
The scrolling animation between floors in a segment takes about 3.5 seconds,
while starting a new segment (with the associated fanfares, menuing, etc.) costs around 11.5 seconds.
For perspective, this route with 1 repeat is
171 frames (2.9 seconds) faster than the fastest route I found
with no repeats.
It's a small fraction of the overall time,
but once you've optimized every individual floor,
the only improvements can come from better routing.
The sum of in-game times per segment is 23:39.
| Skill | Seed | # Floors | In-game time |
|---|
| Easy | 42 | 30 | 4:30 |
| Hard | 34 | 22 | 5:37 |
| Hard | 22 | 10 | 2:34 |
| Hard | 58 | 8 | 1:37 |
| Average | 37 | 12 | 2:16 |
| Average | 2 | 15 | 3:02 |
| Average | 4 | 15 | 2:31 |
| Average | 17 | 9 | 1:32 |
| total | | | 23:39 |
I won't comment on every floor, just some of the more noteworthy ones.
01:42 Easy floor 30i
Floor 30i is the shortest floor in Easy,
with 26 steps and 240 frames.
Perhaps surprisingly,
it is not the shortest floor overall,
which is rather floor 76 in Average.
04:25 Easy floor 52i
Floor 52i is the longest floor in Easy,
with 56 steps and 528 frames.
06:13 Hard floor 148i
Floor 148i is the longest floor in Hard,
and the longest of the run overall,
with 132 steps and 1239 frames.
07:40 Hard floor 131
Floor 131 is the shortest floor in Hard,
with 34 steps and 318 frames.
09:53 Hard floor 141
Floor 141 is the only floor
that is not sight-readable,
by which I mean it violates a convention
that is observed everywhere else in the game.
In the initial configuration,
the west spoke of the "T" turnstile
covers a hole tile, which never happens in any other floor,
whether in Going Up? or Heading Out? mode.
Although you cannot see it at first,
without that hole the floor is unsolvable.
18:55 Average floor 86
Floor 86 is the longest floor in Average,
with 128 steps and 1218 frames.
20:54 quick restart
There are two consecutive segments
that both have a difficulty level of Average
and a floor count of 15;
only the RNG seed is different.
Because the difficulty level and number of floors is the same,
we do not even have to
enter the menus
between these two segments,
just wait for the next RNG seed.
This is not something the route optimizer was trained to look for,
just a lucky coincidence.
21:58 Average floor 76
Floor 76 is the shortest floor in Average,
and the shortest of the run overall,
with 26 steps and 238 frames.
22:52 Average floor 90 repeated
Here we repeat floor 90, which is the only repeated floor of the run.
It is a pretty short floor, 41 steps and 388 frames.
It was played for the first time at 16:56.
Availability
My source code and notes are in a Git repository:
git clone https://www.bamsoftware.com/git/kwirk.git
Thanks
nymx: Claiming for judging.
nymx: Re-uploading to correct any possible cycle count issues.
nymx: I'm a big fan of solving tools that optimize game-play. This TAS is no exception. You caught my attention, when you confirmed my
[6148] C64 Match Blox by nymx in 00:55.66 solutions with math...instead of my brute forcing scripts. So naturally, I find your tools and efforts to have great strength, and I have complete confidence in this run. A lot times, I can't see the end coming, until the last moment. In my opinion, that is the sign of a true solution...where human effort can often be foreseen. On top of all this, finding that RNG seed is also important. I've observed a small group of members that really focus on finding that perfect seed. So, with all that said...I'm always cautious about saying that nothing else can be found, but it sure does look like you have clinched this game. Congratulations on excellent work! I look forward to your future submissions!
Happily Accepting!
