I came up with this question playing the online game "Hades Star". In this game you have a 2D star system filled with some planets and need to deliver shipments from one planet to others. Ships always travel in a straight line. Depending on how far away the planets are it takes more time and more ressources (hydrogen) to deliver, so chosing short ways is always better.

You can, however, build a tunnel (in fact, multiple tunnels but let's forget that for a second) consisting of two arbitrary points (entrances) in your coordinate system to allow your ships to "teleport" from one point to the other, using no time and no hydrogen.

The question is simple: is there a way to find the best tunnel entrances that make your ships save the most time and hydro?

​

For only two planets this is trivial: position the entrances as close as possible to both planets. But with more planets this gets really difficult.

​

My first attempts is the following:

1. calculate the distance from each planet to each other (omitting duplicate routes)
2. sum up all calculated distances
3. now chose two points for the tunnel entrances
4. calculate all distances again but for each chose the shorter one: using the tunnel or going the straight way
5. sum up and compair to the prior number

​

the problem remains in step 3. You could just try ALL different positions but this is a BIG number. Also, if you want to place more than one tunnel it gets really painful

​

I'm excited to hear some ideas to this problem :)

​

EDIT: although it might be affordable for high level players, in this problem we will assume that we can NOT afford a lot of tunnels connecting every planet with each other. I would be glad if we just find a solution for ONE tunnel