path: root/src/shared/world/chunk.cc

#include "shared/world/chunk.hh"

namespace shared {
namespace world {

// Because C++ doesn't allow us to iterate over an enum,
// (or get the size of an enum, or get the name of an enum, etc) biomes defined
// in the chunk::biome enum class have to be readded here. Alternatively we
// could use some compiler hack library.
constexpr std::array<enum shared::world::chunk::biome, 7> biome_enums{
    shared::world::chunk::biome::alpine, shared::world::chunk::biome::tundra,
    shared::world::chunk::biome::forest, shared::world::chunk::biome::plains,
    shared::world::chunk::biome::ocean,  shared::world::chunk::biome::islands,
    shared::world::chunk::biome::desert};

static unsigned long get_3d_index(const glm::ivec3& v) noexcept {
#ifndef NDEBUG
    if (chunk::is_outside_chunk(v)) {
        throw std::range_error("bad chunk block coordinate access");
    }
#endif
    return static_cast<unsigned long>(
        v.x + (chunk::WIDTH * (v.y + (chunk::HEIGHT * v.z))));
}

constexpr long
get_biome_index(const enum shared::world::chunk::biome biome) noexcept {
    return std::distance(std::begin(biome_enums),
                         std::ranges::find(biome_enums, biome));
}

block& chunk::get_block(const glm::ivec3& v) noexcept {
    return (*this->blocks)[get_3d_index(v)];
}

const block& chunk::get_block(const glm::ivec3& v) const noexcept {
    return (*this->blocks)[get_3d_index(v)];
}

const char* chunk::get_biome(const int x, const int z) const noexcept {
    const auto biome = (*this->biomes)[(unsigned long)x][(unsigned long)z];
    switch (biome) {
    case chunk::biome::desert:
        return "desert";
    case chunk::biome::islands:
        return "islands";
    case chunk::biome::forest:
        return "forest";
    case chunk::biome::plains:
        return "plains";
    case chunk::biome::ocean:
        return "ocean";
    case chunk::biome::tundra:
        return "tundra";
    case chunk::biome::alpine:
        return "alpine";
    }
}

bool chunk::is_outside_chunk(const glm::ivec3& v) noexcept {
    return (std::min(v.x, v.z) < 0) || (std::max(v.x, v.z) >= WIDTH) ||
           (std::clamp(v.y, 0, HEIGHT - 1) != v.y);
}

shared::math::coords
chunk::get_normalised_chunk(const shared::math::coords& coords, const int x,
                            const int z) noexcept {
    return coords +
           shared::math::coords{(x >= WIDTH) - (x < 0), (z >= WIDTH) - (z < 0)};
}

std::pair<unsigned short, unsigned short>
chunk::get_normalised_coords(const int x, const int z) noexcept {
    return {x + WIDTH * ((x < 0) - (x >= WIDTH)),
            z + WIDTH * ((z < 0) - (z >= WIDTH))};
}

glm::ivec3 chunk::get_normalised_coords(const glm::ivec3& c) noexcept {
    const auto [x, z] = get_normalised_coords(c.x, c.z);
    return {x, c.y, z};
}

// Returns a deterministic random number based on the args.
static unsigned long make_prandom(const uint64_t seed,
                                  const shared::math::coords& coords) noexcept {
    const auto ulx = static_cast<unsigned long>(coords.x);
    const auto ulz = static_cast<unsigned long>(coords.z);
    return std::ranlux48{std::ranlux48{std::ranlux48{seed}() + ulx}() + ulz}();
}

// Returns a pseduorandom gradient vector.
static glm::vec2 make_gvect(const std::uint64_t& seed,
                            const shared::math::coords& coords) noexcept {
    const unsigned long pseudo = make_prandom(seed, coords);
    // Return a vector based on the first four bits of this random number.
    // This vector can point in dirs (x with a + on it) with range [-1, 1].
    const float v1 = ((pseudo & 0b00001111) / 7.5f) - 1.0f;
    const float v2 = (((pseudo & 0b11110000) >> 4) / 7.5f) - 1.0f;
    return {v1, v2};
}

// Returns a distance vector between a vector and a grid position in a chunk.
static glm::vec2 make_dvect(const glm::vec2 v, const unsigned int x,
                            const unsigned int z, const int width) noexcept {
    const auto div = static_cast<float>(width - 1);
    const float v1 = v.x - (static_cast<float>(x) / div);
    const float v2 = v.y - (static_cast<float>(z) / div);
    return {v1, v2};
}

static float fade(const float v) noexcept {
    return v * v * v * (v * (v * 6 - 15) + 10);
}

static std::int32_t reflect_outer(const std::int32_t& n,
                                  const int WIDTH = chunk::WIDTH) noexcept {
    return n < 0 ? ((n - (WIDTH - 1)) / WIDTH) : n / WIDTH;
}

static std::int32_t reflect_inner(const std::int32_t& n,
                                  const int WIDTH = chunk::WIDTH) noexcept {
    return ((n % WIDTH) + WIDTH) % WIDTH;
}

// Moves perlin noise values from the range of [-1.0f, 1.0f] to [0.0f, 1.0f].
// It's more useful to have a perlin layer add nothing at its absolute lowest,
// then it is for a perlin layer to potentially remove 1.0f at its lowest.
static float normalise_perlin(const float perlin) noexcept {
    return 0.5f * (perlin + 1.0f);
}

using chunk_array = std::array<std::array<float, chunk::WIDTH>, chunk::WIDTH>;
using chunk_array_map =
    std::unordered_map<shared::math::coords, chunk_array,
                       decltype(&chunk::hash), decltype(&chunk::equal)>;

// 2D Perlin noise, in which we:
// 1. Define corners of a square as vectors, in this case using 0 or 1.
// 2. Assign pseudorandom normalised gradient vectors to each corner vector.
// 3. Create and iterate through a 2d array, where we:
//    3.1: Generate distance vectors from each corner vector to the cell.
//    3.2: Dot our gradient vectors and distance vectors respectively.
//    3.3: Lerp our bottom and top dot product values by a fade function and x.
//    3.4: Lerp (3.3) via fade function and z. This is the cell result.
// There is an additional step where we make use of "scale" (any s* var). This
// involves moving the requested chunk into a potentially different chunk, and
// accessing a greater level of detail. It's just zoom and enhance.
static chunk_array make_2d_perlin_array(const std::uint64_t& seed,
                                        const shared::math::coords& pos,
                                        const int scale) noexcept {
    constexpr glm::vec2 tr = {1.0f, 1.0f}; // (1)
    constexpr glm::vec2 tl = {0.0f, 1.0f};
    constexpr glm::vec2 bl = {0.0f, 0.0f};
    constexpr glm::vec2 br = {1.0f, 0.0f};

    const int scx = reflect_outer(pos.x, scale);
    const int scz = reflect_outer(pos.z, scale);
    const int swidth = chunk::WIDTH * scale;

    // clang-format off
    const glm::vec2 tr_g = glm::normalize(make_gvect(seed, shared::math::coords{scx, scz})); // (2)
    const glm::vec2 tl_g = glm::normalize(make_gvect(seed, shared::math::coords{scx - 1, scz}));
    const glm::vec2 bl_g = glm::normalize(make_gvect(seed, shared::math::coords{scx - 1, scz - 1}));
    const glm::vec2 br_g = glm::normalize(make_gvect(seed, shared::math::coords{scx, scz - 1}));
    // clang-format on

    chunk_array perlin; // (3)

    const int x_offset = reflect_inner(pos.x, scale) * chunk::WIDTH;
    const int z_offset = reflect_inner(pos.z, scale) * chunk::WIDTH;
    for (auto x = 0u; x < chunk::WIDTH; ++x) {
        const unsigned sx = x + static_cast<unsigned>(x_offset);

        for (auto z = 0u; z < chunk::WIDTH; ++z) {
            const unsigned sz = z + static_cast<unsigned>(z_offset);

            const glm::vec2 tr_d = make_dvect(tr, sx, sz, swidth); // (3.1)
            const glm::vec2 tl_d = make_dvect(tl, sx, sz, swidth);
            const glm::vec2 bl_d = make_dvect(bl, sx, sz, swidth);
            const glm::vec2 br_d = make_dvect(br, sx, sz, swidth);

            const float tr_dp = glm::dot(tr_g, tr_d); // (3.2)
            const float tl_dp = glm::dot(tl_g, tl_d);
            const float bl_dp = glm::dot(bl_g, bl_d);
            const float br_dp = glm::dot(br_g, br_d);

            const float fswidth = static_cast<float>(swidth - 1);
            const float fracx = (static_cast<float>(sx) + 0.5f) / fswidth;
            const float fracz = (static_cast<float>(sz) + 0.5f) / fswidth;
            const float tl_tr = std::lerp(tl_dp, tr_dp, fade(fracx)); // (3.3)
            const float bl_br = std::lerp(bl_dp, br_dp, fade(fracx));

            const float result = std::lerp(tl_tr, bl_br, fade(1.0f - fracz));

            perlin[x][z] = normalise_perlin(result); // (3.4)
        }
    }

    return perlin;
}

static auto array_map_access(const auto& array_map,
                             const shared::math::coords& coords) noexcept {
    return array_map.find(coords)->second;
}

static auto array_map_access(const auto& array_map,
                             const shared::math::coords& coords, const int x,
                             const int z) noexcept {
    const shared::math::coords normalised_coords =
        chunk::get_normalised_chunk(coords, x, z);
    const auto [nx, nz] = chunk::get_normalised_coords(x, z);
    return array_map_access(array_map, normalised_coords)[nx][nz];
}

// We take a std::function that generates a chunk array to fill an unordered
// map with a 3x3 chunk_array contents, where those contents refer to the
// values in the surrounding chunks.
template <typename T>
static auto make_array_map(const std::uint64_t& seed,
                           const shared::math::coords& coords,
                           const T& make_chunk_array_func) noexcept {

    std::unordered_map<shared::math::coords,
                       decltype(make_chunk_array_func(seed, coords)),
                       decltype(&chunk::hash), decltype(&chunk::equal)>
        array_map{9, chunk::hash, chunk::equal};
    for (int x = -1; x <= 1; ++x) {
        for (int z = -1; z <= 1; ++z) {
            const shared::math::coords pos{coords + shared::math::coords{x, z}};
            array_map.emplace(pos, make_chunk_array_func(seed, pos));
        }
    }

    return array_map;
}

// START VORONOI NOISE GENERATION FUNCTIONS
// biome_*'s are used in the generation of voronoi noise which becomes the basis
// of our biome definitions.
using biome_array = std::array<
    std::array<std::array<float, std::size(biome_enums)>, chunk::WIDTH>,
    chunk::WIDTH>;
using biome_array_map =
    std::unordered_map<shared::math::coords, biome_array,
                       decltype(&chunk::hash), decltype(&chunk::equal)>;
// Decreasing NUM_POINTS to the smallest meaningful value of 1 while
// simultaneously decreasing our scale results in FAR lower computational
// cost while achieving approximately the same result. This is because we
// only have to generate 9 random numbers, as opposed to n * 9, which is a
// performance KILLER. There is no reason to move this > 1.
constexpr int NUM_BIOME_POINTS = 1;
struct biome_point {
    glm::vec2 pos;
    enum chunk::biome biome;
};

using biome_point_array = std::array<struct biome_point, NUM_BIOME_POINTS>;
static biome_point_array
make_biome_point_array(const std::uint64_t& seed,
                       const shared::math::coords& coords) noexcept {

    constexpr int BITS_PER_FLOAT = 48 / 2; // ranlux 48 / 2
    constexpr int MASK = ((2 << BITS_PER_FLOAT) - 1);
    static_assert(BITS_PER_FLOAT * 2 * NUM_BIOME_POINTS <= 48);

    const unsigned long prand = make_prandom(seed, coords);
    std::uniform_int_distribution<> uniform{0, std::size(biome_enums) - 1};
    std::ranlux48 generator{prand};

    biome_point_array points;
    std::ranges::generate(points, [&, n = 0]() mutable -> biome_point {
        const int x = (prand >> ((n + 1) * BITS_PER_FLOAT)) & MASK;
        const int y = (prand >> ((n)*BITS_PER_FLOAT)) & MASK;
        const glm::vec2 pos = glm::vec2{x, y} / static_cast<float>(MASK);
        const auto biome = static_cast<chunk::biome>(uniform(generator));
        ++n;
        return {pos, biome};
    });
    return points;
}

// result of calling make_array_map with make_biome_point_array
using biome_point_map = decltype(make_array_map(0u, shared::math::coords{0, 0},
                                                make_biome_point_array));

struct biome_point_info {
    struct biome_point point;
    glm::vec2 pos;
    shared::math::coords coords;
    float distance;
};
using biome_point_info_vector = std::vector<biome_point_info>;

static biome_point_info_vector
make_biome_point_info_vector(const biome_point_map& point_map,
                             const glm::vec2& pos,
                             const shared::math::coords& coords) noexcept {

    biome_point_info_vector point_infos{};
    for (int x = -1; x <= 1; ++x) {
        for (int z = -1; z <= 1; ++z) {
            const glm::vec2 offset = {x, z};
            const biome_point_array& point_array = array_map_access(
                point_map, coords + shared::math::coords{x, z});

            for (const auto& point : point_array) {

                const float distance = glm::distance(point.pos + offset, pos);
                if (distance > 1.0f) {
                    continue;
                }

                point_infos.push_back(biome_point_info{
                    .point = point,
                    .pos = point.pos,
                    .coords = shared::math::coords{x, z} + coords,
                    .distance = distance});
            }
        }
    }

    return point_infos;
}

using biome_point_info_vector_array =
    std::array<std::array<biome_point_info_vector, chunk::WIDTH>, chunk::WIDTH>;

static biome_array make_2d_biome_array(const std::uint64_t& seed,
                                       const shared::math::coords& coords,
                                       const int scale) noexcept {

    const shared::math::coords scaled_coords{reflect_outer(coords.x, scale),
                                             reflect_outer(coords.z, scale)};

    const auto point_2d_map =
        make_array_map(seed, scaled_coords, make_biome_point_array);

    const int x_offset = reflect_inner(coords.x, scale) * chunk::WIDTH;
    const int z_offset = reflect_inner(coords.z, scale) * chunk::WIDTH;
    const int scaled_width = chunk::WIDTH * scale;

    // We generate a bit of perlin noise here so we can add some (jitter?)
    // along our distances - the end result is less of an obvious line and more
    // variance along our chunk borders.
    constexpr int BIOME_JITTER_SCALE = 3;
    const chunk_array jitter =
        make_2d_perlin_array(seed, coords, BIOME_JITTER_SCALE);

    // For our 2d array (ultimately columns of blocks in the world), we get the
    // point that we're closest to in our world's voronoi noise points. For
    // the points that are relevant (relatively close), we get the biome the
    // point represents and add it to the column's array of biome influences.
    // We ensure that these values add up to 1.0f. In the end, we have a struct
    // that describes how much each biome affects each column as a %.
    biome_array array = {};
    for (auto x = 0u; x < chunk::WIDTH; ++x) {
        const unsigned sx = x + static_cast<unsigned>(x_offset);

        for (auto z = 0u; z < chunk::WIDTH; ++z) {
            const unsigned sz = z + static_cast<unsigned>(z_offset);

            // clang-format off
            const glm::vec2 inner_pos = 
            (glm::vec2{static_cast<float>(sx) + 0.5f, 
                       static_cast<float>(sz) + 0.5f} 
                / static_cast<float>(scaled_width)) +
            (glm::vec2{std::sin(jitter[x][z]), std::cos(jitter[x][z])} * 0.1f);
            // clang-format on

            const auto point_infos = make_biome_point_info_vector(
                point_2d_map, inner_pos, scaled_coords);

            float total_dominance = 0.0f;
            for (const auto& point_info : point_infos) {
                const auto index = get_biome_index(point_info.point.biome);

                const float dominance = std::clamp(
                    -1.0f * std::pow(0.5f * point_info.distance - 1.0f, 21.0f),
                    0.0f, 1.0f);

                auto& loc = array[x][z][static_cast<unsigned long>(index)];
                if (loc > dominance) {
                    continue;
                }
                const float diff = dominance - loc;
                loc += diff;
                total_dominance += diff;
            }

            for (float& dominance : array[x][z]) {
                dominance *= (1.0f / total_dominance);
            }
        }
    }
    return array;
}
// END VORONOI NOISE GENERATION FUNCTIONS

// These are constexpr for our static assert.
static constexpr float
get_biome_offset(const enum chunk::biome biome) noexcept {
    switch (biome) {
    case chunk::biome::ocean:
    case chunk::biome::islands:
        return 0.0f;
    default:
        break;
    }
    return 10.0f;
}

static constexpr float
get_biome_variation17(const enum chunk::biome biome) noexcept {
    switch (biome) {
    case chunk::biome::alpine:
        return 80.0f;
    case chunk::biome::tundra:
        return 10.0f;
    case chunk::biome::forest:
        return 30.0f;
    case chunk::biome::ocean:
        return 0.0f;
    case chunk::biome::islands:
        return 5.0f;
    default:
        break;
    }
    return 15.0f;
}

static constexpr float
get_biome_variation11(const enum chunk::biome biome) noexcept {
    switch (biome) {
        break;
    case chunk::biome::alpine:
        return 40.0f;
    case chunk::biome::tundra:
        return 30.0f;
    default:
        break;
    }
    return 20.0f;
}

static constexpr float
get_biome_variation7(const enum chunk::biome biome) noexcept {
    switch (biome) {
    case chunk::biome::alpine:
        return 20.0f;
    case chunk::biome::islands:
        return 30.0f;
    case chunk::biome::desert:
    case chunk::biome::plains:
        return 15.0f;
    default:
        break;
    }
    return 10.0f;
}

static constexpr float
get_biome_variation3(const enum chunk::biome biome) noexcept {
    switch (biome) {
    default:
        break;
    }
    return 7.5f;
}

constexpr float BASE_HEIGHT = 40.0f;
// Ensure any perlin values of our biome generation does not result in a y value
// that is outside our max height.
static_assert(std::ranges::all_of(biome_enums, [](const auto& biome) {
    const float max_height =
        BASE_HEIGHT + get_biome_offset(biome) + get_biome_variation3(biome) +
        get_biome_variation7(biome) + get_biome_variation11(biome) +
        get_biome_variation17(biome);
    return max_height < static_cast<float>(chunk::HEIGHT);
}));

// Line that crosses at 0.5f, 0.5f with a variable gradient, should be clamped.
static float linear_gradient(const float x, const float m) noexcept {
    return m * (x - (0.5f - (0.5f / m)));
}

// The functions for ...these functions... should be domain and range [0, 1].
static float process_variation(float variation,
                               const enum chunk::biome biome) noexcept {
    switch (biome) {
    case chunk::biome::alpine:
        variation = linear_gradient(variation, 2.2f);
        break;
    default:
        variation = linear_gradient(variation, 1.5f);
        break;
    }
    return std::clamp(variation, 0.0f, 1.0f);
}

chunk_array make_topography(const std::uint64_t& seed,
                            const shared::math::coords& coords,
                            const biome_array_map& biome_map) noexcept {

    chunk_array topography = {};

    const biome_array& biomes = biome_map.find(coords)->second;
    const chunk_array perlin17 = make_2d_perlin_array(seed, coords, 17);
    const chunk_array perlin11 = make_2d_perlin_array(seed, coords, 11);
    const chunk_array perlin7 = make_2d_perlin_array(seed, coords, 7);
    const chunk_array perlin3 = make_2d_perlin_array(seed, coords, 3);

    for (auto x = 0ul; x < chunk::WIDTH; ++x) {
        for (auto z = 0ul; z < chunk::WIDTH; ++z) {

            // Initial topography of 40.0f.
            topography[x][z] = BASE_HEIGHT;

            const auto biome_dominance = biomes[x][z];
            for (auto i = 0u; i < std::size(biome_dominance); ++i) {
                const enum chunk::biome biome = biome_enums[i];

                const float dominance = biome_dominance[i];
                const float v3 = process_variation(perlin3[x][z], biome) *
                                 get_biome_variation3(biome);
                const float v7 = process_variation(perlin7[x][z], biome) *
                                 get_biome_variation7(biome);
                const float v11 = process_variation(perlin11[x][z], biome) *
                                  get_biome_variation11(biome);
                const float v17 = process_variation(perlin17[x][z], biome) *
                                  get_biome_variation17(biome);

                topography[x][z] +=
                    (get_biome_offset(biome) + v3 + v7 + v11 + v17) * dominance;
            }
        }
    }

    return topography;
}

static chunk_array
make_probabilities(const std::uint64_t& seed,
                   const shared::math::coords& coords) noexcept {

    chunk_array chunk_array;

    std::uniform_real_distribution<float> uniform{
        0.0f, std::nextafter(1.0f, std::numeric_limits<float>::max())};
    std::ranlux48 generator(make_prandom(seed, coords));
    for (auto x = 0ul; x < chunk::WIDTH; ++x) {
        for (auto z = 0ul; z < chunk::WIDTH; ++z) {
            chunk_array[x][z] = uniform(generator);
        }
    }

    return chunk_array;
}

static biome_array make_biomes(const std::uint64_t& seed,
                               const shared::math::coords& coords) noexcept {

    constexpr int BIOME_SCALE = 99;
    return make_2d_biome_array(seed, coords, BIOME_SCALE);
}

constexpr int SAND_HEIGHT = 65;
constexpr int WATER_HEIGHT = 63;

constexpr int SAND_DEPTH = 5;
constexpr int SANDSTONE_DEPTH = 6;
constexpr int GRASS_DEPTH = 1;
constexpr int DIRT_DEPTH = 7;

// Rulesets common to all chunks go here. Water inhabits all blocks below 63
// and above the topography value. In addition, stone fills all blocks after
// the initial biome blocks.
static void generate_post_terrain_column(chunk::block_array_t& blocks,
                                         const glm::ivec3& pos,
                                         const int lowest) noexcept {
    for (int y = lowest; y > WATER_HEIGHT; --y) {
        blocks[get_3d_index({pos.x, y, pos.z})] = block::type::sand;
    }
    for (int y = WATER_HEIGHT; y > pos.y; --y) {
        blocks[get_3d_index({pos.x, y, pos.z})] = block::type::water;
    }
    for (int y = lowest; y >= 0; --y) {
        blocks[get_3d_index({pos.x, y, pos.z})] = block::type::stone;
    }
}

static int generate_sandy_terrain_column(chunk::block_array_t& blocks,
                                         const glm::ivec3& pos) noexcept {
    int y = pos.y;
    for (const int lowest = y - SAND_DEPTH; y > lowest; --y) {
        blocks[get_3d_index({pos.x, y, pos.z})] = block::type::sand;
    }
    for (const int lowest = y - SANDSTONE_DEPTH; y > lowest; --y) {
        blocks[get_3d_index({pos.x, y, pos.z})] = block::type::sandstone;
    }
    return y;
}

static int generate_grassy_terrain_column(chunk::block_array_t& blocks,
                                          const glm::ivec3& pos,
                                          const enum block::type top) noexcept {
    int y = pos.y;
    if (y <= SAND_HEIGHT) {
        for (const int lowest = y - SAND_DEPTH; y > lowest; --y) {
            blocks[get_3d_index({pos.x, y, pos.z})] = block::type::sand;
        }
    } else {
        for (const int lowest = y - GRASS_DEPTH; y > lowest; --y) {
            blocks[get_3d_index({pos.x, y, pos.z})] = top;
        }
        for (const int lowest = y - DIRT_DEPTH; y > lowest; --y) {
            blocks[get_3d_index({pos.x, y, pos.z})] = block::type::dirt;
        }
    }
    return y;
}

static void generate_terrain_column(chunk::block_array_t& blocks,
                                    const glm::ivec3& pos,
                                    const enum chunk::biome biome) noexcept {
    const int lowest = [&]() {
        switch (biome) {
        case chunk::biome::desert:
            return generate_sandy_terrain_column(blocks, pos);

        case chunk::biome::islands:
        case chunk::biome::forest:
        case chunk::biome::plains:
        case chunk::biome::ocean:
            return generate_grassy_terrain_column(blocks, pos,
                                                  block::type::grass);

        case chunk::biome::tundra:
        case chunk::biome::alpine:
            return generate_grassy_terrain_column(blocks, pos,
                                                  block::type::snow);
        }
    }();

    generate_post_terrain_column(blocks, pos, lowest);
}

static enum chunk::biome get_dominant_biome(const auto& array) noexcept {
    const auto max_it =
        std::max_element(std::begin(array), std::end(array),
                         [](const auto& a, const auto& b) { return a < b; });
    return biome_enums[static_cast<unsigned long>(
        std::distance(std::begin(array), max_it))];
}

static void generate_terrain(chunk::block_array_t& blocks,
                             const shared::math::coords& coords,
                             const chunk_array_map& topography_map,
                             const biome_array_map& biome_map) noexcept {

    const biome_array& biomes = biome_map.find(coords)->second;
    const chunk_array& topography = topography_map.find(coords)->second;

    // We fill in our chunk column by column, where the column refers to a
    // function which maps to a biome.
    for (unsigned long x = 0ul; x < chunk::WIDTH; ++x) {
        for (unsigned long z = 0ul; z < chunk::WIDTH; ++z) {
            generate_terrain_column(blocks, glm::vec3{x, topography[x][z], z},
                                    get_dominant_biome(biomes[x][z]));
        }
    }
}

// Objects have a max WIDTH, but no max WIDTH.
constexpr int MAX_OBJECT_WIDTH = 5;
constexpr int OBJECT_HALFWIDTH = MAX_OBJECT_WIDTH / 2;
// A layer is an x, z slice of an object.
using object_layer =
    std::array<std::array<block, MAX_OBJECT_WIDTH>, MAX_OBJECT_WIDTH>;
using object = std::vector<object_layer>;
struct biome_object {
    const object* const blocks;
    const float probability;
    const int altitude; // lowest alt we can gen at
};
using biome_objects = std::vector<biome_object>;

static object make_tree_object() noexcept {
    object tree;
    object_layer layer = {};

    layer[OBJECT_HALFWIDTH][OBJECT_HALFWIDTH] = block::type::wood;
    for (int i = 0; i < 3; ++i) {
        tree.push_back(layer);
    }

    for (unsigned x = 0; x < std::size(layer); ++x) {
        for (unsigned z = 0; z < std::size(layer); ++z) {
            if (x == OBJECT_HALFWIDTH && z == OBJECT_HALFWIDTH) {
                continue;
            }
            layer[x][z] = block::type::leaves;
        }
    }
    for (int i = 0; i < 2; ++i) {
        tree.push_back(layer);
    }
    for (unsigned x = 0; x < std::size(layer); ++x) {
        for (unsigned z = 0; z < std::size(layer); ++z) {
            if (!(x == 0 || x == 4 || z == 0 || z == 4)) {
                continue;
            }
            layer[x][z] = block::type::air;
        }
    }
    tree.push_back(layer);
    for (unsigned x = 0; x < std::size(layer); ++x) {
        for (unsigned z = 0; z < std::size(layer); ++z) {
            if (x < 1 || x > 3 || z < 1 || z > 3 ||
                (std::abs(int(x) - 2) + std::abs(int(z) - 2) == 2)) {
                layer[x][z] = block::type::air;
                continue;
            }
            layer[x][z] = block::type::leaves;
        }
    }
    tree.push_back(layer);
    return tree;
}

static object make_alpine_tree() noexcept {
    object tree;
    object_layer layer = {};

    layer[OBJECT_HALFWIDTH][OBJECT_HALFWIDTH] = block::type::snowy_wood;
    constexpr int HEIGHT = 10;
    for (int y = 0; y <= HEIGHT; ++y) {

        constexpr float BASE_RAD = static_cast<float>(MAX_OBJECT_WIDTH) / 2.0f;

        const float radius =
            BASE_RAD * std::exp(-1.0f * (static_cast<float>(y) /
                                         static_cast<float>(HEIGHT)));

        for (unsigned x = 0; x < MAX_OBJECT_WIDTH; ++x) {
            for (unsigned z = 0; z < MAX_OBJECT_WIDTH; ++z) {
                if (x == OBJECT_HALFWIDTH && z == OBJECT_HALFWIDTH) {
                    if (y == HEIGHT) {
                        layer[x][z] = block::type::snowy_leaves;
                    }

                    continue; // leave as wood
                }

                if ((y + 1) % 2) {
                    layer[x][z] = block::type::air;
                    continue;
                }

                const float lhs = std::pow((float)x - 2.0f, 2.0f) +
                                  std::pow((float)z - 2.0f, 2.0f);
                const float rhs = std::pow(radius, 2.0f);

                layer[x][z] =
                    lhs < rhs ? block::type::snowy_leaves : block::type::air;
            }
        }

        tree.push_back(layer);
    }

    return tree;
}

static object make_column_object(const enum block::type type,
                                 const int WIDTH) noexcept {
    object obj;
    object_layer layer = {};

    layer[OBJECT_HALFWIDTH][OBJECT_HALFWIDTH] = type;
    for (int i = 0; i < WIDTH; ++i) {
        obj.push_back(layer);
    }
    return obj;
}

static const biome_objects&
get_biome_objects(const chunk::biome biome) noexcept {
    using btype = enum block::type;
    static const object tree = make_tree_object();
    static const object alpine_tree = make_alpine_tree();
    static const object cactus1 = make_column_object(btype::cactus, 1);
    static const object cactus2 = make_column_object(btype::cactus, 2);
    static const object cactus3 = make_column_object(btype::cactus, 3);
    static const object grass = make_column_object(btype::shrub, 1);
    static const object dead_shrub = make_column_object(btype::dead_shrub, 1);
    static const object snowy_grass = make_column_object(btype::snowy_shrub, 1);

    switch (biome) {
    case chunk::biome::islands:
        static const biome_objects island_objects{
            biome_object{&tree, 0.0005f, SAND_HEIGHT},
            biome_object{&grass, 0.025f, SAND_HEIGHT}};
        return island_objects;

    case chunk::biome::plains:
        static const biome_objects plains_objects{
            biome_object{&tree, 0.0005f, SAND_HEIGHT},
            biome_object{&grass, 0.1f, SAND_HEIGHT}};
        return plains_objects;

    case chunk::biome::forest:
        static const biome_objects forest_objects{
            biome_object{&tree, 0.01f, SAND_HEIGHT},
            biome_object{&grass, 0.1f, SAND_HEIGHT}};
        return forest_objects;

    case chunk::biome::desert:
        static const biome_objects desert_objects{
            biome_object{&cactus1, 0.0002f, WATER_HEIGHT},
            biome_object{&cactus2, 0.0005f, WATER_HEIGHT},
            biome_object{&cactus3, 0.0009f, WATER_HEIGHT},
            biome_object{&dead_shrub, 0.0012f, WATER_HEIGHT}};
        return desert_objects;

    case chunk::biome::alpine:
        static const biome_objects alpine_objects{
            biome_object{&alpine_tree, 0.0008f, SAND_HEIGHT},
            biome_object{&snowy_grass, 0.0025f, SAND_HEIGHT}};
        return alpine_objects;

    case chunk::biome::tundra:
        static const biome_objects tundra_objects{
            biome_object{&alpine_tree, 0.0008f, SAND_HEIGHT},
            biome_object{&snowy_grass, 0.004f, SAND_HEIGHT}};
        return tundra_objects;

    case chunk::biome::ocean:
        static const biome_objects ocean_objects{
            biome_object{&tree, 0.001f, SAND_HEIGHT},
            biome_object{&grass, 0.1f, SAND_HEIGHT}};
        return ocean_objects;
    }
}

static std::optional<biome_object>
maybe_get_object(const float probability, const chunk::biome biome) noexcept {
    const auto& biome_objects = get_biome_objects(biome);

    const auto find_it =
        std::ranges::find_if(biome_objects, [&](const auto& object) {
            return object.probability >= probability;
        });

    if (find_it != std::end(biome_objects)) {
        return *find_it;
    }
    return std::nullopt;
}

static int get_block_priority(const enum block::type& b) noexcept {
    switch (b) {
    case block::type::air:
        return 0;
    case block::type::leaves:
    case block::type::snowy_leaves:
        return 1;
    default:
        break;
    }
    return 2;
}

static void generate_object(const object& object, chunk::block_array_t& blocks,
                            const glm::ivec3& pos) noexcept {
    for (unsigned y = 0; y < std::size(object); ++y) {

        const auto& layer = object[y];
        for (unsigned x = 0; x < std::size(layer); ++x) {
            for (unsigned z = 0; z < std::size(layer); ++z) {

                const block block = layer[x][z];
                if (block == block::type::air) {
                    continue;
                }

                const glm::ivec3 block_pos =
                    pos + glm::ivec3{x - MAX_OBJECT_WIDTH / 2, y + 1,
                                     z - MAX_OBJECT_WIDTH / 2};
                if (chunk::is_outside_chunk(block_pos)) {
                    continue;
                }

                const auto index = get_3d_index(block_pos);

                const class block old_block = blocks[index];
                if (get_block_priority(block) < get_block_priority(old_block)) {
                    continue;
                }

                blocks[index] = block;
            }
        }
    }
}

static void generate_objects(chunk::block_array_t& blocks,
                             const shared::math::coords& coords,
                             const chunk_array_map& topography_map,
                             const biome_array_map& biome_map,
                             const chunk_array_map& probability_map) noexcept {

    // This is really expensive as it is x^2
    // We don't want to create any structures that are very wide as a result.
    // (at least, structures which generate via this method).
    const int MAX_READ = MAX_OBJECT_WIDTH / 2;
    for (int x = -MAX_READ; x < MAX_READ + chunk::WIDTH; ++x) {
        for (int z = -MAX_READ; z < MAX_READ + chunk::WIDTH; ++z) {
            const float probability =
                array_map_access(probability_map, coords, x, z);
            const chunk::biome biome =
                get_dominant_biome(array_map_access(biome_map, coords, x, z));

            const auto& object = maybe_get_object(probability, biome);
            if (!object.has_value()) {
                continue;
            }

            const glm::ivec3 pos{
                x, array_map_access(topography_map, coords, x, z), z};

            if (pos.y <= object->altitude) {
                continue;
            }

            generate_object(*object->blocks, blocks, pos);
        }
    }
}

static chunk::biomes_t make_biome_array(const biome_array& array) noexcept {
    auto ret = std::make_unique<chunk::biome_array_t>();
    for (unsigned long x = 0; x < chunk::WIDTH; ++x) {
        for (unsigned long z = 0; z < chunk::WIDTH; ++z) {
            (*ret)[x][z] = get_dominant_biome(array[x][z]);
        }
    }
    return ret;
}

// Use perlin noise and extrapolation of eigen vectors along a mobius strip.
chunk::chunk(const std::uint64_t& seed,
             const shared::math::coords& coords) noexcept
    : pos(coords) {
    const biome_array_map biome_arrays =
        make_array_map(seed, coords, make_biomes);
    // Topography relies on block temperature so we bind it as a hidden
    // third argument as to avoid unnecessary generation.
    const chunk_array_map topography_arrays =
        make_array_map(seed, coords,
                       std::bind(make_topography, std::placeholders::_1,
                                 std::placeholders::_2, biome_arrays));

    const chunk_array_map probability_map =
        make_array_map(seed, coords, make_probabilities);

    chunk::blocks_t ret = std::make_unique<chunk::block_array_t>();

    generate_terrain(*ret, coords, topography_arrays, biome_arrays);
    generate_objects(*ret, coords, topography_arrays, biome_arrays,
                     probability_map);
    // generate caves
    // generate better terrain generation

    this->blocks = std::move(ret);
    this->biomes = make_biome_array(biome_arrays.find(coords)->second);
}

chunk::chunk(const std::uint64_t& seed, const proto::chunk& proto) noexcept
    : pos(shared::net::get_coords(proto.chunk_pos())) {

    blocks_t ret = std::make_unique<chunk::block_array_t>();

    for (int i = 0; i < proto.blocks_size(); ++i) {
        const std::uint32_t packed_blocks = proto.blocks(i);
        for (int j = 0; j < 4; ++j) {
            (*ret)[static_cast<unsigned>(i * 4 + j)] =
                static_cast<enum block::type>(
                    static_cast<std::uint8_t>(packed_blocks >> j * 8));
        }
    }

    // Our protobuf constructor doesn't call any of the worldgen stuff, but
    // needs to gen the biomes locally to populate this->biomes.
    this->blocks = std::move(ret);
    this->biomes = make_biome_array(make_biomes(seed, this->pos));
}

void chunk::pack(proto::chunk* const proto) const noexcept {
    shared::net::set_coords(proto->mutable_chunk_pos(), this->pos);

    // Since protobuf can store at minimum uint32, we mash four of our
    // uint_8 chunk blocks into a single uint32.
    static_assert(shared::world::chunk::VOLUME % 4 == 0);
    for (unsigned i = 0u; i < shared::world::chunk::VOLUME / 4u; ++i) {
        std::uint32_t packed_blocks = 0u;

        for (unsigned j = 0; j < 4; ++j) {
            const auto block =
                static_cast<std::uint8_t>((*this->blocks)[i * 4 + j].type);
            packed_blocks |= static_cast<unsigned>(block << j * 8);
        }

        proto->add_blocks(packed_blocks);
    }
}

} // namespace world
} // namespace shared