Automated generation of Jet Set Willy speedrun/walkthrough

[crem]

And now the stats:

• The algorithm is running for 40 hours
• 2470 entryways (and 4077 entrypoints; ways to enter a room) were discovered so far. I expect there will be no more than 3000-3500 entryways in total, as there are only few rooms which the algorithm hasn't reached yet and not generated the entryways:
  • Room 14   Rescue Esmerelda
  • Room 15   I'm sure I've seen this before..
  • Room 38  Priests' Hole
  • Room 39   Emergency Generator
  • Room 44   On top of the house
  • Room 47   [
  • Room 50   Watch Tower
  • Room 59   The Yacht
  • Room 60   The Bow
• 806 entryways already computed. So, roughly 20 entryways per hour. Meaning there's ~6 days more to go (maybe a bit longer as I'm planning to move it from my primary computer to another one). Not that much at all!
• 59801 in-room routes are generated from those 806 entryways.

There will be ~260000 routes in the end. I wonder whether there is any value in sharing/publishing them... I'm sure there will be something unexpected, but 260000 is a bit too much to review manually.
I will check them all for unexpected wraps (probably there won't be any, but maybe?).
Could you think about any other open questions about what's possible in JSW is?

[jetsetdanny]

Your work looks extremely impressive to me, crem! 👍 Regretfully, it's way over my head, I won't be able to help you in any significant way programming-wise.

As for the number of frames during the rope cycle, there is only one rope guardian in the original JSW (guardian 01) - in other words, all the ropes are the same in the game. According to JSWED, each of them has a swing of 054 (while the rope length is 032 and rope position is 034). I don't know if this is what we are looking for, but I'm wondering if the swing of 054 does not effectively mean that the rope takes 54 frames while it's on its way (one way, perhaps?).

 

[crem]

49 minutes ago, crem said:

Meaning there's ~6 days more to go (maybe a bit longer as I'm planning to move it from my primary computer to another one).

I've moved the code from my main computer to Fitlet H mini-computer which I had standing around without use, and fps dropped from 5000 to 1100... Meaning if it's slower proportionally, it would take 27 days.

Hmmm not sure I want to keep it there. On one hand it's handier when the computer I work on doesn't run anything in background. On the other hand 27 days instead of 6 is quite a difference...

[IRF]

1 hour ago, crem said:

In the previous message I mentioned entrypoints, possible Willy positions (together with jumping/falling state) when he enters the room.

If my interpretation is right that you're referring there to jumping into a new room, rather than walking into it, I would just point out that in most circumstances that's an unwise manouevre, as Willy can end up in an Infinite Death cycle...

[IRF]

6 hours ago, jetsetdanny said:

As for the number of frames during the rope cycle, there is only one rope guardian in the original JSW (guardian 01) - in other words, all the ropes are the same in the game. According to JSWED, each of them has a swing of 054 (while the rope length is 032 and rope position is 034). I don't know if this is what we are looking for, but I'm wondering if the swing of 054 does not effectively mean that the rope takes 54 frames while it's on its way (one way, perhaps?).

It's not quite that simple.  The rope animation frame counter is incremented/decremented by 2 - except when it's close to its equilibrium position (i.e. hanging vertically), where it swings faster (the animation variable is incremented/decremented by 4).

I've just watched a rope swinging whilst keeping the A (pause) key depressed, stabbing at the '1' (non-movement) key, and counting the rope's animation frame-by-frame, and I think it takes 90 frames for each there-and-back swing of the rope.

Edited May 4, 2021 by IRF

[crem]

Status update:

I've just restarted the entire thing from scratch (so 2 days are wasted, but that's not so much), with the following changes:

• Changed number of frames with no progress after which algorithm gives up from 15 to 200 frames.
  I already wrote above that in rooms with rope 15 frames threshold is too little. I was going to redo all rooms with ropes afterwards, but it turns out these are not the only rooms that are affected. The room Halfway up the East Wall involves a few seconds wait to go upwards, and the algorithm missed that.
  Probably it makes sense to set it to the longest guardian cycle, but I think 200 is higher than any such cycle.
• I changed the threshold for combining entrypoints into entryways from 2 pixels to 16. Not sure whether it will bring more harm than good, but if so, we can always restart.
• The limit of the route length within one room is now 2000 frames (it was intended to be set to 1500 but was actually set to 15000). In RuffledBricks speedrun the longest room is The Wine Cellar which takes exactly one minute, which I estimate to be ~800 frames. 2000 should be enough slack.

I also decided that it's too long to wait 28 days for it to finish, so I moved the pipeline back to my computer. I'll pause it when I need my computer for something else, but it will be computing during the night and during the worktime. I expect that the 15->200 change will increase the time needed, so it will be longer than 7 days, but I don't know yet how much longer (quick calculation shows it will increase that by 6 days, but hopefully I miscalculated it).

[jetsetdanny]

Thanks for the update, crem.

How much in Bitcoin will you be losing by not mining them but computing JSW room routes instead? 😄

[crem]

9 hours ago, jetsetdanny said:

Thanks for the update, crem.

How much in Bitcoin will you be losing by not mining them but computing JSW room routes instead? 😄

I think it's only possible to mine Bitcoins for profit when you use specialized hardware (otherwise you lose on electricity costs more than you gain), so I'm quite sure it's "net positive" not to mine Bitcoins. 😛

I don't have a very good CPU though, it's i5 4690K which I bought in 2015, and even back then it was decent but surely not cutting edge. Modern CPU (especially ones with more than 2 cores) would compute JSW routes much faster, but I think waiting 1-2 weeks is fine.

For all the Bitcoin stuff, while I like the idea, I refuse to deal with it because it's very environmentally unfriendly, it wastes too much of a world energy.

[crem]

A bit of a status update. I'll have to restart it once again, but maybe only for rooms with a rope.

 

First good news:

Increasing entryway radius from 2 to 16 seemed to decrease number of things to compute by 30%, so it would be 11 days to compute, not 14.
Another thing is that the time needed for computation increases by 1 day for every 40 additional frames of "no progress persistence counter". Yesterday I increased it from 15 to 200, that means 4.5 extra days, most of which are probably not for any reason. Maybe I'll tune it back to 100 or so.

 

And now to the bad part:

DigitalDuck from the spectrum speedrunning Discord, pointed that in the "On the Roof" room it should be possible to climb up a rope up to wrap into the same room from the bottom. My tool already computed that room but it turned out that such route was not found.

I thought there must be still some issue with the rope handing, and after checking the "best route to go from left, grab the item and then go back to the left" (see the attached video) it became apparent that the tool still has problems cooking the rope...

I won't have much time until the weekend to debug it, but I have an idea what may be wrong.
Currently, when the falling status variable is not 0, I don't attempt moving/jumping (as during the fall/jump controls don't work anyway).

I suspect that this variable is also non-0 when Willy is on the rope. Maybe someone remembers whether it's so? Then it should be a quick fix.

Thanks!

[IRF]

1 hour ago, crem said:

DigitalDuck from the spectrum speedrunning Discord, pointed that in the "On the Roof" room it should be possible to climb up a rope up to wrap into the same room from the bottom. My tool already computed that room but it turned out that such route was not found.

I thought there must be still some issue with the rope handing, and after checking the "best route to go from left, grab the item and then go back to the left" (see the attached video) it became apparent that the tool still has problems cooking the rope...

I won't have much time until the weekend to debug it, but I have an idea what may be wrong.
Currently, when the falling status variable is not 0, I don't attempt moving/jumping (as during the fall/jump controls don't work anyway).

I suspect that this variable is also non-0 when Willy is on the rope. Maybe someone remembers whether it's so? Then it should be a quick fix.

It depends whether Willy was jumping/falling at the moment when he becomes entangled on the rope:

- If he's walking along (e.g. in the Swimming Pool) and the rope touches him, then he will end up on the rope and the Airborne Status Indicator (#85D1) will still be set at zero;

- If he jumps up onto the rope, then #85D1 will hold and retain the value #01;

- If he falls down and touches the rope (e.g. dropping out of the Orangery into the Swimming Pool), then #85D1 will have a value somewhere in the range #02-#0F.

The value of #85D1 is only updated when Willy departs from the rope:

- If he jumps off the rope, it is set to #01;

- If he climbs down and drops off the bottom segment, it is reset to zero;

- If he climbs up to the top, to emerge in the room above, then #85D1 is also reset to zero (the same as if he jumps up into the room above).

Note that the manoeuvre you refer to in 'On the Roof' is only possible by jumping off the rope when it is at or near the widest deviation of its swing from the centre.