Add support for Alpha 1.2 - Beta 1.7 biome system

[KaiSandstrom]

The aim of this PR is to eventually add support for the old pre- Beta 1.8 biome system to Cubiomes. The purpose of posting this as a draft is to allow maintainers to easily view changes as they happen, and suggest improvements or intervene if they so choose.

Somewhat similarly to the modern 1.18+ biome system, the old beta biome system uses climate noise maps to determine biomes; however, these older versions use simplex noise instead of regular Perlin noise.

The existing PerlinNoise and OctaveNoise structs can be re-used, as can the existing perlinInit and sampleSimplex2D functions. Due to the different way these older versions handle lacunarity and amplitude across octaves, a new variant of octaveInit will be needed in order to set these parameters correctly. A modified variant of sampleOctave will also be included, which adds each octave's PerlinNoise struct's random values 'a' and 'b' onto ax and az respectively, ignores y, and uses calls to sampleSimplex2D instead of samplePerlin.

Biomes that have no direct equivalent in modern versions of Minecraft will be mapped to existing biome IDs and will use those biomes' colors.

As it currently sits, the code in this fork produces block-accurate climate maps for Beta 1.7 (without oceans). The accuracy is tested against a Java test program using the original MCP'd Minecraft code from Beta 1.7.3, as well as manually checking desert borders in the game itself.

The most difficult task will be determining land vs. water:

Technically speaking, there were no ocean or river biomes in these old versions. Water placement was determined purely by terrain height variation, with any areas under sea level becoming oceans/lakes. However, the climate map based purely on temperature and humidity is an insufficient representation of a Minecraft world, as aside from water in tundra and taiga biomes becoming frozen, no biome-specific features generate in water.

Determining where oceans generate in these old versions will require sampling terrain noise. I currently have a working Java test program made from the original Minecraft ChunkProviderGenerate code that produces accurate ocean maps, and I'm working on cutting it down as much as possible before porting it to C and attempting to make use of the existing getSurfaceHeight.

[Cubitect]

I'm not very familiar with these old versions, so all this is open to discussion...

I'm wondering, existed biome IDs back then? Did the biomes get stored in the level file at all? If so, we could also check how biomes get converted when upgrading a world. For the 1.17 -> 1.18 update I did something similar to decide if a biome should get a new biome ID or not.

For the old temperature and humidity noise, there could be a new BetaNoise structure that can be unionized in the Generator with the overworld BiomeNoise and LayerStack.

On the interface side, I'm leaning towards solving the ocean/water issue by introducing a new flag for the generator. (Maybe FORCE_BETA_OCEAN, or as a negative BETA_NO_WATER, keeping in mind that the default is a zero value though.) When set, the generation could override the biomes with ocean where the height falls below sea level. However, this will require that any data required for the surface height also is part of the Generator or BetaNoise.

The surface height can still be determined with mapApproxHeight, dropping the SurfaceNoise argument (i.e. allow NULL for beta 1.7). The main reason why SurfaceNoise is not part of the Generator structure is because of it's byte size.

[KaiSandstrom]

Biome IDs did not exist back then. The lookup table contained BiomeGenBase object variables, each of which was set to a static final instance of each biome's subclass. For this reason, I'm mapping old Beta biomes to existing biome IDs -- although perhaps they could be split off into separate new biome IDs to allow users to change their colors independent of the newer biomes associated with those IDs.

Even though biome IDs were introduced with the layered system in Beta 1.8, biomes were not stored in world saves until the introduction of the Anvil format in 1.2. Instead, biome values were generated on-the-fly as saved chunks were loaded. Players updating from Beta 1.7.3 to Beta 1.8.1 found their existing worlds' biomes completely changed, with drastically different grass/leaves colors, rain and melting snow in what used to be a tundra, etc.

This lack of persistent biome data even affected the update from Beta 1.8 to Release 1.0 -- oceans were in different places and new ice plains and mushroom islands were added, so even though the patchwork quilt of biomes placed in GenLayerBiome at 1:256 remained the same, players often had existing chunks turn into ocean or tundra. This is pure speculation, but I suspect that a major force behind the creation of the Anvil format was a desire by Mojang to prevent another biome corruption when jungles were added in 1.2, shuffling the 1:256 continental biomes.

As for the temperature and humidity noise generators, my original plan was to modify BiomeNoise and unionize an array of OctaveNoise with the existing DoublePerlinNoise array and spline variables -- that would allow me to re-use some functions that process BiomeNoise, only introducing new functions for Beta biomes when necessary. However, I can easily change this to a new struct unionized in Generator, with its own set of Beta-specific functions.

Now, about the ocean height problem -- Unlike all later biome systems, the old Beta biome system operates natively at a 1:1 scale. The 1:4 scale map is created the same way the other higher scales are: sampling midpoints. For this reason, my ultimate goal is to get surface heights that are block-accurate just like the land biomes.

I haven't studied mapApproxHeight enough to know if it's suitable for this purpose, but if it is, it will require significant modification. Before Beta 1.8, biomes did not have depth and scale values to influence terrain height. Terrain height was nearly completely independent from biome, with only the humidity value affecting terrain height variation. Humidity varies block to block even within the same biome.

I've been messing around with Minecraft b1.7.3's chunk generation code, and I've found that the getSurfaceHeight function used for End mapping is very similar, so if a modified mapApproxHeight isn't suitable, I may base a final solution on getSurfaceHeight. In order to be practically efficient, this will likely require strategic use of dynamically allocated and deallocated heap memory along with generation of 4x4 sections in a diagonal pattern starting from the southeast.

[Cubitect]

I think a new Noise structure would be preferable unless the BiomeNoise fits very well to the needs. The Generator structure/union was more or less intended as the hub that switches to the appropriate data, while genBiomes() switches to the appropriate functions. BiomeNoise is also pretty large and I'm not sure how many functions you hope to reuse. Most of the code regarding BiomeNoise is very 1.18+ specific.

Sounds like a 1:1 height map would make sense to have first. For newer pre-1.18 versions a function like that would also probably make use getSurfaceHeight. The mapApproxHeight function (for 1.17-) is mostly a simplification and optimization of the full 1:1 generation, by removing the up-scaling done with getSurfaceHeight (which conveniently leaves a scale of 1:4 that matches the biomes) and by only generating the sections required to find the surface.

[KaiSandstrom]

I recently pushed a new commit, which adds Beta 1.7 climate mapping functionality without oceans. There is some placeholder code in place for ocean generation. The additions incorporate the design choices you outlined above, including using the union in the Generator struct to switch between LayerStack, BiomeNoise, and BiomeNoiseBeta, and using genBiomes to switch between different generation functions. I made a test build of Cubiomes Viewer using my code and confirmed that it works smoothly at all scales.

If you get the chance to look through the commit notes and code changes, I'd appreciate any feedback you may have. Some potential concerns:

Currently, I have a SurfaceNoiseBeta struct included in Generator. SurfaceNoiseBeta is about 3K larger than SurfaceNoise, and the inclusion of the SurfaceNoiseBeta struct drastically increases the size of Generator. Would you prefer that the SurfaceNoiseBeta be allocated in genBiomes only when a pre-B1.8 version is selected in order to save space in Generator?

Also, I wrote sampleBiomeNoiseBeta to be able to return temperature and humidity individually as integers just like sampleBiomeNoise, but since the original double climate values vary from 0 to 1 instead of -1 to 1, the resulting integers range from 0 to 10000 instead of -10000 to 10000. I could have mapped the climate values to this expanded range, but I chose not to so the values remain recognizable -- For example, the biome is always tundra when temperature is below 0.1, which becomes 1000 and in this format is easily recognizable as the tundra cutoff. If I remapped the values, this would become -8000, which is much less recognizable to someone familiar with the biome cutoffs. For the temperature and humidity map views to eventually work properly in Cubiomes Viewer, this different range will need to be taken into account, otherwise low areas that are supposed to be black will show up gray.

On the topic of ocean mapping, there's a design choice that needs to be made. I currently have a working Java test program using Minecraft's code that makes ocean maps by sampling the block at y=64. This means that if the original raw pre-decorator terrain has water at y=64, it will show as ocean regardless of what exists at higher y-levels. In contrast, getSurfaceHeight appears to find the y-level of the first solid block from the top of the world, even if there's water at sea level. These two different approaches will lead to subtle differences in ocean mapping. The vast majority of coastlines will be exactly the same, but when dealing with the kind of shattered terrain that these old versions are often remembered for (such as near spawn in the famous seed "Glacier"), large overhangs can generate over water.

Currently, I'm leaning towards only sampling at sea level, as this will require far less noise generation and I'm anticipating that getting good performance will be an issue. I plan to try out both approaches though, and compare the final maps.

[KaiSandstrom]

I'm getting ready to push another commit later today or tomorrow. In addition to removing the SurfaceNoiseBeta struct from the Generator, instead declaring it and initializing it in genBiomes(), I've implemented initSurfaceNoiseBeta() and written all new functions needed to generate raw terrain noise. The functions that process the noise into surface noise columns and determine the block at sea level are not yet implemented.

In addition to the usual octmin, octmax, and octmain noise (which are initialized differently in these versions), there are two additional Perlin noise maps used for terrain generation. These are 2D rather than 3D, and I've temporarily named them octA and octB. Proper 2D noise can be obtained from samplePerlin() by manipulating the ay input such that d2 becomes 0. I've modified samplePerlin() slightly to skip unnecessary lerps when d2 is 0, in order to improve performance when sampling 2D noise.

As for the method of determining oceans, I'm leaning heavily towards only sampling the block at y=64. Good performance will make or break the practicality of adding support for these early versions, and sampling noise columns from the top of the world all the way down to sea level would mean spending more than 4 times longer cranking out 3D Perlin noise.

In order to optimize performance at scale 1, 2, and 4, the raw noise outputs used to calculate adjacent noise columns will be saved so they can be re-used later. Extra cache will be allocated and used for storing pointers to dynamically-allocated structs containing 8 doubles each. These doubles will be used to calculate the final noise columns processed to sample the block at sea level, and memory for structs that won't be re-used again will be freed. The reason for storing the noise before processing into columns is that the processing is affected by temperature and humidity values, which will be different when columns along chunk borders are re-used. 4x4 regions will be processed diagonally so the size of the extra cache is determined by the minimum of height and width.

At scales 8 and above, no noise can be re-used, so each sample will generate fresh noise columns.

[KaiSandstrom]

I've now marked this PR as open, as ocean-finding for Beta 1.7 is now functional. There are still a few small changes I plan to make in the next few days for the sake of consistency with the rest of the program -- for example, copy biome values into extra cache when sy != 1.

Note that surface height detection is currently not supported for this version, as the noise column processing functions only find the block at sea level.

I made a test build of Cubiomes Viewer using this code, and while it does function, the region images are quite slow to appear even when zoomed out. I'm open to any suggestions that could speed up the code -- ideally without sacrificing the accuracy of ocean detection.

[Cubitect]

Only just got the chance to properly review everything. Looks great, with a very detailed report. Thanks.

Mapping the noise to the integer range [0, 10000] for consistency seems like a good idea to me. The 1.18 climate noise isn't actually meaningfully bounded anyway. In fact there is some interesting world generation when the weirdness falls outside the range [-18000, 18000] for versions 1.19.0 - 1.19.2.

After giving it some more thought, I think I will allocate some new biome IDs in the 0 to 63 value range for the old beta biomes. I believe that might simplify some biome finder code later on. Also seeing that SurfaceNoise and SurfaceNoiseBeta look indeed quite similar in size and form, they can probably be merged at some point.

For the surface finding code, I'll happily merge the current version, but as you have pointed out it probably needs some work on better integration and performance. In particular scale=4 should be performant and may have some implementation leeway, since we can more or less arbitrarily define what accurate means within 4 blocks. Maybe there is some bilinear interpolation that can be done to speed things up, I'll have to check and test when I get the chance. The code only needs to support scale values that are a power of 4, so I wouldn't worry too much about scales 2 and 8 if the code can be simpler.

Regarding some of the new functions: isn't sampleOctave2D(noise, x, z) the same as sampleOctaveAmp(noise, x, 0, z, 0, 0, 1)? Unless there is a noticeable performance reason, I wouldn't add a new function for this. Also I don't see the column noise functions and sampleBlocks being relevant to the user so I don't think they need to be exposed in the header.

One thing I noticed: are you sure the usage of x/4 and z/4 are correct for negative coordinates? Division of -3 and 3 will all round to zero (and modulo yields negative values with negative input). Usually code like this uses a right bit-shift which is faster and analogous to a floor division.

[KaiSandstrom]

Regarding sampleOctaveAmp() -- I will admit that I didn't look into this function and just assumed that no compatible method of sampling 2D Perlin noise existed. My mistake! sampleOctave2D() can be removed and replaced with a call to sampleOctaveAmp() with the arguments you listed.

I did consider omitting those internal functions from the header, like how most functions in biome_tree.c are hidden (and use snake case), but I held off on doing this because there are other functions in layers.c that are only used internally and was unsure how you would want this approached. But now that you've said they should be left out of the header, they should be left out of the header.

As for the division with negative coordinates -- I did wrap the divisions that find cx1 and cz1 in calls to floor() for exactly this reason, but I now see that I failed to do this at lines 1720-1721 in layers.c when finding the noise column climate coordinates. As you point out, these divisions should all be changed to bit shifts. I also see the problem in these same lines with the modulo operations when x or z is negative. I'll replace them with something like (x % 4 + 4) % 4, etc.

[Cubitect]

Seeing that modulo expression, I'd like to offer some friendly performance advice that might also help with the optimization: An expression like (x % 4 + 4) % 4 is equivalent to x & 3, and (int) floor((double) x / 4.0) is functionally equivalent to x >> 2.

Integer division is among the slowest instructions on a CPU and takes around 40-90 cycles and clobbers three registers. For reference, a multiplication just takes 3 cycles, and simple addition as well as bit-operations can often execute 3 times per cycle (when queued suitably). Likewise, invoking a function call and moving a variable between the integer and floating point units can be pretty expensive. The compiler may be smart enough to optimize some of these away, but I wouldn't count on it. Especially, since the compiler is sometimes not allowed to make certain optimizations to not alter some edge case behavior.

[KaiSandstrom]

Ah, thanks for the tip! Now that you point it out, x & 3 makes perfect sense to me given how negatives are represented in binary. I'll make these changes and open a new PR tomorrow, unless you'd prefer to do it yourself.

[Cubitect]

I made an attempt to simplify some of the code, which re-formatted a fair chunk of it, and made two optimizations for scales 4 and above which trade a little bit of accuracy for speed. This includes sampling the column noise only once and skipping the interpolation, as well as dropping noise octaves which have a period that is smaller than the scale size. I wasn't really able to improve the performance for scale 1:1.

[KaiSandstrom]

These seem like sensible changes. I would like to give some feedback:

First of all, there are some very slight differences at 1:1 scale: in a 4096x4096 region, 33 pixels out of more than 16 million were different compared to the previous code. I'm just bringing this up in case the reason for this change is readily apparent, otherwise I doubt anyone will ever notice. I wouldn't have noticed if I hadn't programmatically compared the images and searched for different pixels.

Like you pointed out earlier, "accuracy" is relative at higher scales since the higher scales are obtained by sampling midpoints; however, the inaccuracies caused by these optimizations tend to have some characteristics that could perhaps be improved upon.

From my quick observations, perhaps the most glaring issue occurs only at 1:4 scale: coastlines appear to be shifted in the positive-x, positive-z direction compared to the pure sampling method used before.

Another issue, perhaps more difficult to address while maintaining speed, is that the inaccuracies caused by the optimization tend to favor too much water over too much land, which is especially noticeable in inland lakes.

The following images represent a 4096x4096 region at 1:4 scale, with the top-left block at 6850, -5400. The first image was generated by the previous code, the second was generated by the current code, and the third is a diff of the two. When rapidly flipping between the two, the slight southeastward shift of landmasses is readily apparent.

[Cubitect]

I simplified some of the constant expressions, which may have caused the slight differences at scale 1:1, but I'll have to investigate. The coast offset can probably be improved by sampling in-between the 4 columns, rather than using the first original column. The excess ocean is a trade-off from the octave trimming. Maybe it can be lessened with another offset, but I suspect it can't easily be improved without adding octaves back in.