3D grid distance calculator

[Tricky Majik]

Hi
Not sure if this is useful for anyone else, or if indeed something similar has previously been posted, but just in case...

During my exploration travels, I found it useful to calculate the distance between two sets of 3 dimensional coordinates on the galactic map. The Excel formula for this is as follows:

=SQRT(ABS(X2-X1)^2+ABS(Y2-Y1)^2+ABS(Z2-Z1)^2)

Where X1, Y1, Z1 are the x,y,z coordinates shown on the galactic map of the first location
Where X2, Y2, Z2 are the x,y,z coordinates shown on the galactic map of the second location

So, for example, if you were trying to calculate the distance between the Earth Like at BLEIA EOHN EM-M D7-0 (located at -1007, -1021, 2167) and Robigo (located at -303, 7, -314), the formula above calculates the distance to be 2776 LY, which is correct.

I was trying to work out a formula for plotting the most efficient route between multiple locations, but I ran out of maths! I believe this is often called the "travelling salesman problem" - perhaps it should be the "exploring CMDR taking in sights problem" in Elite!

 

[dognosh]

Hi
Not sure if this is useful for anyone else, or if indeed something similar has previously been posted, but just in case...

During my exploration travels, I found it useful to calculate the distance between two sets of 3 dimensional coordinates on the galactic map. The Excel formula for this is as follows:

=SQRT(ABS(X2-X1)^2+ABS(Y2-Y1)^2+ABS(Z2-Z1)^2)

Where X1, Y1, Z1 are the x,y,z coordinates shown on the galactic map of the first location
Where X2, Y2, Z2 are the x,y,z coordinates shown on the galactic map of the second location

So, for example, if you were trying to calculate the distance between the Earth Like at BLEIA EOHN EM-M D7-0 (located at -1007, -1021, 2167) and Robigo (located at -303, 7, -314), the formula above calculates the distance to be 2776 LY, which is correct.

I was trying to work out a formula for plotting the most efficient route between multiple locations, but I ran out of maths! I believe this is often called the "travelling salesman problem" - perhaps it should be the "exploring CMDR taking in sights problem" in Elite!

I did mention something similar in the prospecting thread after I found this http://www.calculatorsoup.com/calculators/geometry-solids/distance-two-points.php
P.s. ABS is not needed, as squaring any number is always positive

 

[Cmdr Frawd Digger]

Hi
Not sure if this is useful for anyone else, or if indeed something similar has previously been posted, but just in case...

During my exploration travels, I found it useful to calculate the distance between two sets of 3 dimensional coordinates on the galactic map. The Excel formula for this is as follows:

=SQRT(ABS(X2-X1)^2+ABS(Y2-Y1)^2+ABS(Z2-Z1)^2)

Where X1, Y1, Z1 are the x,y,z coordinates shown on the galactic map of the first location
Where X2, Y2, Z2 are the x,y,z coordinates shown on the galactic map of the second location

So, for example, if you were trying to calculate the distance between the Earth Like at BLEIA EOHN EM-M D7-0 (located at -1007, -1021, 2167) and Robigo (located at -303, 7, -314), the formula above calculates the distance to be 2776 LY, which is correct.

I was trying to work out a formula for plotting the most efficient route between multiple locations, but I ran out of maths! I believe this is often called the "travelling salesman problem" - perhaps it should be the "exploring CMDR taking in sights problem" in Elite!

Excellent ...thanks for that Cmdr. Good to know.

+1 rep

Frawd

 

[SvennoJ]

Although the game lists it nowadays after exploring a planet, another useful formula is to find out the gravity of a planet beforehand:

It boils down to g = earth masses * 40.68 / (radius * radius)
Where the radius is in MM, for example Venus = 0.055 earth masses, radius 2,440km -> g = 0.055 * 40.68 / (2.44^2) = 0.38G
That could safe you a trip if you're unsure if you want to attempt a landing somewhere.

And if you want to know what the gravity on the surface of a star is:
g = Sol masses * 28.02 / (SolRadius * SolRadius)
Simply use the numbers in the stat screen. On the surface of the sun you would experience just over 28g.
For what you should experience while stationary in fuel scooping range:
g = Sol masses * 151 / (ls * ls)
ls = distance in light seconds. Currently I'm experiencing over 17g while stationary fuel scooping around a class M star. I should be falling like a brick if I drop out of super cruise...
Then again the game lets you sit right in front of a black hole Gravity is restricted to land-able planets.

 

[Zieman]

Although the game lists it nowadays after exploring a planet, another useful formula is to find out the gravity of a planet beforehand:

It boils down to g = earth masses * 40.68 / (radius * radius)
Where the radius is in MM, for example Venus = 0.055 earth masses, radius 2,440km -> g = 0.055 * 40.68 / (2.44^2) = 0.38G
That could safe you a trip if you're unsure if you want to attempt a landing somewhere.

Umm, Venus is 0.815 Earth masses, radius 6.05 Mm, resulting in ~0.9 G...

 

[AnnuverScotinExile]

Good old Pythagoras.

 

[AJW]

Good old Pythagoras.

Did Pythagoras (who apparently got the theorem from the Babylonians) ever apply it to three dimensions?

 

[AnnuverScotinExile]

Did Pythagoras (who apparently got the theorem from the Babylonians) ever apply it to three dimensions?

No idea, but he didn't need to. The 3D problem can easily be broken down into 2 2D problems, where the result from the first gets fed into the second.

 

[Wedgetail]

No idea, but he didn't need to. The 3D problem can easily be broken down into 2 2D problems, where the result from the first gets fed into the second.

and can be further extended to any number of dimensions you like, (i.e. d6 = sqrt[u^2 + v^2 + w^2 + x^2 + y^2 + z^2])

 

[Ziljan]

.
I was trying to work out a formula for plotting the most efficient route between multiple locations, but I ran out of maths! I believe this is often called the "travelling salesman problem" - perhaps it should be the "exploring CMDR taking in sights problem" in Elite!

This problem is easily solved by forcing it to become deterministic by having a pilot choose way points in a preferred order. Then we just need to use normal galmap pathing calculator between any TWO points in 1000 LY increments.

Bingo bango bongo. Problem solved.

Now the only major annoyance would be in saving routes to the client side in a way so that they can be deviated from without being forced to recalculate more than 1000 LY of the remaining route.

 

[SvennoJ]

Umm, Venus is 0.815 Earth masses, radius 6.05 Mm, resulting in ~0.9 G...

Oops, my numbers were correct, wrong planet name I meant Mercury.
But yes Venus is listed at 0.91g on the system map.

 

[AnnuverScotinExile]

This problem is easily solved by forcing it to become deterministic by having a pilot choose way points in a preferred order. Then we just need to use normal galmap pathing calculator between any TWO points in 1000 LY increments.

Bingo bango bongo. Problem solved.

Now the only major annoyance would be in saving routes to the client side in a way so that they can be deviated from without being forced to recalculate more than 1000 LY of the remaining route.

Not really. The travelling salesman problem would be wanting to know the sequence to visit all the objects in a system to minimise the travel between them. Except they are moving, which the salesman did not have to deal with (though with FTL travel that probably doesn't really matter in E: D).

 

[virosh]

Hi
Not sure if this is useful for anyone else, or if indeed something similar has previously been posted, but just in case...

During my exploration travels, I found it useful to calculate the distance between two sets of 3 dimensional coordinates on the galactic map. The Excel formula for this is as follows:

=SQRT(ABS(X2-X1)^2+ABS(Y2-Y1)^2+ABS(Z2-Z1)^2)

Where X1, Y1, Z1 are the x,y,z coordinates shown on the galactic map of the first location
Where X2, Y2, Z2 are the x,y,z coordinates shown on the galactic map of the second location

So, for example, if you were trying to calculate the distance between the Earth Like at BLEIA EOHN EM-M D7-0 (located at -1007, -1021, 2167) and Robigo (located at -303, 7, -314), the formula above calculates the distance to be 2776 LY, which is correct.

I was trying to work out a formula for plotting the most efficient route between multiple locations, but I ran out of maths! I believe this is often called the "travelling salesman problem" - perhaps it should be the "exploring CMDR taking in sights problem" in Elite!

If you search inside Nutter's Explorer guide you will find the same formula shared by @AnnuverScotinExile.
And yeah, it's working and it's pretty useful sometimes.
I even wrote a small calculator for my personal use - Galaxy Map Distance Calculator.

 

[Ziljan]

Not really. The travelling salesman problem would be wanting to know the sequence to visit all the objects in a system to minimise the travel between them. Except they are moving, which the salesman did not have to deal with (though with FTL travel that probably doesn't really matter in E: D).

The human brain is excellent at solving seemingly NP problems simply by connecting dots that don't have any obviously quantifiable least path or least Hamiltonian.

We can do this because unlike a computer we have emotions and can use them to weed through "unimportant" results.

This is why I am suggesting that we outsource the problem to selectively ordered waypoints rather than connecting dots in a more formalized recursive method. As long as the number of way points is reasonably small, say under 50, a human could easily play connect the dots and come up with an approximate shortest path just by eyeballing it. Even when a machine might get stuck comparing near infinite possible paths. The brain is a truly remarkable machine, able to parse massive amounts of data and arrive at (often overly) simple conclusions.

 

[AnnuverScotinExile]

The human brain is excellent at solving seemingly NP problems simply by connecting dots that don't have any obviously quantifiable least path or least Hamiltonian.

We can do this because unlike a computer we have emotions and can use them to weed through "unimportant" results.

This is why I am suggesting that we outsource the problem to selectively ordered waypoints rather than connecting dots in a more formalized recursive method. As long as the number of way points is reasonably small, say under 50, a human could easily play connect the dots and come up with an approximate shortest path just by eyeballing it. Even when a machine might get stuck comparing near infinite possible paths. The brain is a truly remarkable machine, able to parse massive amounts of data and arrive at (often overly) simple conclusions.

... but that is still not the travelling salesman problem!

 

[Allitnil]

The human brain is excellent at solving seemingly NP problems simply by connecting dots that don't have any obviously quantifiable least path or least Hamiltonian.

We can do this because unlike a computer we have emotions and can use them to weed through "unimportant" results.

This is why I am suggesting that we outsource the problem to selectively ordered waypoints rather than connecting dots in a more formalized recursive method. As long as the number of way points is reasonably small, say under 50, a human could easily play connect the dots and come up with an approximate shortest path just by eyeballing it. Even when a machine might get stuck comparing near infinite possible paths. The brain is a truly remarkable machine, able to parse massive amounts of data and arrive at (often overly) simple conclusions.

I think you are wholly underestimating the complexity, and probably even the basic problem. Optimising the Travelling Salesman problem is well beyond your sort of suck it & see solution which is why it exists in the first place - humans are crap at it! Modern computing power is such that it is relatively trivial now to solve via pure brute force (*). Back in the early 90s I was involved in this when I worked on the main British Railways journey planner software. The solution we adopted was relatively simple (way less complex than modern sat navs which have much more computing power than was available to us with mere mainframes at our disposal ) but it didn't rely on brute force and gave significantly better solutions than all but the most experienced of booking clerks. As a testament to its longevity, it is still in regular use today.

* - a simple brute force solution to the 3D travelling salesman problem would take many magnitudes of less time to implement than that required to collect the 3D co-ordinates of the relevant systems in Elite.

 

[BadBilly]

CMDR Billy

Hi
Not sure if this is useful for anyone else, or if indeed something similar has previously been posted, but just in case...

During my exploration travels, I found it useful to calculate the distance between two sets of 3 dimensional coordinates on the galactic map. The Excel formula for this is as follows:

=SQRT(ABS(X2-X1)^2+ABS(Y2-Y1)^2+ABS(Z2-Z1)^2)

Where X1, Y1, Z1 are the x,y,z coordinates shown on the galactic map of the first location
Where X2, Y2, Z2 are the x,y,z coordinates shown on the galactic map of the second location

So, for example, if you were trying to calculate the distance between the Earth Like at BLEIA EOHN EM-M D7-0 (located at -1007, -1021, 2167) and Robigo (located at -303, 7, -314), the formula above calculates the distance to be 2776 LY, which is correct.

I was trying to work out a formula for plotting the most efficient route between multiple locations, but I ran out of maths! I believe this is often called the "travelling salesman problem" - perhaps it should be the "exploring CMDR taking in sights problem" in Elite!

I've just started exploration side of ED and I'm sure that will come in useful. But does anyone know how this could be improved to calculate 'waypoint' coordinates under 1000ly between start system and destination system?...