Galaxy plotter inefficiency

[MEPHEDRONE]

Why when I choose fastest route + jump through neutron-stars (aka jet-cone jump) it makes a route with maximum one jet-cone boost (but for trips longer than 5-6 jumps its like almost zero) and then its just simple star-to-star jumps? For example everyone we know about Spansh Neutron plotter which do it exactly how it should work - minimizes jumps by using only jet-cone paths (when it possible). You can test it with any source-destination system yourself. Like Sol -> Colonia, with Spansh plotter is about 130 jumps but with native plotter - up to 300 on the same ship (numbers are not accurate especially for native, maybe about 400-500). It's definetelly not works as it should -> I want to use fastest route and I want to jump through jet-cones but I dont recieve this

 

[Ashnak]

For Sol - Colonia probably because the native router makes tighter restrictions on route efficiency, i.e. how far the plotted route can deviate from the straight line and how heavily using a neutron jump is weighed against going the shortest route.
On Spansh, you can adjust one (IIRC) one parameter for efficiency - in the native router, all parameters are fixed.
Why this matters (a lot) is of course because there are a lot of stars on the direct route between Sol and Colonia, but only very few Neutrons. Both Sol and Colonia are pretty much on the ecliptic, while the Neutron fields start roughly 1 kly above and below.
Counter experiment: check out the boundary of the Neutron fields, plot your route there, then use the native router with Neutron jumps until you're straight above ( or below) Colonia and drop down. Works like a charm, although for my taste the native plotter makes too many refueling stops - I could have done one more boosted jump most of the time on my trip from BP to Colonia.

This guide is now six years old, but the Galaxy hasn't changed: https://forums.frontier.co.uk/threads/the-neutron-fields-a-definitive-guide.163816/

 

[MEPHEDRONE]

For Sol - Colonia probably because the native router makes tighter restrictions on route efficiency, i.e. how far the plotted route can deviate from the straight line and how heavily using a neutron jump is weighed against going the shortest route.
On Spansh, you can adjust one (IIRC) one parameter for efficiency - in the native router, all parameters are fixed.
Why this matters (a lot) is of course because there are a lot of stars on the direct route between Sol and Colonia, but only very few Neutrons. Both Sol and Colonia are pretty much on the ecliptic, while the Neutron fields start roughly 1 kly above and below.
Counter experiment: check out the boundary of the Neutron fields, plot your route there, then use the native router with Neutron jumps until you're straight above ( or below) Colonia and drop down. Works like a charm, although for my taste the native plotter makes too many refueling stops - I could have done one more boosted jump most of the time on my trip from BP to Colonia.

This guide is now six years old, but the Galaxy hasn't changed: https://forums.frontier.co.uk/threads/the-neutron-fields-a-definitive-guide.163816/

Thank you for the answer. Idea about deviation from straight line is definetelly make sense, seems like this is why native plotter behaves like that. Didn't know that neutron fields is away from ecliptic (especially bcos first neutron I've seen was Jackson's Lighthouse that is not). But don't you think that this behaviour shouldn't be fixed? I mean native plotter straight line deviation rule. Because even if it's correct in terms of geographically shortest route it's absolutelly not in terms of most time efficient route (this is exactly how I understand the word "fastest" when I click that checkbox). Maybe I should create a ticket about this?

P.S. Why neutron fields is placed like that? Just aksing if you know astronomical/physical explaination, it's really interesting and bothering me now Ofc if ED correctly replicates real Milky Way and this fields actually exist in reality and wasn't made by Frontier just4fun or for neutron-highway

 

[Ashnak]

Haven't watched it (yet...), but this video is supposed to ber the best explanation for the shape of the ED Galaxy:

As for the Neutron fields replicating the real Milky Way - no such luck. We simply don't have that data.

 

[MEPHEDRONE]

Haven't watched it (yet...), but this video is supposed to ber the best explanation for the shape of the ED Galaxy:

As for the Neutron fields replicating the real Milky Way - no such luck. We simply don't have that data.

Could you please share your opinion about that behaviour of native plotter? Cuz still dont undestand why everyone is fine with it, maybe its considered OK by community, idk. Talking about this quote:

But don't you think that this behaviour shouldn't be fixed? I mean native plotter straight line deviation rule. Because even if it's correct in terms of geographically shortest route it's absolutelly not in terms of most time efficient route (this is exactly how I understand the word "fastest" when I click that checkbox). Maybe I should create a ticket about this?

 

[varonica]

Could you please share your opinion about that behaviour of native plotter? Cuz still dont undestand why everyone is fine with it, maybe its considered OK by community, idk. Talking about this quote:

The changes with the route plotter to reduce deviation from a straight line were prompted by problems players were having in dense star regions. The problem is we are dealing with computers, and they don't have abstract thinking capability, so if you tell a computer to determine the shortest possible route between two points it has to check every possible route between the two points to determine the shortest possible route. It's not a possibility, as it would be in humans, to decide not to use that route without checking because it's obviously longer, a computer can't do that because it requires abstract thinking. Now checking every possible route is fine is you only have a small number of waypoints to check, but in ED we are dealing with millions, and for really long routes billions of possible paths.

Before the route plotter was changed to the way it was hitting dense areas of stars and trying to plot through would sometimes lead to 30 minutes of sitting there waiting while the route plotter spent it's time checking every possible route to determine which is the shortest. Yes there are algorithms which can help, which is why we have the route plotter we have now, large deviations from a straight line are automatically eliminated from the search.

 

[Ashnak]

Could you please share your opinion about that behaviour of native plotter? Cuz still dont undestand why everyone is fine with it, maybe its considered OK by community, idk. Talking about this quote:

Finding a fastest path through many points is a computational hard problem. It's actually one of the toughest unsolved problems in mathematics. The only thing that can be proven is that it's tough . The current plotter is a reasonable compromise - and much better at least than its predecessors.
What would be the alternatives?
An overall better plotter that would find the fastest path across the Galaxy would be nice, but either take too long or require the development of new algorithms which don't exist yet (or, if they do, would be very expensive to buy...). The Spansh plotter makes some different assumptions and adds more controls, but unlike the in-game plotter only works with discovered stars - far less than 1% of what is actually out there. So finding new systems is impossible if you use that one.
It's a decision by FD I can live with - there are other problems in the game that have a larger impact and should require less money/effort to fix.

 

[MEPHEDRONE]

It's not a possibility, as it would be in humans, to decide not to use that route without checking because it's obviously longer, a computer can't do that because it requires abstract thinking. Now checking every possible route is fine is you only have a small number of waypoints to check, but in ED we are dealing with millions, and for really long routes billions of possible paths.

Finding a fastest path through many points is a computational hard problem. It's actually one of the toughest unsolved problems in mathematics. The only thing that can be proven is that it's tough . The current plotter is a reasonable compromise - and much better at least than its predecessors.

Guys, I'm a programmer myself. I know how it works and what it costs. But

1) it's not "a computational hard problem". route finding is a trivial task that commonly appears in any beginner-level course of programming and even matrixes applications of 1st degree math courses
2) you dont have to check billions of routes, even Bubble->Colonia route have quite determined boundaries (which we called efficiency before) that easily can be calculated and set so you wont have to check another billions unrelated paths
3) there is a lot of optimizations techniques and tricks about route finding and in our case it's absolutelly solved problem
4) it's already done by Spansh plotter. idk if they use client-side calculation or server-side but I doubt that they are using 3285235 TFLOPS servers so they are definetelly not faster than average user PC (include there input lag too). in case of client-side JS calculcations it's even clearer - if it's done in seconds by browser's JS -> this will be done in pure binary in milliseconds

So I dont see a problem actually. At least they could improve plotter so it would work in 2 modes (really fastest and closest-fastest), add advanced options for advanced users, etc.. Because if current implementation is "right" - why would people even use Spansh, hm?

 

[varonica]

Finding a fastest path through many points is a computational hard problem. It's actually one of the toughest unsolved problems in mathematics. The only thing that can be proven is that it's tough . The current plotter is a reasonable compromise - and much better at least than its predecessors.
What would be the alternatives?
An overall better plotter that would find the fastest path across the Galaxy would be nice, but either take too long or require the development of new algorithms which don't exist yet (or, if they do, would be very expensive to buy...). The Spansh plotter makes some different assumptions and adds more controls, but unlike the in-game plotter only works with discovered stars - far less than 1% of what is actually out there. So finding new systems is impossible if you use that one.
It's a decision by FD I can live with - there are other problems in the game that have a larger impact and should require less money/effort to fix.

For further reading for the OP and to add some depth I suggest looking up "The Traveling Salesman" problem;

Travelling salesman problem - Wikipedia

en.wikipedia.org

 

[varonica]

4) it's already done by Spansh plotter.

No it's not, they have a tiny, almost infinitesmal fraction of the total number of stars in the galaxy, so they are doing calculation based on a tiny fraction of the stars the in game route plotter is using.

 

[Ashnak]

route finding is a trivial task that commonly appears in any beginner-level course of programming and even matrixes applications of 1st degree math courses

Nope - some simplifed algorithms are taught. And even in this case, the examples (and practically computable applications) are, for a good reason, limited to small two-dimanesional problems. You can even see this working in ED: whenever I plot a longer route, every ten full range jumps or so I get a small jump in the plotted route, even though there would be further suitable stars en route. Indicating that I'm crossing one of the segment boundaries the plotter has introduced to split the route into manageable segments.

you dont have to check billions of routes

sorry - but that one actually made me laugh (and reach for a pencil). Sol - Colonia is about 20,000 ly. To reach the Neutron layer, you'll need to deviate by about 1,000 ly from the direct route. So, that's roughly speaking a volume of 2,000 x 2,000 x 20,000 ly³ - 8e10 ly³. Yes, you could reduce it a little bit - but that's an order-of-magnitude estimation, let's not haggle about a factor 10. To make calculation simpler, I assume on average one star per 20 cubic lightyears (something like 8 ly to the nearest neighbour, more on the rim, much less in the core). Divide 8e10 by 20, and you end up with 4e9 stars in that volume. Roughly 1% of the number of stars in the Galaxy, looks about right.
So, how many routes can you plot through 4 billion stars in three dimensions? The point of the algorithms you mentioned above is to reduce that selection - but even using those, "billions" is probably lowballing the number of computationally feasible routes by "a few" orders of magnitude. And remember - you wanted the fastest (in time) overall route.

there is a lot of optimizations techniques and tricks about route finding and in our case it's absolutelly solved problem

Errmmm... no. There are a few widely used algorithms that provide solutions. For a small number of nodes, a shortest path is computationally calculable - but for a large number of nodes (in two dimensions!), V*log(V) is the best these algorithms will do (still better than V²), and that always catches you out. For large numbers of nodes, there are approximations. FD uses one of them, Spansh is likely using another.

it's already done by Spansh plotter

Again, no. Spansh may use a different algorithm, but, as already stated, more important is that Spansh only uses a tiny subset of the stars in the Galaxy. And people who really want to push the edge (like breaking the Sol-Colonia record, or going to Colonia without a fuel scoop) still use their own algorithms.

 

[MEPHEDRONE]

No it's not, they have a tiny, almost infinitesmal fraction of the total number of stars in the galaxy, so they are doing calculation based on a tiny fraction of the stars the in game route plotter is using.

yep I know that it's stripped. but main point in that search array is filtered out, this is why it works. still it WORKS and many people actually use this. while native plotter is absolutelly useless in that case, isn't it?

sorry - but that one actually made me laugh (and reach for a pencil). Sol - Colonia is about 20,000 ly. To reach the Neutron layer, you'll need to deviate by about 1,000 ly from the direct route. So, that's roughly speaking a volume of 2,000 x 2,000 x 20,000 ly³ - 8e10 ly³. Yes, you could reduce it a little bit - but that's an order-of-magnitude estimation, let's not haggle about a factor 10. To make calculation simpler, I assume on average one star per 20 cubic lightyears (something like 8 ly to the nearest neighbour, more on the rim, much less in the core). Divide 8e10 by 20, and you end up with 4e9 stars in that volume. Roughly 1% of the number of stars in the Galaxy, looks about right.
So, how many routes can you plot through 4 billion stars in three dimensions? The point of the algorithms you mentioned above is to reduce that selection - but even using those, "billions" is probably lowballing the number of computationally feasible routes by "a few" orders of magnitude. And remember - you wanted the fastest (in time) overall route.

I think you probably got me wrong. You are talking about ALL possible routes while we dont have to check them at all. As you've mentioned before there is as it called Neutron Field which is Spansh using that filter out 99.(9)% of this "4e9 stars" you are talking about.

Errmmm... no. There are a few widely used algorithms that provide solutions. For a small number of nodes, a shortest path is computationally calculable - but for a large number of nodes (in two dimensions!), V*log(V) is the best these algorithms will do (still better than V²), and that always catches you out. For large numbers of nodes, there are approximations. FD uses one of them, Spansh is likely using another.

But you've just confirmed what I've told - it's solved problem which was already heavily researched and have determined most efficient alghoritms (as I've found you are talking about Delaunay Triangulation approach). I dont understand what you are trying to refute in this message since it doesn't conflict with anything I've
said before

Again, no. Spansh may use a different algorithm, but, as already stated, more important is that Spansh only uses a tiny subset of the stars in the Galaxy. And people who really want to push the edge (like breaking the Sol-Colonia record, or going to Colonia without a fuel scoop) still use their own algorithms.

My point was in the fact that on Spansh we have already working and widely used by community solution. We can dive until infinity into mathematical discussion about path-finding algos and their effeciency but its absolutelly not the case. I'm not blaming the current ED plotting algo but only want to fix fastest-route+jet-cone plotting since again - anyone who knows Spansh plotter would prefer this instead of native plotter when we are talking about this case because AGAIN the numbers speak for themself - native plotter: 34 jumps, Spansh plotter - 13 jumps. Just integrate Spansh solution into native plotter as a side-feature. I dont understand whats wrong with that and why you guys are against this

 

[Ashnak]

My opinion? Because adding another plotter that uses a thinned out starmap would be an expert mode - too many people would start to complain, for example, that they won't get any new discoveries on that.
Yes, it would be optional - but there's too many people around already who don't realize that they run on economic plotting and then come here to complain that they need too many jumps. And experts who rely heavily on other plotters would probably also already use something like the SpanshRouter, so the added value would be very small.

Again, it boils down to a business decision - how much value added at which cost. My opinion is on the "too expensive for a niche product" side.