Discussion What is the most efficient way to crowdsource the 3D system coordinates
- Thread starter wolverine2710
- Start date
As time permits, aka slowly, I'm hoping to work on a Windows application (C# WPF using Visual Studio 2013 Community Edition) to help with mapping/navigation. It's early days yet, but I've made the source available on Github for possible collaboration.
So far I have it reading the systems.json file into a database and monitoring the log so if I enter a system that isn't in the database it uses TTS to warn me the system needs adding.
I've also got it reading data from EDDN.
My goals moving forward are:
NOTE: I plan to use SharpDX to handle any Vector mathematics.
If anyone out there would be interested in collaborating/helping and has experience with C# and WPF please do get in touch.
So far I have it reading the systems.json file into a database and monitoring the log so if I enter a system that isn't in the database it uses TTS to warn me the system needs adding.
I've also got it reading data from EDDN.
My goals moving forward are:
- Store the EDDN data in the database.
- Provide a report of any systems in the EDDN data that aren't in the navigation data.
- Provide a way to add systems/stations/etc
- Provide a way to generate a systems.json file
- Integrate with the EDStarCoordinator website via its API to both find new systems and submit to the site via the app
- Implement some form of shortest path navigation aid similar to Elite Copilot without the need for Python and a huge executable.
- Provide a way to search the EDDN data for handy trade routes, etc
NOTE: I plan to use SharpDX to handle any Vector mathematics.
If anyone out there would be interested in collaborating/helping and has experience with C# and WPF please do get in touch.
Last edited:
It doesn't seem like the database is incrementing CR. I've updated numerous systems and the CR doesn't change. In fact George Pantazis has been sitting at CR 2 for a while now. That is a very common system for people running rares. I know that I've put in at least 15-20 systems for George and its still CR 2
I thought about system coordinates a lot in the past days, as I don't really like the way they are "calculated" right now. There is a solution to really calculate the coordinates of an unknown system, when you have 4 distances to 4 known systems.
Good news: after a few days thinking, trying and with some help of a friend I got the solution. Well, my own walks in the maths are several decades in the past...
Testing with random known coordinates from EDSC shown errors of 10^-8 to 10^-9 when calculating.
Bad news: after rounding the distances from EDSC to 2 decimal values, like given in the ingame GM, most of the coordinates look good, but there are errors up to 2, maybe 3 units of 1/32 Ly. This is too much.
Right now I'm fiddling around with 5 known reference systems, maybe 6. I hope this gives more precise results.
Edit: With 5 or 6 reference systems it gets more precise, but still some remarkable errors in it.
I tried to take a look at the angles between the reference systems from the view of the unknown system. The error gets smaller when the angles are between 30 & 150 deg, but still hard to predict if the calculation is precise enough.
Good news: after a few days thinking, trying and with some help of a friend I got the solution. Well, my own walks in the maths are several decades in the past...
Testing with random known coordinates from EDSC shown errors of 10^-8 to 10^-9 when calculating.Bad news: after rounding the distances from EDSC to 2 decimal values, like given in the ingame GM, most of the coordinates look good, but there are errors up to 2, maybe 3 units of 1/32 Ly. This is too much.
Right now I'm fiddling around with 5 known reference systems, maybe 6. I hope this gives more precise results.
Edit: With 5 or 6 reference systems it gets more precise, but still some remarkable errors in it.
I tried to take a look at the angles between the reference systems from the view of the unknown system. The error gets smaller when the angles are between 30 & 150 deg, but still hard to predict if the calculation is precise enough.
Last edited:
wolverine2710
Tutorial & Guide Writer
Does anyone know what happened to TornSoul? I checked his profile and he doesn't seem to be online (as in posted in the forums) for a few weeks. Last thing I heart was that he seemed to be really burned out. If that is the case and given the fact he is the maintainer of TGC I'm wondering how this will effect TGC?
I thought about system coordinates a lot in the past days, as I don't really like the way they are "calculated" right now. There is a solution to really calculate the coordinates of an unknown system, when you have 4 distances to 4 known systems.
Good news: after a few days thinking, trying and with some help of a friend I got the solution. Well, my own walks in the maths are several decades in the past...
Bad news: after rounding the distances from EDSC to 2 decimal values, like given in the ingame GM, most of the coordinates look good, but there are errors up to 2, maybe 3 units of 1/32 Ly. This is too much.
Right now I'm fiddling around with 5 known reference systems, maybe 6. I hope this gives more precise results.
Edit: With 5 or 6 reference systems it gets more precise, but still some remarkable errors in it.
I tried to take a look at the angles between the reference systems from the view of the unknown system. The error gets smaller when the angles are between 30 & 150 deg, but still hard to predict if the calculation is precise enough.
The system distances are rounded values from the original galaxy layout. You can't ever get back from the distances to the original coordinates. What consequences has this for our custom database?
Can you elaborate? Do you mean you don't like the algorithms the rest of us are using?
There is a solution to really calculate the coordinates of an unknown system, when you have 4 distances to 4 known systems.
Good news: after a few days thinking, trying and with some help of a friend I got the solution. Well, my own walks in the maths are several decades in the past...
Bad news: after rounding the distances from EDSC to 2 decimal values, like given in the ingame GM, most of the coordinates look good, but there are errors up to 2, maybe 3 units of 1/32 Ly. This is too much.
Right now I'm fiddling around with 5 known reference systems, maybe 6. I hope this gives more precise results.
Edit: With 5 or 6 reference systems it gets more precise, but still some remarkable errors in it.
I tried to take a look at the angles between the reference systems from the view of the unknown system. The error gets smaller when the angles are between 30 & 150 deg, but still hard to predict if the calculation is precise enough.
Even with 5 or 6 fixed references you will find systems that can't be located well. You can choose references that will work for the inhabited region of the galaxy, e.g. I use Kato, Cayu, Nuwach, Marra, Zhuar, and Juro. But the precision of the distances shown in the galaxy map will cause issues for systems more than a couple of hundred Ly away. That is why we've focused a lot of effort into developing algorithms that can determine if a set of references is a good one for locating a particular system, and for detecting likely data errors.
Are you using single precision floating point for calculating distances? You will get small differences to the galaxy map if you don't.
Last edited:
I hope he's just on holiday. Given that TGC does not store anything but coordinates I think we'll need a new implementation if he has quit.
I thought about system coordinates a lot in the past days, as I don't really like the way they are "calculated" right now. There is a solution to really calculate the coordinates of an unknown system, when you have 4 distances to 4 known systems.
Good news: after a few days thinking, trying and with some help of a friend I got the solution. Well, my own walks in the maths are several decades in the past...
Bad news: after rounding the distances from EDSC to 2 decimal values, like given in the ingame GM, most of the coordinates look good, but there are errors up to 2, maybe 3 units of 1/32 Ly. This is too much.
Right now I'm fiddling around with 5 known reference systems, maybe 6. I hope this gives more precise results.
Edit: With 5 or 6 reference systems it gets more precise, but still some remarkable errors in it.
I tried to take a look at the angles between the reference systems from the view of the unknown system. The error gets smaller when the angles are between 30 & 150 deg, but still hard to predict if the calculation is precise enough.
Calculating the system coordinates is pretty much a solved problem at this point. I know there are probably 4-5 of us with slightly different implementations, with all of them agreeing with each other.
One thing to keep in mind when you're thinking about this problem conceptually is that the 2 decimal point distances we get from the galaxy map actually give you a range of possible distances. i.e. if the distance is 12.34, then you know that the actual distance is in [12.335, 12.345). So you end up with a thin spherical shell, with the outside surface formed by the outer sphere of radius 12.345, and the inner surface formed by the inner sphere of 12.335.
So each distance you have gives you a different thin spherical shell. And you know the actual grid-aligned coordinate of the star lies somewhere in the intersection of all of these thin spherical shells, which forms some smallish 3d volume. If this volume is small enough that in only encompasses 1 grid-aligned point, then you know you have found the coordinate, assuming all of the distances are accurate.
What most of us do is to evaluate the distances from all "near" 1/32ly grid points near the calculated point, based on some arbitrary sphere/cube, or some sort of more advanced heuristic. For each near point, you calculate the rounded distances using the exact same calculation the game uses and compare the calculated rounded distance with the rounded distance recorded from the game. If there are multiple grid-aligned points that exactly match the distances from the game, then you can conclude the intersection volume described above is still too large, and you need more distances to calculate the coordinate.
In addition, in order to help detect and account for potentially incorrect distances, it's a good idea to ensure that all points other than the 1 correct point have at least 2 or more incorrect distances. This provides enough redundancy to ensure that 1 incorrect distance would have been detected. My personal target is 3 or more incorrect distances for each non-correct point, which is enough redundancy to detect at least 2 incorrect distances.
Last edited:
Short answer, because I'm on my way back from holidays.
I have in mind that EDSC uses a quadratical approximation to find the coordinates. This involves some (small) errors caused by the system, and it's quite CPU-intense, as far as I read. Besides that it is in Python, and I like PHP
The preferred way is to have an algorithm which calculates the location based on some distances,and no estimation in here.
I know the values are rounded to 2 decimal points, and there are CMDRs mistyping distance values by mistake, and sure there are trolls giving false distances by purpose.
I don't know which methods are used by others, except EDSC. And maybe my information about the EDSC way is outdated, so pls let me know, also about other methods already used by others. Maybe I overlooked something here.
Anyway yesterday I implemented backwards checking of the coordinates found, did about 100-200 manual tests with EDSC coordinates, using 4-6 reference systems. And it showed either false coordinates which were easily detected, or the right coordinates. No false positive.
In the next days I'll make it work with any number of distances >= 4 and make some 10.000 tests with random EDSC coordinates.
I have in mind that EDSC uses a quadratical approximation to find the coordinates. This involves some (small) errors caused by the system, and it's quite CPU-intense, as far as I read. Besides that it is in Python, and I like PHP
The preferred way is to have an algorithm which calculates the location based on some distances,and no estimation in here.
I know the values are rounded to 2 decimal points, and there are CMDRs mistyping distance values by mistake, and sure there are trolls giving false distances by purpose.
I don't know which methods are used by others, except EDSC. And maybe my information about the EDSC way is outdated, so pls let me know, also about other methods already used by others. Maybe I overlooked something here.
Anyway yesterday I implemented backwards checking of the coordinates found, did about 100-200 manual tests with EDSC coordinates, using 4-6 reference systems. And it showed either false coordinates which were easily detected, or the right coordinates. No false positive.
In the next days I'll make it work with any number of distances >= 4 and make some 10.000 tests with random EDSC coordinates.
Short answer, because I'm on my way back from holidays.
I have in mind that EDSC uses a quadratical approximation to find the coordinates. This involves some (small) errors caused by the system, and it's quite CPU-intense, as far as I read. Besides that it is in Python, and I like PHP
The preferred way is to have an algorithm which calculates the location based on some distances,and no estimation in here.
I know the values are rounded to 2 decimal points, and there are CMDRs mistyping distance values by mistake, and sure there are trolls giving false distances by purpose.
I don't know which methods are used by others, except EDSC. And maybe my information about the EDSC way is outdated, so pls let me know, also about other methods already used by others. Maybe I overlooked something here.
Anyway yesterday I implemented backwards checking of the coordinates found, did about 100-200 manual tests with EDSC coordinates, using 4-6 reference systems. And it showed either false coordinates which were easily detected, or the right coordinates. No false positive.
In the next days I'll make it work with any number of distances >= 4 and make some 10.000 tests with random EDSC coordinates.
We've been doing trilateration since first pages of this thread. The 1/32 grid is a FD thing. Not getting it on the grid will give you errors. Tornsouls system is doing what its doing to compensate for human error, and its working very nicely when staying near human settled space. The CR<5 is going to become a pain when submitting stars further away from FD submitted systems.
I have in mind that EDSC uses a quadratical approximation to find the coordinates. This involves some (small) errors caused by the system, and it's quite CPU-intense, as far as I read. Besides that it is in Python, and I like PHP
EDSC/TGC is using trilateration with local grid testing as JesusFreke described. His code is C# I believe, and not publicly available. I use a very similar algorithm in my Javascript version which is available here: https://github.com/SteveHodge/ed-systems
The CPU requirements stem from testing the grid locations around possible candidates generated by trilateration. This is necessary because of the imprecise input data, to maximise the chance of getting an accurate location from poorly chosen references, and out of a desire to have confidence in the outcome. Try testing your algorithm with Sagittarius A* or Alpha Cygni to see why this approach is helpful.
Yes, you can get back, because the coordinates are on a fixed grid, provided enough rounded distances. Because our database uses the same grid (and EDSC et al do) no further consequences.
If you say we have an effective way to calculate new coordinates, I'll stop (or pause) my effort in this. Still waiting for Tornsoul, hope he turns back in.
If I want to test these systems I'd need some more distances, but I don't think my algorithm will be better or worse than EDSC's, so no need here. Do you know a way to get the stored distances f.ex. to Alpha Cygni out of EDSC?
I think we're all comfortable with the current methods for calculating new coordinates. Personally speaking, I'm comfortable with TornSoul's implementation that is used for EDSC/TGC. But feel free to keep working on yours if you find it interesting. It was definitely a fun project for me
You can use the GetDistances api to get the distances from TGC. e.g. http://jsfiddle.net/8d7szc64/
Last edited:
You can use TGC's GetDistances API as JesusFreke suggested, or you can grab systems.json from my stuff which has most of the distance data that was collected up to the end of gamma. It has plenty of distances for those two systems. Incidentally my algorithm is not able to correctly locate Sagittarius A* with the data I have, that one is a real challenge. I think JesusFreke was able to do it with his more sophisticated technique for determining the candidate region.
Last edited:
Cool, I didn't knew this one, only the getSystems. Quick check: With only 6 reference systems my code doesn't find any solution for Alpha Cygni. In the next week or two I'll probably make my code use n reference systems instead of 6, then I'll try this. But no hurry, as yousay the existing way is comfortable.
Mostly uncomfortable is pinning entering reference systems' names and writing down the distances by hand...
In case Turnsoul does not come back, does anyone know how to get all data from his API, to have a backup in hand? Has he described this API anywhere?
I don't have a backup of TornSoul's data, but I do at least keep all the data that I've submitted.
Api docs are at http://www.edstarcoordinator.com/api.html
I grab a complete dump of the systems (full output) and distances (simple output) periodically. I've been checking the systems dump into my github repo as I use it as a cache (https://github.com/SteveHodge/ed-systems/raw/master/tgcsystems.json). The distances I'm only storing locally at the moment.
You can grab all the systems or distances by using a CR of 0 and an old date and no other filter.
*redface* I had this in a browser tab, read the GetSystem docu but didn't see the rest. Maybe I have to clean my glasses