Discussion What is the most efficient way to crowdsource the 3D system coordinates

wolverine2710

Tutorial & Guide Writer
wolverine2710
Announcement: Saturday the 23th of January 2016.
Brilliant news: On the 5th of January 2016, Zac Antonaci -Head of Community Management of FD- wrote in the "Open Letter to Frontier Developments" thread that usage of the iPhone companion app api is LEGAL. Source. Which makes the usage of tools which use this api like EDMC, EDAPI and EDCE LEGAL. Other great news: On the 18th of January 2016, Brett C. -Community Assistant/Manager of FD- created the "Elite Dangerous->Gameplay and Features->Player Tools & API Development" subforum. Its an excellent place for checking out new and existing tools. The EDCodex thread is also there.


Current status: Tuesday 21th of October 2014.The crowd source project has been very successful. At the moment we have coordinates for 573 star systems which are inside the pill of SB2. Twelve outside the pill. The newsletter mentioned there are 570 systems. It turns out there are a few more. Michael Brookes was very helpful and patient and has answered all my PM's. But it was not possible for him to provide us with a complete list of system names - without coordinates. Its entirely possible that in the next days more systems will be found - and mapped. Volunteers are still very much welcomed to the project. More info about this beneath in the spoiler tag "How to obtain the remaining coordinates for SB2"

Why do navigation route planners and trading tools need star system coordinates?
Currently there a multiple navigation route planners out there. Some take fuel into consideration some don't. Some show a map of the universe and the suggested route in it. Some show you where you jump to if you have specific ship/equipment, ie you know how big your island is. Of course trade route planners have also navigation planners inside them. What they all have in common is the need for system coordinates. These can then by used by all kind of graph algorithm like Shortest Path -to calculate a certain route. Two examples of that are Dijkstra's algorithm and A* search.
Why is a crowd source effort to obtain the star system coordinates necessary?
For SB1 commander wtbw extracted the system coordinates out of ED and with permission of Michael Brookes he published them. All navigation planners use them. With the changed policy of TD this kind of tools are no longer permitted. I contacted Michael Brookes and he could give the community a list of 307 systems.

With the start of SB1 the system coordinates were unknown and a crowd source effort was undertaken by some BPC users to get the data. Basically any one in a longe range ship went to a system, then used the Galaxy Map to determine the distance to all other systems. That way of graph was being constructed. This approach is time consuming. In the end we ended up with a graph which had all the connections. On this Dijkstra/A* search shortest path could operate. We still had no 3D coordinates in Euclidean space but for SP that doesn't matter. Now with 570 systems this task will be much bigger.
Is it possible to make crowd sourcing more effective then with Standard Beta 1?
So the question is, can be this crowd sourcing be done more efficiently. Fact, we have:
1) All 3D coordinates for SB1.
2) The GM which can be used to determine the location in 3D space relative to the 55 3D coordinates. Ie under/above,right,left etc.

Can the above perhaps be used to calculate the 3D-coordinates for the new star systems. Take new system M. Instead of determining all distances from M to the other systems we perhaps only need to take X distances and then the 3D-coordinates for M can be calculated. I lack the math skills to determining that. Perhaps some other commanders can determine if this can be done.
List of tools and programs created for the crowd source project.
Not all tools created by commanders have been made public.
Before I give a list of tools I have to give credit to Codec. He was the first person who published a spreadsheet with input form. It also calculates/shows coordinates. Atm most crowd source data is coming from other tools.

The tools are listed by commander name - in alphabetic order.
  1. Biteketkergetek. Verifier tool. Verifies calculated 3D coordinates by crowd source project. Takes 1/32LY grid into account. Sourcecode.
  2. Chromatix.Generates 3D map with routes based on fuel-efficiency. Thread "Complete Maps of the Bubble ". Sourcecode.
  3. CMDR Generic EventHandler. Trilateration solution in C#.
  4. Harbinger. Web based. Website
  5. JesusFreke. Verifier tool. Verifies calculated 3D coordinates by crowd source project. Takes 1/32LY grid into account. . sourcecode.
  6. RedWizzard. Web based. Runs locally in your browser.Github url. Download as zip.
  7. Snuble. Webbased tool. Shows bubble/pill split up in grids. Useful to communicate in which part of the bubble a volunteer is collecting distances. Website. Sbuble also created a tool using the Galaxy Map to determining coordinates of a star system. His method and explanation can be found here.
  8. TornSoul. Web based tool. Has a web-api for retrieving systems and distances. EDStarCoordinator. The website also has support for TGC (The Great Collector). TGC currently calculates 3D coordinates, stores them and also stores distances. It goal is to have all static data in it.
  9. TunaMage. Google spreadsheet. Can be download as an .xlsx file for Excel. System Plotter.
Which tool is best?
I won't answer that one here as they all are (technically) beautiful and suited for the crowd source effort. Try them out. You can ask the commanders in the forum which tool they like the most - for a certain task.
List of third party tools using star systems (coordinates).
The tools are listed by commander name - in alphabetic order.

Athan. Stardata. From the author: "The tool is using real star data and the information I could find on transforming that to the ED co-ordinate system. It's absolutely not based on the actual ED stars at all. Thus it will be missing every single procedurally generated star, and it's also at least missing all the WISE ones as well. I highlighted it here purely as a helper if people are wondering "hmmm, I wonder which ED star such and such real star is based on". Website
Mod authors. How to get the latest up to date coordinates?
I consider that (at least for the moment) THE reference for coordinates for ED is the tool created by RedWizzard. It consists of 4 html files (basically near 100% Javascript) which performs miscellaneous tasks. The git repository can be found here. Recommended by kfsone of Trade Dangerous and used by me is SourceTree - a windows git client. RW's tool runs locally. The data is in file system.json which can be easily parsed. The system.html file has a button "generate CSV". That format is the same as used by Trade Dangerous.

The reference for Trade Dangerous is maintained by Smacker - its the file data/systems.csv. Smacker syncs with RedWizzards list. Currently everyday before RW goes asleep he updates his git repository with everything found out that day here in this thread -coordinates wise. Smacker then syncs with that. He also maintains a Google spreadsheet.

In the future a simple url will be made available where the coordinates can directly be downloaded from - in a number of formats.
How to obtain the remaining coordinates for SB2?
Todo
How to make crowd sourcing feasible and easy in the future?
Aside from the technical challenge ONE thing became absolutely clear. How to organize things in such a way that volunteers don't input data for systems which already have been done and double check results of different tools. One word: PITA. Quite a few tools aside from outputting coordinates also give the distances which were input. This can be used by other tools to double check results. A few commanders have volunteered to provide web space and create programs so that the in the end the output of all programs can be transferred to one central place where also the coordinates list will be shown. This is WIP and will be really started ones we get the data for all SB2 systems.
Credits aka my eternal thanks.
A humungous amount of work has been done by commanders who volunteered. Multiple commanders have created tools to calculate the 3D coordinates. Good reference points were found. Quite a few different approaches exist, which all return the same coordinates. Distances measured by volunteers where checked by commanders. Output of programs were double checked by the other tools. Issues were found AND solved. LOTS and lots of blood sweat and tears but above all love and dedication went into this project.

I want to thank the following commanders. TODO. Because I want to do this right BUT the list is long.

For those commanders who want to develop tools to calculate coordinates there are some pitfalls because of the way FD stores/calculates the coordinates - in for example the Procedural Generated engine. This aside from the fact that all coordinates lay on a 1/32 LY grid. Commander TornSoul has recapped all the things found here.

Please do NOT turn this into another pro vs contra third party (trading) tools thread. Those discussions for me are the equivalent of the trenches war of WWI. Nobody makes progress. If you want to discuss it, the perfect place is "Direct question for Michael Brookes". I hope and trust you respect my wishes.

Original version OP.
Atm there a multiple navigation planners out there. Some take fuel into consideration some don't. Some show a map of the universe and the suggested route in it. Some show you where you jump to if you have specific ship/equipment, ie you know how big your island is. Of course trade route planners have also navigation planners inside them. What they all have in common is the need for system coordinates. These can then by used by all kind of graph algorithm like Shortest Path -to calculate a certain route. Two examples of that are Dijkstra's algorithm and A* search.

For SB1 wtbw extracted the system coordinates out of ED and with permission of Michael Brookes he published them. All navigation planners use them. With the changed policy of TD this kind of tools are no longer permitted. Now that SB2 is due for tomorrow those coordinates will be missed. When the FD policy changed the author of "Fansite: CMDR.club + Routeplanner discontinued." OP thread TODAY (20140925) wrote the following.
"Hoping to at least get the star data for in beta (an simple export, that should not be too much work) i contacted Michael Brookes (Executive Producer) and asked if they would release the star data for beta2. The response was that there are no such plans.
Click to expand...
So it seems we are on our own.

With the start of SB1 the system coordinates were unknown and a crowd source effort was undertaken by some BPC users to get the data. Basically any one in a longe range ship went to a system, then used the Galaxy Map to determine the distance to all other systems. That way of graph was being constructed. This approach is time consuming. In the end we ended up with a graph which had all the connections. On this Dijkstra/A* search could operate. We still had no 3D coordinates in Euclidean space but for SP that doesn't matter. Now with 500 systems this task will be much bigger.

So the question is, can be this crowd sourcing be done more efficiently. Fact, we have:
1) All 3D coordinates for SB1.
2) The GM which can be used to determine the location in 3D space relative to the 55 3D coordinates. Ie under/above,right,left etc.

Can the above perhaps be used to calculate the 3D-coordinates for the new star systems. Take new system M. Instead of determining all distances from M to the other systems we perhaps only need to take X distances and then the 3D-coordinates for M can be calculated. I lack the math skills to determining that. Perhaps some other commanders can determine if this can be done.

Edit: I hope FD publishes the system coordinates for SB2. I personally don't see any harm in it. Its crucial data and will be discovered by crowd sourcing but it would be time consuming. FD could really help the community with this information.

Edit2: Michael Brookes has been able to supply us with a spreadsheet with 307 out of 570 star systems.

Edit3: Commander Codec has setup a spreadsheet where data can be entered. Spreadsheet and the form for easy entering of distances.

Edit4: Missed this one initially. Codec also has a spreadsheet which contains the 3D-coordinates - new entries can be added. You can find it here. Atm of writing 20141113 it contains 336 entries. Which is the same number of systems I've been able to construct in this file.

Please do NOT turn this into another pro vs contra third party (trading) tools thread. Those discussions for me are the equivalent of the trenches war of WWI. Nobody makes progress. If you want to discuss it, the perfect place is "Direct question for Michael Brookes". .
I hope and trust you respect my wishes.
 
Last edited:

MrBungle

Banned
M
Assuming they don't wipe, I'm more than happy to do the crowdsourcing thing after B2 drops tomorrow. I couldn't help last time around as I was new to the game & had no idea, but I have long range ship at my disposal now & tons of time on my hands ;-))
 

RedWizzard

RedWizzard
wolverine2710 said:
So the question is, can be this crowd sourcing be done more efficiently. Fact, we have:
1) All 3D coordinates for SB1.
2) The GM which can be used to determine the location in 3D space relative to the 55 3D coordinates. Ie under/above,right,left etc.

Can the above perhaps be used to calculate the 3D-coordinates for the new star systems. Take new system M. Instead of determining all distances from M to the other systems we perhaps only need to take X distances and then the 3D-coordinates for M can be calculated. I lack the math skills to determining that. Perhaps some other commanders can determine if this can be done.
Click to expand...
Distance to 4 known systems is sufficient, provided they don't all lie in a plane (which is unlikely).
 

wolverine2710

Tutorial & Guide Writer
wolverine2710
RedWizzard said:
Distance to 4 known systems is sufficient, provided they don't all lie in a plane (which is unlikely).
Click to expand...

Could you eloborate on the 4 distances and the "don't lie all in a plane" part of your post. Very curious in the math behind it.
Some in short: for 500 sytems only 4*500 distances have to be read from the Galaxy Map? That I believe less then what needed to be done for SB1.
 

bamber

B
I would gues if you have a point x and you know that point Y is 10LY away you can draw a circle around x with a radius 10LY point Y must lie on that line

Do the same for point Z at 8LY to point Y and you will have another circle. with 2 intersection points 1 will be correct and one will be wrong

so you need another at point A at 5LY there can now only be 1 intesection point.

so in 2D you need three known points so in 3D you will need 4 points

Its then simulataneous equations which is the hard part but sure with a bit of time could figure it out
 

Codec

Codec
Yes basically go from known systems to unknown systems, and take the points to constrain the positions.

Isn't it 4 points define a sphere, so the centre will be the location of the new system.
 

emacinnes

emacinnes
wolverine2710 said:
Atm there a muliple navigation planners out there. Some take fuel into consideration some don't. Some show a map of the universe and the suggested route in it. Some show you where you jump to if you have specific ship/equipment, ie you know how big your island is. Of course trade route planners have also navigation planners inside them. What they all have in common is the need for system coordinates. These can then by used by all kind of graph algorithm like Shortest Path -to calculat a certain route. Two examples of that are Dyckstra's algorithm and A* search.

For SB1 wtbw extracted the system coordinates out of ED and with permission of Michael Brookes he published them. All navigation planners use them. With the changed policy of TD this kind of tools are no longer permitted. Now that SB2 is due for tomorrow those coordinates will be missed. When the FD policy changed the author of "Fansite: CMDR.club + Routeplanner discontinued." OP thread TODAY (20140925) wrote the following. So it seems we are on our own.

With the start of SB1 the system coordinates were unknown and a crowdsource effort was undertaken by some BPC users to get the data. Basically any one in a longe range ship went to a system, then used the Galaxy Map to determine the distance to all other systemsn. That way of graph was being constructed. This approach is time consuming. In the end we ended up with a graph which had all the connections. On this Dckstra/A* search could operate. We still had no 3D coordinates in Euclidian space but for SP that doesn't matter. Now with 500 systems this task will be much bigger.

So the question is, can be this crowd sourcing be done more efficiently. Fact, we have:
1) All 3D coordinates for SB1.
Click to expand...

I'm hoping we don't need this and the updated B2 galaxy map has workable pathing and full trading tools in place. Perhaps we should give it a day or two to evaluate what's there and then decide on the next course of action.
 

Codec

Codec
I think its a useful thing to do because
  • such a spreadsheet gives you a useful list of things. I use it to tick off all the systems I've been to and the ones I haven't yet.
  • You can note down other things, like black market, distance from star to trading post.
  • I would like to use the mapping tools I've worked on to make a 2-d map I can print out next to me for quick reference.
    No matter how good the beta-2 galaxy map is, it's hard to beat a bit of paper tacked up next to the monitor to glance at and make plans from.
So - I'm up for some mapping.
 

Peter Powers

Peter Powers
wolverine2710 said:
Two examples of that are Dyckstra's algorithm and A* search.
Click to expand...
Dijkstra's, not Dyckstra's ;)

wolverine2710 said:
Edit: I hope FD publishes the system coordinates for SB2. I personally don't see any harm in it. Its crucial data and will de discovered by crowd sourcing but it would be time consuming. FD could really help the community with this information.
Click to expand...
agreed.

also, if someone wants to pick up, i've opensourced the a* implementation i did for cmdr.club a while ago, you can use that lib (simple PHP, can be found at https://github.com/ppetermann/pathfinder, and installed through composer, package: devedge/pathfinder).

regards,
PP
 

Peter Powers

Peter Powers
RedWizzard said:
Distance to 4 known systems is sufficient, provided they don't all lie in a plane (which is unlikely).
Click to expand...

the problem is that you end up with pretty imprecise locations, as the distances you are shown in the client are rounded a lot, and that can make the difference between being able to make the jump or not
 

Peter Powers

Peter Powers
wolverine2710 said:
I'm a Dutchie like Edsger Wybe Dijkstra so yes I should have spelled his name correctly ;-) Although in the English press/publications you often see Dykstra's Algorithm mentioned - without the c that is.
Click to expand...

sorry, but you seem to confuse something ;)
Dykstra's (projection) algorithm is a completely different algorithm - while the name might seem quite close it is about finding a point in the intersection of convex sets. (named after Dykstra, R. L.)

EDIT: meaning both exist, you just pointed at the wrong one.. but thats not an completely uncommon mistake to make ;)
 

wolverine2710

Tutorial & Guide Writer
wolverine2710
Peter Powers said:
the problem is that you end up with pretty imprecise locations, as the distances you are shown in the client are rounded a lot, and that can make the difference between being able to make the jump or not
Click to expand...

I remember that from the last crowd sourcing activity. The GM was less arounded (2 decimals iirc) then the navigation map. There also was the issue that due to erronous input in the beginning thinks could happen like: route directly from X to Z was longer then from X to Y to Z. Slopey had in BPC at some point unit tests in place which could check all inputs for validity. Or better said his checks could verify that all 3D data later supplied by wtbw was correct

Then wtbw came along with his highly accurate 3D-coordinates. Coordinates he can no longer supply due to the changed policy by FD. Still hoping that FD supplies the community with the coordinates. That would be a great gesture.
 

Tiran Kenja

T
wolverine2710 said:
Then wtbw came along with his highly accurate 3D-coordinates. Coordinates he can no longer supply due to the changed policy by FD. Still hoping that FD supplies the community with the coordinates. That would be a great gesture.
Click to expand...

Personally I am still having a hard time understanding how we have come to a point in 1300 years where we don't use coordinates anymore. Sure you don't see latitude and longitude on a GPS device on the main screen (except maybe the ones for boats). But you can usually look at them if you want to.

So I find it a bit strange that in space you don't need to know where you are.

In other words: Coordinates of some kind should really be available in-game somewhere
 

Grau

G
wolverine2710 said:
Could you eloborate on the 4 distances and the "don't lie all in a plane" part of your post. Very curious in the math behind it.
Some in short: for 500 sytems only 4*500 distances have to be read from the Galaxy Map? That I believe less then what needed to be done for SB1.
Click to expand...

Given: you are at a system with unknown coordinates, but you have the distances to 4 systems with known coordinates. This provides you with 4 quadratic equations based on Euclidean distance. Subtracting the first equation from the other three leaves you with 3 linear equations and 3 unknowns, the coordinates in question.

Of course the resulting numbers are only an approximation. But 4*500 distances are sufficient to locate 500 systems in space. Having more than 4 distances per point should improve precision.
 

Maedhros

Maedhros
Tiran Kenja said:
So I find it a bit strange that in space you don't need to know where you are.

In other words: Coordinates of some kind should really be available in-game somewhere
Click to expand...

I would agree with this. In the ED universe there must be some co-ordinate system that they use - so why not make it obvious in game?
 

Cmdr Eagleboy

Cmdr Eagleboy
Completionists strike again aka there goes exploration gameplay.

Guys, you maybe could just, you know, play game as intended at this point.
 

MrBungle

Banned
M
Pecisk said:
Completionists strike again aka there goes exploration gameplay.

Guys, you maybe could just, you know, play game as intended at this point.
Click to expand...

And you could perhaps, you know, mind your own damn business & stop posting this crap everytime you see something you disagree with on here :rolleyes:

If you don't want to do this sort of thing, don't. But don't you dare prescribe what other people can/can't do & how they can/can't play the game :-|
 

wolverine2710

Tutorial & Guide Writer
wolverine2710
Pecisk said:
Completionists strike again aka there goes exploration gameplay.

Guys, you maybe could just, you know, play game as intended at this point.
Click to expand...

We meet again in another thread it seems... Have you by any change flown in a long range ship like a L-6 and have you tried to find your route to your destination in the Galaxy Map - aka spiderweb ? I have and I personally find the navigation route planners a blessing. Hopefully the spiderweb issue is fixed in SB2.

Please can we stay ON topic and not go into the equivalent of the trenches war of WWI, nobody made progress there.
 
Last edited:
You must log in or register to reply here.
Back
Top Bottom