Submission #9235: mohoc's GBA Kuru Kuru Kururin "100%" in 23:51.95

Game Boy Advance
100%
(Submitted: 100%)
(Submitted: Kuru Kuru Kururin (Europe).gba Europe)
BizHawk 2.9.1
85527
59.7275005696058
0
PowerOn
Submitted by mohoc on 8/15/2024 3:48 PM
Submission Comments
My second submission here, I hope you will all enjoy it as much as the first one!
To the best of my knowledge, this is the first 100% TAS of this game.
ROM SHA1 checksum: 6025ef597db2684ae064ffe22b4fd1d37941f887

About the game

Released in 2001 as one of the GBA launch titles, Kuru Kuru Kururin is an unusual game that is a mix of racing/puzzle genres. The player controls a slowly spinning stick called the Helirin, and must maneuver it through a series of mazes. The player controls the direction and speed of movement but not the Helirin's constant rotation.

About the run

  • Emulator used: Bizhawk 2.9.1, mGBA core
  • 100% completion
  • Uses a game restart sequence
  • Genre: Puzzle
  • Genre: Racing
The goal is to complete everything the game has to offer in Normal difficulty. In other words, we must complete the following tasks:
  • complete all 93 levels without taking damage (5 Training levels, 33 Adventure levels and 55 Challenge levels),
  • get all 30 Make Up items (skins and birds),
  • get the Master rank (in-game time target in 85 levels),
  • reach the credits.

The basics

Objective of a level

Reach the goal zone (= yellow zone).
When you hit a wall, you lose a heart. If you lose all your three hearts, the Helirin breaks and you must restart the level from the beginning. In some levels there are heart zones on your way that heal you and prevent you from taking damage.
There is a collectible item in each Adventure level from Grasslands 1 to Ghost Castle 3. It is a bird in the third level of each world and a cosmetic bonus in the other levels. You reach the credits when you save all ten birds.
If you complete a level without taking damage then it becomes a star on the level selection menu. The Last Land is unlocked when all Adventure levels from Grasslands 1 to Ghost Castle 3 are stars. And the eleventh row of Challenge levels (from 11-1 to 11-5) is unlocked when all Challenge levels from 1-1 to 10-5 are stars.

Position

Position is given by a triple (X,Y,R) with X,Y the coordinates and R the angle of the Helirin.
  • X and Y are 32-bit values. Both can be interpreted as a triplet (pixel,subpixel,subsubpixel) with the pixel in the range [-32768..32767] and both subpixel and subsubpixel in the range [0..255]. Subsubpixels are rarely relevant, so it is usually enough to work with the couple (pixel,subpixel).
  • R is a 16-bit value in the range [0..65535]. 0 and 32768 are vertical (32768 is 180°).
Axes:
 ― — > X
|
|
v
Y

Speed under ”normal” behavior

X/Y speed depends on how many A/B buttons are held. The more buttons you hold, the faster you go. Base speed is 1.5 pixels per frame. Holding 1 (resp. 2) action button(s) makes you go 1.5x (resp. 2x) faster. So top speed under ”normal” behavior is 3 pixels per frame.
Rotation is at a constant +/-182 rate, which is about 1° per frame. + is clockwise. A rotation cycle is 180° and corresponds to a bit more than 180 frames, which is about 3s in real time.

Collision

When you hit a wall you get pushed back. It has an impact on all three parameters:
  • you get an X/Y bump speed that decreases with time (it takes them about 30 to 40 frames to get back to zero).
  • your rotation speed is set to +/-1024 and gradually gets back to its initial value (it takes about 15 frames). When collision lasts two or more consecutive frames, rotation speed switches back and forth between +1024 and -1024, which could result in your rotation being sped up instead of being pushed back.

Springs

Some levels include blue springs. They are the only way to switch between clockwise and counterclockwise motion. They can also be used to speed up rotation.

Moving objects

Some levels include pistons and spiked balls. They hurt. Their movement is cyclic and fixed: if you hit them, they will not deflect.
Some levels also feature cannons, which turn on the spot to aim at the Helirin and shoot periodically.

Horns

The best feature in the game. While in a level, press L or R to have fun. Holding A/B while pressing L or R gives other sound effects for a grand total of six.
#A/B pressed L R
0 Low pitched horn Squeak horn
1 Bicycle bell Dog barking
2 Horse neighing Rooster crowing

Glitches and tricks used

No damage means no major glitches

Note that 100% requires you to beat every level without taking damage. As a result it is not possible to go out of bounds to take shortcuts, reach faster speeds or reach duplicate goal zones. You also cannot take intentional hits to get pushed back and skip rotation cycles… unless you are in a safe zone (i.e. the starting zone or a heart zone).

Safe zone tricks

As a long as the center of the Helirin is in a safe zone, you are protected from any form of damage. This allows you to hit walls either to go back in your rotation or to speed it up.
Additionally bumping a wall grants you a bump speed of up to 2 pixels per frame which decreases over time. The direction of this bump speed depends on both the Helirin position and the input pressed during the bump. These can be manipulated to reach speeds of up to 5 pixels per frame in the desired direction instead of just 3 with movement speed alone. The first notable example in the run is in Jungle 2.

Spring tricks

While the main purpose of springs is to switch between clockwise and counterclockwise motion, you can keep interacting with them in order to speed up your rotation like at the end of Ocean 3.
When springs are not positioned along a wall, you can also go through them to get a significant speed boost. When you hit multiple springs at the same time, these boosts can add up and make you go stupidly fast. The most notable example is at the end of Star Land 3. While this is definitely an intended mechanic, it can be used in more subtle places like the second half of Cave 2.

Credits storage

When you complete the third level of any Adventure world from Grasslands to Ghost Castle, the game checks if you saved all ten birds. If so, it triggers the credits which are intended to be unskippable and only visible once per save file. However while a bird is counted as being saved right when the level result screen appears, the credits are counted as being watched only at their very end. So if you reset the game beforehand, you can skip the credits while saving your progress. Then the credits can be triggered again at any time by completing the third level of any Adventure world another time from Grasslands to Ghost Castle.

Routing

Below is an overview of the route (which is actually the same as in RTA speedruns):
  • Say “No” to the tutorial and complete Grasslands 1.
  • Go back to the Tutorial levels and complete them.
  • Complete Adventure levels from Grasslands 2 to Ghost Castle 3.
  • Reset the game at the Ghost Castle 3 results screen to skip credits.
  • Head to Challenge mode and complete all levels from 1-1 to 11-5.
  • Go back to Adventure mode and complete the three Last Land levels.
  • Select and complete Grasslands 3 (this time possibly with damage) to trigger credits again.
The initial back and forth between Adventure levels and Tutorial levels skips several seconds of slow scripted movement in the Adventure map. Other than that the route is rather straightforward. The objectives in each level (i.e. no damage completion, the Master in-game time to beat and the item to collect in Adventure levels) can all be achieved in a single run.
Overall this game tends to run quite consistently with very little desync/extra lag issues. I did get two single frames of extra lag throughout this TAS: one during the “Goal” animation of Star Land 3, and one after selecting Last Land 1. I also delayed entering Last Land 1 by one frame to avoid a massive lag spike. For now these lag occurrences and their causes are not well understood.
Other than that I took a 29 frame detour right before Challenge mode to open the Make Up menu and put all birds on the Helirin. This brings additional entertainment value in both Challenge mode and Last Land levels. Note that this is only extra menuing and it does not bring any gameplay change, so I believe that it does not warrant the “Contains speed/entertainment tradeoffs” tag.

Tools

Memory watch

A .wch file is available here.
Name Address (IWRAM) Size Description
X / Y 0x4544 / 0x4548 32 bits Position of the center of the Helirin. If you only look at the 16 most significant bits, you get the position in pixels.
XB / YB 0x454C / 0x4550 32 bits Bump speed. A bump speed is applied when the Helirin hits a wall, then it decreases gradually.
XS / YS 0x4554 / 0x4558 32 bits Input speed. It only depends on the direction pressed at the previous frame.
Angle 0x4572 16 bits Angle of the Helirin. 0 and 32768 are vertical. 216 = 65536 corresponds to 360°. For instance: (90 / 360) * 216 = 16384 is 90°.
Angle Rate 0x4574 16 bits Rotation speed. It is 182 or -182 by default, but it momentarily changes when the Helirin hits something.
Default Rate 0x4576 16 bits 182 when the Helirin rotates clockwise, and -182 when it rotates counter-clockwise. Can change when hitting a spring.
Invulnerability 0x4585 8 bits Number of invulnerability frames left. Grows to 20 when the Helirin loses a heart, then decreases by 1 every frame until 0. This value is decremented before being used, so having it to 1 is equivalent to having it to 0.
MapW and MapH 0x313C / 0x313E 16 bits Size of the map in a number of tiles. A tile is 8x8 px so multiplying these numbers by 8 gives the size of the map in pixels.
Collision Mask 0x45D4 32 bits Indicates which parts of the Helirin are in collision with a wall.

TAStudio

While this game can have (very) occasional desync/lag issues in menus, to my knowledge there are no known instances of this occurring during gameplay. As a result my progress was nonlinear and I just had to glue the segments together at the end. This has made TAStudio a very efficient and comfortable interface to work with.

KuruBot

Bot designed by E-Sh4rk. Efficient and customizable tool to help finding new strategies in Kuru Kuru Kururin’s levels (more details in the “Technical details” section). Available on Github.

Technical details

Game physics

A thorough breakdown is available in the submission notes of the fastest completion TAS. Here I focus on the information most relevant to the 100% category.

Collision mask
Even though the Helirin is 63 pixels long, only 17 points are checked for collision. These points, which I call collision points, are marked as “O” below. (O) is the center, which is also a collision point.
    O⁃⁃O⁃⁃⁃O⁃⁃⁃O⁃⁃⁃O⁃⁃⁃O⁃⁃⁃O⁃⁃⁃O⁃⁃⁃(O)⁃⁃⁃O⁃⁃⁃O⁃⁃⁃O⁃⁃⁃O⁃⁃⁃O⁃⁃⁃O⁃⁃⁃O⁃⁃O
In order to keep track of which points are in collision, the game uses a collision mask. The collision mask is a 32-bit value that must be read in binary: each bit tells if a certain point is in collision with something. If we number collision points in the following way:
16⁃⁃14⁃⁃⁃12⁃⁃⁃10⁃⁃⁃8⁃⁃⁃6⁃⁃⁃4⁃⁃⁃2⁃⁃⁃(0)⁃⁃⁃1⁃⁃⁃3⁃⁃⁃5⁃⁃⁃7⁃⁃⁃9⁃⁃⁃11⁃⁃⁃13⁃⁃15

then (with 0 being the least significant bit): bit n°i is 1 when point i is in collision with a wall.
(Note that the bits 17 to 31 are not used.)
This can be abused around wall corners to clip part of the Helirin inside a wall without taking damage. In practice the constant rotation makes it hard to keep such a state for more than a couple frames. Nevertheless this explains why this curiosity in Last Land 2 is even possible.

Speed
Speed can be decomposed in the following way:
  • Rotation speed:
    • constant +/-182 under normal conditions, temporarily changed to (+/-)1024 when hitting a wall, then returns to its initial value by steps of 91 per frame.
  • X/Y speed:
    • Input speed: based on the input. The norm is 3, 2.25 or 1.5px/frame depending on the number of A/B buttons that are held. It changes instantly (no inertia, instant acceleration). If applying this speed would make the Helirin hit a wall, then it is canceled (so the player has no control when the Helirin hits a wall).
    • Bump speed: applied when the Helirin hits a wall. The norm is 2px/frame. It takes the same direction as the vector starting from the collision point to the center of the Helirin. It is then multiplied by 3/4 each frame until reaching 0. If both sides of the Helirin are in collision at the same time, then no bump speed is applied (which sounds reasonable since the game cannot determine in which direction to apply it).
    • Wall speed: only applied when the center of the Helirin hits a wall, with a norm of 4px/frame. This results in a damage hit, so it has only been triggered at the very end of this TAS in the final Grasslands 3 completion with damage.
So the theoretical max X/Y speed with no damage and no spring interaction is 5px/frame if you are in (or around) safe zones and 3px/frame otherwise.

KuruBot


General
KuruBot is a program written in C# by E-Sh4rk. At the center of it is a shortest path finding algorithm based on a recreation of the Kuru Kuru Kururin game physics. It comes with a graphical interface and the possibility to connect to Bizhawk via a Lua script. Then emulator states can be loaded into KuruBot, and conversely the input sequences found by KuruBot can be sent to the emulator in order to be played back. Since KuruBot was already introduced in the submission notes of the fastest completion TAS, in this section I focus on giving advice on how to use it effectively.
KuruBot uses a custom A* as its shortest path finding algorithm. A* relies on a cost map to guide the search. In a no damage completion the level layout must be followed and is generally closer to a linear path than an open area. So a flooding-based heuristic which follows the level layout works well as a base cost map.
While KuruBot is a powerful and convenient tool, it does not trivialize the TASing process, especially in the longer levels. Indeed the overwhelming size of the search space calls for clever ways to reduce the number of explored states with minimal impact on optimality. In other words depending on the level one must find the right balance between precision and time complexity. This process takes place in two stages.

Level segmenting
The first stage is to break the level into small segments which can be optimized in isolation. This is made possible by a drawing option setting a custom target. Such a level decomposition typically revolves around the safe zones and the bottlenecks (i.e. the narrow portions where a waiting time is most likely inevitable). Ideally a segment should end right after a bottleneck in order to ensure the continuity with the following segment. And whenever possible it should begin right before a safe zone or a set of springs in order to explore the many rotation alternatives offered by these regions.
Below is an example with Ocean 1. Here is the layout of this level:
There are two easily identifiable bottlenecks, conveniently with a set of springs after each one. So one can consider the following segments successively in KuruBot:
In practice the first bottleneck was actually fake, so the first two segments could be merged in the hope of finding a slightly faster strategy.
In most Adventure levels (especially the longer ones) this level segmenting was not this simple. Depending on the strategy some bottlenecks may become “reverse bottlenecks”, where there is no waiting time around them but they still limit possibilities for the following relevant bottleneck. In such situations you want to go past the reverse bottleneck while advancing your rotation as much as possible. There is one such example at the beginning of Ocean 2.

Parametrization
The second stage is to find the best KuruBot parametrization for each of these segments. A number of parameters for the A* cost map and the reduction rates are gathered in configuration files that the user can access and modify at will. Some examples of configuration files are given in the releases. These files come in three types: bot configs, bot modifiers and gameplay configs. They must be loaded in this order and multiple files of each type can be combined.
A bot config sets the base values of the main parameters like the reduction rates, the properties of the flooding-based cost map and whether you are allowed to take damage. I mainly used the “config_damageless_precise.ini” default file, sometimes with some adjustments on the additional reduction applied far from walls.
A bot modifier can alter specific parameters without having to reload a bot config. For example by default KuruBot only considers inputs with the fastest speed, i.e. with both A and B pressed. So you can load the “allow_minimal_speed.ini” to also consider slower speeds, at the expense of increased running time and space. The files of the form “decrease_cost_map_k.ini” for some k were notably useful in levels filled with springs like Cave 2 and Star Land 3. Their role is to mitigate the impact of the flooding-based heuristic on the cost map. This results in a more width-oriented search, which is more prone to find the speed boosts coming from multiple spring interactions that KuruBot was not primarily designed around. However this had a significant impact on both the running time and RAM usage, so I recommend using these files sparingly.
Finally a gameplay config can set parameters outside the A* algorithm and its cost map like changing the Helirin size between Easy and Normal difficulty or enabling moving objects. From my experience the latter slows down the search by quite a lot, so it should only be used when necessary.

Dynamic between stages
In practice there is a lot of back and forth between both stages. If no good parametrization can be found for some segment (i.e. either the proposed input sequence is too slow or the running time is too high for every parametrization) then the level segmenting must be reimagined. For example the concerned segment can be made smaller, notably with one less bottleneck, at the expense of another segment or the addition of a new one. Conversely if a solution was quickly found then some level segments can be merged with other ones, notably those with a safe zone in it, in the hope of finding faster transitions from one bottleneck to the next one. This process was particularly challenging in the Machine Land, Ghost Castle and Last Land levels.
For some segments it was not rare to reach an hour of running time and 10GB of RAM usage. As such it was crucial to use the drawing options of KuruBot, notably the one setting additional constraints manually, in order to limit the width of the search and focus around a theorized optimal path.

Times per level

Why not IGT?

Although the game gives an in-game time per level, I decided to go for real-time. The main reason is that the in-game time only starts when you leave the starting zone. Other than an extra waiting time at the beginning of most levels the resulting TAS would be very similar. So in my eyes it would have made for a slightly (albeit strictly) worse experience.
Note that I plan to make both an “All levels, No Damage, Fastest IGT” TAS and an “All Levels, Fastest IGT” TAS in the future, with the intention of submitting the latter to TASVideos.

Table

A detailed time breakdown (including the Master time and the in-game time obtained in each level) is available in this Google spreadsheet. The individual level movie files are available on Github.
The following table gives the time spent in each level from Helirin control to entering the goal zone (= when Kururin looks happy). This is compared to several previous works:
  • ”Matt” refers to the 2015 “cheat bot” ““100%”” TAS by Matt Shepcar, which was actually an “All Make Up, No Damage” run. A higher quality encode with quality of life changes (i.e. less shaky camera movement) and minor improvements (i.e. less than a second total) is available here.
  • ”Negi-san” refers to this 2014 IGT-focused “All Adventure Levels, No Damage” TAS by some Japanese TASer(s). At the start of each level the Helirin stood still until the desired rotation angle was reached, so the comparison with real time-focused runs is not completely fair. Even so nearly all the featured strategies were the fastest known at the time even in real time. The time in parenthesis removes the standing still time at the start and serves as a lower bound of their strategy in each level. Note that they did not systematically collect the items, so I only referenced the times that were comparable.
  • ”kentora12” made a low-optimized “All Levels, No Damage” TAS back in 2012, the first of its kind to my knowledge. Again the items were not systematically collected in Adventure levels, so I only referenced the times that were comparable.
Level nameTASMattNegi-sankentora12
Training 11.98/2.39 (1.86)2.23
Training 22.51/3.15 (2.65)2.63
Training 33.37/3.82 (3.37)4.03
Training 43.21/4.07 (3.23)3.83
Training 52.23/3.80 (2.33)2.24
Grasslands 16.196.19/ (/)7.53
Grasslands 211.1011.10/ (/)/
Grasslands 312.7412.74/ (/)16.06
Ocean 15.966.01/ (/)/
Ocean 210.1510.5513.23 (10.67)/
Ocean 320.1920.38/ (/)28.06
Jungle 113.0913.0914.83 (14.83)/
Jungle 210.9510.9512.66 (12.44)/
Jungle 318.3018.3218.99 (18.99)26.57
Cake Land 116.4716.7818.32 (16.44)/
Cake Land 229.4729.4835.36 (34.16)44.60
Cake Land 326.8426.9728.01 (27.41)29.52
Cave 18.668.668.79 (8.72)/
Cave 217.3017.33/ (/)/
Cave 316.1416.1419.59 (17.88)20.98
Cloud Land 18.648.71/ (/)/
Cloud Land 27.948.029.53 (7.85)/
Cloud Land 39.669.66/ (/)16.99
Star Land 14.895.068.44 (7.75)/
Star Land 23.823.92/ (/)/
Star Land 311.6711.67/ (/)14.42
Ice Land 18.208.209.39 (9.18)/
Ice Land 29.699.699.89 (9.61)12.32
Ice Land 330.1530.1931.68 (30.87)33.40
Machine Land 113.1914.11/ (/)/
Machine Land 219.6619.66/ (/)/
Machine Land 329.3729.37/ (/)36.95
Ghost Castle 122.4722.50/ (/)/
Ghost Castle 246.1846.3152.67 (50.58)57.61
Ghost Castle 333.1033.32/ (/)36.00
Last Land 156.62/62.03 (60.29)64.28
Last Land 258.18/66.12 (64.01)68.93
Last Land 368.96/75.51 (73.07)80.67
Challenge 1-12.29// (/)2.31
Challenge 1-22.65// (/)2.65
Challenge 1-33.16// (/)3.88
Challenge 1-42.98// (/)3.45
Challenge 1-53.65// (/)4.29
Challenge 2-15.79// (/)7.72
Challenge 2-22.63// (/)2.70
Challenge 2-33.67// (/)4.82
Challenge 2-44.20// (/)5.83
Challenge 2-53.38// (/)4.03
Challenge 3-15.31// (/)5.64
Challenge 3-28.27// (/)9.39
Challenge 3-33.78// (/)6.61
Challenge 3-47.85// (/)8.54
Challenge 3-55.34// (/)6.14
Challenge 4-14.59// (/)5.26
Challenge 4-25.89// (/)7.52
Challenge 4-34.45// (/)5.36
Challenge 4-45.09// (/)6.09
Challenge 4-52.26// (/)2.73
Challenge 5-13.77// (/)4.27
Challenge 5-21.98// (/)2.58
Challenge 5-35.11// (/)6.08
Challenge 5-43.92// (/)5.12
Challenge 5-53.32// (/)4.00
Challenge 6-13.92// (/)4.99
Challenge 6-22.95// (/)3.70
Challenge 6-32.61// (/)3.58
Challenge 6-42.11// (/)2.41
Challenge 6-52.83// (/)3.13
Challenge 7-12.93// (/)3.13
Challenge 7-23.62// (/)4.55
Challenge 7-32.71// (/)3.32
Challenge 7-42.53// (/)3.43
Challenge 7-52.13// (/)2.39
Challenge 8-14.39// (/)4.67
Challenge 8-24.22// (/)4.34
Challenge 8-32.96// (/)4.12
Challenge 8-48.52// (/)12.12
Challenge 8-58.10// (/)8.66
Challenge 9-12.95// (/)3.00
Challenge 9-23.63// (/)3.95
Challenge 9-34.12// (/)4.64
Challenge 9-43.42// (/)3.60
Challenge 9-57.97// (/)8.81
Challenge 10-15.16// (/)6.13
Challenge 10-23.42// (/)3.72
Challenge 10-32.85// (/)2.86
Challenge 10-46.18// (/)8.57
Challenge 10-54.42// (/)5.37
Challenge 11-110.58// (/)15.29
Challenge 11-24.24// (/)4.64
Challenge 11-34.62// (/)5.69
Challenge 11-43.52// (/)4.17
Challenge 11-52.26// (/)4.35

Possible improvements

Good luck

In all seriousness there might be some lying dormant frames here and there, notably in levels filled with springs like Cave 2 or Star Land 3. But I do not expect any level to be improvable by more than a handful of frames. Several levels might look close to saving an extra frame. But most of the strategies used in this TAS are at least tight at a local level. So any frame gain is expected to require a significant overhaul in the level input sequence. Still this game has had a history of being deceptive in terms of optimization. We will see if future events will correct my guess.
Additionally, even though lag only represented 3 frames of potential non-gameplay time save in this TAS, it would be nice to better understand where it comes from and how to get around it.

Closing

Well, this TAS could have been made five years ago but it is finally here! The TAS itself took about one month to make and optimize, so around 150+ hours of work if I had to estimate. Of course this does not count my seven years of experience speedrunning this game, which included phases when I ran this exact category. With all this extra knowledge, I believe that taking this long to resume this 100% TAS project was actually beneficial.
I feel that this game is the perfect fit for a beginner TASer like me. It is short with very simple gameplay and zero RNG. It also runs very consistently, which allows me to consider each level independently from the others. Yet it still has a decent amount of depth in optimization. My next project TAS will be an IGT-focused “All levels” run and I expect to be surprised several more times by this game along the way.
Many thanks to E-Sh4rk for his feedback throughout the making of this TAS and his quickness in updating KuruBot whenever I gave suggestions. I hope you are ready for the upcoming in-game time shenanigans!

Darkman425: Claiming for judging.
Darkman425: A lot of work and care went into this 100% TAS and it definitely shows! I like how a lot of the found solutions involve incredibly dicey to watch situations through narrow passages. This submission also beats all known real time records, sometimes by quite a bit, so I can say that optimization is on point. Nice work!
On submitting in-game time focused TASes: I'd say it's worth also submitting the no damage variant alongside the one that takes damage to save time. It would lead to future discussions about it's acceptability but comparing this to the standard TAS that takes damage to get out of bounds shows that, for me at least, both are entertaining to watch for different reasons.
Accepting to Standard for full completion of the game.
fsvgm777: Processing.
Last Edited by fsvgm777 on 8/22/2024 10:31 AM
Page History Latest diff List referrers