Automated generation of Jet Set Willy speedrun/walkthrough

[RuffledBricks]

I think if @crem's gonna spend that much time and effort on it then he should at least start a Patreon account. 😄

[jetsetdanny]

My understanding is that crem is doing it because he wants to and I hope he's enjoying it (just as one can enjoy struggling to solve a forbiddingly difficult and frustrating JSW game, like one of Dr. Broad's extreme challenges 😉).

For my part, I can say I'm enjoying following his updates and learning about the developments of the situation. Certainly, I would not encourage crem to continue his quest just for the sake of this enjoyment of mine, but I do trust he's enjoying it, too 🙂 . And the results, as Ian mentioned, may be useful by revealing manoeuvres and timinigs that human players have not come up with so far 👍.

[Spider]

I was going to say I do have some CPU power but I'm not sure its going to help as its not that "modern" (HP XW6600 workstation as my desktop) but I tend to leave my computer on most of the time anyway, mind you having said that if it is running high CPU usage it will start to eat electricity.

Spoiler

About 5 years ago, I tried running a HP DL rack server (the one with two PSU's with a different non IEC connector, 4 Xeons inside. I was highly disturbed to connect an ammeter to find it was happy to eat almost a KW of power at idle (OS running nothing else)

 

[crem]

23 hours ago, MtM said:

Don't take this the wrong way Crem - but is it worth the effort? Sounds like a lot of time and work.

It indeed happens sometimes that hobby project suddenly starts to feel like a second job. At some moment you realize that you "have to" do something, and that instantly kills all the motivation. That's why I'd like to say that it's very possible that I'll just drop the idea or suddenly pause it for years. Having this option actually makes it less likely to do so.

But the JSW route finding project is currently nowhere near feeling like an obligation. I enjoy the process of solving it a lot, and also like the fact that the results turn out to be useful. Actually, the result itself is not that important to me (i.e. I'm not that curious myself what is the fastest way to finish the game, but I like that other people are).

I also try to structure it that way that I'm learning something useful for the next projects, so that it doesn't feel like I'm wasting time for pure joy. 🙂

[crem]

21 hours ago, Spider said:

I was going to say I do have some CPU power but I'm not sure its going to help as its not that "modern" (HP XW6600 workstation as my desktop) but I tend to leave my computer on most of the time anyway, mind you having said that if it is running high CPU usage it will start to eat electricity.

  Reveal hidden contents

About 5 years ago, I tried running a HP DL rack server (the one with two PSU's with a different non IEC connector, 4 Xeons inside. I was highly disturbed to connect an ammeter to find it was happy to eat almost a KW of power at idle (OS running nothing else)

 

Thanks for the offer! Currently most of the tasks I run are pretty short (6 hours or so), and I think it will take longer than that to set it up to run on a different computer, especially it the operating system is not Linux.

I may want to regenerate all the routes without combining entrances into "portals", as it caused more problems than good so far. If I'll do that, this will take 2 weeks on my computer, and sharing the efforts will help to cut the time.

[crem]

1. I implemented the tweak I mentioned but it didn't help much.

I added more fine-grained progress metric for the algorithm than just number of items collected. While it did help a bit, the route it finds are still worse than human-generated ones.

I've streamed some of those attempts here: https://www.twitch.tv/mooskagh/videos, mostly in Maxlives and Any% categories.

At this point I stop trying to improve this approach and will switch to other ones, which will take some time.

 

2. For realtime walkthrough, I'll need to regenerate all the routes.

I realized that the shortest in-room route in terms of number of frames doesn't necessary mean it's the shortest in real time. This is largely due to sound when jumping, but I think that there may be also a tiny difference whether Willy stays or walks. And in the generated routes, Willy tended to avoid being idle.

I considered regenerating the routes anyway. This should take 2 weeks on my computer, but I'm trying to find other places to run it as it's someone inconvenient and also it heats up my room to 25℃.

[TobyLobster]

In case it is useful, this looks like it's a pretty industrial strength solver for Travelling Salesman and related problems, written in C http://www.math.uwaterloo.ca/tsp/concorde/index.html

[crem]

12 hours ago, TobyLobster said:

In case it is useful, this looks like it's a pretty industrial strength solver for Travelling Salesman and related problems, written in C http://www.math.uwaterloo.ca/tsp/concorde/index.html

I considered it, but the problem is that routing is not really a travelling salesman problem (it's easy to "reduce" TSP to what is needed for JSW routing, but in opposite direction it's not so):

• In JSW, "visit" happens on edges rather than vertices.
  If this along would be a problem, it could be worked around by inserting a fake vertex inside the edge with item collection.
• There are several edges (in-room routes) that have the same label (collect the same item).
  In TSP it doesn't matter from which edge you came to a vertex, all outgoing edges still available and have the same cost.

[crem]

Random useless graph. 🙂

[crem]

This is even more arbitrary. 🙂