X-Git-Url: http://git.localhorst.tv/?a=blobdiff_plain;f=src%2Fworld%2Fchunk.cpp;h=7f7b185dc91eaff3d9c71c0126ddcd414b3d02d2;hb=d2f4c8720ae2326fac4203fa4984d835e875b355;hp=190fe3d7b9e4c4aa25d4fbaf6745845c97b0565b;hpb=5998b18978bd8e7a0c9deb516474634e1d3521c9;p=blank.git diff --git a/src/world/chunk.cpp b/src/world/chunk.cpp index 190fe3d..7f7b185 100644 --- a/src/world/chunk.cpp +++ b/src/world/chunk.cpp @@ -1,53 +1,75 @@ #include "BlockLookup.hpp" #include "Chunk.hpp" +#include "ChunkIndex.hpp" #include "ChunkLoader.hpp" +#include "ChunkRenderer.hpp" +#include "ChunkStore.hpp" #include "Generator.hpp" #include "WorldCollision.hpp" +#include "../app/Assets.hpp" +#include "../geometry/distance.hpp" +#include "../graphics/BlockLighting.hpp" +#include "../graphics/BlockMesh.hpp" +#include "../graphics/Viewport.hpp" +#include "../io/WorldSave.hpp" #include -#include #include +#include #include +#include +#include + namespace blank { -constexpr int Chunk::width; -constexpr int Chunk::height; -constexpr int Chunk::depth; +constexpr int Chunk::side; constexpr int Chunk::size; Chunk::Chunk(const BlockTypeRegistry &types) noexcept : types(&types) , neighbor{0} -, blocks{} +, gravity() , light{0} -, model() +, generated(false) +, lighted(false) , position(0, 0, 0) -, dirty(false) { +, ref_count(0) +, dirty_mesh(false) +, dirty_save(false) { } Chunk::Chunk(Chunk &&other) noexcept : types(other.types) -, model(std::move(other.model)) +, gravity(std::move(other.gravity)) +, generated(other.generated) +, lighted(other.lighted) , position(other.position) -, dirty(other.dirty) { +, ref_count(other.ref_count) +, dirty_mesh(other.dirty_mesh) +, dirty_save(other.dirty_save) { std::copy(other.neighbor, other.neighbor + sizeof(neighbor), neighbor); std::copy(other.blocks, other.blocks + sizeof(blocks), blocks); std::copy(other.light, other.light + sizeof(light), light); + other.ref_count = 0; } Chunk &Chunk::operator =(Chunk &&other) noexcept { types = other.types; std::copy(other.neighbor, other.neighbor + sizeof(neighbor), neighbor); + gravity = std::move(other.gravity); std::copy(other.blocks, other.blocks + sizeof(blocks), blocks); std::copy(other.light, other.light + sizeof(light), light); - model = std::move(other.model); + generated = other.generated; + lighted = other.lighted; position = other.position; - dirty = other.dirty; + std::swap(ref_count, other.ref_count); + dirty_mesh = other.dirty_save; + dirty_save = other.dirty_save; return *this; } @@ -57,9 +79,9 @@ namespace { struct SetNode { Chunk *chunk; - Chunk::Pos pos; + RoughLocation::Fine pos; - SetNode(Chunk *chunk, Chunk::Pos pos) + SetNode(Chunk *chunk, RoughLocation::Fine pos) : chunk(chunk), pos(pos) { } int Get() const noexcept { return chunk->GetLight(pos); } @@ -67,6 +89,9 @@ struct SetNode { const BlockType &GetType() const noexcept { return chunk->Type(Chunk::ToIndex(pos)); } + int EmitLevel() const noexcept { return GetType().luminosity; } + bool EmitsLight() const noexcept { return EmitLevel() > 0; } + bool HasNext(Block::Face face) noexcept { const BlockType &type = GetType(); if (type.block_light && !type.luminosity) return false; @@ -85,7 +110,7 @@ struct UnsetNode int level; - UnsetNode(Chunk *chunk, Chunk::Pos pos) + UnsetNode(Chunk *chunk, RoughLocation::Fine pos) : SetNode(chunk, pos), level(Get()) { } UnsetNode(const SetNode &set) @@ -129,9 +154,13 @@ void work_dark() noexcept { for (int face = 0; face < Block::FACE_COUNT; ++face) { if (node.HasNext(Block::Face(face))) { UnsetNode other = node.GetNext(Block::Face(face)); - // TODO: if there a light source here with the same level this will err if (other.Get() != 0 && other.Get() < node.level) { - other.Set(0); + if (other.EmitsLight()) { + other.Set(other.EmitLevel()); + light_queue.emplace(other); + } else { + other.Set(0); + } dark_queue.emplace(other); } else { light_queue.emplace(other); @@ -148,8 +177,15 @@ void Chunk::SetBlock(int index, const Block &block) noexcept { const BlockType &new_type = Type(block); blocks[index] = block; + Invalidate(); + + if (old_type.gravity && !new_type.gravity) { + gravity.erase(index); + } else if (new_type.gravity && !old_type.gravity) { + gravity.insert(index); + } - if (&old_type == &new_type) return; + if (!lighted || &old_type == &new_type) return; if (new_type.luminosity > old_type.luminosity) { // light added @@ -175,7 +211,7 @@ void Chunk::SetBlock(int index, const Block &block) noexcept { } else if (!new_type.block_light && old_type.block_light) { // obstacle removed int level = 0; - Pos pos(ToPos(index)); + RoughLocation::Fine pos(ToPos(index)); for (int face = 0; face < Block::FACE_COUNT; ++face) { BlockLookup next_block(this, pos, Block::Face(face)); if (next_block) { @@ -190,115 +226,39 @@ 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; + RoughLocation::Fine pos(0, 0, 0); + for (; pos.z < side; ++pos.z) { + for (pos.y = 0; pos.y < side; ++pos.y) { + for (pos.x = 0; pos.x < side; ++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(Chunk &other) noexcept { - if (other.position == position + Pos(-1, 0, 0)) { - if (neighbor[Block::FACE_LEFT] != &other) { - neighbor[Block::FACE_LEFT] = &other; - other.neighbor[Block::FACE_RIGHT] = this; - 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); - } - } - work_light(); - } - } else if (other.position == position + Pos(1, 0, 0)) { - if (neighbor[Block::FACE_RIGHT] != &other) { - neighbor[Block::FACE_RIGHT] = &other; - other.neighbor[Block::FACE_LEFT] = this; - 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); - } - } - work_light(); - } - } else if (other.position == position + Pos(0, -1, 0)) { - if (neighbor[Block::FACE_DOWN] != &other) { - neighbor[Block::FACE_DOWN] = &other; - other.neighbor[Block::FACE_UP] = this; - 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); - } - } - work_light(); - } - } else if (other.position == position + Pos(0, 1, 0)) { - if (neighbor[Block::FACE_UP] != &other) { - neighbor[Block::FACE_UP] = &other; - other.neighbor[Block::FACE_DOWN] = this; - 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); - } - } - work_light(); - } - } else if (other.position == position + Pos(0, 0, -1)) { - if (neighbor[Block::FACE_BACK] != &other) { - neighbor[Block::FACE_BACK] = &other; - other.neighbor[Block::FACE_FRONT] = this; - 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); - } - } - work_light(); - } - } else if (other.position == position + Pos(0, 0, 1)) { - if (neighbor[Block::FACE_FRONT] != &other) { - neighbor[Block::FACE_FRONT] = &other; - other.neighbor[Block::FACE_BACK] = this; - 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); - } - } - work_light(); +void Chunk::ScanActive() { + gravity.clear(); + for (int index = 0; index < size; ++index) { + if (Type(index).gravity) { + gravity.insert(gravity.end(), index); } } } -void Chunk::ClearNeighbors() noexcept { +void Chunk::SetNeighbor(Block::Face face, Chunk &other) noexcept { + neighbor[face] = &other; + other.neighbor[Block::Opposite(face)] = this; +} + +void Chunk::Unlink() noexcept { for (int face = 0; face < Block::FACE_COUNT; ++face) { if (neighbor[face]) { neighbor[face]->neighbor[Block::Opposite(Block::Face(face))] = nullptr; @@ -319,7 +279,7 @@ int Chunk::GetLight(int index) const noexcept { return light[index]; } -float Chunk::GetVertexLight(const Pos &pos, const BlockModel::Position &vtx, const EntityModel::Normal &norm) const noexcept { +float Chunk::GetVertexLight(const RoughLocation::Fine &pos, const BlockMesh::Position &vtx, const EntityMesh::Normal &norm) const noexcept { int index = ToIndex(pos); float light = GetLight(index); @@ -409,7 +369,21 @@ float Chunk::GetVertexLight(const Pos &pos, const BlockModel::Position &vtx, con } -bool Chunk::IsSurface(const Pos &pos) const noexcept { +glm::vec3 Chunk::GravityAt(const ExactLocation &coords) const noexcept { + glm::vec3 grav(0.0f); + for (int index : gravity) { + RoughLocation::Fine block_pos(ToPos(index)); + ExactLocation block_coords(position, ToCoords(block_pos)); + // trust that block type hasn't changed + grav += Type(index).gravity->GetGravity( + coords.Difference(block_coords).Absolute(), + ToTransform(block_pos, index)); + } + return grav; +} + + +bool Chunk::IsSurface(const RoughLocation::Fine &pos) const noexcept { const Block &block = BlockAt(pos); if (!Type(block).visible) { return false; @@ -424,48 +398,47 @@ bool Chunk::IsSurface(const Pos &pos) const noexcept { } -void Chunk::Draw() noexcept { - if (dirty) { - Update(); - } - model.Draw(); -} - - bool Chunk::Intersection( const Ray &ray, - const glm::mat4 &M, - int &blkid, - float &dist, - glm::vec3 &normal -) const noexcept { + const ExactLocation::Coarse &reference, + WorldCollision &coll +) noexcept { int idx = 0; - blkid = -1; - dist = std::numeric_limits::infinity(); - for (int z = 0; z < depth; ++z) { - for (int y = 0; y < height; ++y) { - for (int x = 0; x < width; ++x, ++idx) { + coll.chunk = this; + coll.block = -1; + coll.depth = std::numeric_limits::infinity(); + for (int z = 0; z < side; ++z) { + for (int y = 0; y < side; ++y) { + for (int x = 0; x < side; ++x, ++idx) { const BlockType &type = Type(idx); - if (!type.visible) { + if (!type.collision || !type.shape) { + continue; + } + RoughLocation::Fine pos(x, y, z); + + // center of the blok relative to the ray + glm::vec3 relative_center(glm::vec3((position - reference) * ExactLocation::Extent() + pos) + 0.5f); + if (ray.DistanceSquared(relative_center) > 3.0f) { continue; } + float cur_dist; glm::vec3 cur_norm; - if (type.shape->Intersects(ray, M * ToTransform(Pos(x, y, z), idx), cur_dist, cur_norm)) { - if (cur_dist < dist) { - blkid = idx; - dist = cur_dist; - normal = cur_norm; + if (type.shape->Intersects(ray, ToTransform(reference, pos, idx), cur_dist, cur_norm)) { + if (cur_dist < coll.depth) { + coll.block = idx; + coll.depth = cur_dist; + coll.normal = cur_norm; } } } } } - if (blkid < 0) { + if (coll.block < 0) { return false; } else { - normal = glm::vec3(BlockAt(blkid).Transform() * glm::vec4(normal, 0.0f)); + coll.normal = glm::vec3(BlockAt(coll.block).Transform() * glm::vec4(coll.normal, 0.0f)); return true; } } @@ -475,7 +448,7 @@ bool Chunk::Intersection( const glm::mat4 &Mbox, const glm::mat4 &Mchunk, std::vector &col -) const noexcept { +) noexcept { bool any = false; float penetration; glm::vec3 normal; @@ -483,14 +456,33 @@ bool Chunk::Intersection( if (!blank::Intersection(box, Mbox, Bounds(), Mchunk, penetration, normal)) { return false; } - for (int idx = 0, z = 0; z < depth; ++z) { - for (int y = 0; y < height; ++y) { - for (int x = 0; x < width; ++x, ++idx) { + + // box's origin relative to the chunk + const glm::vec3 box_coords(Mbox[3] - Mchunk[3]); + const float box_rad = box.OriginRadius(); + + // assume a bounding radius of 2 for blocks + constexpr float block_rad = 2.0f; + const float bb_radius = box_rad + block_rad; + + const RoughLocation::Fine begin(max( + RoughLocation::Fine(0), + RoughLocation::Fine(floor(box_coords - bb_radius)) + )); + const RoughLocation::Fine end(min( + RoughLocation::Fine(side - 1), + RoughLocation::Fine(ceil(box_coords + bb_radius)) + ) - 1); + + for (RoughLocation::Fine pos(begin); pos.z < end.y; ++pos.z) { + for (pos.y = begin.y; pos.y < end.y; ++pos.y) { + for (pos.x = begin.x; pos.x < end.x; ++pos.x) { + int idx = ToIndex(pos); const BlockType &type = Type(idx); - if (!type.collision) { + if (!type.collision || !type.shape) { continue; } - if (type.shape->Intersects(Mchunk * ToTransform(Pos(x, y, z), idx), box, Mbox, penetration, normal)) { + if (type.shape->Intersects(Mchunk * ToTransform(pos, idx), box, Mbox, penetration, normal)) { col.emplace_back(this, idx, penetration, normal); any = true; } @@ -500,59 +492,106 @@ bool Chunk::Intersection( return any; } +bool Chunk::Intersection( + const Entity &entity, + const glm::mat4 &Mentity, + const glm::mat4 &Mchunk, + std::vector &col +) noexcept { + // entity's origin relative to the chunk + const glm::vec3 entity_coords(Mentity[3] - Mchunk[3]); + const float ec_radius = entity.Radius() + Radius(); -namespace { + if (distance2(entity_coords, Center()) > ec_radius * ec_radius) { + return false; + } -BlockModel::Buffer buf; + bool any = false; + float penetration; + glm::vec3 normal; + // assume a bounding radius of 2 for blocks + constexpr float block_rad = 2.0f; + const float eb_radius = entity.Radius() + block_rad; + + const RoughLocation::Fine begin(max( + RoughLocation::Fine(0), + RoughLocation::Fine(floor(entity_coords - eb_radius)) + )); + const RoughLocation::Fine end(min( + RoughLocation::Fine(side), + RoughLocation::Fine(ceil(entity_coords + eb_radius)) + )); + + for (RoughLocation::Fine pos(begin); pos.z < end.z; ++pos.z) { + for (pos.y = begin.y; pos.y < end.y; ++pos.y) { + for (pos.x = begin.x; pos.x < end.x; ++pos.x) { + int idx = ToIndex(pos); + const BlockType &type = Type(idx); + if (!type.collision || !type.shape) { + continue; + } + if (type.shape->Intersects(Mchunk * ToTransform(pos, idx), entity.Bounds(), Mentity, penetration, normal)) { + col.emplace_back(this, idx, penetration, normal); + any = true; + } + } + } + } + return any; } -void Chunk::CheckUpdate() noexcept { - if (dirty) { - Update(); - } + +namespace { + +BlockMesh::Buffer buf; + } -void Chunk::Update() noexcept { +void Chunk::Update(BlockMesh &model) noexcept { int vtx_count = 0, idx_count = 0; for (const auto &block : blocks) { - const Shape *shape = Type(block).shape; - vtx_count += shape->VertexCount(); - idx_count += shape->VertexIndexCount(); + const BlockType &type = Type(block); + if (type.visible && type.shape) { + vtx_count += type.shape->VertexCount(); + idx_count += type.shape->IndexCount(); + } } buf.Clear(); buf.Reserve(vtx_count, idx_count); - int idx = 0; - BlockModel::Index vtx_counter = 0; - for (size_t z = 0; z < depth; ++z) { - for (size_t y = 0; y < height; ++y) { - for (size_t x = 0; x < width; ++x, ++idx) { - const BlockType &type = Type(BlockAt(idx)); - const Pos pos(x, y, z); - - if (!type.visible || Obstructed(pos).All()) continue; - - type.FillBlockModel(buf, ToTransform(pos, idx), vtx_counter); - size_t vtx_begin = vtx_counter; - vtx_counter += type.shape->VertexCount(); - - for (size_t vtx = vtx_begin; vtx < vtx_counter; ++vtx) { - buf.lights.emplace_back(GetVertexLight( - pos, - buf.vertices[vtx], - type.shape->VertexNormal(vtx - vtx_begin, BlockAt(idx).Transform()) - )); + if (idx_count > 0) { + int idx = 0; + BlockMesh::Index vtx_counter = 0; + for (size_t z = 0; z < side; ++z) { + for (size_t y = 0; y < side; ++y) { + for (size_t x = 0; x < side; ++x, ++idx) { + const BlockType &type = Type(BlockAt(idx)); + const RoughLocation::Fine pos(x, y, z); + + if (!type.visible || !type.shape || Obstructed(pos).All()) continue; + + type.FillBlockMesh(buf, ToTransform(pos, idx), vtx_counter); + size_t vtx_begin = vtx_counter; + vtx_counter += type.shape->VertexCount(); + + for (size_t vtx = vtx_begin; vtx < vtx_counter; ++vtx) { + buf.lights.emplace_back(GetVertexLight( + pos, + buf.vertices[vtx], + type.shape->VertexNormal(vtx - vtx_begin, BlockAt(idx).Transform()) + )); + } } } } } model.Update(buf); - dirty = false; + ClearMesh(); } -Block::FaceSet Chunk::Obstructed(const Pos &pos) const noexcept { +Block::FaceSet Chunk::Obstructed(const RoughLocation::Fine &pos) const noexcept { Block::FaceSet result; for (int f = 0; f < Block::FACE_COUNT; ++f) { @@ -566,17 +605,21 @@ Block::FaceSet Chunk::Obstructed(const Pos &pos) const noexcept { return result; } -glm::mat4 Chunk::ToTransform(const Pos &pos, int idx) const noexcept { +glm::mat4 Chunk::ToTransform(const RoughLocation::Fine &pos, int idx) const noexcept { return glm::translate(ToCoords(pos)) * BlockAt(idx).Transform(); } +glm::mat4 Chunk::ToTransform(const ExactLocation::Coarse &ref, const RoughLocation::Fine &pos, int idx) const noexcept { + return glm::translate(ExactLocation::Fine((position - ref) * ExactLocation::Extent()) + ToCoords(pos)) * BlockAt(idx).Transform(); +} -BlockLookup::BlockLookup(Chunk *c, const Chunk::Pos &p) noexcept + +BlockLookup::BlockLookup(Chunk *c, const RoughLocation::Fine &p) noexcept : chunk(c), pos(p) { - while (pos.x >= Chunk::width) { + while (pos.x >= Chunk::side) { if (chunk->HasNeighbor(Block::FACE_RIGHT)) { chunk = &chunk->GetNeighbor(Block::FACE_RIGHT); - pos.x -= Chunk::width; + pos.x -= Chunk::side; } else { chunk = nullptr; return; @@ -585,16 +628,16 @@ BlockLookup::BlockLookup(Chunk *c, const Chunk::Pos &p) noexcept while (pos.x < 0) { if (chunk->HasNeighbor(Block::FACE_LEFT)) { chunk = &chunk->GetNeighbor(Block::FACE_LEFT); - pos.x += Chunk::width; + pos.x += Chunk::side; } else { chunk = nullptr; return; } } - while (pos.y >= Chunk::height) { + while (pos.y >= Chunk::side) { if (chunk->HasNeighbor(Block::FACE_UP)) { chunk = &chunk->GetNeighbor(Block::FACE_UP); - pos.y -= Chunk::height; + pos.y -= Chunk::side; } else { chunk = nullptr; return; @@ -603,16 +646,16 @@ BlockLookup::BlockLookup(Chunk *c, const Chunk::Pos &p) noexcept while (pos.y < 0) { if (chunk->HasNeighbor(Block::FACE_DOWN)) { chunk = &chunk->GetNeighbor(Block::FACE_DOWN); - pos.y += Chunk::height; + pos.y += Chunk::side; } else { chunk = nullptr; return; } } - while (pos.z >= Chunk::depth) { + while (pos.z >= Chunk::side) { if (chunk->HasNeighbor(Block::FACE_FRONT)) { chunk = &chunk->GetNeighbor(Block::FACE_FRONT); - pos.z -= Chunk::depth; + pos.z -= Chunk::side; } else { chunk = nullptr; return; @@ -621,7 +664,7 @@ BlockLookup::BlockLookup(Chunk *c, const Chunk::Pos &p) noexcept while (pos.z < 0) { if (chunk->HasNeighbor(Block::FACE_BACK)) { chunk = &chunk->GetNeighbor(Block::FACE_BACK); - pos.z += Chunk::depth; + pos.z += Chunk::side; } else { chunk = nullptr; return; @@ -629,249 +672,511 @@ BlockLookup::BlockLookup(Chunk *c, const Chunk::Pos &p) noexcept } } -BlockLookup::BlockLookup(Chunk *c, const Chunk::Pos &p, Block::Face face) noexcept +BlockLookup::BlockLookup(Chunk *c, const RoughLocation::Fine &p, Block::Face face) noexcept : chunk(c), pos(p) { pos += Block::FaceNormal(face); if (!Chunk::InBounds(pos)) { - pos -= Block::FaceNormal(face) * Chunk::Extent(); + pos -= Block::FaceNormal(face) * ExactLocation::Extent(); chunk = &chunk->GetNeighbor(face); } } -ChunkLoader::ChunkLoader(const Config &config, const BlockTypeRegistry ®, const Generator &gen) noexcept -: base(0, 0, 0) -, reg(reg) +ChunkLoader::ChunkLoader( + ChunkStore &store, + const Generator &gen, + const WorldSave &save +) noexcept +: store(store) , gen(gen) -, loaded() -, to_generate() -, to_free() -, gen_timer(config.gen_limit) -, load_dist(config.load_dist) -, unload_dist(config.unload_dist) { - gen_timer.Start(); +, save(save) { + } -namespace { +void ChunkLoader::Update(int dt) { + // check if there's chunks waiting to be loaded + // load until one of load or generation limits was hit + constexpr int max_load = 10; + constexpr int max_gen = 1; + int loaded = 0; + int generated = 0; + while (loaded < max_load && generated < max_gen && store.HasMissing()) { + if (LoadOne()) { + ++generated; + } else { + ++loaded; + } + } -struct ChunkLess { + // store a few chunks as well + constexpr int max_save = 10; + int saved = 0; + for (Chunk &chunk : store) { + if (chunk.ShouldUpdateSave()) { + save.Write(chunk); + ++saved; + if (saved >= max_save) { + break; + } + } + } +} - explicit ChunkLess(const Chunk::Pos &base) noexcept - : base(base) { } +int ChunkLoader::ToLoad() const noexcept { + return store.EstimateMissing(); +} - bool operator ()(const Chunk::Pos &a, const Chunk::Pos &b) const noexcept { - Chunk::Pos da(base - a); - Chunk::Pos db(base - b); - return - da.x * da.x + da.y * da.y + da.z * da.z < - db.x * db.x + db.y * db.y + db.z * db.z; - } +bool ChunkLoader::LoadOne() { + if (!store.HasMissing()) return false; - Chunk::Pos base; + ExactLocation::Coarse pos = store.NextMissing(); + Chunk *chunk = store.Allocate(pos); + if (!chunk) { + // chunk store corrupted? + return false; + } -}; + bool generated = false; + if (save.Exists(pos)) { + save.Read(*chunk); + } else { + gen(*chunk); + generated = true; + } -} + ChunkIndex *index = store.ClosestIndex(pos); + if (!index) { + return generated; + } -void ChunkLoader::Generate(const Chunk::Pos &from, const Chunk::Pos &to) { - for (int z = from.z; z < to.z; ++z) { - for (int y = from.y; y < to.y; ++y) { - for (int x = from.x; x < to.x; ++x) { - Chunk::Pos pos(x, y, z); - if (Known(pos)) { - continue; - } else if (pos == base) { - Generate(pos); - - // light testing - // for (int i = 0; i < 16; ++i) { - // for (int j = 0; j < 16; ++j) { - // loaded.back().SetBlock(Chunk::Pos{ i, j, 0 }, Block(1)); - // loaded.back().SetBlock(Chunk::Pos{ i, j, 15 }, Block(1)); - // loaded.back().SetBlock(Chunk::Pos{ 0, j, i }, Block(1)); - // loaded.back().SetBlock(Chunk::Pos{ 15, j, i }, Block(1)); - // } - // } - // loaded.back().SetBlock(Chunk::Pos{ 1, 0, 1 }, Block(13)); - // loaded.back().SetBlock(Chunk::Pos{ 14, 0, 1 }, Block(13)); - // loaded.back().SetBlock(Chunk::Pos{ 1, 0, 14 }, Block(13)); - // loaded.back().SetBlock(Chunk::Pos{ 14, 0, 14 }, Block(13)); - // loaded.back().SetBlock(Chunk::Pos{ 1, 15, 1 }, Block(13)); - // loaded.back().SetBlock(Chunk::Pos{ 14, 15, 1 }, Block(13)); - // loaded.back().SetBlock(Chunk::Pos{ 1, 15, 14 }, Block(13)); - // loaded.back().SetBlock(Chunk::Pos{ 14, 15, 14 }, Block(13)); - // loaded.back().SetBlock(Chunk::Pos{ 7, 7, 0 }, Block(13)); - // loaded.back().SetBlock(Chunk::Pos{ 8, 7, 0 }, Block(13)); - // loaded.back().SetBlock(Chunk::Pos{ 7, 8, 0 }, Block(13)); - // loaded.back().SetBlock(Chunk::Pos{ 8, 8, 0 }, Block(13)); - // loaded.back().SetBlock(Chunk::Pos{ 7, 7, 15 }, Block(13)); - // loaded.back().SetBlock(Chunk::Pos{ 8, 7, 15 }, Block(13)); - // loaded.back().SetBlock(Chunk::Pos{ 7, 8, 15 }, Block(13)); - // loaded.back().SetBlock(Chunk::Pos{ 8, 8, 15 }, Block(13)); - // loaded.back().SetBlock(Chunk::Pos{ 0, 7, 7 }, Block(13)); - // loaded.back().SetBlock(Chunk::Pos{ 0, 7, 8 }, Block(13)); - // loaded.back().SetBlock(Chunk::Pos{ 0, 8, 7 }, Block(13)); - // loaded.back().SetBlock(Chunk::Pos{ 0, 8, 8 }, Block(13)); - // loaded.back().SetBlock(Chunk::Pos{ 15, 7, 7 }, Block(13)); - // loaded.back().SetBlock(Chunk::Pos{ 15, 7, 8 }, Block(13)); - // loaded.back().SetBlock(Chunk::Pos{ 15, 8, 7 }, Block(13)); - // loaded.back().SetBlock(Chunk::Pos{ 15, 8, 8 }, Block(13)); - // loaded.back().Invalidate(); - // loaded.back().CheckUpdate(); - - // orientation testing - // for (int i = 0; i < Block::FACE_COUNT; ++i) { - // for (int j = 0; j < Block::TURN_COUNT; ++j) { - // loaded.back().BlockAt(512 * j + 2 * i) = Block(3 * (j + 1), Block::Face(i), Block::Turn(j)); - // } - // } - // loaded.back().Invalidate(); - // loaded.back().CheckUpdate(); - } else { - to_generate.emplace_back(pos); + ExactLocation::Coarse begin(pos - ExactLocation::Coarse(1)); + ExactLocation::Coarse end(pos + ExactLocation::Coarse(2)); + for (ExactLocation::Coarse 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) continue; + if (index->HasAllSurrounding(iter)) { + if (!light_chunk->Lighted()) { + light_chunk->ScanLights(); + } else { + light_chunk->InvalidateMesh(); + } } } } } - to_generate.sort(ChunkLess(base)); -} -Chunk &ChunkLoader::Generate(const Chunk::Pos &pos) { - loaded.emplace_back(reg); - Chunk &chunk = loaded.back(); - chunk.Position(pos); - gen(chunk); - Insert(chunk); - return chunk; + return generated; } -void ChunkLoader::Insert(Chunk &chunk) noexcept { - for (Chunk &other : loaded) { - chunk.SetNeighbor(other); +void ChunkLoader::LoadN(std::size_t n) { + std::size_t end = std::min(n, std::size_t(ToLoad())); + for (std::size_t i = 0; i < end && store.HasMissing(); ++i) { + LoadOne(); } } -std::list::iterator ChunkLoader::Remove(std::list::iterator chunk) noexcept { - // fetch next entry while chunk's still in the list - std::list::iterator next = chunk; - ++next; - // unlink neighbors so they won't reference a dead chunk - chunk->ClearNeighbors(); - // and move it from loaded to free list - to_free.splice(to_free.end(), loaded, chunk); - return next; + +ChunkRenderer::ChunkRenderer(ChunkIndex &index) +: index(index) +, models(index.TotalChunks()) +, block_tex() +, fog_density(0.0f) { + } -Chunk *ChunkLoader::Loaded(const Chunk::Pos &pos) noexcept { - for (Chunk &chunk : loaded) { - if (chunk.Position() == pos) { - return &chunk; +ChunkRenderer::~ChunkRenderer() { + +} + +int ChunkRenderer::MissingChunks() const noexcept { + return index.MissingChunks(); +} + +void ChunkRenderer::LoadTextures(const AssetLoader &loader, const ResourceIndex &tex_index) { + block_tex.Bind(); + loader.LoadTextures(tex_index, block_tex); + block_tex.FilterNearest(); +} + +void ChunkRenderer::Update(int dt) { + for (int i = 0, updates = 0; updates < dt && i < index.TotalChunks(); ++i) { + if (!index[i]) continue; + if (!index[i]->Lighted() && index.HasAllSurrounding(index[i]->Position())) { + index[i]->ScanLights(); + } + if (index[i]->ShouldUpdateMesh()) { + index[i]->Update(models[i]); + ++updates; } } - return nullptr; } -bool ChunkLoader::Queued(const Chunk::Pos &pos) noexcept { - for (const Chunk::Pos &chunk : to_generate) { - if (chunk == pos) { - return true; +void ChunkRenderer::Render(Viewport &viewport) { + BlockLighting &chunk_prog = viewport.ChunkProgram(); + chunk_prog.SetTexture(block_tex); + chunk_prog.SetFogDensity(fog_density); + + Frustum frustum(transpose(chunk_prog.GetVP())); + AABB box; + + for (int i = 0; i < index.TotalChunks(); ++i) { + if (!index[i]) continue; + box.min = (index[i]->Position() - index.Base()) * ExactLocation::Extent(); + box.max = box.min + ExactLocation::FExtent(); + + if (!CullTest(box, frustum)) { + if (index[i]->ShouldUpdateMesh()) { + index[i]->Update(models[i]); + } + if (!models[i].Empty()) { + chunk_prog.SetM(index[i]->Transform(index.Base())); + models[i].Draw(); + } } } - return false; } -bool ChunkLoader::Known(const Chunk::Pos &pos) noexcept { - if (Loaded(pos)) return true; - return Queued(pos); + +ChunkIndex::ChunkIndex(ChunkStore &store, const ExactLocation::Coarse &base, int extent) +: store(store) +, base(base) +, extent(extent) +, side_length(2 * extent + 1) +, total_length(side_length * side_length * side_length) +, total_indexed(0) +, last_missing(0) +, stride(1, side_length, side_length * side_length) +, chunks(total_length, nullptr) { + Scan(); } -Chunk &ChunkLoader::ForceLoad(const Chunk::Pos &pos) { - Chunk *chunk = Loaded(pos); - if (chunk) { - return *chunk; - } +ChunkIndex::~ChunkIndex() { + Clear(); +} - for (auto iter(to_generate.begin()), end(to_generate.end()); iter != end; ++iter) { - if (*iter == pos) { - to_generate.erase(iter); - break; +bool ChunkIndex::InRange(const ExactLocation::Coarse &pos) const noexcept { + return Distance(pos) <= extent; +} + +bool ChunkIndex::IsBorder(const ExactLocation::Coarse &pos) const noexcept { + return Distance(pos) == extent; +} + +int ChunkIndex::Distance(const ExactLocation::Coarse &pos) const noexcept { + return manhattan_radius(pos - base); +} + +bool ChunkIndex::HasAllSurrounding(const ExactLocation::Coarse &pos) const noexcept { + ExactLocation::Coarse begin(pos - ExactLocation::Coarse(1)); + ExactLocation::Coarse end(pos + ExactLocation::Coarse(2)); + for (ExactLocation::Coarse 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 ExactLocation::Coarse &pos) const noexcept { + ExactLocation::Coarse mod_pos( + GetCol(pos.x), + GetCol(pos.y), + GetCol(pos.z) + ); + return mod_pos.x * stride.x + + mod_pos.y * stride.y + + mod_pos.z * stride.z; +} + +ExactLocation::Coarse ChunkIndex::PositionOf(int i) const noexcept { + ExactLocation::Coarse zero_pos( + (i / stride.x) % side_length, + (i / stride.y) % side_length, + (i / stride.z) % side_length + ); + ExactLocation::Coarse zero_base( + GetCol(base.x), + GetCol(base.y), + GetCol(base.z) + ); + ExactLocation::Coarse base_relative(zero_pos - zero_base); + if (base_relative.x > extent) base_relative.x -= side_length; + else if (base_relative.x < -extent) base_relative.x += side_length; + if (base_relative.y > extent) base_relative.y -= side_length; + else if (base_relative.y < -extent) base_relative.y += side_length; + if (base_relative.z > extent) base_relative.z -= side_length; + else if (base_relative.z < -extent) base_relative.z += side_length; + return base + base_relative; +} - return Generate(pos); +Chunk *ChunkIndex::Get(const ExactLocation::Coarse &pos) noexcept { + if (InRange(pos)) { + return chunks[IndexOf(pos)]; + } else { + return nullptr; + } } -bool ChunkLoader::OutOfRange(const Chunk::Pos &pos) const noexcept { - return std::abs(base.x - pos.x) > unload_dist - || std::abs(base.y - pos.y) > unload_dist - || std::abs(base.z - pos.z) > unload_dist; +const Chunk *ChunkIndex::Get(const ExactLocation::Coarse &pos) const noexcept { + if (InRange(pos)) { + return chunks[IndexOf(pos)]; + } else { + return nullptr; + } } -void ChunkLoader::Rebase(const Chunk::Pos &new_base) { - if (new_base == base) { +void ChunkIndex::Rebase(const ExactLocation::Coarse &new_base) { + if (new_base == base) return; + + ExactLocation::Coarse diff(new_base - base); + + if (manhattan_radius(diff) > extent) { + // that's more than half, so probably not worth shifting + base = new_base; + Clear(); + Scan(); + store.Clean(); return; } - base = new_base; - // unload far away chunks - for (auto iter(loaded.begin()), end(loaded.end()); iter != end;) { - if (OutOfRange(*iter)) { - iter = Remove(iter); - } else { - ++iter; - } + while (diff.x > 0) { + Shift(Block::FACE_RIGHT); + --diff.x; } - // abort far away queued chunks - for (auto iter(to_generate.begin()), end(to_generate.end()); iter != end;) { - if (OutOfRange(*iter)) { - iter = to_generate.erase(iter); - } else { - ++iter; + while (diff.x < 0) { + Shift(Block::FACE_LEFT); + ++diff.x; + } + while (diff.y > 0) { + Shift(Block::FACE_UP); + --diff.y; + } + while (diff.y < 0) { + Shift(Block::FACE_DOWN); + ++diff.y; + } + while (diff.z > 0) { + Shift(Block::FACE_FRONT); + --diff.z; + } + while (diff.z < 0) { + Shift(Block::FACE_BACK); + ++diff.z; + } + store.Clean(); +} + +int ChunkIndex::GetCol(int c) const noexcept { + c %= side_length; + if (c < 0) c += side_length; + return c; +} + +void ChunkIndex::Shift(Block::Face f) { + int a_axis = Block::Axis(f); + int b_axis = (a_axis + 1) % 3; + int c_axis = (a_axis + 2) % 3; + int dir = Block::Direction(f); + base[a_axis] += dir; + int a = GetCol(base[a_axis] + (extent * dir)); + int a_stride = a * stride[a_axis]; + for (int b = 0; b < side_length; ++b) { + int b_stride = b * stride[b_axis]; + for (int c = 0; c < side_length; ++c) { + int bc_stride = b_stride + c * stride[c_axis]; + int index = a_stride + bc_stride; + Unset(index); + int neighbor = ((a - dir + side_length) % side_length) * stride[a_axis] + bc_stride; + if (chunks[neighbor] && chunks[neighbor]->HasNeighbor(f)) { + Set(index, chunks[neighbor]->GetNeighbor(f)); + } } } - // add missing new chunks - GenerateSurrounding(base); } -void ChunkLoader::GenerateSurrounding(const Chunk::Pos &pos) { - const Chunk::Pos offset(load_dist, load_dist, load_dist); - Generate(pos - offset, pos + offset); +void ChunkIndex::Clear() noexcept { + for (int i = 0; i < total_length && total_indexed > 0; ++i) { + Unset(i); + } } -void ChunkLoader::Update(int dt) { - // check if a chunk generation is scheduled for this frame - // and if there's a chunk waiting to be generated - gen_timer.Update(dt); - if (!gen_timer.Hit() || to_generate.empty()) { - return; +void ChunkIndex::Scan() noexcept { + for (Chunk &chunk : store) { + Register(chunk); + } +} + +void ChunkIndex::Register(Chunk &chunk) noexcept { + if (InRange(chunk.Position())) { + Set(IndexOf(chunk.Position()), chunk); + } +} + +void ChunkIndex::Set(int index, Chunk &chunk) noexcept { + Unset(index); + chunks[index] = &chunk; + chunk.Ref(); + ++total_indexed; +} + +void ChunkIndex::Unset(int index) noexcept { + if (chunks[index]) { + chunks[index]->UnRef(); + chunks[index] = nullptr; + --total_indexed; + } +} + +ExactLocation::Coarse ChunkIndex::NextMissing() noexcept { + if (MissingChunks() > 0) { + int roundtrip = last_missing; + last_missing = (last_missing + 1) % total_length; + while (chunks[last_missing]) { + last_missing = (last_missing + 1) % total_length; + if (last_missing == roundtrip) { + break; + } + } } + return PositionOf(last_missing); +} - // take position of next chunk in queue - Chunk::Pos pos(to_generate.front()); - to_generate.pop_front(); - // look if the same chunk was already generated and still lingering - for (auto iter(to_free.begin()), end(to_free.end()); iter != end; ++iter) { - if (iter->Position() == pos) { - loaded.splice(loaded.end(), to_free, iter); - Insert(loaded.back()); +ChunkStore::ChunkStore(const BlockTypeRegistry &types) +: types(types) +, loaded() +, free() +, indices() { + +} + +ChunkStore::~ChunkStore() { + +} + +ChunkIndex &ChunkStore::MakeIndex(const ExactLocation::Coarse &pos, int extent) { + indices.emplace_back(*this, pos, extent); + return indices.back(); +} + +void ChunkStore::UnregisterIndex(ChunkIndex &index) { + for (auto i = indices.begin(), end = indices.end(); i != end; ++i) { + if (&*i == &index) { + indices.erase(i); return; + } else { + ++i; + } + } +} + +ChunkIndex *ChunkStore::ClosestIndex(const ExactLocation::Coarse &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 ExactLocation::Coarse &pos) noexcept { + for (ChunkIndex &index : indices) { + Chunk *chunk = index.Get(pos); + if (chunk) { + return chunk; + } + } + return nullptr; +} + +const Chunk *ChunkStore::Get(const ExactLocation::Coarse &pos) const noexcept { + for (const ChunkIndex &index : indices) { + const Chunk *chunk = index.Get(pos); + if (chunk) { + return chunk; } } + return nullptr; +} - // if the free list is empty, allocate a new chunk - // otherwise clear an unused one - if (to_free.empty()) { - loaded.emplace_back(reg); +Chunk *ChunkStore::Allocate(const ExactLocation::Coarse &pos) { + Chunk *chunk = Get(pos); + if (chunk) { + return chunk; + } + if (free.empty()) { + loaded.emplace(loaded.begin(), types); } else { - to_free.front().ClearNeighbors(); - loaded.splice(loaded.end(), to_free, to_free.begin()); + loaded.splice(loaded.begin(), free, free.begin()); + loaded.front().Unlink(); } + chunk = &loaded.front(); + chunk->Position(pos); + for (ChunkIndex &index : indices) { + if (index.InRange(pos)) { + index.Register(*chunk); + } + } + for (int i = 0; i < Block::FACE_COUNT; ++i) { + Block::Face face = Block::Face(i); + ExactLocation::Coarse neighbor_pos(pos + Block::FaceNormal(face)); + Chunk *neighbor = Get(neighbor_pos); + if (neighbor) { + chunk->SetNeighbor(face, *neighbor); + } + } + return chunk; +} - Chunk &chunk = loaded.back(); - chunk.Position(pos); - gen(chunk); - Insert(chunk); +bool ChunkStore::HasMissing() const noexcept { + for (const ChunkIndex &index : indices) { + if (index.MissingChunks() > 0) { + return true; + } + } + return false; +} + +int ChunkStore::EstimateMissing() const noexcept { + int missing = 0; + for (const ChunkIndex &index : indices) { + missing += index.MissingChunks(); + } + return missing; +} + +ExactLocation::Coarse ChunkStore::NextMissing() noexcept { + for (ChunkIndex &index : indices) { + if (index.MissingChunks()) { + return index.NextMissing(); + } + } + return ExactLocation::Coarse(0, 0, 0); +} + +void ChunkStore::Clean() { + for (auto i = loaded.begin(), end = loaded.end(); i != end;) { + if (i->Referenced() || i->ShouldUpdateSave()) { + ++i; + } else { + auto chunk = i; + ++i; + free.splice(free.end(), loaded, chunk); + chunk->Unlink(); + chunk->InvalidateMesh(); + } + } } }