1 2 3 4 5
Posted: 12/28/2018 9:58 PM
Quote
mohoc
He/Him
Reviewer, Player (250)
Joined: 5/20/2018
Posts: 34
Location: France
So, I guess it is time to share some of my findings. I have replicated some little parts of Matt Shepcar's video: - full Grasslands 1: http://tasvideos.org/userfiles/info/52179138490002530 - first wall clip in Cake Land 2: http://tasvideos.org/userfiles/info/52177977673438241 - first wall clip in Ice Land 3: http://tasvideos.org/userfiles/info/52172978644903455 The goal was to get the inputs back and to get info with RAM Watch about what makes wall clipping possible. The Ice Land 3 wall clip is especially interesting because it has very simple inputs. And I got an idea from it about how it potentially works (well, at least for horizontal/vertical walls). It has to do with subpixels. For a vertical wall at the right (like in Ice Land 3), the idea is that you must be at very low X speed (like less than a quarter of a pixel, if not even less) but still gain a pixel from the subpixels at the exact frame you bump. What allows you to do that is to collide slightly earlier. When you collide, it impacts your rotation, but also your X speed and Y speed independently from the inputs (only the input at the frame of the collision matters). This lasts about a dozen frames and decreases with time. But because of this, you could still have non zero X speed while holding up for example. So this is how I suspect wall clipping to work: gain 1 pixel from the subpixel at the exact frame you bump thanks to the momentum from an earlier collision. The problem I faced to replicate it in other levels is that the starting zone is very different from the one in the other levels: you are further from the right wall. I tried to adapt it, and I suceeded! Here is an example: - Grasslands 3 early wall clip: http://tasvideos.org/userfiles/info/52177347080337677 If you look at this file and the one for Ice Land 3, you would see that they are very similar, except for a few inputs at the beginning after the loading. As I am closer to the right wall in Grasslands 3, I just wait and hope to sync with Ice Land 3 at some point. However it did not work directly because for some reason the X pixel alignment modulo 3 between the starting point and the right wall is off by 1 pixel in Ice Land 3 compared to the other levels. I say "modulo 3" because your up/down/right/left speed is 3 pixels/frame at full speed (and respectively 3/4 and 1/2 of it with the slower speeds). But with diagonal inputs I found a way to change the X pixel with minor impact on the X subpixel (it is +1 pixel and +2 subpixels). That's why there are these weird inputs at the beginning in the Grasslands 3 file compared to the iceland 3 one. It also works by a 180° rotation of the inputs, like here: - Grasslands 1 early wall clip: http://tasvideos.org/userfiles/info/52177554086850103 What makes these wall clipping methods interesting is that they could be used in many, many levels: you would go out-of-bounds with it and then reach an out-of-bounds goal zone (yes, there are out-of-bounds goal zones in this game). In some levels this could be even faster than what we see in Matt Shepcar's "cheat bot" video. I made an example where Matt is beaten by about 2s: - Grasslands 2 done with wall clip + OOB goal zone: http://tasvideos.org/userfiles/info/52177778535894963
Posted: 12/28/2018 10:12 PM
(Edited: 12/30/2018 12:44 AM)
Quote
mohoc
He/Him
Reviewer, Player (250)
Joined: 5/20/2018
Posts: 34
Location: France
And here is some trivia about the game mechanics: 
Axes:
 ----> X
|
|
v
Y
******************************************
Notation:
-- X(pixel,subpixel) Y(pixel,subpixel)
-- "R2": R = direction in {U,L,D,R,UL,UR,DL,DR}
         2 = speed in {0,1,2} (=number of held buttons in {A,B})
******************************************
Movement:
-- R0: X+1,128 (2*R0 = R2)
-- R1: X+2, 64 (4*R1 = 3*R2, 2*R1 = R0+R2)
-- R2: X+3,  0

note: same for directions L,U,D
*
-- DR0: 2-cycle
        X+1, 15 Y+1, 15
        X+1, 16 Y+1, 16 (2*DR0 = DR2)
-- DR1: 4-cycle
        X+1,151 Y+1,151
        X+1,151 Y+1,151
        X+1,151 Y+1,151
        X+1,152 Y+1,152 (4*DR1 = 3*DR2)
/!\ X and Y could be desynced
-- DR2: X+2, 31 Y+2, 31

note: same for directions UR,DL,UL
*
-- DR0+UR0: X+2,31 (2*DR0-UR0 = DR2-UR2)
-- DR1+UR1: 2-cycle
            X+3,46
            X+3,47 (4*DR1-UR1 = 3*DR2-UR2)
-- DR2+UR2: X+4,62

note: same for combinations DL+UL,DR+DL,UR+UL
******************************************
Rotation:
-- 65536 possible values(=2**16bits=2byte)
-- starts at 0
-- normal behaviour: +182 every frame (=14*13)
-- offset by -16 every 360∞/360 frames (=6.00s)
   => offset by -2 every 45∞

-- rotating clockwise
   -- when pushed counterclockwise:
        speed: -933,-842,-751,-660,-569,-478,-387,
               -296,-205,-114, -23, +68,+159,+182
        => +91 every frame, except last (+23)
      => offset value: -40 frames, -117 (=-9*13)
      => after 14 hits without interruption:
       value back to the same modulus by 182 (offset: -569 frames)
   -- when pushed clockwise:
        speed: +933,+842,+751,+660,+569,+478,+387,
               +296,+205,+182
        => -91 every frame, except last (-23)
      => offset value: +19 frames, +25
-- rotating counterclockwise
     same behaviour

-- multiple hits with interruption:
     no stacking: speed value set to -/+933 at each new hit
-- sometimes, collision is messy and speed is set to +/-933 instead of -/+933
******************************************
Method to change X pixel with minor impact on X subpixel:
DL2+UL2 [-4, 62]
R1      [+2, 64]
R2      [+3,  0]
=> [+1,  2] using 4 frames

note: with reverse moves: [-1,  2] using 4 frames
note: there is a similar method for Y
******************************************
Methods to adjust X subpixel:
DL0+UL0 [-2,31]
R1      [+2,64]
=> [+0, 33] using 3 frames
*
DR1+UR1 [+3,46]
L2      [-3, 0]
=> [+0, 46] using 3 frames
*
DL2+UL2 [-4, 62]
2*R1    [+4,128]
=> [+0, 66] using 4 frames
*
DL2+UL2 [-4, 62]
DR1+UR1 [+3, 46]
R0      [+1,128]
=> [+0,112] using 5 frames

note: they can be reversed + similar methods for Y
******************************************
Starting info:

1 direction of the opening
2 starting clockwise?
3 starting positions in levels (=> all multiples of 8) 
              |1|2  |3
Grasslands 1  |R|Yes|X(136,0) Y(192,0)
Grasslands 2  |R|Yes|X( 80,0) Y(440,0)
Grasslands 3  |U|Yes|X(128,0) Y(552,0) 
Ocean 1       |U|Yes|X(128,0) Y(240,0)
Ocean 2       |L|Yes|X(224,0) Y(256,0) 
Ocean 3       |R|Yes|X(128,0) Y(256,0) 
Jungle 1      |D|Yes|X(144,0) Y(272,0) 
Jungle 2      |R|Yes|X( 80,0) Y(328,0) 
Jungle 3      |D|No |X( 80,0) Y(512,0) 
Cake Land 1   |R|Yes|X( 88,0) Y(128,0) 
Cake Land 2   |L|No |X(536,0) Y(320,0) 
Cake Land 3   |R|Yes|X(248,0) Y(160,0) 
Cave 1        |R|No |X(184,0) Y(312,0) 
Cave 2        |R|No |X(864,0) Y(800,0) 
Cave 3        |U|Yes|X(248,0) Y(384,0) 
Cloud Land 1  |R|No |X(128,0) Y(392,0) 
Cloud Land 2  |R|Yes|X(232,0) Y(232,0) 
Cloud Land 3  |D|Yes|X(472,0) Y(160,0) 
Star Land 1   |U|Yes|X(160,0) Y(488,0) 
Star Land 2   |R|Yes|X(200,0) Y(256,0) 
Star Land 3   |U|No |X(560,0) Y(616,0) 
Ice Land 1    |U|Yes|X(248,0) Y(552,0) 
Ice Land 2    |U|No |X(440,0) Y(560,0) 
Ice Land 3    |U|Yes|X(608,0) Y(432,0) 
Machine Land 1|R|No |X( 96,0) Y(400,0) 
Machine Land 2|R|Yes|X(112,0) Y(128,0) 
Machine Land 3|R|Yes|X(112,0) Y(208,0) 
Ghost Castle 1|U|Yes|X(136,0) Y(944,0) 
Ghost Castle 2|R|Yes|X(440,0) Y(648,0) 
Ghost Castle 3|U|No |X(336,0) Y(768,0) 

Some statistics:
Yes: 21|No: 9
R: 15|U: 10|D: 3|L: 2
R Yes: 11|U Yes: 7|D Yes: 2|L Yes: 1
R No: 4|U No: 3|D No: 1|L No: 1
Posted: 12/29/2018 7:42 PM
Quote
ThunderAxe31
Any
Editor, Reviewer, Skilled player (1358)
Joined: 9/12/2016
Posts: 1646
Location: Italy
Arcade TAS of 2023 Homebrew TAS of 2023 PSX TASer of 2022 Gameboy TASer of 2017
Great job, mohoc! I still have doubts that the movie by Matt Schepcar could be improved (without OoB goals), but now I'm starting to consider it possible... In any case, I have to note that the first level by Schepcar does move the Helirin at max speed all the time, so I there is a chance that he didn't take in account the possibility of making use of low speed and half speed...
MUGG wrote:
If you do Kuru Kuru Kururin with the trick, I suggest that you skip the training levels to make it aim for fastest completion.
We now have a clear definition of movie superseeding (please see here the examples for Private Eye and Toki Tori), so it's preferred to include the training levels since it would add contents without affecting the execution of the rest of the movie. It wouldn't be considered as a waste of time, even for fastest completion.
my personal page - my YouTube channel - my GitHub - my Discord: thunderaxe31 <Masterjun> if you look at the "NES" in a weird angle, it actually clearly says "GBA"
Posted: 12/29/2018 7:43 PM
Quote
ais523
Editor, Player (44)
Joined: 7/11/2010
Posts: 1029
The tutorial is skippable, so I think it'd be interpreted as not being needed in an any%. An "all levels" run will be great, but it should probably play the postgame levels too (which would in turn means you have to unlock them, making a rather different category from any%).
Posted: 12/29/2018 7:49 PM
Quote
ThunderAxe31
Any
Editor, Reviewer, Skilled player (1358)
Joined: 9/12/2016
Posts: 1646
Location: Italy
Arcade TAS of 2023 Homebrew TAS of 2023 PSX TASer of 2022 Gameboy TASer of 2017
ais523 wrote:
The tutorial is skippable, so I think it'd be interpreted as not being needed in an any%.
The hard levels for Toki Tori are also skippable, yet my any% submission was rejected due of its completely overlapping contents with the full completion publicaton. This has been thoroughly discussed and tested in the staff, so please look closely at Judge Guidelines paragraph that I linked in my previous post.
my personal page - my YouTube channel - my GitHub - my Discord: thunderaxe31 <Masterjun> if you look at the "NES" in a weird angle, it actually clearly says "GBA"
Posted: 12/29/2018 7:51 PM
Quote
ais523
Editor, Player (44)
Joined: 7/11/2010
Posts: 1029
That's not directly comparable; doing "all levels" in Kuru Kuru Kururin requires a no-damage completion of most of them, in order to unlock the Last Land. So this would be "all initially unlocked levels" or the like, which is a somewhat arbitrary category.
Posted: 12/30/2018 11:47 AM
Quote
ViGadeomes
He/Him
Judge, Active player (311)
Joined: 10/16/2017
Posts: 461
Location: France
I think in this situation, that a no branch (any%) have to be done without the tutorial since credits are reachable without it and a "all levels" category which includes tutorial and extra world too. Compared to Private Eye (and a lot of Atari 2600 games), Private Eye is considered as 5 different games since you are only able to choose one of them separatly. In the case of Toki Tori, all level's strats of the any% submission weren't changed compared to the "all levels" submission ! But in this game, since you need to do perfect (without any damage) levels which is not done in the any%, then it can be considered as a full completion and both accepted.
Posted: 12/30/2018 12:28 PM
Quote
ThunderAxe31
Any
Editor, Reviewer, Skilled player (1358)
Joined: 9/12/2016
Posts: 1646
Location: Italy
Arcade TAS of 2023 Homebrew TAS of 2023 PSX TASer of 2022 Gameboy TASer of 2017
Can we please continue this discussion in the Ask a Judge thread or in IRC? I'd like to stick to game research here... Today I almost managed to create a new setup for diagonal clip from scratch: User movie #52215351809436264 This screenshot shows the moment while I was inside the wall (yeah, it lasted just for two frames...): Though, I need to look closer at how is achieved in Matt Schepcar's run, because there is something that I'm missing about how it works...
my personal page - my YouTube channel - my GitHub - my Discord: thunderaxe31 <Masterjun> if you look at the "NES" in a weird angle, it actually clearly says "GBA"
Posted: 12/31/2018 12:49 PM
Quote
mohoc
He/Him
Reviewer, Player (250)
Joined: 5/20/2018
Posts: 34
Location: France
That sounds interesting, I know a couple levels where we could take advantage of diagonal clips. For my part, I am almost done figuring out what could be the fastest strategies in every level between the "cheat bot" video and reaching an OOB goal zone. This is my progress: 
1 fastest strategy (matt="cheat bot" video | oob=reach an OOB goal zone)
2 done? ("x"=done | "(x)"=done but probably improvable | " "=not done)
3 comments
____________________________
______________|1_____|2__|3_
Grasslands 1  |matt  | x |
Grasslands 2  |oob   | x |
Grasslands 3  |matt  |   |
Ocean 1       |oob   | x |
Ocean 2       |matt  |   |
Ocean 3       |oob   | x |
Jungle 1      |oob   | x |
Jungle 2      |oob   |(x)|might do more intentional hits to push back to horizontal when reaching OOB goal zone
Jungle 3      |matt  |   |
Cake Land 1   |oob   |(x)|another goal zone just up-left to start but it seems unreachable for now, unless some wall clipping is done
Cake Land 2   |matt  |   |
Cake Land 3   |oob?  |   |TODO: way to clip in corners
Cave 1        |matt  |   |might be easy to replicate?
Cave 2        |oob?  |   |TODO: way to clip in corners
Cave 3        |oob?  |   |TODO: way to clip in corners
Cloud Land 1  |matt? |   |What is OOB at the left is invisible and weird
Cloud Land 2  |matt? |   |What is OOB at the left is invisible and weird
Cloud Land 3  |matt  |   |
Star Land 1   |matt  |   |
Star Land 2   |oob   | x |
Star Land 3   |matt  |   |
Ice Land 1    |matt  |   |
Ice Land 2    |matt  |   |
Ice Land 3    |matt  |   |
Machine Land 1|oob   |(x)|probably beatable, but difficult to optimize with all these invisible walls
Machine Land 2|oob   | x |might be slightly improved with a better idea about when to take the final damage
Machine Land 3|oob   |(x)|TODO: way to reach upper-left goal zone (only 3s away from start)
Ghost Castle 1|oob   |   |What is OOB at the left is invisible and weird
Ghost Castle 2|"matt"|(x)|TODO: faster way to reach the regular goal zone from outside
Ghost Castle 3|oob   |(x)|TODO: investigate better strategies
You can find all the levels I have done using OOB goal zones here: https://www.dropbox.com/s/ptzmw5f573btdvh/levels_done_with_oob_goal_zones.zip?dl=0 (There should be 11 levels: Grasslands 2, Ocean 1 & 3, Jungle 1 & 2, Cake Land 1, Star Land 2, Machine Land 1, 2 & 3, Ghost Castle 3) I also have done this: - Ghost Castle 1 early wall clip: http://tasvideos.org/userfiles/info/52237142160912306 - full Ghost Castle 2: http://tasvideos.org/userfiles/info/52237265785563966
Posted: 12/31/2018 12:59 PM
Post subject: OOB Viewer (update)
Quote
E-Sh4rk
Player (99)
Joined: 12/30/2018
Posts: 9
Hi everyone. ThunderAxe31 and I are currently working on improving the OOB Viewer script. I've just finished the v1.3, with the following changes: - The code has been refactored and commented - It now displays the helirin - The issue with some maps like Machine Land 1 has been solved Healing zones and ending zones in the OOB are still not accurate, we are working on this. Here is the repo to download it (it will be kept updated): https://github.com/E-Sh4rk/KururinTAS Please feel free to post issues or pull request!
Posted: 1/1/2019 11:38 PM
Quote
mohoc
He/Him
Reviewer, Player (250)
Joined: 5/20/2018
Posts: 34
Location: France
v1.4 (beta) looks neat and it is very useful to work with! I made good use of it today to complete more levels with wall clipping + OOB goal zones: - Cave 3: http://tasvideos.org/userfiles/info/52269565877650126 - Cloud Land 2: http://tasvideos.org/userfiles/info/52269660021613854 - a 0.2s improvement on Machine Land 1: http://tasvideos.org/userfiles/info/52269764288546723 - Ghost Castle 1: http://tasvideos.org/userfiles/info/52269947472336163 I have also been able to tie Matt Shepcar's time in Cave 1 (only the end is different because I was unable to exactly reproduce it, but the final time is the same): http://tasvideos.org/userfiles/info/52269414949784408 This is my current progress: 
1 fastest strategy (matt="cheat bot" video | oob=reach an OOB goal zone)
2 done? ("x"=done | "(x)"=done but probably improvable | " "=not done)
3 comments
____________________________
______________|1_____|2__|3_
Grasslands 1  |matt  | x |
Grasslands 2  |oob   | x |
Grasslands 3  |matt  |   |
Ocean 1       |oob   | x |
Ocean 2       |matt  |   |
Ocean 3       |oob   | x |
Jungle 1      |oob   | x |
Jungle 2      |oob   |(x)|might do more intentional hits to push back to horizontal when reaching OOB goal zone
Jungle 3      |matt  |   |
Cake Land 1   |oob   |(x)|there may be a way to reach the upper-left goal zone?
Cake Land 2   |matt  |   |
Cake Land 3   |oob?  |   |TODO: way to clip in corners
Cave 1        |matt  | x |
Cave 2        |oob?  |   |TODO: way to clip in corners
Cave 3        |oob   | x |
Cloud Land 1  |matt  |   |
Cloud Land 2  |oob   | x |there might be a faster way to go OOB with two hearts?
Cloud Land 3  |matt  |   |
Star Land 1   |matt  |   |
Star Land 2   |oob   | x |
Star Land 3   |matt  |   |
Ice Land 1    |matt  |   |
Ice Land 2    |matt  |   |
Ice Land 3    |matt  |   |
Machine Land 1|oob   | x |
Machine Land 2|oob   | x |might be slightly improved with a better idea about when to take the final damage
Machine Land 3|oob   | x |there may be a way to reach upper-left goal zone? (3s away from start)
Ghost Castle 1|oob   |(x)|slow beginning (waited for a 180° to adjust position)
Ghost Castle 2|"matt"|(x)|TODO: faster way to reach the regular goal zone from outside
Ghost Castle 3|oob   |(x)|TODO: investigate better strategies
Posted: 1/6/2019 4:17 PM
Quote
mohoc
He/Him
Reviewer, Player (250)
Joined: 5/20/2018
Posts: 34
Location: France
Hey, I made a github repository for the current fastest completion TAS project: https://github.com/mohoc/KuruTAS You will find: - all the current records per level - my current progress on the project - the beginning of each stage if you want to try to beat my times (they start at selecting the level on the world map and end at Helirin control) - a folder "tricks" with the main wall clipping methods I have used I have done all the levels where Matt Shepcar's "cheat bot" is not the fastest strategy. My plan is to improve my current records until we hopefully get a response from Matt Shepcar. Btw I have found a new early clipping method that saves 10 frames (you can find it in the "tricks" folder, it was performed in Cake Land 3), so I'm gonna update every level that could benefit from it for now.
Posted: 1/9/2019 11:36 PM
Post subject: Level escapes
Quote
MattShepcar
Joined: 1/9/2019
Posts: 2
Location: UK
Hi, interesting progress, especially the improved ice 2 time. I think mohoc's idea about how the wall clip works is mostly right, i.e. it relies on residual velocity from a previous impact. Looking at my implementation of the game physics it would seem to work like this: 1. When you bump a wall the game resets any user movement of the helirin BUT it does not reset any movement caused by residual velocity from a previous collision. This is the bug that makes it possible. 2. It then moves the helirin by 2 pixels along its axis in the direction away from the end that collided. This 2 pixel thrust velocity is saved and on each subsequent frame it is reduced by 25% and applied again. This is the velocity that must be used to enter a wall. 3. The final ingredient that allows the 'wall zips' and level escapes is that if the centre point of the helirin is in collision then a 4 pixel thrust in the opposite direction to the current user input is applied. I guess this was probably an attempt to prevent level escapes but in fact does the opposite. It essentially allows you to move at 7 pixels per frame along walls because the 4 pixel thrust is applied not only on the current frame but also on the next frame at 75% power as described in step 2 above. 4. If you're playing kururin paradise then the game resets the integer parts of the X & Y position back to their values from the previous frame making level escapes and wall zips impossible (they patched the bug, but did not fix the real cause!) The important thing is to ensure that the 2 pixel correction in step 2 does not push the helirin back out of the wall and counteract the residual velocity from the previous collision. This is why the helirin needs to be at more or less the same angle as the wall you are trying to enter. It's also vitally important to get the centre of the helirin inside the wall to give you control over the 4 pixel thrust, again making it important that the helirin is aligned with the wall. My solver did not properly account for level escapes or wall zips because I didn't really understand what the mechanism was until now. The code is a real mess too. I might try and tidy up the part that deals with the game physics so it could be used to write a new solver that can properly understand wall clips although that could be quite a tough challenge. I look forward to seeing what you guys come up with in the meantime. Matt
Posted: 1/9/2019 11:58 PM
Quote
E-Sh4rk
Player (99)
Joined: 12/30/2018
Posts: 9
Hi Matt! It is very pleasing to have you here! :) I agree with all the details you gave on the game physics: I have made the same observations. I am currently trying to simulate it exactly. I've just finished a first version, but I haven't tested it yet (at least not on a precise setup like a wall clip). It is available here (it is made in C#): https://github.com/E-Sh4rk/KururinTAS/blob/master/Misc/KuruBot/KuruBot/Physics.cs My final goal would be to make a bot like you did :) Maybe we can combine our powers? :P
Posted: 1/10/2019 7:47 AM
Quote
MattShepcar
Joined: 1/9/2019
Posts: 2
Location: UK
The main challenge in writing a solver (apart from replicating the physics of the game precisely) is the size of the search space. If you ignore level escapes it is not too bad. When checking for collisions the game considers only 128 possible orientations for the helirin and only checks at 1 pixel accuracy which makes it just about feasible to use A* and treat each pixel at each orientation in the maze as one A* node. You can implement a simple cost function for the A* algorithm which would be the shortest distance to the exit. For better performance I ran an initial path finding stage that found the distance to the exit from each pixel without crossing any walls by doing a kind of flood fill/dijkstra algorithm. Even with this reduced search space and a pretty good A* cost function the solver could take hours to find a solution in large maps and required a lot of memory. Adding in the moving obstacles made things a bit slower and could also require the helirin to wait around for them to move out of the way. That meant allowing the path finder to revisit a pixel/orientation in the maze more than once in a given solution, increasing size of the search space significantly. Allowing the helirin to move at all 4 possible speeds (0, 1.5, 2.25, 3) also slows things down but it didn't ever seem to generate any improved solutions anyway. I did a few optimisations in my solver, including storing 128 separate collision maps, one for each orientation of the helirin. In this way I was able to check if the helirin collided with the maze with a single table lookup instead of having to check all 17 hit points every time. I was also able to store additional information in this collision map such as whether the helirin might have hit a spring or a moving object meaning I could optimise out those checks when they were unnecessary. Even with those optimisations and writing everything in C the solver still took many hours for some levels. Once wall zips are introduced the problem is compounded and A* becomes much harder to take advantage for a couple of reasons: 1. It's very hard to come up with a useful cost function. Estimating the minimum time it could take to reach the exit from any pixel is hard because now you can possibly move at 7 pixels/frame instead of the normal 3. (In fact, even without wall zips this is a bit of a problem because collisions with walls can give you a speed boost, and springs even more so.) 2. The real problem though, is that you can no longer just use pixel+orientation to represent a particular position in the maze. You also need to consider the bounce velocity. Being at pixel x=123,y=45, orientation=23 and no bounce velocity is no longer the same as being there with some non-zero bounce velocity because the latter may lead on to a position that lets the helirin enter a wall. It's really only by chance that my solver sometimes discovered wall escapes because it happened to visit particular positions with a non-zero bounce velocity first. I think making a brute force/A* solver truly understand wall escapes would require finding ways to significantly reduce the search space by calculating which combinations of position+orientation+velocity could potentially lead to wall escapes and collapse down duplicate states as far as possible. Also I think for such a solver to run at any decent speed it probably needs to run on GPU or at least multi-threaded SIMD. As tempting as it is to try and write a solver to find the 'perfect' solution, it might be more realistic to write some kind of interactive tool that lets you manually guide the path finding algorithm. I don't really have time to get involved too much anyway, I already wasted enough time messing around with this the first time around! :) Matt
Posted: 1/10/2019 4:34 PM
Quote
mohoc
He/Him
Reviewer, Player (250)
Joined: 5/20/2018
Posts: 34
Location: France
Hi Matt, nice to see you here! I am confident that E-Sh4rk is very motivated in conceiving an optimized bot. I think that he would benefit from your solver's code. It is not a problem if the code is messy, we are primarily looking for ideas and experimentation at the moment. For my part, I want to make a first completed draft of the TAS to see how down we already pushed the time. Only the levels where your bot is the fastest are missing. So may you upload a file with the inputs that were performed in your "cheat bot" partial run? (this one) (As a note, the missing levels are: Grasslands 3, Ocean 2, Jungle 3, Cake Land 2, Cloud Land 1 & 3, Star Land 1 & 3, Ice Land 1, 2 & 3.)
Posted: 1/15/2019 2:20 PM
Quote
E-Sh4rk
Player (99)
Joined: 12/30/2018
Posts: 9
Hey, Thank you Matt for your advice. I know it is an hard problem (over 2^100 states if we want to solve it exactly, without taking into account moving objects). However I have some ideas for a cost function that take into account wall clips (not an optimal one since it will not always be a lower bound of the real distance, but... maybe good enough?). As you suggested, I have planned to reduce drastically the search space by collapsing down states that are "almost equivalent". For now I am focusing on asymptotic optimisations. I will see later for other optimisations and multicore support. I finally managed to simulate the physics of Kururin (except the life system and the moving objects that are not supported for now). https://github.com/E-Sh4rk/KururinTAS/tree/master/Misc I have tested it on some levels (with Mohoc's bk2 files), it simulates perfectly the trajectory of the helirin even for wall clips and OOB collisions :) There probably still are some inacurracies in some situations, but I will fix them as and when. So now I can start the round 2: building the bot :P It will surely not be able to compute an optimal path on its own. However, when it is about finding a quick way to wall clip, it can't be worse than a human ;) I will keep you informed!
Posted: 1/19/2019 12:15 AM
Quote
mohoc
He/Him
Reviewer, Player (250)
Joined: 5/20/2018
Posts: 34
Location: France
I have uploaded a first version of an Any% Normal TAS (do all thirty main levels, don't save birds). Time: 5:05.75 (18345 frames) counting the GB intro. Youtube video: https://www.youtube.com/watch?v=tdnZhIvwhi0 Input file: http://tasvideos.org/userfiles/info/52647444906124211 Reminder that the OOB viewer is available here: https://github.com/E-Sh4rk/KururinTAS There are two known potential time saves: - 11 frames in Ocean 2 (Matt's "cheat bot" is faster there) - 3 frames in Star Land 1 (Matt's "cheat bot" is faster there) Matt's levels have been proved difficult to replicate, so I decided to let this for later. There are two next projects: - continue E-Sh4rk's bot project and use it to find some new strategies - make a new TAS with the birds saved (= remake the 3rd level of each of the ten worlds), which will be more likely to be accepted since it triggers the credits. EDIT: I have also uploaded a version with the OOB viewer if you want to better understand what is happening: https://www.youtube.com/watch?v=HHgOrBXwDh8
Posted: 2/18/2019 1:52 PM
Quote
E-Sh4rk
Player (99)
Joined: 12/30/2018
Posts: 9
Hey everyone! I've just released a first version of my bot. It is able to finish easy levels on its own (with or without wall clips), but for bigger levels that require some planning we should only use it on some little segments of the level (in order to perform a tricky wall clip for instance). It has already helped to improve Grasslands 1 by +30 frames, it is encouraging :) It is available here: https://github.com/E-Sh4rk/KururinTAS/tree/master/KuruBot And for the binaries: https://github.com/E-Sh4rk/KururinTAS/releases I have started to explain how to use it in the readme (I will complete it soon). Hope it will be useful! ;)
Posted: 3/29/2019 9:28 AM
Quote
mohoc
He/Him
Reviewer, Player (250)
Joined: 5/20/2018
Posts: 34
Location: France
Hey, E-Sh4rk and I submitted a new Any% TAS. We were unsure whether to include the Training levels or not, so we submitted both and will let the community decide which one to keep. - Any% in 5:35.14 - Any% With Training in 6:19.76
Posted: 7/16/2024 3:00 PM
Quote
mohoc
He/Him
Reviewer, Player (250)
Joined: 5/20/2018
Posts: 34
Location: France
Hey there, it has been a while. I am happy to report that I am back to TASing this game with the 100% category this time. I just finished a revision of the "All make up, no damage" run uploaded by Matt Shpecar back in 2015. User movie #638567371142506129 Encode: Link to video This can be considered a halfway point through the making of the 100% TAS. Except Last Land the rest of the levels should be less difficult to optimize.
1 2 3 4 5