The Last Star - How long will it take to find it ?

[Iron Body]

This post gets a bit technical, but stick with it, the conclusion is worth it.

There was a thread earlier this year about how long it is going to take to explore the whole galaxy: https://forums.frontier.co.uk/threads/how-much-of-the-galaxy-has-been-explored.476528/

This post is related, but takes a different slant on the problem.
I am not going to distinguish between stars and systems in the post, because tbh, it doesn't make much difference.

So, I was thinking about how long it would take to find the very last unexplored star in the galaxy. This is a hard question. Because we wont know where the last star is. There is currently no way of knowing which systems are unexplored. We only know which systems we have not explored personally. So it seems to me that the whole galaxy will need exploring again just to find this last star.

Currently EDSM says that we have discovered 0.011355% of the galaxy, or 45,427,746 systems.
6 months ago that was 39,012,156 systems. So we are exploring about 12,818,818 systems per year.
Note that these numbers change constantly on the EDSM website, they even changed quite a bit whilst I was writing this.
On this basis EDSM reckons that it will take about 38,505 years to explore the whole galaxy. These numbers dont quite add up, but they are near enough to show what is happening.

So, why will it take so long to find the last star? And what about the star before that ?
The problem is that as the galaxy becomes more and more explored it becomes more and more difficult to find unexplored systems.

I reason that if the proportion of the whole galaxy already explored is p, then the probability of the next
system visited being unexplored is (1-p). Currently (1-p) is 0.99988645, which is why there is a good chance of finding unexplored systems at the moment.

If we make a few assumptions, then it is possible to simulate this process and calculate what will happen in the future...

Assumptions.
1) The number of explorers stays constant. Individuals may change, but the number is the same.
(if ED really takes off, or dies, then this assumption will not work !).
It doesnt matter what this number actually is, but it does underlie assumption 2.

2) The rate at which explorers visit systems (R) will not change. Currently it is about 12.8m per year.

3) The chance of the next system being discovered (ie unexplored) is (1-p), where p = (number of discovered systems) divided by (the total number of systems).

4) The number of new systems discovered per year equals R*(1-p)

I wrote a program to do this as it's not easy to do on a spreadsheet :

G = 400,000,000,000 : total number of systems
R = 12,818,818 : exploration system visits per year
D = 45,421,565 : current number of systems discovered
V = D : Assume the number of systems visited currently. Not strictly correct, but close enough.
Y = 2019 : year
repeat
p = D / G : probability of any system visited being discovered
f = (1-p)*R : number of newly discovered systems per year
D += f : increment the number of discovered systems
V += R : increment the total number of system visits
Y += 1 : increment the year

if Y mod 10000 = 2020 then : print out the results
print "Year ";Y;"% explored = " ; p*100 ; " discovered = "; D ; "visited = ";V
endif

until abs(D-G) < 1 : really D=G, but we have to use the absolute difference because of floating point arithmetic (all in 64 bits anyway)

This gave the following results ( after a bit of editing ) ...
Year %explored Discovered Visits
2020 0.011355 58,238,927 58,240,383
3020 3.164945 12,672,193,127 12,877,058,383
4020 6.219072 24,888,309,801 25,695,876,383
5020 9.176874 36,719,136,538 38,514,694,383
6020 12.041387 48,176,825,180 51,333,512,383
7020 14.815556 59,273,144,308 64,152,330,383
8020 17.502229 70,019,491,329 76,971,148,383
9020 20.104166 80,426,904,178 89,789,966,383
10020 22.624038 90,506,072,663 102,608,784,383
11020 25.064436 100,267,349,440 115,427,602,383
12020 27.427864 109,720,760,648 128,246,420,383
13020 29.716752 118,876,016,204 141,065,238,383
14020 31.933449 127,742,519,783 153,884,056,383
15020 34.080232 136,329,378,472 166,702,874,383
16020 36.159307 144,645,412,124 179,521,692,383
17020 38.172809 152,699,162,418 192,340,510,383
18020 40.122807 160,498,901,637 205,159,328,383
19020 42.011302 168,052,641,155 217,978,146,383
20020 43.840235 175,368,139,675 230,796,964,383
21020 45.611485 182,452,911,193 243,615,782,383
22020 47.326870 189,314,232,720 256,434,600,383
23020 48.988153 195,959,151,750 269,253,418,383
24020 50.597040 202,394,493,505 282,072,236,383
25020 52.155184 208,626,867,943 294,891,054,383
26020 53.664184 214,662,676,548 307,709,872,383
27020 55.125592 220,508,118,902 320,528,690,383
28020 56.540907 226,169,199,059 333,347,508,383
29020 57.911584 231,651,731,705 346,166,326,383
30020 59.239031 236,961,348,136 358,985,144,383
31020 60.524610 242,103,502,038 371,803,962,383
32020 61.769644 247,083,475,093 384,622,780,383
33020 62.975409 251,906,382,399 397,441,598,383
34020 64.143145 256,577,177,728 410,260,416,383
40020 70.415535 281,665,931,256 423,079,234,383
50020 78.527483 314,112,686,376 615,361,504,383
60020 84.415166 337,662,663,679 743,549,684,383
70020 88.688469 354,755,326,071 871,737,864,383
80020 91.790048 367,161,244,933 999,926,044,383
90020 94.041186 376,165,507,656 1,128,114,224,383
100020 95.675070 382,700,835,518 1,256,302,404,383
125020 98.058993 392,236,220,679 1,576,772,854,383
150020 99.128886 396,515,654,302 1,897,243,304,383
175020 99.609048 398,436,242,912 2,217,713,754,383
200020 99.824543 399,298,193,565 2,538,184,204,383
300020 99.992882 399,971,528,551 3,820,066,004,383
400020 99.999711 399,998,844,947 5,101,947,804,383
500020 99.999988 399,999,953,141 6,383,829,604,383
600020 100.000000 399,999,998,099 7,665,711,404,383
700020 100.000000 399,999,999,923 8,947,593,204,383
800020 100.000000 399,999,999,997 10,229,475,004,383
835020 100.000000 399,999,999,999 10,678,133,634,383

There are some interesting numbers in here.

In 38,000 years, (year 40,020) we will only have found about 70% of systems, and 70% of exploration visits will be wasted that year. But we will have visited 400 billion systems, many of them thousands of times over.

In 100,000 years, there will still be about 17 billion unexplored systems, but they will be very hard to find.

In 800,000 years there will still be 3 systems left.
The very last star will take around 835,000 years to find.
And over 10 trillion jumps will have to be made to find it.

Conclusion:

FD really need to put a "Discovered" button in the galmap alongside "Visited" and "Not Visited".
This will save a lot of commander effort in the long run.

 

[Jason Clearbrook]

It would be nice. I think it would also boost the number of people who do exploring, which would also increase the rate that systems are discovered.

On the flip side, think of the server load to keep track of all of those systems. As systems are discovered, I am pretty sure only at that time the planetary bodies are created. Look at your numbers above, and calculate how much storage space would be required to track all of that information. I think if you put in an estimate of say 40k bytes per system, that amount of storage currently needed is just under 2 Terabytes, just for the systems currently discovered. Now 40k may seem large, but consider resources available, names of who first mapped, orbital mechanics, etc, and I think that 40k is a lowball estimate. Maybe not. It is a thumb in the wind estimate, but really, the difference between 4k and 400k is insignificant when you consider what I will talk about below. I have a high level of certainty that the number is somewhere in such a broad range. But even that could be off.

Nonetheless, I digress. Let me continue.

Now keeping track of that amount of data is doable. As the number of systems discovered creeps up, that becomes harder. It is not only a matter of database size from a storage limitation, it quickly becomes a matter of speed of data access. I imagine that they index their database on the system level, creating an index for each system, and then storing the entire system data under that one index. That would speed things up considerably, but at a cost of a small storage space overhead.

Now I am addressing this to you at this level, because you seem to be a numbers person. So am I. I think FDev has looked at this and realized the down side. In twenty years from now, at the current rate of progression of real world technology, I still don't think this will be doable unless there is some other limitation that keeps people from getting out to all those star systems.

I'd rather not see such a roadblock. I like exploring now and then and maybe coming across something I can put my name on. That is pretty vain, I know, but enjoyable. I think part of the enjoyment is derived by knowing how much luck and/or work went into making that happen. I don't think I will live long enough to see the problem of "artificial" limitations arising, but you never know...

Still, you had a good thought!

;'{P~~~

 

[Iron Body]

Thanks. I did wonder about the data storage aspect of this suggestion.
Certainly there must be a central db of "discovered by", "mapped by" etc. Which will only grow as more systems get discovered. I'm sure FD have enough storage for the foreseeable future. In the very long term they certainly wont.

Today though, the fact that a system has already been discovered or not is already known to the server. As you say, it may be a question of finding it, and streaming it, quickly enough for the galmap to keep up.

 

[varonica]

This post gets a bit technical, but stick with it, the conclusion is worth it.

There was a thread earlier this year about how long it is going to take to explore the whole galaxy: https://forums.frontier.co.uk/threads/how-much-of-the-galaxy-has-been-explored.476528

As long as the system works as it is we are going to have to take a different slant, because you can get all the stars except one but not know where in the galaxy that star is, so your exploration group would need to start at one side of the galaxy and work methodically across the galaxy to get them all, and even then you can't be guaranteed someone hasn't made a mistake. The actual answer is probably forever because the fewer stars there are to find the longer it's going to take to find each one, but a reasonable time would be the length of time it takes one CMDR to visit every star in the galaxy so they can mark them off their visited list. So if we assume 1 minute for every star to make it easy and there are 400b stars that's 400b divided by 60, or 6,666,666,666.666 years, a nice number.

 

[varonica]

As long as the system works as it is we are going to have to take a different slant, because you can get all the stars except one but not know where in the galaxy that star is, so your exploration group would need to start at one side of the galaxy and work methodically across the galaxy to get them all, and even then you can't be guaranteed someone hasn't made a mistake. The actual answer is probably forever, because the fewer stars to find the longer it will take to find them, but a reasonable time would be the length of time it takes one CMDR to visit every star in the galaxy so they can mark them off their visited list. So if we assume 1 minute for every star to make it easy and there are 400b stars that's 400b divided by 60, or 6,666,666,666.666 years, a nice number.

 

[Iron Body]

As long as the system works as it is we are going to have to take a different slant, because you can get all the stars except one but not know where in the galaxy that star is, so your exploration group would need to start at one side of the galaxy and work methodically across the galaxy to get them all, and even then you can't be guaranteed someone hasn't made a mistake. The actual answer is probably forever because the fewer stars there are to find the longer it's going to take to find each one, but a reasonable time would be the length of time it takes one CMDR to visit every star in the galaxy so they can mark them off their visited list. So if we assume 1 minute for every star to make it easy and there are 400b stars that's 400b divided by 60, or 6,666,666,666.666 years, a nice number.

Thats 6,666,666,666.666 hours, not years. But that works out at 761,035 years, not too different from my estimate.

But you are right about being methodical. If each commander were allocated a small cube to explore they could ensure that all stars in that cube had been visited using the current galmap. There are roughly 2 billion cubes of size one thousand ly per side in the galaxy. If we had 10,000 commanders, that is 200,000 cubes each.

But how long does it take to fully explore a cube 1000 ly across ? I'm off to find out. Unfortunately I'm currently at Explorers Anchorage, in the densest part of the galaxy, so it might take a while. I think organised expeditions divide up space between commanders, but do they ever ensure that every system has been visited in their allotted area ?

 

[varonica]

Thats 6,666,666,666.666 hours, not years. But that works out at 761,035 years, not too different from my estimate.

But you are right about being methodical. If each commander were allocated a small cube to explore they could ensure that all stars in that cube had been visited using the current galmap. There are roughly 2 billion cubes of size one thousand ly per side in the galaxy. If we had 10,000 commanders, that is 200,000 cubes each.

But how long does it take to fully explore a cube 1000 ly across ? I'm off to find out. Unfortunately I'm currently at Explorers Anchorage, in the densest part of the galaxy, so it might take a while. I think organised expeditions divide up space between commanders, but do they ever ensure that every system has been visited in their allotted area ?

Oops, the original number sounded better even if it was wrong lol.

 

[beneuto]

As systems are discovered, I am pretty sure only at that time the planetary bodies are created. Look at your numbers above, and calculate how much storage space would be required to track all of that information.

All the system definitions were generated at the start of the game. System data is only a set of parameters to be fed into standard algorithms for system rendering (done when you enter the system and destroyed when you leave). If parameters are largely flags and integers, 40KB would allow for between 10,000 and 320,000 possibilities per system which is way, way more than required. There is a bit more data required for discovered systems as you say but that is and will likely always be a very small subset.

 

[varonica]

All the system definitions were generated at the start of the game. System data is only a set of parameters to be fed into standard algorithms for system rendering (done when you enter the system and destroyed when you leave). If parameters are largely flags and integers, 40KB would allow for between 10,000 and 320,000 possibilities per system which is way, way more than required. There is a bit more data required for discovered systems as you say but that is and will likely always be a very small subset.

We know exactly how the ID system for the galaxy works, this is something FDEV have discussed in one of their tech talks. Every astronomical object in the galaxy has a unique ID in a single 64 bit ID space, the allowance for objects within any one system gives exactly 255 ID's, including the primary star, so a maximum of 255 astronomical objects that require a unique ID. I would recommend watching the tech talk where they went through this stuff, it's very interesting.

 

[recrudesce]

What you're not taking into account is the change in players. You're assuming that the discovery rate will remain static. What happens if the player base increases by 200% in 2020 ? What if it halves ?

Also, the "45 million systems discovered" is only what EDSM knows. Which is about 0.01%. FDev last year said it was actually 0.04% discovered.