Automated generation of Manic Miner speedrun/walkthrough

[MtM]

That was an ugly route in the Menagerie 😉

 

Good score though 🙂

 

[IRF]

3 minutes ago, crem said:

Actually currently the tool searches for the shortest route in terms of number of frames, not the remaining air. Optimizing air is a bit more complicated, but doable.

The two normally amount to the same thing, don't they? As air is sapped in a linear fashion over time. The only exception to that rule is the solar cavern.

I would imagine it will be quite complicated to optimise for remaining air in the solar cavern.  Bear in mind that the amount of air sapped by the beam in each frame, when Willy is inside the beam, is different if Willy is vertically cell-aligned (occupying only two character rows), than if he is mid-jump or mid-fall and therefore his sprite (technically, his white INK colour-attribute) is spanning three character rows of the screen.

So as well as generally minimising the time when Willy is within the beam, your algorithm might need to take into account that - for those moments when entering the beam is unavoidable - the air-sapping power of the beam differs as explained above.

P.S. Given that you optimise for least number of time-frames of the game, rather than for highest score per se, you presumably won't bother collecting the bonus points for dislodging Kong from his perch? Which will probably mean that you won't match the highest scores in the two Kong caverns.

[crem]

20 minutes ago, IRF said:

P.S. Given that you optimise for least number of time-frames of the game, rather than for highest score per se, you presumably won't bother collecting the bonus points for dislodging Kong from his perch? Which will probably mean that you won't match the highest scores in the two Kong caverns.

That's indeed true, the main motivation for this is to find something useful for speedrunners, not to have the highest score.

Unlike in solar power generator level, Kong levels are pretty easy to fix. Just consider end of level a loss rather than a win, if Kong is still in its initial position.

[RuffledBricks]

55 minutes ago, crem said:

Actually currently the tool searches for the shortest route in terms of number of frames, not the remaining air. Optimizing air is a bit more complicated, but doable.

Yeah, if I understood correctly, this tool was for finding the quickest time for each cavern rather than the highest score (as these aren't necessarily unified in Solar Power Generator). It feels like the trade-off would be the most optimum route that also ended with as little air as possible, so that the countdown time was minimal.

EDIT: didn't notice there was a second page on this thread, so this has pretty much already been covered. Whoops.

Edited March 8, 2021 by RuffledBricks

[IRF]

5 minutes ago, RuffledBricks said:

Yeah, if I understood correctly, this tool was for finding the quickest time for each cavern rather than the highest score (as these aren't necessarily unified in Solar Power Generator). It feels like the trade-off would be the most optimum route that also ended with as little air as possible, so that the countdown time was minimal.

Another fundamental difference in cultural mindset on display here - I enjoy the site of lots of air being counted down at the end of a cavern, as a sign that I've achieved a high score; you presumably see it as a nuisance, holding you back from swiftly tackling the next cavern!

[crem]

Some updates on further levels (tl;dr no success yet):

For level 4 ("Uranium"), the computation was completed, but for some reason Fuse fails to open the resulting .rzx file. Will look why is it so when I have time (hopefully today in the evening). I also have keypress information per frame, so if it's the problem with rzx writing and the rest worked fine, there will be no need to redo the calculation.

Level 5 ("Eugene") has the same problem with opening .rzx, but also it didn't find the win. When I woke up today and checked the results, all 35000 states had Eugene already sitting on the top of the portal, making win impossible. I'll restart this level with adjusted scoring (will make it a loss if Eugene sits on the portal).

In the morning I started Level 6 ("Pacman Processing Plant"), Level 7 ("VAT"), Level 8 ("Kong v1") and Level 9 ("Amoebatrons v1"). For levels 2-5, the search with "width" of 35000 states took 6 hours to complete, so I started Levels 6-9 with 50000 to finish by the end of the day.

Level 7 ("The Vat") finished after 7 frames with "no solution found" status. Clearly some bug on my side, will take a look later. Meanwhile, started Level 11 ("Telephones") instead (and later realized that I missed Level 10 "Endorean Forest").

[IRF]

For Eugene, you might need to adjust your algorithm so that it collects the nearest item to the portal last - even if that means passing close by to it without grabbing it straight away, but coming back for it once all other items have been bagged.

And also, if Eugene is too close to the portal at the point when Willy is about to finally collect that item, you might have to get him to wait around [which I know you've said the algorithm doesn't like to do!] until Eugene has ascended to a height that allows Willy to sneak into the portal once it starts flashing (whereupon Eugene becomes angry and starts descending again).

Thinking ahead, Skylab Landing Bay is another 'special' room, but I don't foresee that one will cause the algorithm any particular problems?

Edited March 8, 2021 by IRF

[jetsetdanny]

Thanks for sharing this, crem, it's fascinating! 👍

I meant to make exactly the same comments as Ian made above (great minds...! 🙂), drawing your attention to the highscore challenge scores and the Solar Power Generator, where you will have to optimise the method for the remaining air, as the solar beam is a huge factor there.

I am also wondering about JSW games, as the possible routes will multiply the possible options the algorithm will have to analyse. The original "JSW" may be "relatively" simple in this respect, but if you ever wanted to carry out a similar analysis for other JSW games that have been released so far (a complete list is here), you will find some real behemoths among them. Take sendy (Alex Cornhill)'s "where's woody?" for example. 256 edited rooms (although the player does not have to visit all of them to complete the game - that's another challenge for the algorithm, to determine which rooms can be skipped safely), non-linear, hundreds of possible room exits altogether, so I would think thousands and thousands of possible routes to take (or even more - it will grow exponentially, won't it?). I don't know if you have enough processing power to analyse that one 🤪. But it would certainly be interesting to know how much my best in-game completion time (achieved using the Rollback feature and what I decided, after a careful analysis, was the most efficient route) of 2:10 pm can be improved...

Meanwhile, I am looking forward to your scores in the next MM caverns - it's very interesting, thanks again! 🙂

[crem]

  

I regenerated the Level 4 from the keypresses information, and it worked fine. However, the result turned out to be 1 frame longer than the current record from another topic in this forum. Not sure if it worth sharing before it's polished. 😛

Level 6 and Level 9 have also finished, but they turned out to be even worse (2 and 5 frames slower respectively, if I remember right).

I tweaked scoring a bit (the duplicate Willy position penalization function is sigmoid now rather than linear function) I think it should help.

I've also made the source code of the tool public at https://bitbucket.org/mooskagh/zx-stratfinder/src/master/ if anyone is curious how it's written, wants to adapt it to other games or wants to help.

[jetsetdanny]

It's comforting to know that human players can still be better than algorithm players, or whatever they should be called properly 🌞.

Not for long, though, I suspect...