Page 1 of 158 1234511 ... LastLast
Results 1 to 15 of 2365

Click here to go to the first staff post in this thread.
Thread: What is the most efficient way to crowdsource the 3D system coordinates

  1. #1

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

    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.
    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.

  2. #2
    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 ;-))

  3. #3
    Originally Posted by wolverine2710 View Post (Source)
    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.
    Distance to 4 known systems is sufficient, provided they don't all lie in a plane (which is unlikely).

  4. #4
    Originally Posted by RedWizzard View Post (Source)
    Distance to 4 known systems is sufficient, provided they don't all lie in a plane (which is unlikely).
    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.

  5. #5
    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

  6. #6
    Originally Posted by bamber View Post (Source)
    so in 2D you need three known points so in 3D you will need 4 points
    ... and the seventh symbol is the point of origin? Oh, wait, wrong universe (Couldn't resist!)

  7. #7
    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.

  8. #8
    Originally Posted by wolverine2710 View Post (Source)
    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.
    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.

  9. #9
    I think its a useful thing to do because
    1. 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.
    2. You can note down other things, like black market, distance from star to trading post.
    3. 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.

  10. #10
    Originally Posted by wolverine2710 View Post (Source)
    Two examples of that are Dyckstra's algorithm and A* search.
    Dijkstra's, not Dyckstra's

    Originally Posted by wolverine2710 View Post (Source)
    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.
    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

  11. #11
    Originally Posted by RedWizzard View Post (Source)
    Distance to 4 known systems is sufficient, provided they don't all lie in a plane (which is unlikely).
    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

  12. #12
    Originally Posted by Peter Powers View Post (Source)
    Dijkstra's, not Dyckstra's
    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.

  13. #13
    Originally Posted by wolverine2710 View Post (Source)
    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.
    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

  14. #14
    Originally Posted by Peter Powers View Post (Source)
    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
    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.

  15. #15
    Originally Posted by wolverine2710 View Post (Source)
    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.
    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

Page 1 of 158 1234511 ... LastLast