Automated generation of Jet Set Willy speedrun/walkthrough

[crem]

6 minutes ago, IRF said:

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

Thanks!

Oh that probably means that I should ignore falling/jumping counters completely while Willy is on the rope.

Otherwise it will introduce lots of the states which appear different to the algorithm but in fact they are completely the same.

 

So do I understand it right that when rope=1 (and Willy is somewhere on the rope at (x,y)), there's no difference in what will happen, whether fall_counter=0 or not 0, and whether jump_counter=0 or not 0. (Currently I only take jump counter into the account when fall_counter==1, I should probably similarly ignore fall_counter when rope_indicator=1).

[IRF]

The only scenario I can think of where the jump/fall counters matter, once Willy has attached to a rope, is if you use the WRITETYPER teleport function to exit to a room without a rope.  Strange things can happen if you do that!

[crem]

1 hour ago, IRF said:

The only scenario I can think of where the jump/fall counters matter, once Willy has attached to a rope, is if you use the WRITETYPER teleport function to exit to a room without a rope.  Strange things can happen if you do that!

Thanks, that really helps.

I've restarted the tool with the following changes:

• Completely reset all the progress made in 5 rooms with the rope (not that much progress is wasted)
• Allowed Willy to jump/move when in rope
• Ignoring fall/jump counters when comparing two Willy states when Willy is on the rope.
• Reduced that "no progress patience" number from 200 to 115

Hopefully it all will work. 🙂

Actually I've waited some time to check whether ropes work now, and they indeed do!
Also the issue in the room "Halfway up the East Wall" which was caused by too little patience was also resolved. Entire route bottom to top took 226 frames, so I decided that 200 frames just for waiting is an overkill, actually logs show that 29 would be already enough, that's why I reduced it from 200 to 115.

Some stats so far:

• 43 out of 60 rooms discovered. Mostly the right part of the map is not yet discovered:
  • Room 0   The Off Licence
  • Room 1   The Bridge
  • Room 2   Under the MegaTree
  • Room 3   At the Foot of the MegaTree
  • Room 4   The Drive
  • Room 6   Entrance to Hades
  • Room 7   Cuckoo's Nest
  • Room 8   Inside the MegaTrunk
  • Room 9   On a Branch Over the Drive
  • Room 12   Tree Top
  • Room 13   Out on a limb
  • Room 14   Rescue Esmerelda
  • Room 15   I'm sure I've seen this before..
  • Room 44   On top of the house
  • Room 45   Under the Drive
  • Room 46   Tree Root
  • Room 47   [
  • Room 50   Watch Tower
• 1111 searches are created for those 43 rooms. I expect those rooms will give 600 more or so..
• 171 of them are already done (it's roughly 18 hours since I started)
• 11191 in-room routes were found so far.

At the current rate, the search should take 8 days.

[jetsetdanny]

Thanks for the updates, crem! 👍

[crem]

The route computation goes quite well. After 3 days, I estimate 40% of all routes are computed. That means that by the next weekend I'll have all the "raw material" do start working on actual routing. Then it will probably take a couple of more weeks until we have some beginning-to-end walkthroughs.

Initially I intended to generate a video with all routes in all rooms (for all entrance and exit points with various sets of collected items), but now it seems that at 60 fps that video would take 23 hours. Probably noone would watch that.

I'm attaching some samples of generated routes, just for keep this thread not very boring.

(71190 routes in total are computed so far, with 2190337 frames total).

[jetsetdanny]

Thank you, crem, that's very interesting 👍.

I think that the movements in "Out on a limb" and "Ballroom West" are more efficient than the ones I am used to (I'm actually sure about the former, not quite sure about the latter). I think we might be in for some surprises once you're done... 🙂  

[RuffledBricks]

Have been trying some of these out today. Already posted some of my thoughts on these in the Speedtrum Specrunning Discord, but I'll repeat them here as well.

Rather pleasingly, I've been finding several of these to be very replicable. The improved Cold Store deathwarp doesn't take too much work to get the hang of, and the triple jump in OOAL is easy once you've found the right starting position - it also reopens the discussion about whether it's worth utilising a deathwarp in that room, as the second half of the room has now been made longer as a result.

Nightmare Room is my favourite of these new ones so far, although the second jump in it is pretty difficult. It's both pixel perfect AND frame perfect as far as I can tell, meaning that the failure threshold is pretty low. However, once you've nailed that jump, the rest of the room is an absolute dream compared to the current strat, so I reckon it's well worth it.

Off Licence I'm having a lot of trouble with, as you need to pass Cyan Ball at the earliest opportunity and hit your turning jump onto the conveyor belt pretty precisely to get the Green Radar jump right. Then you also need to mind your item jumps so that you don't miss any as you head right. It's pretty unforgiving.

Oh, and I cannot get my head around the Ballroom West one at all. I just can't find any good visual hooks to reproduce it yet.

Looking forward to more of these, so cheers for your hard work @crem.

Edited May 9, 2021 by RuffledBricks

[crem]

Meanwhile 70% of all routes are computed (after 4.5 days). That means that there's only 2 more days to finish this stage of the generation. This is a bit faster than I expected, and actually I didn't start to work on the between-rooms routing code, so it will take some time before I'll be able to start the next part of the search.

So far 153459 in-room routes are generated, and although I think it would be interesting to browse them to find something interesting, I cannot think of feasible way to do that.

What I can easily do is to lookup routes with have some properties. So if you have any questions regarding the fastest route in the particular room, or some question of "whether it's possible" type, I'll show the route.

Here are all possible room transitions. Very unlikely to have anything unexpected, but still here is the list:

Spoiler

Room 0 The Off Licence
  -> 1 The Bridge
Room 1 The Bridge
  -> 0 The Off Licence
  -> 2 Under the MegaTree
Room 2 Under the MegaTree
  -> 1 The Bridge
  -> 3 At the Foot of the MegaTree
Room 3 At the Foot of the MegaTree
  -> 2 Under the MegaTree
  -> 4 The Drive
  -> 8 Inside the MegaTrunk
Room 4 The Drive
  -> 3 At the Foot of the MegaTree
  -> 5 The Security Guard
  -> 45 Under the Drive
Room 5 The Security Guard
  -> 4 The Drive
  -> 6 Entrance to Hades
  -> 10 The Front Door
  -> 19 The Forgotten Abbey
Room 6 Entrance to Hades
Room 7 Cuckoo's Nest
  -> 2 Under the MegaTree
  -> 8 Inside the MegaTrunk
Room 8 Inside the MegaTrunk
  -> 3 At the Foot of the MegaTree
  -> 7 Cuckoo's Nest
  -> 9 On a Branch Over the Drive
  -> 12 Tree Top
Room 9 On a Branch Over the Drive
  -> 4 The Drive
  -> 8 Inside the MegaTrunk
  -> 10 The Front Door
Room 10 The Front Door
  -> 5 The Security Guard
  -> 11 The Hall
Room 11 The Hall
  -> 10 The Front Door
  -> 20 Ballroom East
Room 12 Tree Top
  -> 8 Inside the MegaTrunk
  -> 13 Out on a limb
Room 13 Out on a limb
  -> 9 On a Branch Over the Drive
  -> 10 The Front Door
  -> 12 Tree Top
Room 14 Rescue Esmerelda
  -> 15 I'm sure I've seen this before..
  -> 20 Ballroom East
  -> 39 Emergency Generator
  -> 44 On top of the house
Room 15 I'm sure I've seen this before..
  -> 14 Rescue Esmerelda
  -> 16 We must perform a Quirkafleeg
Room 16 We must perform a Quirkafleeg
  -> 15 I'm sure I've seen this before..
  -> 17 Up on the Battlements
  -> 50 Watch Tower
Room 17 Up on the Battlements
  -> 16 We must perform a Quirkafleeg
  -> 18 On the Roof
Room 18 On the Roof
  -> 17 Up on the Battlements
  -> 18 On the Roof
  -> 48 Nomen Luni
Room 19 The Forgotten Abbey
  -> 5 The Security Guard
  -> 49 The Wine Cellar
Room 20 Ballroom East
  -> 11 The Hall
  -> 21 Ballroom West
  -> 26 East Wall Base
Room 21 Ballroom West
  -> 20 Ballroom East
  -> 22 To the Kitchens    Main Stairway
Room 22 To the Kitchens    Main Stairway
  -> 21 Ballroom West
  -> 23 The Kitchen
  -> 28 First Landing
Room 23 The Kitchen
  -> 22 To the Kitchens    Main Stairway
  -> 24 West of Kitchen
Room 24 West of Kitchen
  -> 23 The Kitchen
  -> 25 Cold Store
  -> 30 The Banyan Tree
Room 25 Cold Store
  -> 24 West of Kitchen
  -> 31 Swimming Pool
  -> 52 Back Stairway
Room 26 East Wall Base
  -> 20 Ballroom East
  -> 32 Halfway up the East Wall
Room 27 The Chapel
  -> 21 Ballroom West
  -> 28 First Landing
Room 28 First Landing
  -> 22 To the Kitchens    Main Stairway
  -> 27 The Chapel
  -> 29 The Nightmare Room
  -> 34 Top Landing
Room 29 The Nightmare Room
  -> 28 First Landing
  -> 30 The Banyan Tree
Room 30 The Banyan Tree
  -> 29 The Nightmare Room
  -> 31 Swimming Pool
  -> 36 A bit of tree
Room 31 Swimming Pool
  -> 30 The Banyan Tree
  -> 37 Orangery
  -> 54 West  Wing
Room 32 Halfway up the East Wall
  -> 26 East Wall Base
  -> 38 Priests' Hole
Room 33 The Bathroom
  -> 34 Top Landing
Room 34 Top Landing
  -> 28 First Landing
  -> 33 The Bathroom
  -> 35 Master Bedroom
Room 35 Master Bedroom
  -> 34 Top Landing
Room 36 A bit of tree
  -> 30 The Banyan Tree
  -> 37 Orangery
  -> 42 Under the Roof
Room 37 Orangery
  -> 31 Swimming Pool
  -> 36 A bit of tree
  -> 43 Conservatory Roof
  -> 56 West Wing Roof
Room 38 Priests' Hole
  -> 32 Halfway up the East Wall
  -> 39 Emergency Generator
Room 39 Emergency Generator
  -> 38 Priests' Hole
  -> 40 Dr Jones will never believe this
Room 40 Dr Jones will never believe this
  -> 16 We must perform a Quirkafleeg
  -> 39 Emergency Generator
  -> 41 The Attic
Room 41 The Attic
  -> 40 Dr Jones will never believe this
  -> 42 Under the Roof
Room 42 Under the Roof
  -> 36 A bit of tree
  -> 41 The Attic
  -> 43 Conservatory Roof
  -> 48 Nomen Luni
Room 43 Conservatory Roof
  -> 37 Orangery
  -> 42 Under the Roof
Room 44 On top of the house
  -> 14 Rescue Esmerelda
  -> 38 Priests' Hole
Room 45 Under the Drive
  -> 4 The Drive
  -> 46 Tree Root
Room 46 Tree Root
  -> 45 Under the Drive
Room 47 [
Room 48 Nomen Luni
  -> 18 On the Roof
  -> 42 Under the Roof
Room 49 The Wine Cellar
  -> 19 The Forgotten Abbey
  -> 51 Tool  Shed
  -> 52 Back Stairway
Room 50 Watch Tower
  -> 0 The Off Licence
  -> 16 We must perform a Quirkafleeg
Room 51 Tool  Shed
  -> 49 The Wine Cellar
  -> 53 Back Door
  -> 58 The Beach
Room 52 Back Stairway
  -> 25 Cold Store
  -> 49 The Wine Cellar
  -> 53 Back Door
  -> 54 West  Wing
Room 53 Back Door
  -> 51 Tool  Shed
  -> 52 Back Stairway
Room 54 West  Wing
  -> 31 Swimming Pool
  -> 52 Back Stairway
  -> 55 West Bedroom
  -> 56 West Wing Roof
Room 55 West Bedroom
  -> 53 Back Door
  -> 54 West  Wing
  -> 57 Above the West Bedroom
Room 56 West Wing Roof
  -> 37 Orangery
  -> 54 West  Wing
  -> 57 Above the West Bedroom
Room 57 Above the West Bedroom
  -> 55 West Bedroom
  -> 56 West Wing Roof
Room 58 The Beach
  -> 51 Tool  Shed
  -> 58 The Beach
  -> 59 The Yacht
Room 59 The Yacht
  -> 58 The Beach
  -> 60 The Bow
Room 60 The Bow
  -> 59 The Yacht

 

 

Edited May 10, 2021 by crem
Hid the text to the spoiler

[Spider]

I've not said much (if at all) in this topic however I have been following it with much interest and fascination. 🙂 I do appreciate the work that's gone into it.

[crem]

Nothing exciting yet, just an update. 🙂

All the in-room routes have just been calculated (255451 routes in total, starting from 5430 entrypoints), it took 6.5 days to do that.

Now it's time to combine those routes into the complete walkthrough. I don't have the code for this yet (I hoped in-room route calculation to take longer!), but I'll try to write it within 2 days. It's not clear whether the first attempt will work though. It's a generalized Travelling salesman problem, for which it's known that straightforward "Dynamic programming" solution usually doesn't work. However it's the easiest to implement and I've discussed it with a few people and everyone agreed that there's a chance it will work in this particular case. If it won't work, I'll have to implement something more complicated.

I'm using the JSW version that speedrunners are using (with bugfixes), and I'll generate all three categories (Any%, Max Lives and Nowarp) in two timing methods, In-game-time (IGT, basically minimize number of frames) and realtime (RT, minimize number of CPU cycles).

I'll do that in the following order (from least interesting to most interesting, and also Max Lives should be easier to compute):

• Max Lives IGT
• Max Lives RT
• Nowarp IGT
• Any% IGT
• Nowarp RT
• Any% RT

It's unlikely that Max Lives RT will differ from Max Lives IGT, but who knows..

The RT timing of my emulator is not precise enough, it doesn't take memory contention into account (I'm not sure whether it happens in JSW though, and now large the effect it), but hope it will be fine that way.