search

toolbox4minecraft / amidst

Advanced Minecraft Interface and Data/Structure Tracking
GNU General Public License v3.0
2.14k stars 238 forks source link

Inaccurate End City Location (and specifying whether a ship is present) #933

Open jakeob28 opened 3 years ago

jakeob28 commented 3 years ago

I do not see an issue or pull request claiming to fix this (they only talked about gateways), but please let me know if I missed something.

Current Behavior The locations of end cities are not accurate. This is evidenced both by the amount of "possible end city" locations shown on the map, and the fact that there many likely end cities that are not actually there.

Test confirming above claims: Seed: -4055115850109366791 Amidst version: 4.6 Minecraft version: 1.16.4

Some Amidst "Likely end cities" that do not exist (verified in game and by chunkbase):

Please note that the majority of "Likely end cities" do exist, it's just frustrating that the application is so uncertain even though their locations are able to be reliably determined using another program.

There are also many actual end cities only classified as "Possible end cities", but these are not very useful as most of the possible end cities do not exist.

Requested Behavior Locate end cities accurately, and specify whether they have an elytra or not. This is proven to be possible by Chunkbase, which can accurately determine the location of cities, and whether or non they have an elytra. I briefly tried to look at their algorithm but I don't know much javascript and it's obfuscated.

Thanks so much for everything you guys do, I really appreciate it and hope this doesn't come off as demanding or begging. Let me know if there's any other information I can include to make your jobs easier!

Treer commented 3 years ago

IIRC Accurate end cities requires generating a height-map of the large islands, so doing this would also mean the island shapes become accurate. If memory serves (and if MC hasn't changed) then the way Minecraft generates the large end island may be simple enough that Amidst could generate/transform 3d simplex noise the same way then binary search for where it cross the stone/air threshold.

burgerindividual commented 3 years ago

I couldn't imagine it being efficient at all unless someone figured out how to check for the existence of a specific block, ex: is there an end stone block at the height we need at this x-z coordinate or not. From what I know, this is not possible, and it would require generating a whole column of end stone.

jakeob28 commented 3 years ago

I couldn't imagine it being efficient at all unless someone figured out how to check for the existence of a specific block, ex: is there an end stone block at the height we need at this x-z coordinate or not. From what I know, this is not possible, and it would require generating a whole column of end stone.

Let me know if I'm missing something, but the existence of the Chunkbase seed mapper would make it seem like it's possible to calculate the locations efficiently. It can generate an end map in less than a second on my machine, and using the browser's dev tools I don't see any network requests or socket messages when changing seeds which indicates to me that it's all being calculated locally through the javascript.

As for the algorithm, I could send them an email asking for how it's done, but ideally this would be done by someone familiar with amidst and minecraft generation, as I'd just be passing messages back and forth between this issue and the email thread (since I'm not familiar with mc structure/terrain generation).

Thanks for your time!

Karang commented 3 years ago

I'm also building a tool like this for the PrismarineJS community (bot and servers for Minecraft in Javascript). So I've studied a bit the chunkbase app (and amidst). They use webassembly for biomes and end heightmap generation that's why they are able to compute it fast. It seems that they did the generation in Rust and compiled it to wasm.

jakeob28 commented 3 years ago

I'm also building a tool like this for the PrismarineJS community (bot and servers for Minecraft in Javascript). So I've studied a bit the chunkbase app (and amidst). They use webassembly for biomes and end heightmap generation that's why they are able to compute it fast. It seems that they did the generation in Rust and compiled it to wasm.

Interesting, that would certainly help with quick computations. I didn't see any .wasm files in the source, but I don't know enough about webassembly to know if it can be done without those.

Even if they used a lower level language like rust to generate heightmaps, I would imagine this would still be possible to do with reasonable efficiency in Java (I would think that even if there's some GC overhead, if it was done in another thread it would still be able to load reasonably quickly).

@Karang, were you able to work out the algorithm for how these heightmaps were generated? I'm not an admist dev so maybe one of the contributors on this project might already know how to implement it, but otherwise it'd probably help to have a reference (if you already have some code from other projects)

Karang commented 3 years ago

I'm not to that part yet (just got the overworld biome generation and strongholds for now), but here is the function that generate the endCity POI in chunkbase: https://gist.github.com/extremeheat/41cbef55c5e8d8e80ed0279859c72ce8#file-chunkbase-js-L8413

buildHeightmap is a call to the wasm module: https://gist.github.com/extremeheat/41cbef55c5e8d8e80ed0279859c72ce8#file-chunkbase-js-L5444

same for getBiomeAtChunk: https://gist.github.com/extremeheat/41cbef55c5e8d8e80ed0279859c72ce8#file-chunkbase-js-L7865

If you want the heightmap algorithm, your best bet is to look at mc sources directly.