Example code for finding lists of structures

[Ldalvik]

I can't seem to figure out what functions allow you to search for more than one structure at a time. I am attempting to search for nearby villages (ideally from a set coordinate, but not needed) from a specific seed. I'm essentially trying to create a text-like version of your cubiome viewer, as I just want to generate a list of coordinates to certain structures.

This is more of a technical question and not an issue, but I couldn't find any form of contact to ask you directly. Please let me know if there's a better way to keep in touch with you.

[Cubitect]

There isn't a designated function to collect the structures in an area, but here is an example how you might do this:

#include "finders.h"
#include <stdio.h>
#include <math.h>

void findStructures(int structureType, int mc, int dim, uint64_t seed,
    int x0, int z0, int x1, int z1)
{
    // set up a biome generator
    Generator g;
    setupGenerator(&g, mc, 0);
    applySeed(&g, dim, seed);

    // ignore this if you are not looking for end cities
    SurfaceNoise sn;
    if (structureType == End_City)
        initSurfaceNoiseEnd(&sn, seed);

    StructureConfig sconf;
    if (!getStructureConfig(structureType, mc, &sconf))
        return; // bad version or structure

    // segment area into structure regions
    double blocksPerRegion = sconf.regionSize * 16.0;
    int rx0 = (int) floor(x0 / blocksPerRegion);
    int rz0 = (int) floor(z0 / blocksPerRegion);
    int rx1 = (int) ceil(x1 / blocksPerRegion);
    int rz1 = (int) ceil(z1 / blocksPerRegion);
    int i, j;

    for (j = rz0; j <= rz1; j++)
    {
        for (i = rx0; i <= rx1; i++)
        {   // check the structure generation attempt in region (i, j)
            Pos pos;
            if (!getStructurePos(structureType, mc, seed, i, j, &pos))
                continue; // this region is not suitable
            if (pos.x < x0 || pos.x > x1 || pos.z < z0 || pos.z > z1)
                continue; // structure is outside the specified area
            if (!isViableStructurePos(structureType, &g, pos.x, pos.z, 0))
                continue; // biomes are not viable
            if (structureType == End_City)
            {   // end cities have a dedicated terrain checker
                if (!isViableEndCityTerrain(&g.en, &sn, pos.x, pos.z))
                    continue;
            }
            else if (mc >= MC_1_18)
            {   // some structures in 1.18+ depend on the terrain
                if (!isViableStructureTerrain(structureType, &g, pos.x, pos.z))
                    continue;
            }
            printf("%d, %d\n", pos.x, pos.z);
        }
    }
}

int main()
{
    uint64_t seed = 123;
    int r = 2000;
    printf("Villages within %d blocks:\n", r);
    findStructures(Village, MC_1_19, DIM_OVERWORLD, seed, -r, -r, +r, +r);
    return 0;
}

[Ldalvik]

This is exactly what i needed, thank you so much. i’m not familiar with any of the crazy algorithms or math related stuff for generating structures, so it’s cool to see some of the outside stuff needed to generate accurate coordinates.

[Ldalvik]

Sorry, one last thing. how could i specify a center to point to search from? could i just add additional parameters and have it start at the coordinates i want instead of iterating from 0,0?

[Cubitect]

The x0, z0 and x1, z1 arguments respectively specify the lower and upper coordinate limits of a rectangular area. You can set whatever you want here as long as x0 <= x1 and z0 <= z1.

[Ldalvik]

Awesome thank you! I've been having a lot of fun with this library, is there a better way to message you by any chance? I don't think I'll need anymore help since what I wanted was pretty simple, but I'd like to keep you updated on what I'm using the library for.

Edit: Do I use similar for loops to find biomes at X/Y/Z?

[Cubitect]

Afraid Github it the only method that I check at a semi-regular bases. You can fork cubiomes if you like, chances are that I'll see your project then.

Usually you'll just want generate the area in as a whole, but you can split it up however you like. The structure generation code segments the area into structure regions to loop over, because that is how the structures generate. The distribution is briefly explained in the readme, but there is also a pretty good explanation on the wiki site for Nether Fortresses. I'm not sure why this is only explained for Fortresses, since the same concept applies most other structures as well, though usually with a region size of 512x512 blocks.

There is an example in the readme how you can get the biomes in an area. However, if you want to search for biomes there are specialized biome filter functions which make use of whatever optimization it can, and will usually be much faster:

int main()
{
    int mc = MC_1_17;
    int required[] = {
        taiga, swamp, mushroom_fields, jungle, dark_forest, savanna, badlands
    };

    BiomeFilter bf;
    setupBiomeFilter(
        &bf, mc, 0, required, sizeof(required)/sizeof(int), NULL, 0, NULL, 0);

    Generator g;
    setupGenerator(&g, mc, 0);

    Range r = {4, -256, -256, 512, 512}; // 1024 blocks radius
    uint64_t seed;
    for (seed = 0; ; seed++)
    {
        if (checkForBiomes(&g, 0, r, DIM_OVERWORLD, seed, &bf, 0) > 0)
        {
            printf("Biomes are presend in seed %" PRId64 "\n", seed);
            break;
        }
    }
    return 0;
}

[Ldalvik]

Perfect. I’ll be sure to fork and upload my code as well. Last thing, can i get the coordinates of the biome using the code above? If i were to supply only a single biome for example. My project won’t actually be using any sort of seed searching, it’s more so just checking a seed that you supply for structures and biomes, similar to how your cubiomes viewer works. i’m just messing with it so i can get the raw data, and use it in my Java project for more functionality (i haven’t used C since highschool, and it’s a little too low-level for me haha)

[Cubitect]

The biome filter is primarily meant to check seeds for a set of biome requirements (inclusions/exclusions). If you want to know how the biomes are distributed in a given seed, you should just generate the area with applySeed() and genBiomes() instead of checkForBiomes(), like in the readme example. You can then examine the biomeIds in whatever way you like.

[Ldalvik]

That's actually what I was trying to do, but as someone who isn't the best at math, I couldn't figure out how to determine coordinates from the biomesId array, even after looking through the source code of cubiomes and cubiomes-viewer.

This is as far as I got, it works, but not very easy to work with when im not entirely sure what im doing haha.

 unsigned int i, j;
    int containsInvalidBiomes = 0;
    for (j = 0; j < r.sy; j++)
    {
        for (i = 0; i < r.sx; i++)
        {
            int id = biomeIds[j * r.sx + i];

            if (id < 0 || id >= 256)
            {
                containsInvalidBiomes = 1;
            }
            else
            {
                printf("%s", biome2str(g.mc, id));
            }
        }
    }  

[Cubitect]

The ids are represented in a flattened 2D array. For example a 6 by 4 area has indices that are distributed like this:

  |  0  1  2  3  4  5 | X
--+-------------------+
0 |  0  1  2  3  4  5 |
1 |  6  7  8  9 10 11 |
2 | 12 13 14 15 16 17 |
3 | 18 19 20 21 22 23 |
--+-------------------+
Z

This is also how the memory is laid out when you create a normal 2D array in C:

int array2d[3][2] = { {0,1}, {2,3}, {4,5} };
int *p = &array2d[0][0]; // get a pointer to the memory of array2d
int i;
for (i = 0; i < 3*2; i++)
    printf("%d\n", p[i]);

However, an important thing to look out for is that we are using X and Z for the first 2 axes and not Y. That is because we are essentially looking down onto the world from above and Minecraft represents the vertical direction with Y, which leaves the X and Z axes when viewed as a 2D map.

Your code looks almost correct, except for the r.sy which should be r.sz.

[Ldalvik]

That helped a lot, i managed to get it working, but only to an extent. Im able to get X,Z but I'm stuck on adding the Y coordinate. You can probably see what im trying to do from the code; I want to scan a range around a specified coordinate and height. This is my (non)-working code after trying to add the Y coordinate:

    Range r;
    int range = 5;
    r.scale = 16;

    r.x = 4500, r.z = 1500;     // position (x,z)
    r.sx = range, r.sz = range; // size (width,height)
    r.y = 100, r.sy = 1;        // height?

    int *biomeIds = allocCache(&g, r);
    genBiomes(&g, biomeIds, r);

    int x0 = r.x - range;
    int z0 = r.z - range;
    int x1 = r.x + range;
    int z1 = r.z + range;

    int i_x, i_y, i_z;

    for (i_x = x0; i_x < x1; i_x++)
    {
        for (i_z = z0; i_z < z1; i_z++)
        {
            for (i_y = 0; i_y < r.y; i_y++)
            {
                int id = biomeIds[i_y * r.sx * r.sz + i_z * r.sx + i_x];

                printf("%s at X:%d,Y:%d,Z:%d\n", biome2str(g.mc, id), i_x, i_y, i_z);
            }
        }
    }

Once again, thanks for all the help. It's nice to get back into C :) Your library is the only thing keeping me wanting to learn more.

[Cubitect]

Your indexing looks okay, but the range is used wrong.

The range structure defines the start coordinates: x, z and y, which sets the lower coordinate corner of a cuboid (3d rectangle) and its size via the sx, sz and sy members. So the resulting cuboid spans the coordinates (x,y,z) to (x+sx-1, y+sy-1, z+sz-1).

The i_x, i_z, and i_y iteration variables index the memory of that cuboid, and not the original coordinates, so they can only have values between 0 and the size in that direction, so for (i_x = 0; i_x < r.sx; i_x++) etc.

A given index [i_y][i_z][i_x] inside the cuboid (which looks flattened like [i_y*r.sx*r.sz + i_z*r.sx + i_x]) consequently represents an offset from the lower corner of the cuboid: (x,y,z), so the index corresponds to coordinate (x+i_x, y+i_y, z+i_z).

What these coordinates actually mean in terms of blocks is complicated a bit by the scale factor. For a scale of 1 or 4 each coordinate represents that many blocks for all axes. For a scale of 16 or above, however, the vertical direction remains at scale 4.

Example:

    Range r;
    r.scale = 16;

    // horizontal axes @ scale 1:16
    r.x = -4, r.z = -4; // position (x, z)
    r.sx = 8, r.sz = 8; // size (width, height), representing 128 blocks

    // vertical axis @ scale 1:4
    r.y = -16; // vertical position
    r.sy = 96; // vertical height

    int *biomeIds = allocCache(&g, r);
    genBiomes(&g, biomeIds, r);

    int i_x, i_y, i_z;

    for (i_y = 0; i_y < r.sy; i_y++)
    {
        for (i_z = 0; i_z < r.sz; i_z++)
        {
            for (i_x = 0; i_x < r.sx; i_x++)
            {
                int index = i_y * r.sx * r.sz + i_z * r.sx + i_x;
                int id = biomeIds[index];
                // scaled coordinate for this index:
                int x = r.x+i_x;
                int z = r.z+i_z;
                int y = r.y+i_y;
                // which represents the block position:
                int bx = x * r.scale;
                int bz = z * r.scale;
                int by = y * (r.scale == 1 ? 1 : 4);

                printf(
                    "index = [%4d] (%3d,%3d,%3d), "
                    "scaled (x,y,z) = (%2d,%3d,%2d) "
                    "=> block (%3d,%3d,%3d) has %s\n",
                    index, i_x, i_y, i_z, x, y, z, bx, by, bz,
                    biome2str(g.mc, id)
                    );
            }
        }
    }

However, I want to point out that biomes do not vary in the vertical direction, even in 1.18 and 1.19, except for cave biomes.

[Ldalvik]

The scaling is what i think i have to look more into, but thank you for the code snippet to get me started. I also didn't realize the biomes didnt change no matter the Y coordinate, but does this apply to things like lush caves? if i want to search for a lush cave from -50 to -64, would i set the variables like so? r.y = -64, r.sy = -50

[Cubitect]

As I said, cave biomes, i.e. lush caves, dripstone caves and the deep dark, are the only biomes that vary with height.

The size (sx, sy, sz) should always be positive. Negative sizes do not make sense.

I would recommend you just stick to a scale of 4, since that is the scale at which the game generates biomes and which makes the most sense if you are dealing with 1.18+ generation. r.y = -16 is the bottom of the world in this case.

[Ldalvik]

Thanks for the help, I'm starting to understand it better. Have a good one!

[Ldalvik]

I'm confused as to what these scaled coordinates and block coordinates mean, im getting very inconsistent results when using a scale of 4.

[Cubitect]

The game, for the most part, does not generate biomes for every block, since that would be too slow. Instead, biomes are generated for only every fourth block. The game does this by generating biomes at biome coordinates, where every position can be roughly thought of as representing a 4x4x4 cube of block coordinates.

Cubiomes refers to these biome coordinates as scale 1:4 (or scale=4), while block coordinates are at scale 1:1.

More precisely, when the game needs the biome at a given block, it will add a small random offset (between -2 and +1) and then divide each coordinate by 4, rounded down. This gives you the biome coordinates that are fed into the biome generation.

If you use cubiomes to generate a range at r.scale=4, it will treat the r.x, r.z, r.sx, r.sz, r.y and r.sy members as biome coodinates, generating a cuboid that starts at (x,y,z) and has size (sx,sy,sz). With r.scale=1, cubiomes instead treats the members as block coordinates, and will apply all the scaling and offsets such that every position is directly mapped to a block.

Since you asked before, there is actually a new function which is essentially a biome finder: getBiomeCenters(). It may still be subject to change, but currently it can be used like this:

// (>>2 is an efficient way to floor divide integers by 4)
int rad = 4000>>2; // 4000 block radius = 1000 @ scale 4
Range r = {4, -rad, -rad, 2*rad, 2*rad, 320>>2, 1};
Pos centers[100];
int minarea = 1;
int tolerance = 8;
int n = getBiomeCenters(centers, NULL, 100, &g, r, swamp, minarea, tolerance, NULL);
for (i = 0; i < n; i++)
    printf("swamp @ %d %d\n", centers[i].x, centers[i].z);

I also had a quick look at your fork and there are a couple of things that I noticed. First, it is not a good idea to pass the Generator objects by value. The setupGenerator() function sets pointers that refer to parts of the object itself, which means that you'll get undefined behavior if either copy is modified afterwards. The second is a bit more of a general point regarding memory management in C: It's almost never a good idea to return a pointer to a dynamically allocated object, unless it's specifically an allocation function, because the caller likely doesn't know how to clean it up. I also noticed the return with a digit check conditional which seems like nonsense to me. I'm guessing you were trying to deal with the uninitialized garbage when the function never reaches the initialization code. You should probably use calloc() instead of malloc() to get zero-initialized memory. However, the dynamic allocation seems misguided for this use case anyway. If you must return a string, you can define a static char array instead. Better still, you can allocate memory at the call site and pass a pointer argument to the function for it to fill.