I'm looking to find the optimal route for a game. Solving it is not as simple as something like the travelling salesman problem, where you just have to find the shortest route through multiple stops. Only a few areas are acessible from any given area, you don't have to visit every area and some areas have more stuff than others. The general concept is you have to collect any 32 out of 64 things. However, most things are made out of 8 smaller things. So, for example, an area might have 1 and 5 eighths out of the 32 things that you need. And of course, different areas take different times to traverse, etc.

I have no experience in coding, and when I search for something like this I can't find anything specific or complex enough to help me. If I timed how long it took to get from one place to another to another, is there some program i could feed the data to? Any other suggestions? Thanks

I don't know any specific program/software tools for this. But the first thing that came to my mind when reading 'Feed data to', I would say Excel / Google Spreadsheet.

I've always used google docs to keep track of notes and the route I believe to be the fastest. I've never heard of any specific "routing software"

I recommend watching this video by ThaRixer / @Ricky, where he talks about the complexity of the speedrunning elements, including routing:

For simple or short games routing can be easy. But if you take bigger games like Fez, where:

• You have to take a certain number of collectibles, but not all of them
• The game is not linear, so you can go to many places in any order
• Sections can be shorter or longer than others, but the time to reach them should also be noted
• Taking note of who is playing - a TAS that can do everything perfectly, or a human that might not be able to do some stuff

Things can get very messy. And no computer program can solve this problem for you automatically in a plausible amount of time. There are people who dedicate themselves to routing a certain game. But even after years of the community working on routing, the popular route might still not be optimal.

Also: [quote]Solving it is not as simple as something like the travelling salesman problem[/quote] This is exactly the travelling salesman problem, which is impossible to solve in reasonable amount of time with current technology.

(Sorry about double post, apparently we have a limit of 1000 characters now)

It doesn't seem implausible oreo. Most rooms in fez have a direction to them, and they mostly have bits along the way rather than out of the way. When they are out of the way, I time them both straight through and taking a detour for bits. I also assume generally mistake-less human play as reference. Considering the amount of operations a computer can do in a second, I cant see this taking too long. I understand the possibilities expand exponentially, but most ways are dead ends, and so they dont. I dont think the problem is raw computing power, rather idk how to code something so specific so I was wondering if there existed a tool for the circumstance or if there was an easy way to code it

And the travelling salesman problem is easily solvable as long as the amount of nodes isn't crazy. I can be certain the map for the game wouldn't trouble it

This isn't quite TSP because you can select which things to visit, but you might be able to set up some sort of Integer Linear Program to solve it (just form a graph of every Thing To Be collected and every doorway, so you can time Item to Item and Item to Doorway in a room. Then reduce it to a complete weighted graph of just the Items. Set a function Value(vertex) for how much progress that item gives you (1/8 for most). Set constraints such that the edges to be included in your route form a path, and you get at least 32 value total. Making it a continuous path instead of possibly some multiple paths is the hard part, not sure what constraints that would require.

Normally, games will have additional restraints about where you can go and when that makes it so that routing is a largely human endeavor and programs aren't necessary, especially given how hard it would be to set this all up. I'm not an expert on integer programming either so even if this would work, idk if it's practical or not.

@MechanicalSnail That still wouldn't work because a 1/8th part doesn't really count as 1/8th unless you get the other 7/8ths.

My suggestion (if you're still looking for it since this thread is 2 weeks old) is two fold. One, start piece by piece based on what's available to you at each stage. Figure out what's the best things to get before the next stage unlocks. If parts from the first area are still faster than parts from the second area, add those in as well. Two, get at least a theory route down that seems reasonably fast. Figure out how long each item takes to get (or how long it takes to get all the parts of an item). Compare that to how long it takes to get items that aren't in the route and see if it would be faster to swap different ones in.

This all reminds me of those projects where people train deep learning AIs on Mario games

neat stuff

This is a bit off the point, but I thought like oreo that the travelling salesman problem isn't 'easy', in fact it is known for being currently impossible to solve perfectly with current technologies - sure someone could make a program that found a slightly better solution than a human could, but that time would be better spent practising the route.

@MrMonkey049 That is not true, it is not impossible to solve perfectly. Rather exact methods take very very long for a high number of variables "n" (e.g. scaling with n! or n² * 2^n). This makes it very hard for common home-PCs to solve such problems, unless you have a supercomputer at home.

Ok fair, impossible to solve exactly in a timely manner / without doing trial and error for nearly every possible option.

But the point still stands, finding the optimal route by computer ain't gonna happen any time soon sadly