From 9240fdf2e68ee014da0d0a89a7fb2f29ebf28e2d Mon Sep 17 00:00:00 2001 From: Daniel Karbach Date: Wed, 7 Oct 2015 15:52:15 +0200 Subject: [PATCH] sped up chunk generation a little --- doc/thanks | 23 ++++ src/client/client.cpp | 4 +- src/rand/SimplexNoise.hpp | 5 +- src/rand/noise.cpp | 122 ++++++++++------- src/server/ServerState.cpp | 4 +- src/standalone/MasterState.cpp | 6 +- src/world/BlockTypeRegistry.hpp | 15 ++- src/world/Chunk.hpp | 11 +- src/world/ChunkIndex.hpp | 6 + src/world/ChunkStore.hpp | 2 + src/world/Generator.cpp | 49 ++++--- src/world/Generator.hpp | 16 ++- src/world/chunk.cpp | 173 +++++++++++------------- tst/rand/StabilityTest.cpp | 227 ++++++++++++++++++++++++++++++++ tst/rand/StabilityTest.hpp | 42 ++++++ tst/world/ChunkTest.cpp | 2 + 16 files changed, 525 insertions(+), 182 deletions(-) create mode 100644 doc/thanks create mode 100644 tst/rand/StabilityTest.cpp create mode 100644 tst/rand/StabilityTest.hpp diff --git a/doc/thanks b/doc/thanks new file mode 100644 index 0000000..aae3fb1 --- /dev/null +++ b/doc/thanks @@ -0,0 +1,23 @@ +I want to thank: + +Glenn Fiedler + for his excellent series on game programming in general and + networked physics in particular. The site is + http://gafferongames.com/ and I can highly recommend his articles. + +Stefan Gustavson + for his implementation of simplex noise. The one I'm using doesn't + resemble much of his original due to language adaptation, + customization, and optimization, but I started out from his and + it's working nicely. + +The libnoise Project + despite not using their library I have learned a lot about noise + and terrain generation there. The library as well as documentation + can be found on sourceforge: http://libnoise.sourceforge.net/ + +The Folks at http://www.opengl-tutorial.org/ + I made my first steps with OpenGL following this tutorial (and this + very project, as one can witness in earlier commits) and from there + acquired the rest through reading their sources and the OpenGL + documentation itself. diff --git a/src/client/client.cpp b/src/client/client.cpp index 7f58dfa..ada697b 100644 --- a/src/client/client.cpp +++ b/src/client/client.cpp @@ -126,7 +126,7 @@ InteractiveState::InteractiveState(MasterState &master, uint32_t player_id) } TextureIndex tex_index; master.GetEnv().loader.LoadBlockTypes("default", block_types, tex_index); - interface.SetInventorySlots(block_types.Size() - 1); + interface.SetInventorySlots(block_types.size() - 1); chunk_renderer.LoadTextures(master.GetEnv().loader, tex_index); chunk_renderer.FogDensity(master.GetWorldConf().fog_density); skeletons.Load(); @@ -233,7 +233,7 @@ void InteractiveState::Handle(const Packet::BlockUpdate &pack) { Block block; pack.ReadIndex(index, i); pack.ReadBlock(block, i); - if (index < Chunk::size && block.type < block_types.Size()) { + if (index < Chunk::size && block.type < block_types.size()) { manip.SetBlock(*chunk, index, block); } } diff --git a/src/rand/SimplexNoise.hpp b/src/rand/SimplexNoise.hpp index 1578931..6260426 100644 --- a/src/rand/SimplexNoise.hpp +++ b/src/rand/SimplexNoise.hpp @@ -7,7 +7,6 @@ namespace blank { -/// (3D only) adaptation of Stefan Gustavson's SimplexNoise java class class SimplexNoise { public: @@ -24,6 +23,10 @@ private: int perm[512]; int perm12[512]; glm::vec3 grad[12]; + glm::ivec3 second_ints[8]; + glm::ivec3 third_ints[8]; + glm::vec3 second_floats[8]; + glm::vec3 third_floats[8]; }; diff --git a/src/rand/noise.cpp b/src/rand/noise.cpp index e4ad310..b3a9bc8 100644 --- a/src/rand/noise.cpp +++ b/src/rand/noise.cpp @@ -28,6 +28,50 @@ SimplexNoise::SimplexNoise(std::uint64_t seed) noexcept { 0.0f, -1.0f, 1.0f }, { 0.0f, 1.0f, -1.0f }, { 0.0f, -1.0f, -1.0f }, +}) +, second_ints({ + // x>y x>z y>z + { 0, 0, 1 }, // 0 0 0 ZYX + { 0, 1, 0 }, // 0 0 1 YZX + { 0, 0, 1 }, // 0 1 0 illogical, but ZYX + { 0, 1, 0 }, // 0 1 1 YXZ + { 0, 0, 1 }, // 1 0 0 ZXY + { 1, 0, 0 }, // 1 0 1 illogical, but XYZ + { 1, 0, 0 }, // 1 1 0 XZY + { 1, 0, 0 }, // 1 1 1 XYZ +}) +, third_ints({ + // x>y x>z y>z + { 0, 1, 1 }, // 0 0 0 ZYX + { 0, 1, 1 }, // 0 0 1 YZX + { 0, 1, 1 }, // 0 1 0 illogical, but ZYX + { 1, 1, 0 }, // 0 1 1 YXZ + { 1, 0, 1 }, // 1 0 0 ZXY + { 1, 1, 0 }, // 1 0 1 illogical, but XYZ + { 1, 0, 1 }, // 1 1 0 XZY + { 1, 1, 0 }, // 1 1 1 XYZ +}) +, second_floats({ + // x>y x>z y>z + { 0.0f, 0.0f, 1.0f }, // 0 0 0 ZYX + { 0.0f, 1.0f, 0.0f }, // 0 0 1 YZX + { 0.0f, 0.0f, 1.0f }, // 0 1 0 illogical, but ZYX + { 0.0f, 1.0f, 0.0f }, // 0 1 1 YXZ + { 0.0f, 0.0f, 1.0f }, // 1 0 0 ZXY + { 1.0f, 0.0f, 0.0f }, // 1 0 1 illogical, but XYZ + { 1.0f, 0.0f, 0.0f }, // 1 1 0 XZY + { 1.0f, 0.0f, 0.0f }, // 1 1 1 XYZ +}) +, third_floats({ + // x>y x>z y>z + { 0.0f, 1.0f, 1.0f }, // 0 0 0 ZYX + { 0.0f, 1.0f, 1.0f }, // 0 0 1 YZX + { 0.0f, 1.0f, 1.0f }, // 0 1 0 illogical, but ZYX + { 1.0f, 1.0f, 0.0f }, // 0 1 1 YXZ + { 1.0f, 0.0f, 1.0f }, // 1 0 0 ZXY + { 1.0f, 1.0f, 0.0f }, // 1 0 1 illogical, but XYZ + { 1.0f, 0.0f, 1.0f }, // 1 1 0 XZY + { 1.0f, 1.0f, 0.0f }, // 1 1 1 XYZ }) { GaloisLFSR random(seed ^ 0x0123456789ACBDEF); unsigned char value; @@ -50,34 +94,20 @@ float SimplexNoise::operator ()(const glm::vec3 &in) const noexcept { glm::vec3 unskewed(skewed - tr); glm::vec3 relative(in - unskewed); - glm::vec3 second, third; - - if (relative.x >= relative.y) { - if (relative.y >= relative.z) { - second = { 1, 0, 0 }; - third = { 1, 1, 0 }; - } else if (relative.x >= relative.z) { - second = { 1, 0, 0 }; - third = { 1, 0, 1 }; - } else { - second = { 0, 0, 1 }; - third = { 1, 0, 1 }; - } - } else if (relative.y < relative.z) { - second = { 0, 0, 1 }; - third = { 0, 1, 1 }; - } else if (relative.x < relative.z) { - second = { 0, 1, 0 }; - third = { 0, 1, 1 }; - } else { - second = { 0, 1, 0 }; - third = { 1, 1, 0 }; - } + bool x_ge_y = relative.x >= relative.y; + bool x_ge_z = relative.x >= relative.z; + bool y_ge_z = relative.y >= relative.z; + unsigned int st = (x_ge_y << 2) | (x_ge_z << 1) | y_ge_z; + + glm::ivec3 second_int(second_ints[st]); + glm::ivec3 third_int(third_ints[st]); + glm::vec3 second_float(second_floats[st]); + glm::vec3 third_float(third_floats[st]); glm::vec3 offset[4] = { in - unskewed, - relative - second + one_sixth, - relative - third + one_third, + relative - second_float + one_sixth, + relative - third_float + one_third, relative - 0.5f, }; @@ -89,37 +119,31 @@ float SimplexNoise::operator ()(const glm::vec3 &in) const noexcept { float n = 0.0f; + // I know 0.6 is wrong, but for some reason it looks better than 0.5 + // 0 - float t = 0.6f - dot(offset[0], offset[0]); - if (t > 0.0f) { - t *= t; - int corner = Perm12(index[0] + Perm(index[1] + Perm(index[2]))); - n += t * t * dot(Grad(corner), offset[0]); - } + float t = glm::clamp(0.6f - dot(offset[0], offset[0]), 0.0f, 1.0f); + t *= t; + int corner = Perm12(index[0] + Perm(index[1] + Perm(index[2]))); + n += t * t * dot(Grad(corner), offset[0]); // 1 - t = 0.6f - dot(offset[1], offset[1]); - if (t > 0.0f) { - t *= t; - int corner = Perm12(index[0] + int(second.x) + Perm(index[1] + int(second.y) + Perm(index[2] + int(second.z)))); - n += t * t * dot(Grad(corner), offset[1]); - } + t = glm::clamp(0.6f - dot(offset[1], offset[1]), 0.0f, 1.0f); + t *= t; + corner = Perm12(index[0] + second_int.x + Perm(index[1] + second_int.y + Perm(index[2] + second_int.z))); + n += t * t * dot(Grad(corner), offset[1]); // 2 - t = 0.6f - dot(offset[2], offset[2]); - if (t > 0.0f) { - t *= t; - int corner = Perm12(index[0] + int(third.x) + Perm(index[1] + int(third.y) + Perm(index[2] + int(third.z)))); - n += t * t * dot(Grad(corner), offset[2]); - } + t = glm::clamp(0.6f - dot(offset[2], offset[2]), 0.0f, 1.0f); + t *= t; + corner = Perm12(index[0] + third_int.x + Perm(index[1] + third_int.y + Perm(index[2] + third_int.z))); + n += t * t * dot(Grad(corner), offset[2]); // 3 - t = 0.6f - dot(offset[3], offset[3]); - if (t > 0.0f) { - t *= t; - int corner = Perm12(index[0] + 1 + Perm(index[1] + 1 + Perm(index[2] + 1))); - n += t * t * dot(Grad(corner), offset[3]); - } + t = glm::clamp(0.6f - dot(offset[3], offset[3]), 0.0f, 1.0f); + t *= t; + corner = Perm12(index[0] + 1 + Perm(index[1] + 1 + Perm(index[2] + 1))); + n += t * t * dot(Grad(corner), offset[3]); return 32.0f * n; } diff --git a/src/server/ServerState.cpp b/src/server/ServerState.cpp index e6c031f..e16872f 100644 --- a/src/server/ServerState.cpp +++ b/src/server/ServerState.cpp @@ -21,7 +21,7 @@ ServerState::ServerState( , block_types() , world(block_types, wc) , spawn_index(world.Chunks().MakeIndex(wc.spawn, 3)) -, generator(gc, block_types) +, generator(gc) , chunk_loader(world.Chunks(), generator, ws) , skeletons() , spawner(world, skeletons, env.rng) @@ -29,7 +29,7 @@ ServerState::ServerState( , loop_timer(16) { TextureIndex tex_index; env.loader.LoadBlockTypes("default", block_types, tex_index); - generator.Scan(); + generator.LoadTypes(block_types); skeletons.LoadHeadless(); spawner.LimitSkeletons(1, skeletons.size()); server.SetPlayerModel(skeletons[0]); diff --git a/src/standalone/MasterState.cpp b/src/standalone/MasterState.cpp index dedb4ce..ced107d 100644 --- a/src/standalone/MasterState.cpp +++ b/src/standalone/MasterState.cpp @@ -30,7 +30,7 @@ MasterState::MasterState( , manip(env, player.GetEntity()) , input(world, player, manip) , interface(config, env.keymap, input, *this) -, generator(gc, block_types) +, generator(gc) , chunk_loader(world.Chunks(), generator, save) , chunk_renderer(player.GetChunks()) , skeletons() @@ -40,8 +40,8 @@ MasterState::MasterState( , unload(env, world.Chunks(), save) { TextureIndex tex_index; env.loader.LoadBlockTypes("default", block_types, tex_index); - interface.SetInventorySlots(block_types.Size() - 1); - generator.Scan(); + interface.SetInventorySlots(block_types.size() - 1); + generator.LoadTypes(block_types); chunk_renderer.LoadTextures(env.loader, tex_index); chunk_renderer.FogDensity(wc.fog_density); skeletons.Load(); diff --git a/src/world/BlockTypeRegistry.hpp b/src/world/BlockTypeRegistry.hpp index 38afac4..9d9597d 100644 --- a/src/world/BlockTypeRegistry.hpp +++ b/src/world/BlockTypeRegistry.hpp @@ -11,12 +11,23 @@ namespace blank { class BlockTypeRegistry { public: - BlockTypeRegistry(); + using size_type = std::vector::size_type; + using reference = std::vector::reference; + using const_reference = std::vector::const_reference; + using iterator = std::vector::iterator; + using const_iterator = std::vector::const_iterator; public: + BlockTypeRegistry(); + Block::Type Add(const BlockType &); - size_t Size() const noexcept { return types.size(); } + size_t size() const noexcept { return types.size(); } + + iterator begin() noexcept { return types.begin(); } + const_iterator begin() const noexcept { return types.begin(); } + iterator end() noexcept { return types.end(); } + const_iterator end() const noexcept { return types.end(); } BlockType &operator [](Block::Type id) { return types[id]; } const BlockType &operator [](Block::Type id) const { return types[id]; } diff --git a/src/world/Chunk.hpp b/src/world/Chunk.hpp index 23ed869..cc0ae8e 100644 --- a/src/world/Chunk.hpp +++ b/src/world/Chunk.hpp @@ -156,7 +156,12 @@ public: void *BlockData() noexcept { return &blocks[0]; } const void *BlockData() const noexcept { return &blocks[0]; } - static constexpr std::size_t BlockSize() noexcept { return sizeof(blocks) + sizeof(light); } + static constexpr std::size_t BlockSize() noexcept { return offsetof(Chunk, position) - offsetof(Chunk, blocks); } + + bool Generated() const noexcept { return generated; } + void SetGenerated() noexcept { generated = true; } + bool Lighted() const noexcept { return lighted; } + void ScanLights(); void Ref() noexcept { ++ref_count; } void UnRef() noexcept { --ref_count; } @@ -174,8 +179,12 @@ public: private: const BlockTypeRegistry *types; Chunk *neighbor[Block::FACE_COUNT]; + Block blocks[size]; unsigned char light[size]; + bool generated; + bool lighted; + Pos position; int ref_count; bool dirty_model; diff --git a/src/world/ChunkIndex.hpp b/src/world/ChunkIndex.hpp index 91fc704..97956e9 100644 --- a/src/world/ChunkIndex.hpp +++ b/src/world/ChunkIndex.hpp @@ -23,8 +23,14 @@ public: public: bool InRange(const Chunk::Pos &) const noexcept; + bool IsBorder(const Chunk::Pos &) const noexcept; + int Distance(const Chunk::Pos &) const noexcept; + + bool HasAllSurrounding(const Chunk::Pos &) const noexcept; + int IndexOf(const Chunk::Pos &) const noexcept; Chunk::Pos PositionOf(int) const noexcept; + /// returns nullptr if given position is out of range or the chunk /// is not loaded, so also works as a "has" function Chunk *Get(const Chunk::Pos &) noexcept; diff --git a/src/world/ChunkStore.hpp b/src/world/ChunkStore.hpp index 68434bb..3bbe96d 100644 --- a/src/world/ChunkStore.hpp +++ b/src/world/ChunkStore.hpp @@ -23,6 +23,8 @@ public: ChunkIndex &MakeIndex(const Chunk::Pos &base, int extent); void UnregisterIndex(ChunkIndex &); + ChunkIndex *ClosestIndex(const Chunk::Pos &pos); + /// returns nullptr if given position is not loaded Chunk *Get(const Chunk::Pos &); /// returns nullptr if given position is not indexed diff --git a/src/world/Generator.cpp b/src/world/Generator.cpp index f15a252..88ac1eb 100644 --- a/src/world/Generator.cpp +++ b/src/world/Generator.cpp @@ -23,9 +23,10 @@ std::vector candidates; } -Generator::Generator(const Config &config, const BlockTypeRegistry &types) noexcept +Generator::Generator(const Config &config) noexcept : config(config) -, types(types) +, types() +, min_solidity(2.0f) , solidity_noise(config.seed ^ config.solidity.seed_mask) , humidity_noise(config.seed ^ config.humidity.seed_mask) , temperature_noise(config.seed ^ config.temperature.seed_mask) @@ -34,12 +35,18 @@ Generator::Generator(const Config &config, const BlockTypeRegistry &types) noexc } -void Generator::Scan() { - size_t count = 0; - for (size_t i = 0, end = types.Size(); i < end; ++i) { - if (types[i].generate) ++count; +void Generator::LoadTypes(const BlockTypeRegistry ®) { + types.clear(); + min_solidity = 2.0f; + for (const BlockType &type : reg) { + if (type.generate) { + types.push_back(&type); + if (type.min_solidity < min_solidity) { + min_solidity = type.min_solidity; + } + } } - candidates.reserve(count); + candidates.reserve(types.size()); } void Generator::operator ()(Chunk &chunk) const noexcept { @@ -53,30 +60,32 @@ void Generator::operator ()(Chunk &chunk) const noexcept { } } } + chunk.SetGenerated(); } Block Generator::Generate(const glm::vec3 &pos) const noexcept { float solidity = GetValue(solidity_noise, pos, config.solidity); + if (solidity < min_solidity) { + return Block(0); + } float humidity = GetValue(humidity_noise, pos, config.humidity); float temperature = GetValue(temperature_noise, pos, config.temperature); float richness = GetValue(richness_noise, pos, config.richness); candidates.clear(); float total = 0.0f; - for (size_t i = 0, end = types.Size(); i < end; ++i) { - const BlockType &type = types[i]; - if (!type.generate) continue; - if (solidity < type.min_solidity || solidity > type.max_solidity) continue; - if (humidity < type.min_humidity || humidity > type.max_humidity) continue; - if (temperature < type.min_temperature || temperature > type.max_temperature) continue; - if (richness < type.min_richness || richness > type.max_richness) continue; - float solidity_match = 4.0f - ((solidity - type.mid_solidity) * (solidity - type.mid_solidity)); - float humidity_match = 4.0f - ((humidity - type.mid_humidity) * (humidity - type.mid_humidity)); - float temperature_match = 4.0f - ((temperature - type.mid_temperature) * (temperature - type.mid_temperature)); - float richness_match = 4.0f - ((richness - type.mid_richness) * (richness - type.mid_richness)); - float chance = (solidity_match + humidity_match + temperature_match + richness_match) * type.commonness; + for (const BlockType *type : types) { + if (solidity < type->min_solidity || solidity > type->max_solidity) continue; + if (humidity < type->min_humidity || humidity > type->max_humidity) continue; + if (temperature < type->min_temperature || temperature > type->max_temperature) continue; + if (richness < type->min_richness || richness > type->max_richness) continue; + float solidity_match = 4.0f - ((solidity - type->mid_solidity) * (solidity - type->mid_solidity)); + float humidity_match = 4.0f - ((humidity - type->mid_humidity) * (humidity - type->mid_humidity)); + float temperature_match = 4.0f - ((temperature - type->mid_temperature) * (temperature - type->mid_temperature)); + float richness_match = 4.0f - ((richness - type->mid_richness) * (richness - type->mid_richness)); + float chance = (solidity_match + humidity_match + temperature_match + richness_match) * type->commonness; total += chance; - candidates.emplace_back(&type, total); + candidates.emplace_back(type, total); } if (candidates.empty()) { return Block(0); diff --git a/src/world/Generator.hpp b/src/world/Generator.hpp index 5251ac6..cf94356 100644 --- a/src/world/Generator.hpp +++ b/src/world/Generator.hpp @@ -2,15 +2,16 @@ #define BLANK_WORLD_GENERATOR_HPP_ #include "../rand/SimplexNoise.hpp" -#include "../rand/WorleyNoise.hpp" #include +#include #include namespace blank { class Block; +class BlockType; class BlockTypeRegistry; class Chunk; @@ -28,16 +29,15 @@ public: float growth; }; NoiseParam solidity = { 0xA85033F6BCBDD110, 3, 0.5f, 1.0f/64.0f, 2.0f, 2.0f }; - NoiseParam humidity = { 0x3A463FB24B04A901, 3, 0.5f, 1.0f/256.0f, 2.0f, 2.0f }; - NoiseParam temperature = { 0x2530BA6C6134A9FB, 3, 0.5f, 1.0f/512.0f, 2.0f, 2.0f }; + NoiseParam humidity = { 0x3A463FB24B04A901, 2, 0.5f, 1.0f/512.0f, 2.0f, 2.0f }; + NoiseParam temperature = { 0x2530BA6C6134A9FB, 2, 0.5f, 1.0f/1024.0f, 2.0f, 2.0f }; NoiseParam richness = { 0x95A179F180103446, 3, 0.5f, 1.0f/128.0f, 2.0f, 2.0f }; NoiseParam randomness = { 0x074453EEE1496390, 3, 0.5f, 1.0f/16.0f, 2.0f, 2.0f }; }; - explicit Generator(const Config &, const BlockTypeRegistry &) noexcept; + explicit Generator(const Config &) noexcept; - // scan types for generation - void Scan(); + void LoadTypes(const BlockTypeRegistry &); void operator ()(Chunk &) const noexcept; @@ -50,7 +50,9 @@ private: private: const Config &config; - const BlockTypeRegistry &types; + std::vector types; + float min_solidity; + SimplexNoise solidity_noise; SimplexNoise humidity_noise; SimplexNoise temperature_noise; diff --git a/src/world/chunk.cpp b/src/world/chunk.cpp index 6fb4679..7ef09c7 100644 --- a/src/world/chunk.cpp +++ b/src/world/chunk.cpp @@ -32,6 +32,8 @@ Chunk::Chunk(const BlockTypeRegistry &types) noexcept , neighbor{0} , blocks{} , light{0} +, generated(false) +, lighted(false) , position(0, 0, 0) , ref_count(0) , dirty_model(false) @@ -159,7 +161,7 @@ void Chunk::SetBlock(int index, const Block &block) noexcept { blocks[index] = block; Invalidate(); - if (&old_type == &new_type) return; + if (!lighted || &old_type == &new_type) return; if (new_type.luminosity > old_type.luminosity) { // light added @@ -200,104 +202,27 @@ void Chunk::SetBlock(int index, const Block &block) noexcept { } } -namespace { - -// propagate light from a's edge to b -void edge_light( - Chunk &a, const Chunk::Pos &a_pos, - Chunk &b, const Chunk::Pos &b_pos -) noexcept { - if (a.GetLight(a_pos) > 1) { - const BlockType &b_type = b.Type(Chunk::ToIndex(b_pos)); - if (!b_type.block_light) { - light_queue.emplace(&a, a_pos); - } - if (b_type.visible) { - b.Invalidate(); +void Chunk::ScanLights() { + int idx = 0; + Pos pos(0, 0, 0); + for (; pos.z < depth; ++pos.z) { + for (pos.y = 0; pos.y < height; ++pos.y) { + for (pos.x = 0; pos.x < width; ++pos.x, ++idx) { + const BlockType &type = Type(blocks[idx]); + if (type.luminosity) { + SetLight(idx, type.luminosity); + light_queue.emplace(this, pos); + } + } } } -} - + work_light(); + lighted = true; } void Chunk::SetNeighbor(Block::Face face, Chunk &other) noexcept { neighbor[face] = &other; other.neighbor[Block::Opposite(face)] = this; - - switch (face) { - - default: - // error - break; - - case Block::FACE_LEFT: - for (int z = 0; z < depth; ++z) { - for (int y = 0; y < height; ++y) { - Pos my_pos(0, y, z); - Pos other_pos(width - 1, y, z); - edge_light(*this, my_pos, other, other_pos); - edge_light(other, other_pos, *this, my_pos); - } - } - break; - - case Block::FACE_RIGHT: - for (int z = 0; z < depth; ++z) { - for (int y = 0; y < height; ++y) { - Pos my_pos(width - 1, y, z); - Pos other_pos(0, y, z); - edge_light(*this, my_pos, other, other_pos); - edge_light(other, other_pos, *this, my_pos); - } - } - break; - - case Block::FACE_DOWN: - for (int z = 0; z < depth; ++z) { - for (int x = 0; x < width; ++x) { - Pos my_pos(x, 0, z); - Pos other_pos(x, height - 1, z); - edge_light(*this, my_pos, other, other_pos); - edge_light(other, other_pos, *this, my_pos); - } - } - break; - - case Block::FACE_UP: - for (int z = 0; z < depth; ++z) { - for (int x = 0; x < width; ++x) { - Pos my_pos(x, height - 1, z); - Pos other_pos(x, 0, z); - edge_light(*this, my_pos, other, other_pos); - edge_light(other, other_pos, *this, my_pos); - } - } - break; - - case Block::FACE_BACK: - for (int y = 0; y < height; ++y) { - for (int x = 0; x < width; ++x) { - Pos my_pos(x, y, 0); - Pos other_pos(x, y, depth - 1); - edge_light(*this, my_pos, other, other_pos); - edge_light(other, other_pos, *this, my_pos); - } - } - break; - - case Block::FACE_FRONT: - for (int y = 0; y < height; ++y) { - for (int x = 0; x < width; ++x) { - Pos my_pos(x, y, depth - 1); - Pos other_pos(x, y, 0); - edge_light(*this, my_pos, other, other_pos); - edge_light(other, other_pos, *this, my_pos); - } - } - break; - - } - work_light(); } void Chunk::Unlink() noexcept { @@ -680,13 +605,35 @@ bool ChunkLoader::LoadOne() { return false; } + bool generated = false; if (save.Exists(pos)) { save.Read(*chunk); - return false; } else { gen(*chunk); - return true; + generated = true; } + + ChunkIndex *index = store.ClosestIndex(pos); + if (!index) { + return generated; + } + + Chunk::Pos begin(pos - Chunk::Pos(1)); + Chunk::Pos end(pos + Chunk::Pos(2)); + for (Chunk::Pos iter(begin); iter.z < end.z; ++iter.z) { + for (iter.y = begin.y; iter.y < end.y; ++iter.y) { + for (iter.x = begin.x; iter.x < end.x; ++iter.x) { + if (index->IsBorder(iter)) continue; + Chunk *light_chunk = index->Get(iter); + if (!light_chunk || light_chunk->Lighted()) continue; + if (index->HasAllSurrounding(iter)) { + light_chunk->ScanLights(); + } + } + } + } + + return generated; } void ChunkLoader::LoadN(std::size_t n) { @@ -766,7 +713,28 @@ ChunkIndex::~ChunkIndex() { } bool ChunkIndex::InRange(const Chunk::Pos &pos) const noexcept { - return manhattan_radius(pos - base) <= extent; + return Distance(pos) <= extent; +} + +bool ChunkIndex::IsBorder(const Chunk::Pos &pos) const noexcept { + return Distance(pos) == extent; +} + +int ChunkIndex::Distance(const Chunk::Pos &pos) const noexcept { + return manhattan_radius(pos - base); +} + +bool ChunkIndex::HasAllSurrounding(const Chunk::Pos &pos) const noexcept { + Chunk::Pos begin(pos - Chunk::Pos(1)); + Chunk::Pos end(pos + Chunk::Pos(2)); + for (Chunk::Pos iter(begin); iter.z < end.z; ++iter.z) { + for (iter.y = begin.y; iter.y < end.y; ++iter.y) { + for (iter.x = begin.x; iter.x < end.x; ++iter.x) { + if (!Get(iter)) return false; + } + } + } + return true; } int ChunkIndex::IndexOf(const Chunk::Pos &pos) const noexcept { @@ -962,6 +930,21 @@ void ChunkStore::UnregisterIndex(ChunkIndex &index) { } } +ChunkIndex *ChunkStore::ClosestIndex(const Chunk::Pos &pos) { + ChunkIndex *closest_index = nullptr; + int closest_distance = std::numeric_limits::max(); + + for (ChunkIndex &index : indices) { + int distance = index.Distance(pos); + if (distance < closest_distance) { + closest_index = &index; + closest_distance = distance; + } + } + + return closest_index; +} + Chunk *ChunkStore::Get(const Chunk::Pos &pos) { for (ChunkIndex &index : indices) { Chunk *chunk = index.Get(pos); diff --git a/tst/rand/StabilityTest.cpp b/tst/rand/StabilityTest.cpp new file mode 100644 index 0000000..9ed047d --- /dev/null +++ b/tst/rand/StabilityTest.cpp @@ -0,0 +1,227 @@ +#include "StabilityTest.hpp" + +#include "rand/GaloisLFSR.hpp" +#include "rand/SimplexNoise.hpp" + +#include +#include +#include +#include + +CPPUNIT_TEST_SUITE_REGISTRATION(blank::test::StabilityTest); + +using namespace std; + + +namespace blank { +namespace test { + +void StabilityTest::setUp() { + +} + +void StabilityTest::tearDown() { + +} + + +void StabilityTest::testRNG() { + GaloisLFSR random(0); + uint16_t value; + random(value); + CPPUNIT_ASSERT_EQUAL_MESSAGE( + "unexpected value #1 from RNG", + uint16_t(0x0000), value + ); + random(value); + CPPUNIT_ASSERT_EQUAL_MESSAGE( + "unexpected value #2 from RNG", + uint16_t(0x0000), value + ); + random(value); + CPPUNIT_ASSERT_EQUAL_MESSAGE( + "unexpected value #3 from RNG", + uint16_t(0xB000), value + ); + random(value); + CPPUNIT_ASSERT_EQUAL_MESSAGE( + "unexpected value #4 from RNG", + uint16_t(0x0000), value + ); + random(value); + CPPUNIT_ASSERT_EQUAL_MESSAGE( + "unexpected value #5 from RNG", + uint16_t(0x0000), value + ); + random(value); + CPPUNIT_ASSERT_EQUAL_MESSAGE( + "unexpected value #6 from RNG", + uint16_t(0x0000), value + ); + random(value); + CPPUNIT_ASSERT_EQUAL_MESSAGE( + "unexpected value #7 from RNG", + uint16_t(0x4500), value + ); + random(value); + CPPUNIT_ASSERT_EQUAL_MESSAGE( + "unexpected value #8 from RNG", + uint16_t(0x0000), value + ); + CPPUNIT_ASSERT_EQUAL_MESSAGE( + "unexpected value #9 from RNG", + uint16_t(0x0000), value + ); + random(value); + CPPUNIT_ASSERT_EQUAL_MESSAGE( + "unexpected value #10 from RNG", + uint16_t(0x0000), value + ); + random(value); + CPPUNIT_ASSERT_EQUAL_MESSAGE( + "unexpected value #11 from RNG", + uint16_t(0x0000), value + ); + random(value); + CPPUNIT_ASSERT_EQUAL_MESSAGE( + "unexpected value #12 from RNG", + uint16_t(0x2E70), value + ); + random(value); + CPPUNIT_ASSERT_EQUAL_MESSAGE( + "unexpected value #13 from RNG", + uint16_t(0x0000), value + ); + random(value); + CPPUNIT_ASSERT_EQUAL_MESSAGE( + "unexpected value #14 from RNG", + uint16_t(0x0000), value + ); + random(value); + CPPUNIT_ASSERT_EQUAL_MESSAGE( + "unexpected value #15 from RNG", + uint16_t(0x0000), value + ); + random(value); + CPPUNIT_ASSERT_EQUAL_MESSAGE( + "unexpected value #16 from RNG", + uint16_t(0x1011), value + ); + random(value); + CPPUNIT_ASSERT_EQUAL_MESSAGE( + "unexpected value #17 from RNG", + uint16_t(0x0000), value + ); + random(value); + CPPUNIT_ASSERT_EQUAL_MESSAGE( + "unexpected value #18 from RNG", + uint16_t(0x0000), value + ); + random(value); + CPPUNIT_ASSERT_EQUAL_MESSAGE( + "unexpected value #19 from RNG", + uint16_t(0xB000), value + ); + random(value); + CPPUNIT_ASSERT_EQUAL_MESSAGE( + "unexpected value #20 from RNG", + uint16_t(0x0B0B), value + ); + random(value); + CPPUNIT_ASSERT_EQUAL_MESSAGE( + "unexpected value #21 from RNG", + uint16_t(0x0000), value + ); + random(value); + CPPUNIT_ASSERT_EQUAL_MESSAGE( + "unexpected value #22 from RNG", + uint16_t(0x0000), value + ); + random(value); + CPPUNIT_ASSERT_EQUAL_MESSAGE( + "unexpected value #23 from RNG", + uint16_t(0x1500), value + ); + random(value); + CPPUNIT_ASSERT_EQUAL_MESSAGE( + "unexpected value #24 from RNG", + uint16_t(0x0454), value + ); + random(value); + CPPUNIT_ASSERT_EQUAL_MESSAGE( + "unexpected value #25 from RNG", + uint16_t(0x0000), value + ); + random(value); + CPPUNIT_ASSERT_EQUAL_MESSAGE( + "unexpected value #26 from RNG", + uint16_t(0x0000), value + ); + random(value); + CPPUNIT_ASSERT_EQUAL_MESSAGE( + "unexpected value #27 from RNG", + uint16_t(0xC970), value + ); + random(value); + CPPUNIT_ASSERT_EQUAL_MESSAGE( + "unexpected value #28 from RNG", + uint16_t(0x02E5), value + ); + random(value); + CPPUNIT_ASSERT_EQUAL_MESSAGE( + "unexpected value #29 from RNG", + uint16_t(0x0000), value + ); + random(value); + CPPUNIT_ASSERT_EQUAL_MESSAGE( + "unexpected value #30 from RNG", + uint16_t(0x0000), value + ); + random(value); + CPPUNIT_ASSERT_EQUAL_MESSAGE( + "unexpected value #31 from RNG", + uint16_t(0x0101), value + ); + random(value); + CPPUNIT_ASSERT_EQUAL_MESSAGE( + "unexpected value #32 from RNG", + uint16_t(0x0100), value + ); +} + +void StabilityTest::testSimplex() { + SimplexNoise noise(0); + + Assert(noise, glm::vec3(0.0f, 0.0f, 0.0f), 0.0f); + Assert(noise, glm::vec3(0.0f, 0.0f, 1.0f), 0.652221322059631f); + Assert(noise, glm::vec3(0.0f, 1.0f, 0.0f), 0.867977976799011f); + Assert(noise, glm::vec3(0.0f, 1.0f, 1.0f), -0.107878111302853f); + Assert(noise, glm::vec3(1.0f, 0.0f, 0.0f), -0.107878260314465f); + Assert(noise, glm::vec3(1.0f, 0.0f, 1.0f), -6.31356940061778e-08f); + Assert(noise, glm::vec3(1.0f, 1.0f, 0.0f), -0.107878245413303f); + Assert(noise, glm::vec3(1.0f, 1.0f, 1.0f), 0.0f); + + Assert(noise, glm::vec3( 0.0f, 0.0f, -1.0f), -0.107878483831882f); + Assert(noise, glm::vec3( 0.0f, -1.0f, 0.0f), -0.760099768638611f); + Assert(noise, glm::vec3( 0.0f, -1.0f, -1.0f), 0.0f); + Assert(noise, glm::vec3(-1.0f, 0.0f, 0.0f), 0.760099768638611f); + Assert(noise, glm::vec3(-1.0f, 0.0f, -1.0f), 0.0f); + Assert(noise, glm::vec3(-1.0f, -1.0f, 0.0f), -0.107878118753433f); + Assert(noise, glm::vec3(-1.0f, -1.0f, -1.0f), 0.0f); +} + +void StabilityTest::Assert( + const SimplexNoise &noise, + const glm::vec3 &position, + float expected +) { + stringstream msg; + msg << "unexpected simplex noise value at " << position; + CPPUNIT_ASSERT_DOUBLES_EQUAL_MESSAGE( + msg.str(), + expected, noise(position), numeric_limits::epsilon() + ); +} + +} +} diff --git a/tst/rand/StabilityTest.hpp b/tst/rand/StabilityTest.hpp new file mode 100644 index 0000000..a4ea86e --- /dev/null +++ b/tst/rand/StabilityTest.hpp @@ -0,0 +1,42 @@ +#ifndef BLANK_TEST_RAND_STABILITYTEST_HPP +#define BLANK_TEST_RAND_STABILITYTEST_HPP + +#include +#include + + + +namespace blank { + +class SimplexNoise; + +namespace test { + +class StabilityTest +: public CppUnit::TestFixture { + +CPPUNIT_TEST_SUITE(StabilityTest); + +CPPUNIT_TEST(testRNG); +CPPUNIT_TEST(testSimplex); + +CPPUNIT_TEST_SUITE_END(); + +public: + void setUp(); + void tearDown(); + + void testRNG(); + void testSimplex(); + + static void Assert( + const SimplexNoise &noise, + const glm::vec3 &position, + float expected); + +}; + +} +} + +#endif diff --git a/tst/world/ChunkTest.cpp b/tst/world/ChunkTest.cpp index 0da68d0..c40f9da 100644 --- a/tst/world/ChunkTest.cpp +++ b/tst/world/ChunkTest.cpp @@ -380,6 +380,8 @@ void ChunkTest::testLight() { void ChunkTest::testLightPropagation() { unique_ptr chunk(new Chunk(types)); + // this is required to make the chunk do lighting propagation at all + chunk->ScanLights(); // 0 air, 1 solid, 2 solid and emits light level of 5 chunk->SetBlock(Chunk::Pos(7, 7, 7), Block(2)); -- 2.39.2