TASVideos

Tool-assisted game movies
When human skills are just not enough

Submission #6854: Jigwally's NES Clu Clu Land in 10:48.13

Console: Nintendo Entertainment System
Game name: Clu Clu Land
Game version: JPN/USA
ROM filename: Clu Clu Land (World).nes
Branch:
Emulator: BizHawk 2.4.2.1
Movie length: 10:48.13
FrameCount: 38952
Re-record count: 1184
Author's real name: Basil Gruber
Author's nickname: Jigwally
Submitter: Jigwally
Submitted at: 2020-08-23 20:59:30
Text last edited at: 2020-08-23 21:01:24
Text last edited by: Jigwally
Download: Download (11056 bytes)
Status: decision: cancelled
Submission instructions
Discuss this submission (also rating / voting)
List all submissions by this submitter
List pages on this site that refer to this submission
View submission text history
Back to the submission list
Author's comments and explanations:

I wanted to try improving the solutions for this existing TAS because they seemed suboptimal and solving these puzzles in the fewest steps was an interesting problem for me to solve.

Each puzzle can be simplified and reduced to an instance of the traveling salesman problem, where each of the ingots to be revealed is a vertex to be visited in the graph. For the easier (red) stages, each ingot needs to be duplicated as two nodes depending on which direction you are traveling through it since this affects the distance from that point to other points. This makes the problem a "generalized TSP" meaning that rather than visit every point we only need to visit one point out of each "cluster" of points. This type of problem can be easily converted into a regular TSP problem with some manipulation.

However, this only applies to the red stages. Where it gets interesting (as noted in the previous submission) is that after the first stage of each loop, the game begins to prohibit certain turns. Specifically, it prohibits a RD turn directly into a DR turn, and an UR turn directly into a RU turn. This is presumably because the player speed increases with each level which causes the player to miss the very small frame window allowing for switching between a CW or CCW turn (normally 1 or 2 frame window on the slowest speed). In order to account for this in my model I instead duplicated every vertex in the graph a maximum of six times depending on which direction the player travels through it and whether they are going straight, clockwise or counterclockwise. Then in the ensuing graph, I made sure not to directly connect any vertices that would only be directly connected by one of these illegal turns. This produces a distance matrix from which any ensuing solution will avoid these turns.

The 5th stage in each loop as well as the bonus stage both seem to have additional turn restrictions, however this is not actually the case. As it turns out, for some turns if you do a full connected 180-270 degree turn (by holding the button down the whole time), if you try to switch out of it into an opposite turn it won't let you. However, if instead of doing a full turn, you break it down into smaller turns (that is, if you are turning CW three times you do a 90 degree turn, release, grab back on and continue for another 90 degree turn, and so on), it delays your movement just slightly so that you are within the right frame window and are able to make that turn that seemed impossible.

After producing the distance matrix for each puzzle I then used the program LKH-3 (http://akira.ruc.dk/~keld/research/LKH-3/) to solve the multiple TSP problem for 2 vehicles. Specifically you indicate the "min-max" objective meaning that you are trying to balance the paths in order to minimize the maximum path length for any vehicle.

Some problems with this simplified form of the puzzle are:

As for the tally screen:

There seems to be a frame rule in effect where delaying your completion of the level by a few frames still results in the next stage starting at the same time. In some cases it actually saves you time to delay a frame or two. Sometimes I intentionally delay a frame in order to avoid the clock item spawning in the next stage (since this causes the other player to stop moving).

For resetting back to the title screen, the original publication was kind of vague as to exactly when this should be done ("after the last screen flash") so I defined it here as making sure there are exactly 242 frames between when the P1/P2 sprites disappear and when the title screen is visible after resetting. Manipulating which stages appear in the loops is a matter of delaying when you press start (the level order for each loop is visible in RAM starting at 0x720) but getting each stage to appear among each of the 4 loops is kind of tricky. Rather than being truly random it seems like only about a third of the 1028 total possible combinations will ever appear as the pattern for the first loop. I spent 301 frames total manipulating this particular stage order but it's possible an improvement exists.

Temp encode: https://www.youtube.com/watch?v=SosinPzW3MQ&feature=youtu.be


Similar submissions (by title and categories where applicable):