Hi bzt, I hope you have some time, strap yourself in, get a drink..
bzt wrote: ↑Thu Nov 11, 2021 19:34
Blockhead wrote: ↑Thu Nov 11, 2021 06:34
This is really convoluted way to spin things to make it sound big, and try to excuse engine limitations.
It's not just the engine, we're talking about machine limitations too. Machines can only work with limited precision and with limited and finite natural numbers, furthermore the size of memory is very limited too.
Machines can work with arbitrary precision bounded only by available memory. This is how operations on very very large numbers, like
finding the world's largest prime numbers are done. It is not just extensible to the natural numbers, or even all integers. This same process can be applied to extremely accurate fractional parts of a number as well, such as
trillions of digits of pi. These arbitrary precision operations are not native to the machine but they are achieved by packing several CPU-native datatypes into contiguous memory and operating on them as if they have place value.
GMP is one such library.
Of course, just because we can work with arbitrary precision numbers, that does not mean we should. It becomes quite slow to work on these numbers as their size increases. Thankfully, there is no need to worry because I am not suggesting we make coordinates anywhere near this large. log2(60000000) (60 million) = 25.838, meaning that just 26 bits can store a Minecraft coordinate in one dimension, for a total of 78 bits to store all three dimensions. On a real machine we pad these numbers out to 32 bits each. 32-bit arithmetic is not any slower than 16-bit arithmetic, nor would 64-bit arithmetic be much slower, other than if we need to be doing so much of the longer bitwidth arithmetic that we are loading from main memory too often and this is bottlenecking performance.
The size of main memory (RAM) is small yes, but storage (hard disks, solid state drives) is much, much larger. Hence there are a few things that are important to do in any game engine but particularly block games.
First is that the portion of the entire world that is saved to storage is only a tiny fraction of its theoretical size, because exploring such a large volume (as you established it is extraordinary) takes a long, long time. Another space optimisation that other engines such as
Craft make is that only modified chunks are actually recorded to storage. This approach costs time to regenerate chunks though, so for decently complex Minetest worlds, loading from storage is preferred over generating the mapblocks again, due in parts to CPU usage of generating mapblocks but also so CPU isn't hogged doing mapgen over and over again.
Your point about world size actually starts to become a valid one when you realise that given enough horizontal space to expand to, players of block games are well-known to
actually go hundreds of thousands or even millions of blocks in one direction, and this gets the world file into the terabytes in size range. Server admins will still want to limit world size according to available storage, including settings that disable mapgen beyond those limits.
A second optimisation that is critical for block game engines is that in case of any real exploration ever having been done on your world, most of those mapblocks are not even loaded at any given time. The server has a configurable radius around each player over which it will simulate what is happening in those mapblocks. Some engines also have ways to simulate more such as 'chunk loaders' which force an area to always be loaded, but this exception proves the general rule.
Thirdly, out of those mapblocks that have been recently loaded, some are kept around, cached in main memory, for a while after they have been loaded even if that area is left. This makes loading recently-travelled-to areas quicker. Minetest then has a configurable maximum number of these mapblocks to keep in memory, and a timeout after which they will be unloaded regardless of the limit.
bzt wrote: ↑Thu Nov 11, 2021 19:34
Have you ever considered that Minecraft is limited to just a fraction of what Minetest can do?
5120 x 5120 x 320 in best case (with "large" world). And that a typical Minecraft world is even smaller, only 864 x 864 x 320? Think about that too.
I must point out here that there is a massive disclaimer at the top of that page that says that it refers specifically and only to Legacy Console and Nintendo 3DS editions. To claim it applies to anything else like Java or Bedrock editions is a misunderstanding. I can't blame you for clicking on that page if you searched for "Minecraft world size" in your search engine and clicked on that and thought it was what you were after. It's a failing of search engines and the Minecraft wiki in this case that you didn't get the correct information for Java/Bedrock. Now here is a relevant reference that will explain as I said earlier that Minecraft's actual world size is 60 million blocks in the horizontal:
World border.
bzt wrote: ↑Thu Nov 11, 2021 19:34
Blockhead wrote: ↑Thu Nov 11, 2021 06:34
It should be as big as you want to make it
How? If you want a bigger world, first I would like to hear your opinion on which data structure and indexing algorithm to use for the nodes (Minetest uses
octrees). Take it from an expert, it is quite an achievement and an incredible feat that Minetest can handle 65536 x 65536 x 65536 big world in real-time!
I have already established how it doesn't simulate the whole world the whole time, only a tiny fraction.
Indexing mapblocks in Minetest is and shall remain the job of the database system that stores all of them into the database for us. To increase world size then, we must refactor
the data structure that holds mapblock coordinates to have larger fields for x and z. This isn't the only possible refactoring, but I will discuss that later.
As is I think that each dimension has 12 bits (log2(30192*2) = 15.88)) of information, and these are packed into a 64-bit integer. My calculation is as follows:
Mapblock coordinates must be multiplied by 16 to retrieve the real coordinates.
The world size is -30912 to +30912. 30912*2 = 61824.
61824 / 16 = 3864
log2(3864) = 11.91
So each dimension has 12 bits of information packed into that data structure.
One naive way to refactor would be to just expand each dimension as far as our 64 bit data structure allows. However, minetest uses a v3s16 (vector of 3 signed 16-bit integers) extensively for its full-coordinate system (this system is the in-engine representation of coordinates as opposed to the in-database mapblock coordinate system I previously described) so expanding beyond 16 bits would require more refactoring. However, quadrupling the size of each coordinate I feel wouldn't add enough space to make the change worth it. A v3s32 would probably be enough though.
64/3 = 21.333 so up to 21 bits in each of these would still fit into a 64-bit packed data type. 2^21*16 = 33,554,432. This would fit snugly into the v3s32 data type as well. So our world would be a bit over half of Minecraft's size in the horizontal and vertical and probably too vast in the vertical, unless we insist on keeping the vertical space for dimension hacks.
You can divide these bits however you want really. Getting more drastic, you could add more horizontal space by sacrificing vertical space (and I think we already have enough vertical space), and end up with a world much larger than Minecraft's. If you wanted to be tricky you could allocate some of the bits to a 4th dimension, but then you'd need to refactor Minetest engine to properly support dimensions. This has been discussed but never followed through with.
One division of the whole 64 bits I might suggest is 23 bits in each of x and z, 12 in y, and 6 in D. This totals horizontal space of 8.3 million in the horizontals, existing 60k horizontal which is generous and backwards-compatible, and 64 dimensions which is generous enough for Minecraft-like games that only have 3 builtin and maybe a dozen modded dimensions. Only if you wanted to do more advanced things like using dimensions as swap space, or having per-user dimensions or procedurally-generated dimensions might you have a problem with this.
I have discussed the problems and potential solutions but I will not insist that one particular is 'correct'. I think if such a big undertaking is actually committed to, it will only be after consensus is established about how to do it. I can't established consensus on my own. The only thing I would say for sure is that we need to move to v3s32 for coordinates and use more bits for at least x and z in the mapblock coordinate data structure, with the exact number of bits extra and whether we allocate bits to a 4th dimension to be decided by consensus.
Edit: One thing I neglected to discuss was what happens to coordinates if we add a fourth dimension. There are a few solutions, either include it in the coordinate vector and make it a v4s32, a specialised v3s32+s8 or similar, or leave it out of most of the code where possible and only where it is relevant provide it as a second function parameter/struct member or similar.