diff options
37 files changed, 656 insertions, 400 deletions
@@ -1,4 +1,8 @@ -cmake-build-debug +.DS_Store + .idea +.fleet +build +cmake* assets/generated
\ No newline at end of file diff --git a/CMakeLists.txt b/CMakeLists.txt index bc602f5..af96c71 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -2,6 +2,7 @@ cmake_minimum_required(VERSION 3.23) project(meowcraft) set(CMAKE_CXX_STANDARD 17) +set(CMAKE_EXPORT_COMPILE_COMMANDS ON) find_package(glfw3 3.3 REQUIRED) find_package(GLEW REQUIRED) @@ -10,7 +11,39 @@ if (LINUX) find_package(OpenGL REQUIRED) endif (LINUX) -add_executable(meowcraft src/main.cpp src/GFX/Window.cpp src/GFX/Window.hpp src/GFX/Mesh.cpp src/GFX/Mesh.hpp src/Math/Vector.hpp src/Math/Math.hpp src/GFX/Binder.cpp src/GFX/Binder.hpp src/GFX/Shading/Shader.cpp src/GFX/Shading/Shader.hpp src/GFX/Shading/Program.cpp src/GFX/Shading/Program.hpp src/Math/Matrix.hpp src/Math/MVP.cpp src/Math/MVP.hpp src/GFX/Camera.cpp src/GFX/Camera.hpp src/Math/Rotation.hpp src/GFX/Shading/Uniform.cpp src/GFX/Shading/Uniform.hpp src/GFX/Mouse.cpp src/GFX/Mouse.hpp src/Math/Trig.hpp src/GFX/Texture.cpp src/GFX/Texture.hpp src/Assets.cpp src/Assets.hpp src/GFX/Image/RawImage.cpp src/GFX/Image/RawImage.hpp src/GFX/Image/PPMParser.cpp src/GFX/Image/PPMParser.hpp src/World/Chunk.cpp src/World/Chunk.hpp src/World/BlockType.hpp src/World/Generator.cpp src/World/Generator.hpp src/World/BlockSide.hpp src/World/World.cpp src/World/World.hpp src/World/ChunkIndex.hpp src/Math/Noise.hpp src/Math/Noise.cpp src/Util/ImageViewer.cpp src/Util/ImageViewer.hpp) +add_executable(meowcraft + src/main.cpp + src/GFX/Window.cpp src/GFX/Window.hpp + src/GFX/Mesh.cpp src/GFX/Mesh.hpp + src/Math/Vector.hpp + src/Math/Common.hpp + src/GFX/Binder.cpp src/GFX/Binder.hpp + src/GFX/Shading/Shader.cpp src/GFX/Shading/Shader.hpp + src/GFX/Shading/Program.cpp src/GFX/Shading/Program.hpp + src/Math/Matrix.hpp + src/Math/MVP.cpp src/Math/MVP.hpp + src/GFX/Camera.cpp src/GFX/Camera.hpp + src/Math/Rotation.hpp + src/GFX/Shading/Uniform.cpp src/GFX/Shading/Uniform.hpp + src/GFX/Mouse.cpp src/GFX/Mouse.hpp + src/Math/Trig.hpp + src/GFX/Texture.cpp src/GFX/Texture.hpp + src/Assets.cpp src/Assets.hpp + src/GFX/Image/RawImage.cpp src/GFX/Image/RawImage.hpp + src/GFX/Image/PPMParser.cpp src/GFX/Image/PPMParser.hpp + src/World/Chunk.cpp src/World/Chunk.hpp + src/World/BlockType.hpp + src/World/Generator.cpp src/World/Generator.hpp + src/World/BlockSide.hpp + src/World/World.cpp src/World/World.hpp + src/World/ChunkIndex.hpp + src/Util/ImageViewer.cpp src/Util/ImageViewer.hpp + src/Util/Sampler.hpp + src/Math/Interpolation.cpp + src/Math/Grid.cpp + src/Math/Perlin.cpp + src/Compute/Queue.hpp +) target_link_libraries(meowcraft glfw GLEW::GLEW) if (LINUX) diff --git a/src/Compute/Queue.hpp b/src/Compute/Queue.hpp new file mode 100644 index 0000000..6aba1ab --- /dev/null +++ b/src/Compute/Queue.hpp @@ -0,0 +1,96 @@ +#pragma once + +#include <functional> +#include <sys/types.h> +#include <mutex> +#include <utility> +#include <vector> +#include <iostream> +#include <thread> + +namespace MC::Compute { + +template <typename X, typename I = uint> +class Queue { +public: + explicit Queue(uint workers) : m_control(std::make_shared<Control>()) { + for (uint w = 0; w < workers; w++) { + std::thread thread{[=]() { Queue::run_thread(m_control); }}; + thread.detach(); + } + }; + + void add(I id, std::function<X()> execute) { + std::scoped_lock work_lock(m_control->work.mutex); + m_control->work.jobs.push_back({id, std::move(execute)}); + } + + struct Result { + I id{}; + X res; + }; + + std::vector<Result> done() { + std::vector<Result> done_results; + + std::scoped_lock result_lock(m_control->results.mutex); + for (auto r : m_control->results.results) { + done_results.push_back(r); + } + m_control->results.results.clear(); + return done_results; + } + +private: + struct Job { + I id; + std::function<X()> execute; + }; + + struct Work { + std::mutex mutex; + std::vector<Job> jobs; + }; + + struct Results { + std::mutex mutex; + std::vector<Result> results; + }; + + struct Control { + Work work; + Results results; + }; + + [[noreturn]] static void run_thread(std::shared_ptr<Control> control) { + using namespace std::chrono_literals; + + while (true) { + bool nothing_to_do = true; + Job job; + { + std::scoped_lock work_lock(control->work.mutex); + if (!control->work.jobs.empty()) { + job = control->work.jobs.back(); + control->work.jobs.pop_back(); + nothing_to_do = false; + } + } + + if (nothing_to_do) { + std::this_thread::sleep_for(100ms); + continue; + } + + auto res = job.execute(); + { + std::scoped_lock result_lock(control->results.mutex); + control->results.results.push_back({job.id, res}); + } + } + } + + std::shared_ptr<Control> m_control; +}; + +} diff --git a/src/GFX/Binder.cpp b/src/GFX/Binder.cpp index 0cc844d..0dce06d 100644 --- a/src/GFX/Binder.cpp +++ b/src/GFX/Binder.cpp @@ -4,7 +4,7 @@ namespace MC::GFX { -BindableMesh Binder::load(Mesh& mesh) { +BindableMesh Binder::load(Mesh mesh) { auto vao = create_vao(); if (!mesh.indices().empty()) { store_indices(mesh.indices().data(), mesh.indices().size()); diff --git a/src/GFX/Binder.hpp b/src/GFX/Binder.hpp index 3d3949b..d8a2be9 100644 --- a/src/GFX/Binder.hpp +++ b/src/GFX/Binder.hpp @@ -35,7 +35,7 @@ class Binder { public: Binder() = default;; - static BindableMesh load(Mesh& mesh); + static BindableMesh load(Mesh mesh); private: static uint32_t create_vao(); diff --git a/src/GFX/Camera.hpp b/src/GFX/Camera.hpp index f03f009..77a210f 100644 --- a/src/GFX/Camera.hpp +++ b/src/GFX/Camera.hpp @@ -1,7 +1,6 @@ #pragma once -#include "../Math/Math.hpp" -#include "../Math/Rotation.hpp" +#include "../Math/Common.hpp" namespace MC::GFX { diff --git a/src/GFX/Image/PPMParser.cpp b/src/GFX/Image/PPMParser.cpp index 31be0ab..cf1bf77 100644 --- a/src/GFX/Image/PPMParser.cpp +++ b/src/GFX/Image/PPMParser.cpp @@ -17,7 +17,7 @@ RawImage PPMParser::parse() { auto pixel_count = header.width * header.height; - RawImage image(header.width, header.height, 3); + RawImage image(header.width, header.height); for (uint64_t pixel_index = 0; pixel_index < pixel_count; pixel_index++) { RawImage::Pixel pixel = parse_pixel(header.max_color); image.add(pixel); diff --git a/src/GFX/Image/RawImage.cpp b/src/GFX/Image/RawImage.cpp index aca8fbc..1222fab 100644 --- a/src/GFX/Image/RawImage.cpp +++ b/src/GFX/Image/RawImage.cpp @@ -2,6 +2,19 @@ namespace MC::GFX::Image { +RawImage::RawImage(Util::Sampler<2, float>& sampler, uint32_t width, uint32_t height) + : m_pixels(), m_width(width), m_height(height) +{ + m_pixels.reserve(width * height); + for (int y = 0; y < height; y++) { + for (int x = 0; x < width; x++) { + auto result = sampler.sample({(float)x, (float)y}); + auto intensity = (uint8_t)(result * 255); + add({intensity, intensity, intensity}); + } + } +} + void RawImage::add(RawImage::Pixel pixel) { m_pixels.push_back(pixel); } @@ -26,4 +39,19 @@ uint8_t RawImage::channels() const { return m_channels; } +std::string RawImage::string() const { + std::stringstream str{}; + + bool comma = false; + str << "["; + for (const auto& pixel : m_pixels) { + if (comma) { str << ", "; } + str << "{r=" << (uint)pixel.r << ", g=" << (uint)pixel.g << ", b=" << (uint)pixel.r << "}"; + comma = true; + } + str << "]"; + + return str.str(); +} + }
\ No newline at end of file diff --git a/src/GFX/Image/RawImage.hpp b/src/GFX/Image/RawImage.hpp index 2b10cb0..8a837e6 100644 --- a/src/GFX/Image/RawImage.hpp +++ b/src/GFX/Image/RawImage.hpp @@ -2,19 +2,23 @@ #include <cstdint> #include <cstddef> +#include <string> #include <vector> +#include "../../Util/Sampler.hpp" namespace MC::GFX::Image { class RawImage { public: - RawImage() : m_pixels(), m_width(0), m_height(0), m_channels(0) {}; + RawImage() : m_pixels(), m_width(0), m_height(0) {}; - explicit RawImage(uint32_t width, uint32_t height, uint8_t channels) - : m_pixels(), m_width(width), m_height(height), m_channels(channels) { + RawImage(uint32_t width, uint32_t height) + : m_pixels(), m_width(width), m_height(height) { m_pixels.reserve(width * height); } + RawImage(Util::Sampler<2, float>& sampler, uint32_t width, uint32_t height); + struct Pixel { uint8_t r, g, b; }; @@ -27,11 +31,13 @@ public: uint32_t width() const; uint32_t height() const; uint8_t channels() const; + + std::string string() const; private: std::vector<Pixel> m_pixels; uint32_t m_width, m_height; - uint8_t m_channels; + uint8_t m_channels = 3; }; } diff --git a/src/GFX/Mesh.hpp b/src/GFX/Mesh.hpp index 36a7dac..bfe8eab 100644 --- a/src/GFX/Mesh.hpp +++ b/src/GFX/Mesh.hpp @@ -3,7 +3,7 @@ #include <utility> #include <vector> #include <cstdint> -#include "../Math/Math.hpp" +#include "../Math/Common.hpp" namespace MC::GFX { diff --git a/src/GFX/Shading/Program.hpp b/src/GFX/Shading/Program.hpp index b7db953..6b28de0 100644 --- a/src/GFX/Shading/Program.hpp +++ b/src/GFX/Shading/Program.hpp @@ -3,7 +3,7 @@ #include <string> #include <vector> #include "Shader.hpp" -#include "../../Math/Math.hpp" +#include "../../Math/Common.hpp" #include "Uniform.hpp" namespace MC::GFX::Shading { diff --git a/src/GFX/Shading/Uniform.hpp b/src/GFX/Shading/Uniform.hpp index 8035dfe..3c14315 100644 --- a/src/GFX/Shading/Uniform.hpp +++ b/src/GFX/Shading/Uniform.hpp @@ -3,7 +3,7 @@ #include <cstdint> #include <string> #include <utility> -#include "../../Math/Math.hpp" +#include "../../Math/Common.hpp" namespace MC::GFX::Shading { diff --git a/src/GFX/Texture.cpp b/src/GFX/Texture.cpp index f5474df..ef48631 100644 --- a/src/GFX/Texture.cpp +++ b/src/GFX/Texture.cpp @@ -13,6 +13,10 @@ Texture::Texture(const Image::RawImage& image) { glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MIN_FILTER, GL_NEAREST); glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MAG_FILTER, GL_NEAREST); + // If this is not here, odd-numbered rows (like those in i.e. 5x5 textures) + // will begin at the incorrect byte, causing color artifacts. + glPixelStorei(GL_UNPACK_ALIGNMENT, 1); + glTexImage2D(GL_TEXTURE_2D, 0, GL_RGB, image.width(), image.height(), 0, GL_RGB, GL_UNSIGNED_BYTE, image.raw()); glGenerateMipmap(GL_TEXTURE_2D); diff --git a/src/Math/Math.hpp b/src/Math/Common.hpp index 94840b1..94840b1 100644 --- a/src/Math/Math.hpp +++ b/src/Math/Common.hpp diff --git a/src/Math/Grid.cpp b/src/Math/Grid.cpp new file mode 100644 index 0000000..422cf87 --- /dev/null +++ b/src/Math/Grid.cpp @@ -0,0 +1,77 @@ +#include "Grid.hpp" + +namespace Math { + +GridCellBoundaries grid_cell_for_point(Vector<2> point) { + auto x1 = std::trunc(point.x()); + auto y1 = std::trunc(point.y()); + auto x2 = x1 + 1.0f; + auto y2 = y1 + 1.0f; + + return GridCellBoundaries{x1, x2, y1, y2}; +} + +Vector<2> GridCellBoundaries::top_left() const { + return {x1, y1}; +} + +Vector<2> GridCellBoundaries::top_right() const { + return {x2, y1}; +} + +Vector<2> GridCellBoundaries::bottom_left() const { + return {x1, y2}; +} + +Vector<2> GridCellBoundaries::bottom_right() const { + return {x2, y2}; +} + +CubeCellBoundaries cube_cell_for_point(Vector<3> point) { + auto x1 = std::trunc(point.x()); + auto y1 = std::trunc(point.y()); + auto z1 = std::trunc(point.z()); + auto x2 = x1 + 1.0f; + auto y2 = y1 + 1.0f; + auto z2 = z1 + 1.0f; + + return CubeCellBoundaries{x1, x2, y1, y2, z1, z2}; +} + +Vector<3> CubeCellBoundaries::front_top_left() const { + return {x1, y1, z1}; +} + +Vector<3> CubeCellBoundaries::front_top_right() const { + return {x2, y1, z1}; +} + +Vector<3> CubeCellBoundaries::front_bottom_left() const { + return {x1, y2, z1}; +} + +Vector<3> CubeCellBoundaries::front_bottom_right() const { + return {x2, y2, z1}; +} + +Vector<3> CubeCellBoundaries::back_top_left() const { + return {x1, y1, z2}; +} + +Vector<3> CubeCellBoundaries::back_top_right() const { + return {x2, y1, z2}; +} + +Vector<3> CubeCellBoundaries::back_bottom_left() const { + return {x1, y2, z2}; +} + +Vector<3> CubeCellBoundaries::back_bottom_right() const { + return {x2, y2, z2}; +} + +GridCellBoundaries CubeCellBoundaries::grid_cell() const { + return {x1, x2, y1, y2}; +} + +}
\ No newline at end of file diff --git a/src/Math/Grid.hpp b/src/Math/Grid.hpp new file mode 100644 index 0000000..1c1a7ca --- /dev/null +++ b/src/Math/Grid.hpp @@ -0,0 +1,36 @@ +#pragma once + +#include "Common.hpp" +#include "Matrix.hpp" + +namespace Math { + +struct GridCellBoundaries { + float x1, x2, y1, y2; + + [[nodiscard]] Vector<2> top_left() const; + [[nodiscard]] Vector<2> top_right() const; + [[nodiscard]] Vector<2> bottom_left() const; + [[nodiscard]] Vector<2> bottom_right() const; +}; + +GridCellBoundaries grid_cell_for_point(Vector<2> point); + +struct CubeCellBoundaries { + float x1, x2, y1, y2, z1, z2; + + [[nodiscard]] Vector<3> front_top_left() const; + [[nodiscard]] Vector<3> front_top_right() const; + [[nodiscard]] Vector<3> front_bottom_left() const; + [[nodiscard]] Vector<3> front_bottom_right() const; + [[nodiscard]] Vector<3> back_top_left() const; + [[nodiscard]] Vector<3> back_top_right() const; + [[nodiscard]] Vector<3> back_bottom_left() const; + [[nodiscard]] Vector<3> back_bottom_right() const; + + [[nodiscard]] GridCellBoundaries grid_cell() const; +}; + +CubeCellBoundaries cube_cell_for_point(Vector<3> point); + +}
\ No newline at end of file diff --git a/src/Math/Interpolation.cpp b/src/Math/Interpolation.cpp new file mode 100644 index 0000000..a1e6b69 --- /dev/null +++ b/src/Math/Interpolation.cpp @@ -0,0 +1,25 @@ +#include "Interpolation.hpp" +#include <functional> +#include "Common.hpp" + +namespace Math { + +float linear_interpolation(Vector<2> val, float left, float right, float pos) { + return val.x() + (pos - left) * (val.y() - val.x()) / (right - left); +} + +float bilinear_interpolation(Matrix<2, 2> val, GridCellBoundaries cell, Vector<2> pos) { + auto r1 = linear_interpolation(val.row(0), cell.x1, cell.x2, pos.x()); + auto r2 = linear_interpolation(val.row(1), cell.x1, cell.x2, pos.x()); + + return linear_interpolation({r1, r2}, cell.y1, cell.y2, pos.y()); +} + +float trilinear_interpolation(Matrix<2, 2> val_front, Matrix<2, 2> val_back, CubeCellBoundaries cell, Vector<3> pos) { + auto r1 = bilinear_interpolation(val_front, cell.grid_cell(), {pos.x(), pos.y()}); + auto r2 = bilinear_interpolation(val_back, cell.grid_cell(), {pos.x(), pos.y()}); + + return linear_interpolation({r1, r2}, cell.z1, cell.z2, pos.z()); +} + +}
\ No newline at end of file diff --git a/src/Math/Interpolation.hpp b/src/Math/Interpolation.hpp new file mode 100644 index 0000000..9eaf604 --- /dev/null +++ b/src/Math/Interpolation.hpp @@ -0,0 +1,13 @@ +#pragma once + +#include <functional> +#include "Common.hpp" +#include "Grid.hpp" + +namespace Math { + +float linear_interpolation(Vector<2> val, float left, float right, float pos); +float bilinear_interpolation(Matrix<2, 2> val, GridCellBoundaries cell, Vector<2> pos); +float trilinear_interpolation(Matrix<2, 2> val_front, Matrix<2, 2> val_back, CubeCellBoundaries cell, Vector<3> pos); + +}
\ No newline at end of file diff --git a/src/Math/MVP.cpp b/src/Math/MVP.cpp index 754c656..dd5b5e7 100644 --- a/src/Math/MVP.cpp +++ b/src/Math/MVP.cpp @@ -1,6 +1,6 @@ #include <cmath> #include "MVP.hpp" -#include "Math.hpp" +#include "Common.hpp" namespace Math::MVP { diff --git a/src/Math/MVP.hpp b/src/Math/MVP.hpp index 0abad66..af4fbbc 100644 --- a/src/Math/MVP.hpp +++ b/src/Math/MVP.hpp @@ -1,6 +1,6 @@ #pragma once -#include "Math.hpp" +#include "Common.hpp" namespace Math::MVP { diff --git a/src/Math/Matrix.hpp b/src/Math/Matrix.hpp index 545b6a5..276dc4a 100644 --- a/src/Math/Matrix.hpp +++ b/src/Math/Matrix.hpp @@ -15,7 +15,7 @@ public: std::fill(elements, elements + R * C, scalar); }; - template<typename ...Args> + template<typename ...Args, typename std::enable_if<sizeof...(Args) == R * C, int>::type = 0> Matrix<R, C, T>(Args... args): elements{ args... } {}; Matrix<R, C, T>(T values[R * C]) { diff --git a/src/Math/Noise.cpp b/src/Math/Noise.cpp deleted file mode 100644 index 1ef8ce5..0000000 --- a/src/Math/Noise.cpp +++ /dev/null @@ -1,126 +0,0 @@ -#include <vector> -#include "Matrix.hpp" -#include "Noise.hpp" - -namespace Math { - -float noise2d(Vector<2> pos) { - struct Layer { - float scale; - Vector<2> offset; - float weight; - }; - - const std::vector<Layer> layers = { - {0.1f, {0.0f, 0.0f}, 0.2f}, - {0.05f, {10.0f, 50.0f}, 0.5f}, - {0.01f, {250.0f, 20.0f}, 0.5f}, - }; - - auto wrap = [](auto x) -> float { - float wx = std::fmod(x, NOISE_SEED_SIZE); - return wx < 0 ? wx + NOISE_SEED_SIZE : wx; - }; - - auto total_weight = 0.0f; - auto res = 0.0f; - for (const auto& layer : layers) { - auto pos_with_scale_and_offset = (pos - layer.offset) * layer.scale; - auto p = pos_with_scale_and_offset.map(wrap); - - auto x = p.x(); - auto y = p.y(); - auto x1 = x - std::fmod(x, 1.0f); - auto y2 = y - std::fmod(y, 1.0f); - auto x2 = x1 + 1.0f; - auto y1 = y2 + 1.0f; - - auto value = [=](float x, float y){ - return noise_seed[(uint)wrap(x)][(uint)wrap(y)] / 255.0f; - }; - - auto q12 = value(x1, y2); - auto q22 = value(x2, y2); - auto q11 = value(x1, y1); - auto q21 = value(x2, y1); - - auto r1 = q11 * (x2 - x) / (x2 - x1) + q21 * (x - x1) / (x2 - x1); - auto r2 = q12 * (x2 - x) / (x2 - x1) + q22 * (x - x1) / (x2 - x1); - - auto r = r1 * (y2 - y) / (y2 - y1) + r2 * (y - y1) / (y2 - y1); - - total_weight += layer.weight; - res += r * layer.weight; - } - - return res / total_weight; -} - -const uint8_t noise_seed[NOISE_SEED_SIZE][NOISE_SEED_SIZE] = { - 207, 144, 250, 28, 124, 140, 99, 120, 20, 114, 224, 134, 187, 238, 129, 197, 94, 131, 49, 63, 33, 228, 184, 237, 192, 55, 189, 79, 142, 200, 176, 26, 18, 28, 140, 95, 35, 102, 26, 17, 118, 157, 20, 195, 52, 234, 94, 23, 55, 186, 27, 32, 53, 178, 229, 200, 181, 107, 44, 182, 104, 83, 204, 115, - 116, 63, 190, 252, 77, 56, 203, 31, 111, 137, 189, 159, 58, 252, 129, 249, 96, 228, 88, 17, 50, 236, 110, 37, 180, 100, 105, 235, 91, 245, 206, 123, 6, 248, 231, 1, 193, 151, 255, 177, 7, 27, 240, 231, 49, 54, 191, 93, 99, 219, 8, 177, 12, 240, 143, 155, 229, 170, 160, 16, 102, 160, 66, 194, - 137, 130, 104, 225, 17, 37, 207, 183, 99, 161, 219, 134, 201, 6, 165, 140, 159, 11, 134, 55, 122, 232, 241, 41, 105, 183, 69, 127, 100, 69, 226, 180, 142, 209, 17, 75, 120, 224, 152, 119, 84, 18, 247, 198, 153, 107, 115, 142, 79, 220, 251, 161, 227, 202, 183, 34, 21, 151, 240, 80, 75, 149, 59, 216, - 222, 200, 50, 244, 62, 67, 7, 11, 98, 165, 112, 24, 217, 15, 61, 141, 228, 177, 172, 65, 241, 5, 69, 129, 102, 108, 81, 153, 60, 206, 111, 14, 198, 101, 186, 44, 133, 245, 154, 238, 212, 218, 240, 66, 235, 54, 148, 234, 212, 243, 124, 59, 77, 143, 232, 95, 100, 88, 33, 175, 73, 15, 76, 158, - 157, 28, 212, 83, 1, 180, 42, 78, 76, 67, 130, 176, 248, 31, 204, 4, 152, 158, 252, 211, 14, 9, 16, 230, 9, 180, 59, 13, 140, 158, 222, 213, 147, 238, 247, 189, 230, 173, 86, 231, 174, 154, 190, 253, 162, 241, 89, 122, 33, 187, 242, 206, 156, 53, 171, 31, 113, 25, 183, 79, 53, 15, 74, 187, - 98, 226, 172, 127, 160, 169, 246, 2, 117, 180, 28, 42, 252, 84, 36, 59, 171, 249, 206, 5, 206, 62, 64, 109, 96, 183, 177, 130, 245, 243, 78, 253, 194, 94, 154, 243, 239, 171, 162, 100, 117, 254, 70, 170, 203, 46, 180, 136, 144, 123, 28, 204, 66, 145, 90, 202, 127, 99, 216, 17, 39, 98, 175, 129, - 4, 4, 22, 92, 12, 0, 12, 15, 133, 218, 110, 216, 83, 234, 60, 194, 6, 83, 6, 237, 46, 181, 164, 121, 138, 60, 109, 103, 51, 215, 99, 182, 207, 168, 199, 220, 221, 95, 168, 69, 45, 36, 187, 216, 155, 145, 136, 151, 2, 139, 181, 12, 216, 49, 239, 1, 148, 106, 253, 92, 106, 76, 102, 140, - 76, 137, 9, 9, 133, 64, 184, 242, 0, 91, 150, 128, 236, 129, 73, 231, 166, 146, 32, 152, 0, 14, 117, 138, 15, 27, 195, 14, 140, 111, 61, 124, 102, 35, 252, 145, 173, 121, 113, 77, 140, 150, 75, 93, 123, 112, 117, 12, 55, 18, 235, 28, 29, 198, 224, 129, 195, 172, 48, 12, 22, 131, 120, 94, - 154, 93, 49, 28, 49, 226, 43, 231, 226, 165, 37, 21, 245, 32, 16, 153, 193, 43, 20, 154, 87, 66, 148, 81, 52, 129, 228, 156, 103, 254, 2, 85, 245, 158, 96, 177, 112, 57, 231, 84, 162, 154, 207, 213, 106, 58, 17, 176, 67, 112, 13, 64, 36, 160, 183, 217, 2, 33, 228, 133, 89, 228, 45, 154, - 47, 216, 56, 62, 190, 211, 1, 103, 229, 58, 15, 120, 252, 190, 197, 37, 53, 81, 77, 216, 70, 114, 117, 151, 170, 163, 29, 20, 55, 14, 9, 210, 12, 81, 40, 29, 176, 75, 207, 188, 1, 204, 119, 183, 205, 190, 46, 200, 50, 192, 248, 36, 126, 134, 38, 91, 255, 110, 243, 77, 82, 106, 32, 16, - 194, 253, 226, 238, 141, 232, 99, 79, 103, 221, 142, 58, 180, 139, 173, 179, 51, 171, 208, 149, 248, 8, 26, 201, 90, 232, 209, 148, 179, 17, 234, 110, 245, 48, 94, 46, 148, 225, 108, 225, 94, 76, 200, 62, 209, 235, 106, 69, 145, 25, 238, 179, 18, 21, 165, 152, 157, 106, 229, 29, 221, 126, 130, 210, - 152, 130, 141, 166, 25, 104, 74, 80, 242, 225, 228, 118, 12, 156, 42, 186, 218, 20, 226, 167, 182, 28, 69, 87, 236, 226, 73, 78, 218, 51, 177, 213, 69, 224, 131, 69, 188, 140, 97, 66, 58, 71, 156, 206, 14, 32, 79, 206, 32, 80, 23, 83, 111, 29, 146, 244, 118, 12, 27, 32, 140, 76, 191, 177, - 116, 3, 79, 2, 206, 245, 107, 37, 129, 243, 8, 32, 231, 166, 225, 159, 77, 212, 199, 128, 155, 113, 222, 240, 73, 227, 36, 15, 221, 57, 144, 196, 84, 124, 173, 69, 100, 106, 178, 167, 126, 149, 136, 33, 227, 168, 178, 112, 118, 20, 120, 56, 52, 38, 134, 225, 168, 68, 223, 80, 124, 8, 113, 238, - 11, 227, 96, 10, 129, 0, 193, 198, 154, 0, 96, 224, 92, 12, 157, 175, 76, 39, 2, 120, 140, 190, 104, 34, 1, 136, 72, 234, 15, 73, 132, 60, 190, 52, 18, 88, 208, 2, 61, 194, 203, 198, 218, 45, 3, 186, 44, 181, 149, 90, 179, 230, 241, 237, 75, 116, 198, 125, 48, 118, 171, 88, 51, 221, - 202, 48, 120, 134, 123, 99, 106, 237, 91, 164, 199, 46, 63, 219, 116, 74, 63, 53, 161, 182, 85, 247, 196, 181, 44, 225, 199, 226, 4, 27, 59, 125, 168, 233, 187, 184, 95, 98, 248, 199, 154, 10, 178, 174, 164, 213, 116, 129, 39, 182, 248, 172, 48, 23, 22, 162, 242, 160, 196, 74, 36, 51, 58, 101, - 19, 129, 191, 233, 81, 179, 157, 58, 114, 86, 3, 104, 192, 15, 14, 251, 13, 111, 40, 84, 208, 245, 99, 72, 24, 172, 163, 187, 92, 28, 215, 88, 204, 249, 128, 66, 252, 191, 227, 86, 107, 154, 52, 175, 14, 107, 217, 254, 73, 109, 124, 142, 127, 211, 99, 249, 145, 124, 78, 199, 241, 163, 76, 119, - 27, 130, 244, 202, 161, 215, 81, 160, 245, 182, 27, 92, 194, 190, 96, 31, 136, 170, 93, 173, 22, 54, 174, 6, 229, 233, 131, 78, 228, 97, 70, 27, 74, 238, 238, 91, 206, 2, 158, 19, 154, 37, 16, 245, 13, 87, 219, 105, 193, 24, 97, 113, 131, 170, 209, 191, 114, 115, 11, 208, 227, 86, 137, 13, - 74, 185, 127, 50, 104, 186, 226, 142, 254, 141, 181, 179, 153, 168, 216, 187, 128, 245, 54, 230, 89, 11, 74, 176, 77, 181, 83, 100, 107, 191, 40, 76, 94, 77, 226, 246, 64, 233, 21, 148, 70, 124, 60, 34, 212, 27, 133, 165, 199, 128, 87, 100, 125, 177, 249, 49, 190, 189, 117, 93, 232, 155, 236, 209, - 196, 31, 47, 52, 100, 106, 129, 227, 125, 152, 224, 152, 149, 126, 230, 178, 251, 132, 232, 28, 218, 185, 179, 33, 230, 41, 18, 64, 241, 151, 94, 61, 36, 1, 134, 46, 188, 248, 108, 88, 215, 127, 43, 112, 168, 171, 235, 71, 70, 73, 153, 229, 31, 79, 208, 19, 51, 22, 166, 178, 230, 34, 218, 100, - 130, 241, 104, 185, 33, 236, 47, 77, 87, 57, 200, 230, 223, 156, 242, 121, 14, 153, 69, 206, 173, 187, 26, 28, 71, 89, 63, 198, 139, 36, 184, 140, 221, 43, 76, 249, 191, 165, 231, 118, 183, 120, 138, 20, 2, 243, 36, 135, 83, 37, 12, 72, 211, 203, 7, 144, 205, 131, 222, 57, 254, 164, 123, 38, - 74, 157, 69, 64, 232, 55, 75, 52, 78, 43, 69, 152, 72, 144, 238, 252, 83, 202, 88, 208, 248, 35, 221, 2, 5, 215, 83, 31, 81, 227, 46, 63, 234, 146, 208, 137, 119, 33, 171, 223, 52, 233, 30, 115, 153, 74, 141, 183, 122, 220, 5, 218, 137, 98, 1, 129, 230, 10, 204, 146, 134, 170, 237, 94, - 92, 215, 53, 102, 161, 122, 189, 216, 141, 91, 181, 103, 23, 200, 54, 201, 144, 107, 2, 233, 42, 152, 5, 111, 67, 134, 192, 235, 73, 129, 169, 218, 44, 200, 245, 225, 100, 188, 230, 60, 89, 41, 44, 194, 218, 174, 252, 196, 160, 119, 22, 66, 189, 227, 171, 88, 143, 232, 30, 124, 66, 38, 117, 52, - 149, 5, 169, 140, 176, 50, 94, 236, 80, 69, 77, 100, 39, 179, 105, 130, 174, 18, 127, 254, 62, 49, 147, 52, 237, 212, 231, 7, 99, 224, 77, 194, 237, 88, 144, 170, 25, 202, 58, 144, 13, 145, 70, 202, 97, 128, 71, 243, 167, 31, 3, 227, 103, 175, 25, 52, 123, 217, 105, 224, 155, 4, 208, 216, - 4, 232, 106, 162, 248, 219, 176, 246, 78, 155, 26, 110, 4, 144, 246, 218, 169, 42, 155, 61, 176, 69, 225, 197, 150, 0, 225, 231, 252, 78, 83, 97, 243, 149, 218, 242, 102, 63, 3, 239, 206, 140, 228, 153, 19, 202, 41, 42, 251, 10, 234, 175, 93, 87, 38, 180, 69, 250, 171, 187, 169, 0, 176, 152, - 41, 15, 92, 220, 220, 184, 158, 141, 237, 48, 0, 38, 248, 223, 232, 3, 156, 170, 23, 150, 152, 187, 187, 169, 157, 40, 3, 239, 36, 217, 252, 213, 150, 126, 31, 22, 116, 100, 62, 37, 73, 12, 255, 166, 254, 82, 21, 95, 63, 240, 156, 61, 62, 203, 40, 19, 98, 125, 250, 34, 78, 2, 147, 235, - 169, 53, 190, 127, 0, 183, 155, 184, 76, 60, 62, 106, 28, 96, 141, 54, 215, 110, 91, 99, 108, 158, 81, 73, 215, 227, 192, 140, 134, 229, 152, 223, 33, 148, 208, 237, 153, 46, 252, 157, 182, 36, 135, 4, 218, 212, 230, 56, 109, 84, 193, 151, 38, 47, 53, 73, 13, 154, 243, 119, 177, 38, 71, 149, - 53, 230, 241, 131, 234, 173, 13, 65, 29, 86, 83, 117, 71, 170, 144, 241, 193, 61, 181, 175, 99, 156, 242, 182, 69, 215, 104, 30, 56, 234, 178, 132, 170, 188, 137, 67, 195, 64, 236, 79, 204, 239, 91, 140, 104, 158, 151, 98, 211, 149, 64, 117, 254, 166, 175, 0, 99, 50, 59, 60, 98, 172, 223, 131, - 161, 125, 153, 73, 31, 35, 22, 36, 61, 135, 114, 119, 104, 210, 62, 232, 42, 147, 117, 52, 83, 17, 40, 199, 201, 184, 160, 176, 179, 123, 73, 235, 114, 147, 216, 23, 19, 191, 192, 169, 232, 206, 202, 191, 63, 130, 104, 139, 6, 181, 251, 89, 239, 32, 100, 201, 110, 201, 175, 187, 245, 101, 81, 18, - 171, 97, 221, 252, 189, 194, 107, 230, 36, 1, 17, 75, 170, 98, 196, 90, 87, 127, 204, 20, 234, 91, 178, 47, 125, 167, 167, 93, 157, 103, 76, 67, 12, 251, 179, 128, 62, 73, 170, 23, 14, 173, 115, 50, 81, 145, 176, 98, 29, 225, 30, 166, 70, 216, 5, 8, 238, 143, 179, 125, 39, 107, 246, 40, - 194, 207, 103, 247, 78, 10, 182, 203, 182, 80, 41, 206, 214, 48, 132, 202, 144, 198, 157, 221, 200, 216, 191, 214, 89, 249, 201, 41, 165, 178, 251, 227, 64, 222, 158, 115, 101, 210, 239, 170, 113, 102, 217, 195, 25, 25, 103, 141, 250, 12, 93, 197, 79, 134, 233, 71, 45, 73, 107, 15, 180, 57, 134, 138, - 95, 214, 206, 194, 64, 111, 31, 160, 177, 147, 245, 103, 150, 245, 32, 238, 167, 187, 176, 175, 128, 112, 29, 244, 125, 96, 236, 128, 252, 170, 141, 65, 139, 146, 74, 157, 194, 223, 161, 217, 179, 200, 60, 248, 146, 122, 79, 146, 7, 218, 21, 238, 54, 79, 158, 243, 6, 34, 61, 220, 189, 227, 178, 192, - 222, 188, 15, 192, 2, 76, 12, 162, 229, 75, 25, 53, 165, 61, 22, 166, 62, 161, 168, 84, 249, 68, 84, 13, 249, 47, 237, 229, 135, 215, 173, 110, 136, 54, 177, 38, 218, 18, 48, 141, 60, 159, 136, 209, 27, 132, 212, 88, 128, 30, 106, 236, 44, 214, 182, 35, 153, 112, 168, 170, 235, 49, 95, 132, - 66, 32, 233, 220, 253, 48, 177, 183, 227, 113, 216, 133, 83, 64, 66, 172, 82, 184, 106, 244, 20, 182, 239, 4, 153, 62, 99, 131, 116, 181, 190, 117, 201, 192, 136, 87, 19, 69, 194, 56, 53, 208, 239, 24, 104, 230, 215, 220, 81, 74, 215, 250, 91, 228, 37, 216, 231, 7, 95, 10, 102, 200, 148, 198, - 205, 77, 227, 103, 66, 192, 76, 154, 91, 69, 190, 40, 32, 148, 59, 226, 35, 191, 215, 133, 229, 58, 241, 90, 26, 145, 113, 133, 220, 185, 171, 125, 198, 56, 103, 18, 51, 121, 198, 224, 71, 137, 26, 35, 165, 46, 0, 45, 3, 83, 162, 49, 98, 252, 76, 80, 45, 148, 189, 181, 239, 101, 53, 166, - 78, 220, 177, 136, 4, 138, 219, 149, 239, 56, 75, 100, 68, 155, 14, 48, 56, 103, 126, 1, 233, 131, 66, 233, 242, 86, 253, 149, 185, 162, 47, 212, 52, 36, 222, 239, 140, 27, 232, 239, 209, 194, 209, 228, 41, 248, 65, 102, 7, 240, 208, 166, 39, 29, 149, 62, 67, 160, 0, 133, 216, 137, 215, 166, - 108, 12, 86, 237, 63, 205, 150, 238, 27, 207, 236, 21, 176, 172, 73, 64, 112, 34, 38, 63, 20, 157, 254, 88, 226, 73, 109, 87, 133, 18, 157, 213, 211, 42, 108, 233, 54, 187, 254, 133, 194, 5, 167, 136, 253, 38, 183, 24, 58, 195, 82, 198, 172, 254, 155, 30, 214, 40, 218, 255, 170, 124, 185, 250, - 27, 33, 74, 140, 166, 249, 234, 208, 81, 190, 69, 122, 90, 130, 135, 81, 181, 85, 220, 177, 15, 81, 179, 155, 90, 195, 164, 184, 157, 94, 143, 243, 67, 171, 76, 153, 13, 0, 88, 4, 146, 45, 102, 211, 54, 120, 30, 171, 160, 168, 161, 236, 141, 210, 221, 191, 11, 145, 16, 227, 214, 221, 69, 90, - 46, 215, 11, 166, 83, 157, 127, 34, 140, 101, 230, 125, 103, 109, 244, 250, 131, 181, 206, 216, 152, 99, 240, 6, 185, 252, 237, 68, 221, 222, 81, 2, 84, 238, 230, 47, 162, 73, 111, 123, 185, 110, 83, 76, 16, 112, 241, 10, 58, 228, 234, 239, 143, 32, 53, 168, 212, 53, 55, 191, 112, 222, 40, 88, - 68, 192, 85, 84, 97, 14, 68, 166, 203, 226, 142, 156, 27, 181, 101, 116, 68, 156, 133, 216, 82, 220, 51, 19, 169, 104, 173, 191, 94, 27, 146, 20, 192, 194, 35, 33, 37, 219, 180, 3, 130, 186, 23, 25, 89, 240, 97, 212, 7, 39, 84, 122, 242, 242, 100, 252, 122, 87, 250, 187, 225, 127, 173, 173, - 227, 225, 163, 19, 176, 205, 243, 252, 154, 185, 195, 253, 12, 111, 213, 109, 14, 130, 17, 3, 25, 226, 234, 240, 82, 250, 244, 57, 205, 55, 224, 114, 138, 18, 253, 219, 0, 152, 125, 19, 97, 212, 219, 234, 199, 74, 163, 31, 110, 210, 55, 214, 199, 64, 252, 41, 187, 149, 155, 225, 193, 201, 96, 13, - 154, 36, 139, 225, 17, 5, 61, 145, 108, 77, 64, 221, 205, 41, 212, 147, 171, 214, 84, 251, 128, 150, 175, 221, 115, 36, 177, 97, 83, 73, 145, 95, 163, 9, 247, 64, 126, 88, 78, 202, 52, 69, 229, 89, 56, 68, 64, 51, 156, 134, 120, 229, 199, 77, 37, 167, 144, 105, 70, 16, 152, 103, 163, 210, - 22, 38, 4, 205, 218, 252, 207, 109, 231, 79, 146, 65, 35, 29, 138, 142, 199, 53, 145, 97, 214, 245, 196, 190, 223, 105, 180, 111, 124, 57, 135, 229, 177, 180, 166, 197, 194, 124, 105, 215, 237, 214, 36, 175, 200, 76, 170, 5, 123, 205, 210, 148, 81, 167, 212, 234, 36, 203, 48, 247, 215, 18, 45, 229, - 245, 131, 6, 89, 88, 50, 203, 106, 136, 58, 151, 40, 60, 50, 24, 164, 246, 27, 220, 53, 95, 21, 129, 248, 84, 187, 202, 240, 118, 56, 20, 32, 228, 22, 36, 90, 61, 244, 147, 198, 163, 224, 14, 222, 132, 11, 114, 76, 85, 156, 163, 18, 30, 25, 250, 98, 116, 97, 243, 197, 211, 168, 97, 184, - 114, 130, 95, 14, 53, 2, 148, 248, 21, 168, 85, 19, 173, 212, 38, 180, 133, 13, 245, 181, 116, 120, 162, 0, 183, 9, 166, 215, 62, 196, 71, 24, 175, 55, 135, 112, 97, 240, 17, 56, 167, 215, 150, 247, 255, 120, 214, 59, 177, 238, 107, 85, 53, 185, 69, 90, 179, 30, 38, 130, 7, 58, 59, 193, - 211, 99, 190, 32, 199, 97, 54, 10, 17, 119, 50, 76, 249, 93, 151, 129, 247, 66, 125, 158, 69, 189, 56, 157, 226, 169, 113, 169, 91, 168, 199, 230, 175, 93, 178, 177, 128, 247, 70, 212, 106, 17, 243, 45, 165, 153, 51, 209, 5, 106, 145, 243, 135, 194, 22, 236, 198, 247, 164, 124, 174, 86, 241, 2, - 56, 236, 66, 227, 117, 89, 171, 71, 180, 197, 169, 160, 94, 183, 115, 91, 41, 125, 197, 19, 53, 30, 54, 132, 5, 185, 195, 215, 207, 8, 187, 178, 44, 175, 175, 247, 134, 184, 234, 40, 164, 24, 129, 46, 228, 136, 82, 128, 20, 153, 90, 225, 118, 224, 36, 18, 175, 237, 13, 141, 42, 1, 234, 106, - 15, 222, 218, 115, 89, 47, 111, 91, 84, 91, 113, 161, 15, 21, 122, 110, 109, 28, 24, 33, 216, 248, 92, 19, 246, 252, 154, 29, 179, 37, 144, 247, 253, 181, 101, 254, 236, 116, 103, 19, 31, 71, 94, 48, 112, 115, 147, 148, 186, 158, 102, 107, 43, 200, 23, 172, 125, 96, 200, 71, 123, 211, 224, 121, - 120, 122, 131, 128, 3, 64, 205, 238, 142, 122, 48, 41, 38, 29, 98, 163, 160, 157, 108, 51, 35, 170, 21, 101, 166, 50, 226, 174, 243, 216, 33, 239, 166, 230, 108, 121, 173, 254, 121, 37, 108, 155, 126, 152, 3, 185, 3, 31, 101, 231, 144, 243, 53, 8, 49, 94, 32, 53, 88, 23, 219, 56, 203, 3, - 253, 19, 215, 46, 168, 71, 17, 112, 224, 152, 45, 29, 124, 120, 173, 218, 108, 60, 214, 146, 103, 194, 29, 174, 51, 231, 161, 62, 89, 198, 180, 14, 93, 81, 14, 125, 219, 254, 152, 155, 149, 133, 210, 223, 244, 84, 246, 3, 145, 64, 104, 156, 21, 237, 19, 93, 41, 33, 49, 247, 246, 49, 229, 167, - 93, 177, 189, 130, 110, 231, 173, 219, 0, 111, 168, 170, 25, 113, 96, 41, 100, 189, 115, 20, 97, 203, 247, 188, 175, 170, 171, 193, 89, 137, 151, 0, 130, 22, 29, 95, 60, 10, 200, 83, 73, 187, 51, 67, 121, 242, 117, 91, 30, 212, 3, 226, 32, 157, 64, 249, 94, 127, 214, 12, 234, 97, 28, 201, - 93, 40, 48, 133, 19, 13, 9, 224, 198, 250, 208, 33, 82, 75, 222, 212, 94, 206, 151, 186, 208, 80, 156, 247, 171, 52, 78, 92, 166, 4, 200, 225, 59, 181, 160, 126, 77, 63, 215, 72, 141, 83, 239, 81, 229, 99, 240, 65, 132, 168, 9, 8, 216, 207, 254, 61, 160, 252, 140, 92, 121, 4, 223, 186, - 30, 123, 70, 200, 118, 9, 124, 250, 42, 172, 80, 213, 135, 254, 92, 66, 110, 71, 18, 51, 147, 78, 229, 129, 175, 209, 68, 148, 98, 148, 46, 38, 99, 29, 199, 66, 90, 243, 104, 172, 102, 161, 209, 198, 217, 134, 110, 135, 79, 254, 192, 143, 21, 249, 52, 183, 25, 192, 243, 190, 67, 226, 100, 134, - 44, 106, 27, 60, 199, 16, 206, 63, 9, 176, 10, 114, 113, 238, 64, 57, 12, 209, 31, 88, 200, 170, 148, 11, 227, 93, 160, 57, 73, 104, 13, 159, 69, 152, 50, 123, 153, 37, 195, 67, 4, 114, 158, 44, 111, 227, 250, 64, 212, 43, 3, 36, 103, 169, 179, 0, 22, 46, 125, 3, 0, 173, 37, 201, - 43, 223, 240, 62, 89, 253, 31, 204, 119, 209, 26, 243, 101, 7, 192, 66, 183, 193, 228, 91, 147, 155, 171, 148, 120, 128, 72, 239, 220, 42, 158, 31, 77, 95, 55, 24, 71, 240, 199, 104, 89, 246, 72, 100, 145, 186, 255, 247, 85, 241, 140, 168, 219, 209, 164, 228, 99, 152, 8, 162, 239, 91, 13, 96, - 111, 55, 212, 219, 40, 74, 28, 107, 24, 149, 71, 139, 202, 136, 118, 238, 70, 199, 107, 231, 42, 131, 71, 70, 68, 188, 100, 145, 10, 112, 221, 79, 200, 120, 249, 188, 162, 1, 39, 181, 252, 92, 179, 217, 127, 139, 171, 64, 96, 212, 41, 134, 131, 189, 231, 4, 18, 171, 213, 246, 124, 49, 73, 6, - 15, 19, 242, 98, 195, 149, 244, 170, 76, 188, 144, 195, 32, 127, 70, 173, 158, 32, 254, 226, 87, 244, 143, 49, 250, 231, 182, 78, 163, 29, 15, 29, 200, 71, 228, 164, 202, 87, 91, 191, 41, 52, 51, 25, 217, 123, 24, 57, 166, 31, 248, 140, 100, 198, 199, 147, 135, 37, 52, 213, 60, 246, 111, 5, - 23, 38, 169, 143, 32, 23, 18, 251, 20, 147, 110, 240, 213, 27, 76, 153, 64, 73, 134, 254, 255, 15, 122, 36, 183, 56, 61, 76, 30, 174, 22, 20, 76, 150, 4, 7, 222, 81, 26, 30, 112, 70, 144, 20, 239, 207, 60, 49, 39, 179, 237, 111, 200, 181, 53, 81, 85, 236, 104, 194, 39, 56, 12, 173, - 102, 188, 223, 74, 198, 30, 223, 208, 27, 219, 245, 40, 243, 172, 60, 7, 125, 246, 108, 158, 106, 21, 246, 3, 161, 234, 202, 22, 128, 130, 32, 171, 181, 28, 35, 70, 237, 85, 202, 99, 188, 91, 98, 122, 179, 74, 85, 137, 237, 95, 17, 92, 146, 120, 123, 215, 203, 125, 63, 198, 175, 123, 232, 223, - 216, 161, 86, 6, 121, 154, 89, 97, 224, 51, 104, 224, 20, 44, 163, 192, 106, 217, 208, 124, 95, 73, 59, 102, 243, 183, 39, 128, 191, 76, 6, 225, 10, 30, 191, 36, 105, 164, 75, 169, 122, 16, 26, 47, 160, 116, 137, 110, 178, 53, 227, 94, 208, 221, 228, 55, 70, 26, 213, 178, 24, 114, 16, 116, - 129, 163, 65, 165, 176, 237, 66, 202, 227, 170, 89, 122, 4, 63, 73, 115, 152, 30, 145, 139, 228, 94, 221, 216, 133, 128, 151, 95, 109, 128, 98, 214, 67, 98, 17, 233, 51, 229, 126, 252, 213, 176, 118, 167, 247, 106, 144, 14, 67, 145, 156, 167, 146, 152, 147, 137, 175, 196, 192, 63, 62, 152, 2, 156, - 253, 163, 81, 205, 185, 31, 154, 153, 115, 56, 225, 161, 236, 254, 145, 231, 215, 159, 141, 217, 61, 156, 19, 120, 80, 133, 208, 126, 214, 120, 128, 160, 218, 100, 251, 202, 250, 101, 44, 48, 55, 146, 223, 133, 165, 230, 221, 214, 187, 14, 42, 70, 107, 220, 41, 151, 249, 153, 255, 12, 57, 75, 149, 207, - 223, 85, 196, 172, 4, 81, 69, 99, 48, 187, 220, 84, 14, 113, 117, 94, 79, 139, 159, 249, 112, 88, 11, 242, 72, 102, 210, 246, 24, 122, 104, 73, 21, 223, 168, 212, 205, 173, 43, 88, 199, 166, 7, 31, 156, 149, 101, 168, 4, 163, 148, 109, 232, 111, 27, 157, 154, 217, 68, 225, 52, 252, 19, 241, - 59, 50, 90, 73, 52, 52, 235, 108, 128, 124, 52, 144, 140, 164, 114, 94, 116, 149, 110, 169, 78, 11, 181, 171, 94, 83, 174, 206, 39, 139, 235, 235, 7, 116, 7, 80, 1, 255, 32, 94, 184, 188, 133, 112, 220, 155, 165, 91, 100, 184, 55, 131, 61, 140, 91, 206, 70, 132, 115, 188, 234, 70, 55, 143, - 164, 234, 119, 62, 172, 116, 198, 147, 27, 69, 116, 69, 14, 62, 31, 228, 205, 118, 120, 112, 4, 207, 166, 80, 55, 70, 23, 29, 204, 159, 186, 84, 49, 102, 120, 245, 212, 89, 115, 169, 203, 192, 205, 10, 118, 106, 36, 230, 71, 198, 52, 111, 220, 110, 35, 58, 131, 172, 42, 158, 24, 158, 55, 217, -}; - -}
\ No newline at end of file diff --git a/src/Math/Noise.hpp b/src/Math/Noise.hpp deleted file mode 100644 index 80ceb47..0000000 --- a/src/Math/Noise.hpp +++ /dev/null @@ -1,13 +0,0 @@ -#pragma once - -#include "Vector.hpp" - -#define NOISE_SEED_SIZE 64 - -namespace Math { - -extern const uint8_t noise_seed[NOISE_SEED_SIZE][NOISE_SEED_SIZE]; - -float noise2d(Vector<2> pos); - -}
\ No newline at end of file diff --git a/src/Math/Perlin.cpp b/src/Math/Perlin.cpp new file mode 100644 index 0000000..e0982cb --- /dev/null +++ b/src/Math/Perlin.cpp @@ -0,0 +1,92 @@ +#include "Perlin.hpp" +#include "Grid.hpp" +#include "Interpolation.hpp" + +namespace Math::Perlin { + +float ease(float t) { + return t * t * t * ((6 * t - 15) * t + 10); +} + +uint8_t hash(uint8_t x) { + auto rot = (x * 5) % 8; + return x << rot | x >> (8 - rot); +} + +Vector<2> gradient(Vector<2> pos) { + Vector<2> gradients[] = { + {1.0f, 1.0f}, {-1.0f, 1.0f}, + {1.0f, -1.0f}, {-1.0f, -1.0f}, + }; + + auto x = hash(hash(pos.x()) + pos.y()); + return gradients[x % 4].normalize(); +} + +float raw(Vector<2> pos) { + auto cell = grid_cell_for_point(pos); + auto uv = pos - cell.top_left(); + + auto unit = grid_cell_for_point({}); + auto l11 = unit.top_left() - uv; + auto l21 = unit.top_right() - uv; + auto l12 = unit.bottom_left() - uv; + auto l22 = unit.bottom_right() - uv; + + auto g11 = gradient(cell.top_left()); + auto g21 = gradient(cell.top_right()); + auto g12 = gradient(cell.bottom_left()); + auto g22 = gradient(cell.bottom_right()); + + auto v = bilinear_interpolation( + {l11 * g11, l21 * g21, l12 * g12, l22 * g22}, + cell, + uv.map(ease) + cell.top_left() + ); + return (v + 1.0f) / 2.0f; +} + +Vector<3> gradient(Vector<3> pos) { + constexpr float e = 0.5773502692; + static Vector<3> gradients[] = { + {e, e, e}, {-e, e, e}, {e, -e, e}, {-e, -e, e}, + {e, e, -e}, {-e, e, -e}, {e, -e, -e}, {-e, -e, -e}, + }; + + auto x = hash(hash(hash(pos.x()) + pos.y()) + pos.z()); + return gradients[x % 8]; +} + +float raw(Vector<3> pos) { + auto cell = cube_cell_for_point(pos); + auto uv = pos - cell.front_top_left(); + + auto unit = cube_cell_for_point({}); + auto l111 = unit.front_top_left() - uv; + auto l211 = unit.front_top_right() - uv; + auto l121 = unit.front_bottom_left() - uv; + auto l221 = unit.front_bottom_right() - uv; + auto l112 = unit.back_top_left() - uv; + auto l212 = unit.back_top_right() - uv; + auto l122 = unit.back_bottom_left() - uv; + auto l222 = unit.back_bottom_right() - uv; + + auto g111 = gradient(cell.front_top_left()); + auto g211 = gradient(cell.front_top_right()); + auto g121 = gradient(cell.front_bottom_left()); + auto g221 = gradient(cell.front_bottom_right()); + auto g112 = gradient(cell.back_top_left()); + auto g212 = gradient(cell.back_top_right()); + auto g122 = gradient(cell.back_bottom_left()); + auto g222 = gradient(cell.back_bottom_right()); + + auto v = trilinear_interpolation( + {l111 * g111, l211 * g211, l121 * g121, l221 * g221}, + {l112 * g112, l212 * g212, l122 * g122, l222 * g222}, + cell, + uv.map(ease) + cell.front_top_left() + ); + return (v + 1.0f) / 2.0f; +} + +}
\ No newline at end of file diff --git a/src/Math/Perlin.hpp b/src/Math/Perlin.hpp new file mode 100644 index 0000000..c31697b --- /dev/null +++ b/src/Math/Perlin.hpp @@ -0,0 +1,38 @@ +#pragma once + +#include "Common.hpp" + +namespace Math::Perlin { + +float raw(Vector<2> pos); +float raw(Vector<3> pos); + +template <size_t D> +struct Noise { + static_assert(D > 1 && D < 4); + + Vector<D> offset{20000.0f}; + float scale = 15.0f; + + uint octaves = 3; + float persistence = 0.3f; + + float at(Vector<D> pos) const { + float result = 0; + float max = 0; + float frequency = 1; + float amplitude = 1; + + for (uint octave = 0; octave < octaves; octave++) { + result += raw((pos + offset).abs() / scale * frequency) * amplitude; + max += amplitude; + + frequency *= 2; + amplitude *= persistence; + } + + return result / max; + } +}; + +}
\ No newline at end of file diff --git a/src/Math/Vector.hpp b/src/Math/Vector.hpp index cb5eb24..9cc2d75 100644 --- a/src/Math/Vector.hpp +++ b/src/Math/Vector.hpp @@ -12,13 +12,17 @@ struct Vector { public: Vector(): elements{} {}; - template<typename ...Args> + template<typename ...Args, typename std::enable_if<sizeof...(Args) == S, int>::type = 0> Vector<S, T>(Args... args) : elements{ args... } {}; Vector<S, T>(T values[S]) { std::copy(values, values + S, elements); }; + Vector<S, T>(T scalar) { + std::fill(elements, elements + S, scalar); + }; + Vector<S, T>(Vector<S - 1, T> vector, T scalar) { std::copy(vector.elements, vector.elements + S - 1, elements); elements[S - 1] = scalar; @@ -61,6 +65,10 @@ public: return map([=](auto x) { return x / m; }); } + Vector<S, T> abs() const { + return map([=](auto x) { return std::abs(x); }); + } + Vector<3, T> cross(Vector<3, T> other) const { return { y() * other.z() - z() * other.y(), @@ -81,6 +89,10 @@ public: return map([&](auto i, auto x) { return x + other[i]; }); } + Vector<S, T> operator+(T scalar) const { + return map([=](auto x) { return x + scalar; }); + } + Vector<S, T> operator*(T scalar) const { return map([=](auto x) { return x * scalar; }); } @@ -97,6 +109,10 @@ public: return map([](T x) -> T { return -x; }); } + Vector<S, T> operator/(T scalar) const { + return map([=](auto x) { return x / scalar; }); + } + T x() const { static_assert(S > 0); return elements[0]; diff --git a/src/Util/ImageViewer.cpp b/src/Util/ImageViewer.cpp index b4d8c6e..7fd5867 100644 --- a/src/Util/ImageViewer.cpp +++ b/src/Util/ImageViewer.cpp @@ -5,13 +5,14 @@ namespace MC::Util { ImageViewer::ImageViewer( - GFX::Image::RawImage& image + GFX::Image::RawImage& image, + float window_aspect ) : m_texture(image), m_program( {GFX::Shading::Shader::Type::Vertex, ImageViewer::vertex}, {GFX::Shading::Shader::Type::Fragment, ImageViewer::fragment} ), - m_mesh(GFX::Binder::load(default_mesh)) { + m_mesh(GFX::Binder::load(create_mesh(window_aspect, image.width(), image.height()))) { m_program.bind(); auto model_uniform = m_program.uniform("model_matrix"); auto view_uniform = m_program.uniform("view_matrix"); @@ -19,7 +20,7 @@ ImageViewer::ImageViewer( model_uniform.set(Math::MVP::model({}, {})); view_uniform.set(Math::MVP::view({}, {})); - projection_uniform.set(Math::MVP::orthographic_projection(1000, 800, 0.0f, 100.0f)); + projection_uniform.set(Math::MVP::orthographic_projection(1000 * window_aspect, 1000, 0.0f, 100.0f)); m_program.unbind(); } @@ -34,19 +35,27 @@ void ImageViewer::render() { m_program.unbind(); } -GFX::Mesh ImageViewer::create_default_mesh() { +GFX::Mesh ImageViewer::create_mesh(float window_aspect, uint32_t image_width, uint32_t image_height) { + auto aspect = (float)image_width / image_height; + float max_size = 500.0f; + float width = max_size * std::min(1.0f, aspect); + float height = max_size * std::min(1.0f, 1/aspect); + + float x = max_size * window_aspect - width / 2.0f; + float y = max_size - height / 2.0f; + return {{ std::vector<Vector<3>>{ - {300.0f, 200.0f, 0.0f}, // top left - {300.0f, 600.0f, 0.0f}, // bottom left - {700.0f, 600.0f, 0.0f}, // bottom right - {700.0f, 200.0f, 0.0f } // top right + {x, y, 0.0f}, // top left + {x, y + height, 0.0f}, // bottom left + {x + width, y + height, 0.0f}, // bottom right + {x + width, y, 0.0f} // top right }, std::vector<Vector<2>>{ - {1.0f, 1.0f}, - {1.0f, 0.0f,}, {0.0f, 0.0f}, {0.0f, 1.0f}, + {1.0f, 1.0f}, + {1.0f, 0.0f}, }, }, {0, 1, 2, 0, 2, 3}}; } diff --git a/src/Util/ImageViewer.hpp b/src/Util/ImageViewer.hpp index cb2dda0..2e4efe3 100644 --- a/src/Util/ImageViewer.hpp +++ b/src/Util/ImageViewer.hpp @@ -1,5 +1,6 @@ #pragma once +#include <ostream> #include "../GFX/Image/RawImage.hpp" #include "../GFX/Binder.hpp" #include "../GFX/Texture.hpp" @@ -9,13 +10,11 @@ namespace MC::Util { class ImageViewer { public: - explicit ImageViewer(GFX::Image::RawImage& image); + explicit ImageViewer(GFX::Image::RawImage& image, float window_aspect); void render(); private: - static GFX::Mesh create_default_mesh(); - - static inline GFX::Mesh default_mesh = create_default_mesh(); + static GFX::Mesh create_mesh(float window_aspect, uint32_t image_width, uint32_t image_height); static const char* vertex; static const char* fragment; diff --git a/src/Util/Sampler.hpp b/src/Util/Sampler.hpp new file mode 100644 index 0000000..3a4ff4f --- /dev/null +++ b/src/Util/Sampler.hpp @@ -0,0 +1,36 @@ +#pragma once + +#include <functional> +#include "../Math/Vector.hpp" +#include "../Math/Grid.hpp" + +namespace MC::Util { + +template<size_t D, typename T> +class Sampler { + using Pos = Vector<D>; + using Sample = std::function<T(Pos)>; + using Interpolate = std::function<T(Pos, Sample)>; +public: + Sampler( + Sample sample, + Pos offset = {}, + float scale = 1.0f, + Interpolate interpolate = nearest_interpolation + ) : m_sample([=](Sampler::Pos pos) -> T { + return interpolate(pos, [=](Sampler::Pos p) -> T { return sample(p * scale + offset); }); + }) {} + + T sample(Pos at) { + return m_sample(at); + } + + static T nearest_interpolation(Pos pos, Sample sample) { + return sample(pos); + } + +private: + Sample m_sample; +}; + +}
\ No newline at end of file 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; diff --git a/src/main.cpp b/src/main.cpp index dcac677..b407a78 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -10,7 +10,6 @@ #include "GFX/Texture.hpp" #include "GFX/Image/PPMParser.hpp" #include "World/World.hpp" -#include "Util/ImageViewer.hpp" #define APP_NAME "Meowcraft" @@ -66,7 +65,6 @@ void run() { auto model_uniform = program.uniform("model_matrix"); auto view_uniform = program.uniform("view_matrix"); auto projection_uniform = program.uniform("projection_matrix"); - auto sun_direction_uniform = program.uniform("sun_direction"); program.bind(); @@ -101,7 +99,7 @@ void run() { glClearColor(0.85f, 0.85f, 0.85f, 1.0f); // #DBDBDB glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT); for (auto& chunk : world.get_visible_chunks(camera.position())) { - auto model = Math::MVP::model(chunk.chunk->position(), {}); + auto model = Math::MVP::model(chunk.chunk.value().position(), {}); model_uniform.set(model); render(chunk.mesh.value(), texture); } @@ -130,11 +128,13 @@ void process_input(MC::GFX::Window& window, MC::GFX::Camera& camera) { float x = key(GLFW_KEY_D) - key(GLFW_KEY_A); float y = key(GLFW_KEY_SPACE) - key(GLFW_KEY_LEFT_SHIFT); float z = key(GLFW_KEY_S) - key(GLFW_KEY_W); + float boost = key(GLFW_KEY_LEFT_CONTROL) * 2.0f; - auto move_speed = 0.2f; + auto move_speed = 0.2f + boost; auto rotation_speed = 0.1f; - camera.move_relative({x * move_speed, y * move_speed, z * move_speed}); + camera.move_relative({x * move_speed, 0.0f, z * move_speed}); + camera.move({0.0f, y * move_speed, 0.0f}); camera.rotate({r.y() * rotation_speed, r.x() * rotation_speed, 0.0f}); } |