The process of making this TAS was probably more interesting than the movie itself. I've been interested in using optimization algorithms for the purpose of helping to route TASes. This is probably the most mundane example possible of that but it's got me thinking about using a similar approach for more complex gameplay.
You can move up/down/left/right or diagonally every other frame & the optimal solution is the one that visits the fewest unnecessary tiles (tiles you've already chiseled or tiles that aren't part of the solution). If all of the tiles in the puzzle are connected in a way that you can solve the puzzle just by visiting each of them once & no other tiles that is clearly an optimal solution (aka a Hamiltonian path).
To verify that all solutions are optimal I converted all the puzzles to a distance matrix which allows the puzzles to be treated as instances of the Traveling Salesman Problem. The Concorde solver ( http://www.math.uwaterloo.ca/tsp/concorde.html ) is a highly efficient TSP solver that quickly verified the fewest number of steps for all puzzles. I also wrote some extra code to convert solutions directly to controller input so they could simply be pasted into TAStudio to speed up the process.
Some notes:
- 2 frames after each level starts there is a single frame where the game allows you to move early (but not chisel). For any level where you start off moving (i.e. if the nearest tile of the solution is more than 1 block away from the start) you save some frames moving here.
- Every 30 frames (when the timer ticks down) the game will drop input so I have to periodically delay some of my input by a frame to account for this.
- Some levels are laggy (1 lag of frame every time I chisel) for reasons I'm not entirely sure of.
- Time Trial mode (the final mode unlocked) gives you a random puzzle from the Time Trial level set and notes the final completion time on the ranking board. Since all levels share the same leaderboard & individual level completion isn't tracked here I chose to "complete" this mode just by finishing the first level it gives me and registering the name "TAS".
Possible improvements:
- Regarding the input that is dropped, it seems that sometimes if the frame on which the timer ticks down isn't being used to chisel a tile (i.e. if you are just moving) then input doesn't get dropped and you don't have to wait a frame. So it might be possible to save some frames by finding solutions that have the same # of moves but where the order of moves is slightly changed so that any frames on which you aren't chiseling land on one of these 60 frame intervals. This would save only a tiny amount of frames throughout the entire run though.
- I'm not sure how the random puzzle selection for Time Trial mode works (it is not simply a matter of delaying frames) but it might be possible to manipulate a slightly faster puzzle than the one I used (Koopa Troopas).
Edit: Will resubmit fixed version
feos: Judging...