Automated generation of Jet Set Willy speedrun/walkthrough

[crem]

Yes, it's happening, I'm generating the walkthrough for Jet Set Willy, similarly to what I did for Manic Miner. \o/

I'll describe the technical part of it in a later posts, for now I just want to announce that I've started it and start this thread.

Initially I thought that I'd make a website where the progress could be tracked, and possibly where people could help with computing power, but:

• I was lazy to implement it,
• Single room generation turns out to be much faster than I expected (around 5 minutes instead of 5 hours per room), thanks to the optimizations suggested on this forum and much easier level structure than Manic Miner.

I'm still finishing the "strategical routing" algorithm (e.g. order of rooms rather than in-room routing; I call it "journey" rather than "route" just to have a different term for it), during the next days while the "journey planner is not yet ready" I'll use @RuffledBricks speedrun route and will run the script to micro-optimize it.

Aaaand to get started with something concrete, here is the speedrun of the very first room. 😛 Enjoy!

[IRF]

Are you going for the fastest 'real world' completion time, or the earliest finish according to the on-screen clock (i.e. the fewest number of frames/ticks/passes through the Main Loop)?

The merits of climbing up the Bathroom ramp at the start of the game, in order to access the Top Landing item, were discussed at an earlier stage (around the time that RuffledBricks first posted his speedruning video), and I think the consensus emerged that that early decision could have a bearing on the completion time, depending on what you're trying to achieve.

If it's the earliest finish according to the on-screen clock (fewest frames), then it stands to reason that you should collect the Top Landing item as the second item (after the Bathroom tap), so that Willy isn't wasting frames walking back into the Bathroom at the end of the game to access the ramp up to the upper levels of Top Landing.

If it's the fastest real world completion time, then RB pointed out that the game runs faster at the end (assuming you've used up all your spare lives by that point 'kamikazeing' items), because the execution of the drawing of spare lives on the status bar during each frame, slows down the game to a degree which is perceptible over the course of a whole game.  So the fact that Willy has to take a longer route (more frames) to collect the Top Landing item at the end, is outweighed by the fact that the game runs quicker at that point if you haven't got any spare lives left.

****

Incidentally, if it's the fastest real world completion that you are trying to achieve via your algorithm, then you would need to get it to release and then press 'ENTER' in the first two frames of the game, in order to turn off the in-game music.  Because the playing of the in-game tune further slows down the running of the game.

[crem]

5 hours ago, IRF said:

Are you going for the fastest 'real world' completion time, or the earliest finish according to the on-screen clock (i.e. the fewest number of frames/ticks/passes through the Main Loop)?

The approach I've picked supports both, but as counting frames is much easier than CPU cycles, I'll start with the in-game time.

It also supports all Any%/Warpless/Max Lives categories, so I'm planning to do all that (in-game time first, then real time later).
It's not possible to process WRITETYPER run with this approach though, but I have a different idea how to do that, so unless I lose enthusiasm by then, after normal JSW runs I'll also generate the WRITETYPE route.

The most labour-intensive part of the realtime-clock-based run generation will be to gather per frame timings:

• "Base" time for one frame per room (which will be different as there will be different amount moving objects)
• How much extra time does every extra life add.
• How much time it takes to switch a room.
• (if there's a difference of speed depending on number of displayed collectible items [which I assume there is, but hopefully negligible], I'll have to ignore that due to the way the algorithm works).

[Norman Sword]

Turning off the music does not interfere with movement. E.g. You can turn the music on/off whilst playing the game.
 

So the music can be turned off on the 2nd frame - when played automatically.

 

 

 

 

[crem]

Actually Speedrunners start the game, stop the music and move to the "long stride" animation frame facing right (to appear as close as possible to the item when the game starts).

Then they stop the game with Caps+space, and restart it without music.

[Norman Sword]

I will leave you to get on with it then.

Addendum

Meaning :- I will not bother myself any further on your behalf. 

 

 

Edited May 5, 2021 by Norman Sword

[IRF]

Yes, the music on/off button can be pressed simultaneously with a movement key. But I was referring to the need to 'unpress' ENTER and then repress it if you want to turn the music off at the start of a game (there is a keypress flag that means if you keep ENTER pressed at the start of a game, then it won't toggle the music off until you let go of ENTER and then repress it).

But starting the game, switching the music off, abandoning that game and restarting another (so the music is already switched off at the start of the game) is an even simpler way of achieving the same thing.

[IRF]

18 hours ago, crem said:

The approach I've picked supports both, but as counting frames is much easier than CPU cycles, I'll start with the in-game time.

In that case, in order to get the fastest in-game time, I think you should probably climb up the Bathroom ramp as soon as you've collected the tap.

***

Incidentally, it would be useful to report the total number of frames that the game runs for, as the in-game completion time only tells you how you've done to the nearest 'minute' (a 'minute' on the on-screen clock equates to 256 'ticks'/passes through the Main Loop).

Furthermore, the 'tick' counter variable (#85CB) is reset to zero as soon as you reach the toilet at the end of the toilet run, so you would need to interrogate the value of #85CB in the frame immediately prior to him reaching the toilet.

[crem]

I'd like to share some stats about how the search is going so far (and some issues), for it to make sense, here is a bit of information about the algorithmic aspect of the route finding.

Most of "dynamic programming"-based route finding algorithms find shortest route from one source state to all possible states (i.e. it takes roughly equal amount of time to find the shortest batch from A to B, and all shortest paths from A to all B and C and D).
It would be easy just to run the shortest route search for the entire game, but the need to collect items in arbitrary order rather than just running to the end as quickly as possible actually makes the game a travelling salesman problem (something that doesn't have fast solution), not the shortest path problem.

What I do instead, is take all possible entrypoints¹ of all rooms, and generate all shortest routes in this room which start at the entrypoint and end either with a life loss or with transitioning to another room, for all possible² collected items variants.

¹ All possible entrypoints are determined from possible "exitpoints" of previous searches.
² It's not as bad as it sounds. If at given point the search finds out that there is a state strictly better than another one (exactly same Willy location at exactly same frame, but more items collected), it drops the worse state from the database.

As a result, I expect to find the set of in-room routes in the following format:

• From this entrypoint of the room
• It's possible to collect items X and Y.
• And end up in that exitpoint of the room (or loss a life; needed for Any% run)
• In Z frames (and later I'll annotate all those routes with number of CPU cycles, to support RTC speedrun rather than IGT).
• Here is the route: L L L . . . (keypresses per frame)

Ones I generate all such routes, I won't need to emulate the game at all, and will be able to work with the routes as a set of edges. This both reduces the state space, and makes all the algorithms much faster. Instead of generating 5000 frames per second, it will be possible to get to process tens of millions room walks per second.

[crem]

I wanted to get the search running during the weekend, and while I managed to get it running, it feels that if I did a few test runs, if would be a bit more efficient now (but it's good enough!).

Anyway, here are mistakes/problems/issues that I had so far:

1. In the previous message I mentioned entrypoints, possible Willy positions (together with jumping/falling state) when he enters the room. In fact, instead of working with entrypoints, I combine them into entryways, if they meet the following conditions:

• They are close to each other (≤2 pixels initially, ≤4 pixels in the current version)
• The route in the room they came from, took the same amount of frames to reach either of them.

The rationale in that was that in the "source" room routes usually don't differ until e.g. the jump in the very end, and in the "destination" room those routes will converge to the same anyway.

That would help if it worked. But in reality I see that there is only 1.65 entrypoints per entryway in average. Which means not much wins computationally, but possibly lots of headache in future when I'll start building "journeys".

tl;dr I should not have introduced entryways. They don't help but may cause problems later.

2. Currently there are a bit more than a thousand of entryways waiting to be calculated, but the question is in which order to compute them. Initially I didn't think I would want to calculate them all (thought there would be too many), so I wrote a small heuristic routing algorithm.

It didn't work well, so I deleted it, and now entryways to compute are picked (almost) at random. That works fine, but it computes lots of useless stuff, and also the most promising stuff is not yet computed. We have to wait until it finishes.

That's also the reason why I don't share algorithm's version of @RuffledBricks route yet. Those parts are still not picked for the compute.

3. I stop search when algorithm finds no new Willy positions for 15 frames. I just noticed that it doesn't work for rooms with the rope.

E.g. in the Cold Room, if Willy appears on the top left platform, it discovers all possible positions before the rope comes, so the search stops almost immediately.

I'll have to redo all searches in rooms with a rope which stopped too soon.

(btw, does anyone remember what is the period of the rope cycle? in number of frames).

4. As an upper limit of search, I put 1500 frames, which corresponds to roughly 6 minutes of in-game time (and probably 2 minutes of real time).

However, I made a mistype and the actual limit is 15000. Because of that, when it starts to compute Cold Room, it takes half an hour or so (apparently there are new Willy positions even after 1800 frames of entering the room).