crem

A message of assorted topics about how everything is failing but there's hope. 🙂 (1) It is clear now, that the attempted brute force solution to build the route doesn't work. It may find good enough walkthroughs and maybe even better than the currently best known routes, but it surely won't find the optimum. My nightly attempt to re-run the same Warpless+Maxlives lives turned out to give even longer (by 23 frames), despite having much wider search (7'571'762'474 states instead of 2'439'193'796) and entire evening to fighting algorithm's memory hunger. The route is slightly different, here it is: https://www.twitch.tv/videos/1023369202 (I found that the easiest way to record and share the video is to stream on twitch). I won't try any complex improvements to this algorithm. Instead I'll do one small tweak (point 3 below), run the algorithm for all the categories (4), and then probably will try a different approach (6). (2) Combining the spliced walkthrough to the proper one didn't work for some of room transitions. (technical stuff hidden in spoiler) Anyway, that's an easy thing to fix. I split such problematic entryways into several and recalculate affected routes. This is what's happening now, should take 1 day. (3) The current algorithm is too greedy, I'll try to come up with better game progress metric, which should help but not by much. The algorithm prefers to grab lots of easy items right away, and then struggles with the remaining ones. Currently, only "number of collected items" is used as a metric to track progress. Replacing it with a better one can improve things. I'll try to do the following: Make items valued differently (e.g. Ballroom West items are cheapest as they are easily accessible and plentiful). Penalize some sets of remaining items (e.g. if two remaining items are in different corners of the map). That will require some manual judgment though. (4) I'm still planning to generate all the speedrun categories using the current algorithm. But first I'll have to fix issues (2), (3), and for the realtime runs, do the (5). (5) For In-game-time optimization, I use number of frames. For Real-time runs, I'll need number of CPU cycles. My plan is to measure number of CPU cycles for every of ~250000 routes that were generated (including time to draw the next room) and use it as the edge cost in the algorithm. I expect this process to take ~3 hours. Some notes regarding that: I'm not sure how precise is the emulator library that I use. I surely don't emulate any input or memory delays, but otherwise it should be fine. What to do with variable number of lives affecting speed? I can either test a few routes and come up with a formula how number of lives affects frame time, or I can run all routes for all number of lives. Then it will take ~24 hours, still probably that's the easiest. 🙂 (6) Second attempt will be an AlphaZero-style neural network (if there will be a second attempt). If the results of the current algorithm won't be satisfiable, the next thing I'll try (given enough time and enthusiasm) is to try a AlphaZero-style reinforcement learning. For approach I'm very confident that it will work when implemented, but it's not very fast to write. Probably 1-2 months worth of winter evenings, which translates to 3-4 months of summer evenings.. But depends on weather. 🙂

It seems that firefox doesn't support mkv files https://bugzilla.mozilla.org/show_bug.cgi?id=1422891, and that's what OBS took the recording in. You can right click on it to download and open with some other player though. I'll try to record it in other format in future (hopefully just .rzx 🙂)

As I was afraid, the first attempt with the dynamic programming didn't work that well. At every moment I kepts 100'000'000 states with the furthest progress, but given how many variants to collect objects are, that was not so simple. The resulting route turns out to be too greedy (first collect whatever is easy and then travel across entire map again to collect the rest). While I'm working on the improvements, here is the video of the walkthrough for MaxLives+Warpless category (at 25fps). I'm not attaching it here as the file is 50MB in size, not sure whether that's a good use of forum's space. Link to the video: http://crem.xyz/jsw_warpless_maxlives.html It's not a proper walkthrough, it's actually sequence of in-room routes spliced together. That's why timer number of lives and collected items restore between rooms, and Willy jumping state during the room transition is sometimes incorrect.

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.

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:

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). Peek_2021-05-07_18-01.mp4 Peek_2021-05-08_09-00.mp4 Peek_2021-05-08_09-36.mp4 Peek_2021-05-08_09-14.mp4 Peek_2021-05-08_09-43.mp4 Peek_2021-05-08_11-23.mp4 Peek_2021-05-08_13-32.mp4

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.

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).

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! On the roof.mp4

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.

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).

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...

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?

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).

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.

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.

If we think we want to save the site, I think it makes sense to contact the site owner first and ask for the dump of database, rather than trying to scrape it. That's both easier, and it would be nice to get agreement/approval from them. What to do with that data is another question. I could surely help with generating a static website from that data (for example publishing it to GitHub as Jekyll site so be available at through github.io). Also if we have any community-maintained Willy-themed wiki, I can automatically fill content there. As for having a separate full-featured dynamic site where people are able to add new content, I don't think I'd have enough enthusiasm to work on it.

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).

Today while doing some research on JSW, I've got the link to darnkitty.com in search engine. This site apparently just went permanently down, but still can be accessed through google cache (example, won't work for long). It seems that it has per-room trivia for JSW/MM which is quite unique and there's no other place where information like this can be found. The question is, should we somehow preserve that information? If someone knows who the owner of the site is, maybe contact them and ask to share the information? Alternatively, it may be possible to recover at least something from archive.org and (for a few days) Google cache?

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! jsw_init.mp4

Thanks, it was indeed a bug on my side. When I saved/restored states in Manic Miner, I saved some memory locations and all registers. For JSW, I thought that there's no need to store registers as when frame starts (pc=#89ad), none of registers are expected to have meaningful value. But actually the PC itself may be wrong. If during the previous attempt Willy hit a guardian (and breakpoint at #8c01), it's not enough to just restore the memory, PC has to be restored too. I'm not sure whether any other register matters at that point (SP maybe?), but just to be on the safe side, I'll include all registers into the state.

Quick question. I have a breakpoint at address #8C01, and generate various playthroughs in JSW, and it sometimes happens that number of lives decreases (and guardian cycles seemingly reset) without hitting that breakpoint. I'm fairly sure it's bug in my code, but just checking, maybe I missed something in JSW code... Could you think of some ways of this happening in JSW? (number of lives decreases without hitting breakpoint at #8C01). That happens in the very first room, "The bathroom". Thanks!

I didn't write anything for Z80 in C (actually, neither I did in assembler), but my understanding that C compiler produces decently good code as long as you are aware about Z80's limitations: There are no good array indexing instructions in Z80, so accessing e.g. iterating arrays by index should be avoided (the only exception is when array element size is 1 byte and array index is a signed single-byte value). Instead it's better to e.g. compute end pointer and do pointer comparison. Function arguments are passed through registers, so recursion should be avoided. Sorry for another redirect, but I believe this forum should have much more experience in using C with Z80 CPU.

Hi! I've noticed that there are two small things about the website which while not not extremely important, cause minor annoyances, which I think would be easy to fix. 1. Favicon This site happens not to have a favicon. That makes it sometimes hard to find among tabs of other websites. 2. Https I don't care about the security aspect of it, but more and more browsers start to shame http only sites. E.g. it took me like 30 seconds to convince Vivaldi browser to send my password over http when I tried to log in. Also there is a rumour, that doing that would put you slightly higher in search engine ranking. With appearing of https://letsencrypt.org, setting up https is both free and (relatively) simple (using their tool called certbot, which in most cases does everything automatically). There is even easier way which don't require managing/renewing the certificate (but would require switching to use cloudflare nameservers though, so maybe not easier): set up cloudflare layer (also free).

It is possible that two versions require different route for the Amoebatrons' Revenge. The route for the SP version is here: