Multithreaded world generation with Perlin

7 files changed, 108 insertions, 224 deletions

diff --git a/src/World/Chunk.cpp b/src/World/Chunk.cpp
index 08f08bc..1874950 100644
--- a/src/World/Chunk.cpp
+++ b/src/World/Chunk.cpp
@@ -3,8 +3,12 @@
 
 namespace MC::World {
 
-void Chunk::set(uint32_t x, uint32_t y, uint32_t z, BlockType type) {
-    m_blocks[x][y][z].type = type;
+void Chunk::set(uint32_t x, uint32_t y, uint32_t z, BlockData data) {
+    m_blocks[pos(x, y, z)] = data;
+}
+
+Chunk::BlockData Chunk::get(uint32_t x, uint32_t y, uint32_t z) {
+    return m_blocks[pos(x, y, z)];
 }
 
 GFX::Mesh Chunk::mesh() {
@@ -16,7 +20,7 @@ GFX::Mesh Chunk::mesh() {
     for (int x = 0; x < Chunk::Width; x++) {
         for (int y = 0; y < Chunk::Height; y++) {
             for (int z = 0; z < Chunk::Width; z++) {
-                auto type = m_blocks[x][y][z].type;
+                auto type = get(x, y, z).type;
                 if (type == BlockType::Air) {
                     continue;
                 }
@@ -90,7 +94,7 @@ bool Chunk::is_face_visible(uint32_t x, uint32_t y, uint32_t z, BlockSide side)
         return true;
     }
 
-    auto neighbor = m_blocks[neighbor_pos.x()][neighbor_pos.y()][neighbor_pos.z()];
+    auto neighbor = get(neighbor_pos.x(), neighbor_pos.y(), neighbor_pos.z());
     if (neighbor.type == BlockType::Air) {
         return true;
     }
@@ -154,4 +158,8 @@ std::array<Vector<3>, 4> Chunk::face_normals(BlockSide side) {
     return {normal, normal, normal, normal};
 }
 
+uint64_t Chunk::pos(uint32_t x, uint32_t y, uint32_t z) {
+    return x + Chunk::Width * y + Chunk::Width * Chunk::Height * z;
+}
+
 }
diff --git a/src/World/Chunk.hpp b/src/World/Chunk.hpp
index cb4f7e1..2b0379c 100644
--- a/src/World/Chunk.hpp
+++ b/src/World/Chunk.hpp
@@ -12,12 +12,18 @@ namespace MC::World {
 class Chunk {
 public:
     static constexpr const uint32_t Width = 16;
-    static constexpr const uint32_t Height = 64;
+    static constexpr const uint32_t Height = 128;
 
     Chunk(int64_t x, int64_t y)
-        : m_blocks{}, m_position{(float)x * Chunk::Width, 0.0f, (float)y * Chunk::Width} {};
+        : m_blocks{Chunk::Width * Chunk::Height * Chunk::Width, {BlockType::Air}},
+        m_position{(float)x * Chunk::Width, 0.0f, (float)y * Chunk::Width} {};
 
-    void set(uint32_t x, uint32_t y, uint32_t z, BlockType type);
+    struct BlockData {
+        BlockType type;
+    };
+
+    void set(uint32_t x, uint32_t y, uint32_t z, BlockData type);
+    BlockData get(uint32_t x, uint32_t y, uint32_t z);
 
     Vector<3> position();
     GFX::Mesh mesh();
@@ -27,12 +33,10 @@ private:
     static std::array<Vector<2>, 4> face_tex_coords(BlockType type, BlockSide side);
     static std::array<Vector<3>, 4> face_normals(BlockSide side);
 
-    struct BlockData {
-        BlockType type;
-    };
+    static uint64_t pos(uint32_t x, uint32_t y, uint32_t z);
 
     Vector<3> m_position;
-    BlockData m_blocks[Chunk::Width][Chunk::Height][Chunk::Width];
+    std::vector<BlockData> m_blocks;
 };
 
 }
diff --git a/src/World/ChunkIndex.hpp b/src/World/ChunkIndex.hpp
index cf5af07..bdb49b3 100644
--- a/src/World/ChunkIndex.hpp
+++ b/src/World/ChunkIndex.hpp
@@ -7,6 +7,7 @@
 namespace MC::World {
 
 struct ChunkIndex {
+    ChunkIndex() : x(0), y(0) {}
     ChunkIndex(int32_t x, int32_t y) : x(x), y(y) {}
 
     int32_t x, y;
diff --git a/src/World/Generator.cpp b/src/World/Generator.cpp
index 875a79b..e8b3bbd 100644
--- a/src/World/Generator.cpp
+++ b/src/World/Generator.cpp
@@ -1,190 +1,30 @@
 #include "Generator.hpp"
-#include "../Math/Noise.hpp"
+#include "../Math/Perlin.hpp"
 
 namespace MC::World {
 
 Chunk Generator::generate(int64_t chunk_x, int64_t chunk_y) {
     Chunk chunk(chunk_x, chunk_y);
 
-    auto ocean_weights = ocean_weights_pass(chunk_x, chunk_y);
-    auto biome_weights = biome_weights_pass(chunk_x, chunk_y, ocean_weights);
-    auto heights = height_pass(chunk_x, chunk_y, biome_weights);
-    auto biomes = flat_biome_pass(biome_weights);
+    Math::Perlin::Noise<3> noise{.scale=20.0f, .octaves=2};
 
-    float extent = 60.0f;
-    float base = 4.0f;
-
-    for (int x = 0; x < Chunk::Width; x++) {
-        for (int z = 0; z < Chunk::Width; z++) {
-            uint32_t height = std::round(heights(x, z) * extent + base);
-
-            auto biome = biomes(x, z);
-
-            BlockType top_block{};
-            BlockType fill_block{};
-            switch (biome) {
-                case BiomeType::Forest:
-                case BiomeType::Plains:
-                    top_block = BlockType::Grass;
-                    fill_block = BlockType::Dirt;
-                    break;
-                case BiomeType::Desert:
-                    top_block = BlockType::Sand;
-                    fill_block = BlockType::Sand;
-                    break;
-                case BiomeType::Ocean:
-                    top_block = BlockType::Water;
-                    fill_block = BlockType::Dirt;
-                    break;
-            }
-
-            for (int y = 0; y < Chunk::Height; y++) {
-                BlockType type = BlockType::Air;
-                if (y < (int32_t)height - 10) {
-                    type = BlockType::Stone;
-                } else if (y < height) {
-                    type = fill_block;
-                } else if (y == height) {
-                    type = top_block;
-                }
-
-                chunk.set(x, y, z, type);
-            }
-        }
-    }
-
-    return chunk;
-}
-
-Matrix<Chunk::Width, Chunk::Width> Generator::ocean_weights_pass(int64_t chunk_x, int64_t chunk_y) {
-    auto ocean_offset = 1125.0f;
-    auto ocean_scale = 0.05f;
-
-    Matrix<Chunk::Width, Chunk::Width> ocean_weights{};
-    for (int x = 0; x < Chunk::Width; x++) {
-        for (int y = 0; y < Chunk::Width; y++) {
-            float ocean_weight = Math::noise2d({
-                (chunk_x * Chunk::Width + x) * ocean_scale + ocean_offset,
-                (chunk_y * Chunk::Width + y) * ocean_scale + ocean_offset
-            });
-
-            ocean_weights(x, y) = ocean_weight;
-        }
-    }
-
-    return ocean_weights;
-}
-
-Matrix<Chunk::Width, Chunk::Width, Vector<BiomeType::Size>> Generator::biome_weights_pass(
-    int64_t chunk_x,
-    int64_t chunk_y,
-    Matrix<Chunk::Width, Chunk::Width, float> ocean_weights
-) {
-    auto ocean_threshold = 0.4f;
-
-    std::vector<float> biome_offsets = {110.0f, 2450.0f, 5042.0f};
-    auto biome_scale = 0.15f;
-
-    Matrix<Chunk::Width, Chunk::Width, Vector<BiomeType::Size>> biome_weights{};
-    for (int x = 0; x < Chunk::Width; x++) {
-        for (int y = 0; y < Chunk::Width; y++) {
-            Vector<BiomeType::Size> weights{};
-            for (auto biome : MC::World::BiomeType::all_ground()) {
-                float biome_noise = Math::noise2d({
-                    (chunk_x * Chunk::Width + x) * biome_scale + biome_offsets[biome],
-                    (chunk_y * Chunk::Width + y) * biome_scale + biome_offsets[biome]
+    for (uint x = 0; x < Chunk::Width; x++) {
+        for (uint z = 0; z < Chunk::Width; z++) {
+            for (uint y = 0; y < Chunk::Height; y++) {
+                auto value = noise.at({
+                    (float)(chunk_x * Chunk::Width + x),
+                    (float)y,
+                    (float)(chunk_y * Chunk::Width + z),
                 });
 
-                weights[biome] = biome_noise;
-            }
-
-            bool ocean_weight = ocean_weights(x, y) < ocean_threshold;
-            weights[MC::World::BiomeType::Ocean] = ocean_weight;
-
-            biome_weights(x,y) = weights;
-        }
-    }
-
-    return biome_weights;
-}
-
-Matrix<Chunk::Width, Chunk::Width> Generator::height_pass(
-    int64_t chunk_x,
-    int64_t chunk_y,
-    Matrix<Chunk::Width, Chunk::Width, Vector<BiomeType::Size>> biome_weights
-) {
-    auto height_offset = 6050.0f;
-    auto height_scale = 0.7f;
-
-    Matrix<Chunk::Width, Chunk::Width> heights{};
-    for (int x = 0; x < Chunk::Width; x++) {
-        for (int y = 0; y < Chunk::Width; y++) {
-            auto weights = biome_weights(x, y);
-
-            auto total_weight = 0.0f;
-            for (auto biome : MC::World::BiomeType::all()) {
-                total_weight += weights[biome];
-            }
-
-            std::pair<float, float> total_effect{};
-            for (auto biome : MC::World::BiomeType::all()) {
-                auto weight = weights[biome];
-
-                std::pair<float, float> effect{};
-                switch (biome) {
-                    case MC::World::BiomeType::Forest:
-                        effect = {0.5f, 0.45f};
-                        break;
-                    case MC::World::BiomeType::Plains:
-                        effect = {0.4f, 0.4f};
-                        break;
-                    case MC::World::BiomeType::Desert:
-                        effect = {0.6f, 0.35f};
-                        break;
-                    case MC::World::BiomeType::Ocean:
-                        effect = {0.0f, 0.0f};
-                        break;
-                }
-
-                total_effect = {
-                    total_effect.first + effect.first * (weight / total_weight),
-                    total_effect.second + effect.second * (weight / total_weight),
-                };
-            }
-
-            float height = Math::noise2d({
-                (chunk_x * Chunk::Width + x) * height_scale + height_offset,
-                (chunk_y * Chunk::Width + y) * height_scale + height_offset
-            }) * total_effect.first + total_effect.second;
-
-            heights(x, y) = height;
-        }
-    }
-
-    return heights;
-}
-
-Matrix<Chunk::Width, Chunk::Width, BiomeType> Generator::flat_biome_pass(
-    Matrix<Chunk::Width, Chunk::Width, Vector<BiomeType::Size>> biome_weights
-) {
-    Matrix<Chunk::Width, Chunk::Width, BiomeType>  biomes{};
-    for (int x = 0; x < Chunk::Width; x++) {
-        for (int y = 0; y < Chunk::Width; y++) {
-            auto weights = biome_weights(x, y);
-
-            std::pair<MC::World::BiomeType, float> max_biome{MC::World::BiomeType::Plains, 0.0f};
-            for (auto biome : MC::World::BiomeType::all()) {
-                auto weight = weights[biome];
-                if (weight > max_biome.second) {
-                    max_biome = {biome, weight};
+                if (value > 0.6f && value < 0.7f) {
+                    chunk.set(x, y, z, {BlockType::Stone});
                 }
             }
-
-            biomes(x, y) = max_biome.first;
         }
     }
 
-    return biomes;
+    return chunk;
 }
 
 }
\ No newline at end of file
diff --git a/src/World/Generator.hpp b/src/World/Generator.hpp
index f184ff9..afe43c6 100644
--- a/src/World/Generator.hpp
+++ b/src/World/Generator.hpp
@@ -9,24 +9,7 @@ namespace MC::World {
 class Generator {
 public:
     Generator() = default;
-
     Chunk generate(int64_t chunk_x, int64_t chunk_y);
-
-private:
-    Matrix<Chunk::Width, Chunk::Width> ocean_weights_pass(
-            int64_t chunk_x, int64_t chunk_y
-    );
-    Matrix<Chunk::Width, Chunk::Width, Vector<BiomeType::Size>> biome_weights_pass(
-            int64_t chunk_x, int64_t chunk_y,
-            Matrix<Chunk::Width, Chunk::Width> ocean_weight
-    );
-    Matrix<Chunk::Width, Chunk::Width> height_pass(
-            int64_t chunk_x, int64_t chunk_y,
-            Matrix<Chunk::Width, Chunk::Width, Vector<BiomeType::Size>> biome_weights
-    );
-    Matrix<Chunk::Width, Chunk::Width, BiomeType> flat_biome_pass(
-            Matrix<Chunk::Width, Chunk::Width, Vector<BiomeType::Size>> biome_weights
-    );
 };
 
 }
diff --git a/src/World/World.cpp b/src/World/World.cpp
index 7d1b4ee..1782fd4 100644
--- a/src/World/World.cpp
+++ b/src/World/World.cpp
@@ -3,33 +3,55 @@
 namespace MC::World {
 
 std::vector<World::ChunkData> World::get_visible_chunks(Vector<3> position) {
+    auto finished_chunks = load_finished_chunks_from_queue();
     auto visible_chunks = get_visible_chunk_indices(position);
 
-    auto difference = visible_chunks;
+    auto updates = visible_chunks;
     for (auto index : m_visible_chunks) {
-        difference.erase(index);
+        updates.erase(index);
+    }
+    for (auto index : finished_chunks) {
+        updates.insert(index);
     }
 
-    if (!difference.empty()) {
-        for (auto new_index: difference) {
-            auto& data = get_or_generate(new_index);
-            if (!data.mesh.has_value()) {
-                auto mesh = data.chunk->mesh();
-                data.mesh = GFX::Binder::load(mesh);
-            }
-        }
+    if (!updates.empty()) {
+        process_chunk_visibility_updates(updates);
         m_visible_chunks = visible_chunks;
     }
 
     std::vector<World::ChunkData> chunks{};
     chunks.reserve(visible_chunks.size());
     for (auto index : visible_chunks) {
-        chunks.push_back(get_or_generate(index));
+        auto& data = get(index);
+        if (data.status == ChunkStatus::Done) {
+            chunks.push_back(data);
+        }
     }
 
     return chunks;
 }
 
+void World::process_chunk_visibility_updates(std::unordered_set<ChunkIndex>& new_chunks) {
+    for (auto new_index: new_chunks) {
+        auto& data = get(new_index);
+        switch (data.status) {
+            case ChunkStatus::Empty:
+                request_generation(new_index);
+                data.status = ChunkStatus::InFlight;
+                break;
+            case ChunkStatus::InFlight:
+                // Continue waiting...
+                break;
+            case ChunkStatus::Done:
+                if (!data.mesh.has_value()) {
+                    auto mesh = data.chunk.value().mesh();
+                    data.mesh = GFX::Binder::load(mesh);
+                }
+                break;
+        }
+    }
+}
+
 std::unordered_set<ChunkIndex> World::get_visible_chunk_indices(Vector<3> position) const {
     int32_t center_x = std::round(position.x() / Chunk::Width);
     int32_t center_y = std::round(position.z() / Chunk::Width);
@@ -47,11 +69,29 @@ std::unordered_set<ChunkIndex> World::get_visible_chunk_indices(Vector<3> positi
     return indices;
 }
 
-World::ChunkData& World::get_or_generate(ChunkIndex index) {
+std::unordered_set<ChunkIndex> World::load_finished_chunks_from_queue() {
+    std::unordered_set<ChunkIndex> indices;
+    auto results = m_queue.done();
+    for (auto& result : results) {
+        auto& data = get(result.id);
+        data.chunk = {result.res};
+        data.status = ChunkStatus::Done;
+        indices.insert(result.id);
+    }
+
+    return indices;
+}
+
+void World::request_generation(ChunkIndex index) {
+    m_queue.add(index, [=]() {
+        return m_generator.generate(index.x, index.y);
+    });
+}
+
+World::ChunkData& World::get(ChunkIndex index) {
     auto entry = m_chunks.find(index);
     if (entry == m_chunks.end()) {
-        auto chunk = m_generator.generate(index.x, index.y);
-        ChunkData data{index, std::make_shared<Chunk>(chunk)};
+        ChunkData data{index, ChunkStatus::Empty};
 
         m_chunks.insert({index, data});
         return m_chunks.at(index);
@@ -60,5 +100,4 @@ World::ChunkData& World::get_or_generate(ChunkIndex index) {
     return entry->second;
 }
 
-
 }
\ No newline at end of file
diff --git a/src/World/World.hpp b/src/World/World.hpp
index f113bda..dc8f8a7 100644
--- a/src/World/World.hpp
+++ b/src/World/World.hpp
@@ -6,30 +6,39 @@
 #include <utility>
 #include "Generator.hpp"
 #include "ChunkIndex.hpp"
+#include "../Compute/Queue.hpp"
 
 namespace MC::World {
 
 class World {
 public:
-    World() : m_generator(), m_chunks(), m_visible_chunks() {}
+    World() : m_queue(2), m_chunks(), m_visible_chunks() {}
 
-    struct ChunkData {
-        ChunkData(ChunkIndex index, std::shared_ptr<Chunk> chunk)
-            : index(index), chunk(std::move(chunk)), mesh() {}
+    enum class ChunkStatus {
+        Empty,
+        InFlight,
+        Done
+    };
 
+    struct ChunkData {
         ChunkIndex index;
-        std::shared_ptr<Chunk> chunk;
-        std::optional<GFX::BindableMesh> mesh;
+        ChunkStatus status;
+        std::optional<Chunk> chunk = {};
+        std::optional<GFX::BindableMesh> mesh = {};
     };
 
     std::vector<ChunkData> get_visible_chunks(Vector<3> position);
-
 private:
     std::unordered_set<ChunkIndex> get_visible_chunk_indices(Vector<3> position) const;
-    ChunkData& get_or_generate(ChunkIndex index);
+    std::unordered_set<ChunkIndex> load_finished_chunks_from_queue();
+    void process_chunk_visibility_updates(std::unordered_set<ChunkIndex>& new_chunks);
+    void request_generation(ChunkIndex index);
+
+    ChunkData& get(ChunkIndex index);
 
-    uint8_t m_view_distance_radius = 6;
+    uint8_t m_view_distance_radius = 12;
 
+    Compute::Queue<Chunk, ChunkIndex> m_queue;
     Generator m_generator;
 
     std::unordered_map<ChunkIndex, ChunkData> m_chunks;