Automated generation of Manic Miner speedrun/walkthrough

[DigitalDuck]

12 hours ago, IRF said:

Actually, I've just added a timestamp in a comment on your YouTube video (8:52), just before when Will jumps onto the crumbly platform which I think is the one you're talking about (the lower one of the right). Is that correct?

To be clear, it's not my video - the way TASVideos works is that you submit a "movie file" that basically encodes a list of button presses; because I'm using BizHawk, this is a .bk2 file, but a .rzx is also a movie file. Then it's verified by someone independently taking a copy of the game (obviously it has to be the same version) and playing the movie back to prove there's no funny business going on. I'll go further into depth on this, maybe in a new topic, when I have my JSW2 run published (I'm happy with the actual run but I need to provide a writeup for it).

12 hours ago, IRF said:

I wonder how the AI failed to pick it up? Is it because it involves momentary inaction in the present to make things more efficient in the future? Mind you, that's the sort of things that humans are less likely to come up with (our in-built instinct is to do something), whereas the brute force AI approach of trying every possible iteration of moves (or in this case non-moves) should have detected it?

From what I understand, crem's algorithm is heuristic-driven, which means that rather than try every possible iteration for the entire length of the cavern, it only does so over a short period and then gives each state a score (which will likely be a function of items collected and some added checkpoints reached).

If you were to try to brute force every set of inputs over the entire length of the cavern, it would take a very, very, very long time. A typical cavern takes about 500 in-game frames to complete optimally; each frame there are six different actions you can take (nothing, left, right, jump, jump left, jump right), so the total number of inputs to test is on the order of 6^500, which is a number with 390 digits. Granted, the actual number is smaller than this as inputs in the air are ignored, and deaths will cut a branch short, but it's still an unfathomably large number.

By using a heuristic, you can periodically prune the tree, removing any branches that (seemingly) aren't making progress, or are progressing slower than other branches, to keep the number of possibilities to check much lower. The disadvantage of this is if you're keeping a history of (say) five seconds, you're going to miss if there's some secret in Central Cavern in which if you hold left for six seconds it automatically wins the cavern for you.

So it's important to prune the right amount - too little and it never finishes, too much and you miss some optimal solutions. crem almost perfectly straddled this line - as it happens, the right side of the Endorian Forest required just a tiny bit more planning ahead than the algorithm was afforded.

I would still say the algorithm won the battle though - there were a few caverns where I'd played through what I thought was optimal but scored lower than the algorithm, so had to go back and improve it. I wouldn't have known otherwise (and that's one of the reasons crem is listed as a co-author).

1 hour ago, IRF said:

I wonder if someone updated the keypress datastream for The Endorian Forest (I could have a go myself although I'm about to fly off to Nice), whether @NormanSword might consider updating his game file which consisted of automated optimised routes through the caverns, to take account of this new discovery?

If it helps, as I mentioned above the .bk2 file is already a list of inputs - it's just a case of working out when the game actually acts on them. I'm sure there's a way to automate that too but I'm not familiar enough with the actual internals of the game.

[IRF]

11 hours ago, DigitalDuck said:

If it helps, as I mentioned above the .bk2 file is already a list of inputs - it's just a case of working out when the game actually acts on them. I'm sure there's a way to automate that too but I'm not familiar enough with the actual internals of the game.

I was thinking along the lines of the format in the first post of page 6 of this thread, where a full stop indicates no movement keys being pressed for one time frame, with other movement keys being indicated by letters. Norman Sword wrote a program which automated the optimised sequences of keypresses (or lack of keypresses when appropriate), to create a version of Manic Miner which plays itself to a maximum final score (or, as it turns out, at least one point shy of the maximum possible score).

You can also select BB or SP version to watch the automated optimised routes in action.

[DigitalDuck]

2 hours ago, IRF said:

I was thinking along the lines of the format in the first post of page 6 of this thread, where a full stop indicates no movement keys being pressed for one time frame, with other movement keys being indicated by letters. Norman Sword wrote a program which automated the optimised sequences of keypresses (or lack of keypresses when appropriate), to create a version of Manic Miner which plays itself to a maximum final score (or, as it turns out, at least one point shy of the maximum possible score).

You can also select BB or SP version to watch the automated optimised routes in action.

Yes, I have this program (it's a great way to be able to watch individual routes, and thanks to Norman Sword for making it).

If you download the .bk2 file linked and extract it using any unzipper (it's actually a zip file), one of the packaged files is called Input Log.txt and has lines that look like this:

|......................................................................|.....|.....|.....|
|......................................................................|.....|.....|.....|
|.......................O..............................................|.....|.....|.....|
|.......................O..............................................|.....|.....|.....|
|.......................O..............................................|.....|.....|.....|
|.......................O..............................................|.....|.....|.....|
|.......................O..............................................|.....|.....|.....|
|......................................................................|.....|.....|.....|
|......................................................................|.....|.....|.....|
|........................P.............................................|.....|.....|.....|
|........................P.............................................|.....|.....|.....|
|........................P.............................................|.....|.....|.....|

Each line represents one video frame (at ~50.02Hz), and each column represents an individual input (most of them are keyboard keys, shown by a . when not pressed and a different character when pressed; the three groups of five at the end are joystick inputs). This small section tells me that I pressed nothing for two frames (about 0.04 seconds), pressed and held O for five frames (about 0.1 seconds), pressed nothing for two more frames, and then pressed and held P for three frames (about 0.06 seconds).

This could be converted into the same format as before fairly easily; just condense the relevant inputs in each line so this would become:

. . O O O O O . . P P P

The issue is that Manic Miner doesn't run at one step per video frame, or even at a fixed frame rate - in this snippet (taken partway through Central Cavern) the inputs were only processed on the third, seventh, and tenth frames, meaning it would actually be:

O O P

The idea would be to take the original file, remove any line where inputs aren't processed, and then condense it, which can all be automated fairly easily. There are two issues with this:

1. Left/right/jump inputs are not processed while Willy is airborne even though the game continues to step through, but the format used requires these to still be accounted for.

2. Music/pause inputs are processed at an entirely different point in the game cycle (usually about two frames later).

Because of this, I can't just remove lines where inputs aren't processed. In order to convert the format I'd need to find a memory address that changes every game step in very close proximity to the left/right/jump input processing; I then record the current inputs to file whenever this memory address changes and convert it, and we have everything exactly as needed.

1. Is there a memory address that changes every game step in very close proximity to the left/right/jump input processing? I tried using the air counter but that's about as far as away as you can get.

2. Alternatively, are the current step's inputs stored in memory anywhere (i.e. if Willy is walking left/right or has started a jump)? If so, I could just read them whenever the air counter changes.

If the answer is yes to either of these questions then I can convert it pretty easily. Unfortunately a modified version of the game that adds either of these in isn't going to be helpful as it's likely to run at a very slightly different speed than the original game and therefore cause the inputs to become out of sync.

[IRF]

Couple of things:

(1) The program does react to keyperesses in certain circumstances even when the Airborne Indicator is set - namely when Willy lands after a jump up onto a platform higher than the one he jumped from. This allows him to land, turn and jump again in a single time frame. Indeed, that is the very manoeuvre which allowed you to gain an extra point.

(2) There is already a datafile for the previous best performance available earlier on in this thread (Crem provided one for each cavern). So I think the easiest thing to do would be for me to scrutinise the few frames where the new route differs, and manually edit the data accordingly.

[DigitalDuck]

5 hours ago, IRF said:

Couple of things:

(1) The program does react to keyperesses in certain circumstances even when the Airborne Indicator is set - namely when Willy lands after a jump up onto a platform higher than the one he jumped from. This allows him to land, turn and jump again in a single time frame. Indeed, that is the very manoeuvre which allowed you to gain an extra point.

That just makes it even more complicated!

5 hours ago, IRF said:

(2) There is already a datafile for the previous best performance available earlier on in this thread (Crem provided one for each cavern). So I think the easiest thing to do would be for me to scrutinise the few frames where the new route differs, and manually edit the data accordingly.

If you want to do it manually, you're welcome to. It's worth noting that the whole run is different in terms of inputs (mainly because the goal is slightly different - real-time speed vs. in-game score), but obviously there's a lot of overlap between these goals and therefore in the routes, so it shouldn't be too much to tweak.

[IRF]

2 hours ago, DigitalDuck said:

That just makes it even more complicated!

If you want to do it manually, you're welcome to. It's worth noting that the whole run is different in terms of inputs (mainly because the goal is slightly different - real-time speed vs. in-game score), but obviously there's a lot of overlap between these goals and therefore in the routes, so it shouldn't be too much to tweak.

Point 1: makes me wonder if the current optimised routes (because of the way they were created) didn't consider the possibility of pressing turn-around-and-jump-again during a jump, and whether there are any further efficiencies to be found elsewhere as a result? EDIT: Although I've just noticed that Willy does precisely such a manoeuvre halfway through the AI walkthrough of Wacky Amoebatrons, for example. With the immediate benefit of allowing Willy to get up onto the next level of WA slightly quicker. The Endorian Forest example may be unique because the turn/jump move is 'time-neutral' when considering the rate of progression through the cavern on a 'localised' basis; the one time-frame efficiency is only realised later on, when Willy comes to drop down again, and it transpires that the remnant of the crumbly platform lends itself to a slightly quicker descent.

Point 2: I seem to recall that the objectives of fastest completion and highest score are nearly always in perfect alignment in Manic Miner; the only exceptions being the flicking of the switches to dislodge Kong Beast (for extra points, at the cost of one more time frame), and the Solar cavern (due to the need to minimise contact with the beam to reduce air sapping and thus increase the end-of-cavern score). So I don't foresee any difficulty in updating the data stream for The Endorian Forest.

Edited August 25, 2023 by IRF

[DigitalDuck]

2 hours ago, IRF said:

Point 2: I seem to recall that the objectives of fastest completion and highest score are nearly always in perfect alignment in Manic Miner; the only exceptions being the flicking of the switches to dislodge Kong Beast (for extra points, at the cost of one more time frame), and the Solar cavern (due to the need to minimise contact with the beam to reduce air sapping and thus increase the end-of-cavern score). So I don't foresee any difficulty in updating the data stream for The Endorian Forest.

Mostly, but not quite - for example, jumping slows the game down a bit, and it's faster to wait a game step if it means two fewer jumps; however, there were no cases where that tradeoff was actually needed. Some of the caverns were re-routed to minimise jumping, and in at least one cavern I collected an item earlier just to remove it from the game updates to save a frame. (Remembering which one is harder when it was the best part of a year ago.)

In any case, in all cases apart from the three caverns listed (the first Kong Beast level is actually significantly more than one frame - the entire right side of the level has to be climbed and descended again) it doesn't conflict with the maximum score goal, so you're right in that there shouldn't be any issue there.

[IRF]

9 hours ago, DigitalDuck said:

Mostly, but not quite - for example, jumping slows the game down a bit, and it's faster to wait a game step if it means two fewer jumps; however, there were no cases where that tradeoff was actually needed. Some of the caverns were re-routed to minimise jumping, and in at least one cavern I collected an item earlier just to remove it from the game updates to save a frame. (Remembering which one is harder when it was the best part of a year ago.)

In any case, in all cases apart from the three caverns listed (the first Kong Beast level is actually significantly more than one frame - the entire right side of the level has to be climbed and descended again) it doesn't conflict with the maximum score goal, so you're right in that there shouldn't be any issue there.

If Willy is walking sideways and does a jump (landing on the same level), then the last frame of animation of that jump he drops down vertically, so his sideways momentum is slowed down ie it costs time both in terms of air supply (one increment) AND slower execution of the program during the jump.

I can't think of a scenario where jumping might be 'optional' in the way that you suggest in MM? (In JSW, you can allow an arrow to pass through you rather than jump over it if there happens to be some non-solid platform that Willy can hide inside/behind when the arrow passes through him.)

You're right about the first Kong, of course - I was thinking about the second one and completely forgot about the first!

[DigitalDuck]

1 hour ago, IRF said:

If Willy is walking sideways and does a jump (landing on the same level), then the last frame of animation of that jump he drops down vertically, so his sideways momentum is slowed down ie it costs time both in terms of air supply (one increment) AND slower execution of the program during the jump.

I can't think of a scenario where jumping might be 'optional' in the way that you suggest in MM?

In some of crem's routes, there are a few times when extra unnecessary jumps are done (these don't cost score as they come before waiting on a guardian to move out of the way anyway); a good example of this is in The Vat, where there's an unnecessary jump while following the pink kangaroo (as there are more than a few frames of waiting in that cavern, I think I walked Willy further to the right first instead).

[IRF]

11 hours ago, DigitalDuck said:

In some of crem's routes, there are a few times when extra unnecessary jumps are done (these don't cost score as they come before waiting on a guardian to move out of the way anyway); a good example of this is in The Vat, where there's an unnecessary jump while following the pink kangaroo (as there are more than a few frames of waiting in that cavern, I think I walked Willy further to the right first instead).

I've just rewatched Crem's walkthrough of The Vat. When Willy first starts walking behind the pink kangaroo, he is so close to it that I suspect he might have collided with it when trying to jump up to the next platform as it turned around at the end of its trajectory. The early jump whilst walking along probably prevented that, by setting him back a step relative to the kangaroo (for the reason I mentioned earlier - the last step of a sideways jump doesn't actually move him sideways). However, he could have achieved the same thing by simply stopping walking for one time-frame (which, as you say, would have been slightly quicker in real-world time).

Edited August 26, 2023 by IRF