Improving routing with informatics
5 years ago
Rhône-Alpes, France

Have algorithms ever been applied in Odyssey ? Using graphs we can use algorithms to find the apparently quicker route for every kingdom. Has this ever been done ? I doubt it would be efficient anyway but it could lead to surprising results I guess.

Denver, CO, USA

In theory, something like this could be done, but it's a bit difficult to even construct what such a system could be. Depending on what direction (i.e. what other moon) from which you're approaching Moon A, you could have several different movement options, each taking a different amount of time. It is very hard to get a handle on what timing the optimal movement has, so trying to compare "optimal" movement times to each other (if we've timed them correctly) can be very difficult.

Add on top of this just the mathematical complexity of what is essentially a Traveling Salesman problem (for many, many different moon options, as well), and you've got yourself quite the task... I don't expect that anyone will tackle this for quite some time.

Rmac524 likes this
Rhône-Alpes, France

If you remove the too heavy lines the complexity gets way better, and if someone does convenient movement between all the pairs of moons the graph can be constructed

England

For your algorithm to work you would need to know the time from each moon to each other moon, because the route back may not take the same time. there are 89 moons in sand in total... so you'd need 4005 individual times (maybe more or less, my maths could very easily be wrong), averages on those times including optimal times as difficulty of execution can become an issue. then from those 4005 times you construct your travellign salesman problem. 89! is more than 10^100 or more than googol, so you'd need to find a way to cut down that considerably - at which point you are essentially doing it by hand, which i believe is waht's already been done

Yoyoshi and IlluminaTea like this
United States

Of course, some moon combos are outrageous and don't even need to be timed. No route would have you do Knucklotec's fight and then do the Harriet fight, to use an example in Sand. Also, is that 89 moons accounting for two multimoons or not?

United States

You'd need 89 permute 2 or 7832 times for all of sand kingdom, or 15664 times for both average and optimal. I think you could manually prune a lot of these, though you won't be guaranteed correctness. You don't have to search through 89! though, closer to 2^89 using TSP algorithms (still a huge number...).

Another problem you might have to deal with is connecting paths not being independent. Think about how the bird flies around sand kingdom. The time it takes to travel to the bird changes based on your path so far. You also have to consider coin collecting, which can alter the time between moons later on (e.g. you collect coins between moon 1-2, and skip it between 4-5, which reduces the time between 4-5).

Even assuming complete independence, timing almost 8000 moon routes sounds incredibly tedious.

United States

this is why we need a good TAS

England

@hockey0120

we don't need a TAS. first off there isn't a usable switch emulator, and even then it would take longer to make a TAS then it would just to time it with human controlling. it takes upwards of 1 minute of effort to make 1s of a TAS

Rmac524 likes this
Germany

Chowser, those approx. 1000 numbers are the input. Getting the best route out of them is an NP-complete problem known as a variation of the Travelling Salesman problem

Île-de-France, France

@IwerSonsch It seems even more complex because time between A to B is different from B to A