src/world/chunk.cpp

   1 #include "BlockLookup.hpp"
   2 #include "Chunk.hpp"
   3 #include "ChunkIndex.hpp"
   4 #include "ChunkLoader.hpp"
   5 #include "ChunkRenderer.hpp"
   6 #include "ChunkStore.hpp"
   7
   8 #include "Generator.hpp"
   9 #include "WorldCollision.hpp"
  10 #include "../app/Assets.hpp"
  11 #include "../geometry/distance.hpp"
  12 #include "../graphics/BlockLighting.hpp"
  13 #include "../graphics/BlockMesh.hpp"
  14 #include "../graphics/Viewport.hpp"
  15 #include "../io/WorldSave.hpp"
  16
  17 #include <algorithm>
  18 #include <limits>
  19 #include <ostream>
  20 #include <queue>
  21
  22 #include <iostream>
  23 #include <glm/gtx/io.hpp>
  24
  25
  26 namespace blank {
  27
  28 constexpr int Chunk::side;
  29 constexpr int Chunk::size;
  30
  31
  32 Chunk::Chunk(const BlockTypeRegistry &types) noexcept
  33 : types(&types)
  34 , neighbor{0}
  35 , blocks{}
  36 , light{0}
  37 , generated(false)
  38 , lighted(false)
  39 , position(0, 0, 0)
  40 , ref_count(0)
  41 , dirty_mesh(false)
  42 , dirty_save(false) {
  43
  44 }
  45
  46 Chunk::Chunk(Chunk &&other) noexcept
  47 : types(other.types)
  48 , generated(other.generated)
  49 , lighted(other.lighted)
  50 , position(other.position)
  51 , ref_count(other.ref_count)
  52 , dirty_mesh(other.dirty_mesh)
  53 , dirty_save(other.dirty_save) {
  54         std::copy(other.neighbor, other.neighbor + sizeof(neighbor), neighbor);
  55         std::copy(other.blocks, other.blocks + sizeof(blocks), blocks);
  56         std::copy(other.light, other.light + sizeof(light), light);
  57         other.ref_count = 0;
  58 }
  59
  60 Chunk &Chunk::operator =(Chunk &&other) noexcept {
  61         types = other.types;
  62         std::copy(other.neighbor, other.neighbor + sizeof(neighbor), neighbor);
  63         std::copy(other.blocks, other.blocks + sizeof(blocks), blocks);
  64         std::copy(other.light, other.light + sizeof(light), light);
  65         generated = other.generated;
  66         lighted = other.lighted;
  67         position = other.position;
  68         std::swap(ref_count, other.ref_count);
  69         dirty_mesh = other.dirty_save;
  70         dirty_save = other.dirty_save;
  71         return *this;
  72 }
  73
  74
  75 namespace {
  76
  77 struct SetNode {
  78
  79         Chunk *chunk;
  80         RoughLocation::Fine pos;
  81
  82         SetNode(Chunk *chunk, RoughLocation::Fine pos)
  83         : chunk(chunk), pos(pos) { }
  84
  85         int Get() const noexcept { return chunk->GetLight(pos); }
  86         void Set(int level) noexcept { chunk->SetLight(pos, level); }
  87
  88         const BlockType &GetType() const noexcept { return chunk->Type(Chunk::ToIndex(pos)); }
  89
  90         bool HasNext(Block::Face face) noexcept {
  91                 const BlockType &type = GetType();
  92                 if (type.block_light && !type.luminosity) return false;
  93                 const BlockLookup next(chunk, pos, face);
  94                 return next;
  95         }
  96         SetNode GetNext(Block::Face face) noexcept {
  97                 const BlockLookup next(chunk, pos, face);
  98                 return SetNode(&next.GetChunk(), next.GetBlockPos());
  99         }
 100
 101 };
 102
 103 struct UnsetNode
 104 : public SetNode {
 105
 106         int level;
 107
 108         UnsetNode(Chunk *chunk, RoughLocation::Fine pos)
 109         : SetNode(chunk, pos), level(Get()) { }
 110
 111         UnsetNode(const SetNode &set)
 112         : SetNode(set), level(Get()) { }
 113
 114
 115         bool HasNext(Block::Face face) noexcept {
 116                 const BlockLookup next(chunk, pos, face);
 117                 return next;
 118         }
 119         UnsetNode GetNext(Block::Face face) noexcept { return UnsetNode(SetNode::GetNext(face)); }
 120
 121 };
 122
 123 std::queue<SetNode> light_queue;
 124 std::queue<UnsetNode> dark_queue;
 125
 126 void work_light() noexcept {
 127         while (!light_queue.empty()) {
 128                 SetNode node = light_queue.front();
 129                 light_queue.pop();
 130
 131                 int level = node.Get() - 1;
 132                 for (int face = 0; face < Block::FACE_COUNT; ++face) {
 133                         if (node.HasNext(Block::Face(face))) {
 134                                 SetNode other = node.GetNext(Block::Face(face));
 135                                 if (other.Get() < level) {
 136                                         other.Set(level);
 137                                         light_queue.emplace(other);
 138                                 }
 139                         }
 140                 }
 141         }
 142 }
 143
 144 void work_dark() noexcept {
 145         while (!dark_queue.empty()) {
 146                 UnsetNode node = dark_queue.front();
 147                 dark_queue.pop();
 148
 149                 for (int face = 0; face < Block::FACE_COUNT; ++face) {
 150                         if (node.HasNext(Block::Face(face))) {
 151                                 UnsetNode other = node.GetNext(Block::Face(face));
 152                                 // TODO: if there a light source here with the same level this will err
 153                                 if (other.Get() != 0 && other.Get() < node.level) {
 154                                         other.Set(0);
 155                                         dark_queue.emplace(other);
 156                                 } else {
 157                                         light_queue.emplace(other);
 158                                 }
 159                         }
 160                 }
 161         }
 162 }
 163
 164 }
 165
 166 void Chunk::SetBlock(int index, const Block &block) noexcept {
 167         const BlockType &old_type = Type(blocks[index]);
 168         const BlockType &new_type = Type(block);
 169
 170         blocks[index] = block;
 171         Invalidate();
 172
 173         if (!lighted || &old_type == &new_type) return;
 174
 175         if (new_type.luminosity > old_type.luminosity) {
 176                 // light added
 177                 SetLight(index, new_type.luminosity);
 178                 light_queue.emplace(this, ToPos(index));
 179                 work_light();
 180         } else if (new_type.luminosity < old_type.luminosity) {
 181                 // light removed
 182                 dark_queue.emplace(this, ToPos(index));
 183                 SetLight(index, 0);
 184                 work_dark();
 185                 SetLight(index, new_type.luminosity);
 186                 light_queue.emplace(this, ToPos(index));
 187                 work_light();
 188         } else if (new_type.block_light && !old_type.block_light) {
 189                 // obstacle added
 190                 if (GetLight(index) > 0) {
 191                         dark_queue.emplace(this, ToPos(index));
 192                         SetLight(index, 0);
 193                         work_dark();
 194                         work_light();
 195                 }
 196         } else if (!new_type.block_light && old_type.block_light) {
 197                 // obstacle removed
 198                 int level = 0;
 199                 RoughLocation::Fine pos(ToPos(index));
 200                 for (int face = 0; face < Block::FACE_COUNT; ++face) {
 201                         BlockLookup next_block(this, pos, Block::Face(face));
 202                         if (next_block) {
 203                                 level = std::max(level, next_block.GetLight());
 204                         }
 205                 }
 206                 if (level > 1) {
 207                         SetLight(index, level - 1);
 208                         light_queue.emplace(this, pos);
 209                         work_light();
 210                 }
 211         }
 212 }
 213
 214 void Chunk::ScanLights() {
 215         int idx = 0;
 216         RoughLocation::Fine pos(0, 0, 0);
 217         for (; pos.z < side; ++pos.z) {
 218                 for (pos.y = 0; pos.y < side; ++pos.y) {
 219                         for (pos.x = 0; pos.x < side; ++pos.x, ++idx) {
 220                                 const BlockType &type = Type(blocks[idx]);
 221                                 if (type.luminosity) {
 222                                         SetLight(idx, type.luminosity);
 223                                         light_queue.emplace(this, pos);
 224                                 }
 225                         }
 226                 }
 227         }
 228         work_light();
 229         lighted = true;
 230 }
 231
 232 void Chunk::SetNeighbor(Block::Face face, Chunk &other) noexcept {
 233         neighbor[face] = &other;
 234         other.neighbor[Block::Opposite(face)] = this;
 235 }
 236
 237 void Chunk::Unlink() noexcept {
 238         for (int face = 0; face < Block::FACE_COUNT; ++face) {
 239                 if (neighbor[face]) {
 240                         neighbor[face]->neighbor[Block::Opposite(Block::Face(face))] = nullptr;
 241                         neighbor[face] = nullptr;
 242                 }
 243         }
 244 }
 245
 246
 247 void Chunk::SetLight(int index, int level) noexcept {
 248         if (light[index] != level) {
 249                 light[index] = level;
 250                 Invalidate();
 251         }
 252 }
 253
 254 int Chunk::GetLight(int index) const noexcept {
 255         return light[index];
 256 }
 257
 258 float Chunk::GetVertexLight(const RoughLocation::Fine &pos, const BlockMesh::Position &vtx, const EntityMesh::Normal &norm) const noexcept {
 259         int index = ToIndex(pos);
 260         float light = GetLight(index);
 261
 262         Block::Face direct_face(Block::NormalFace(norm));
 263         // tis okay
 264         BlockLookup direct(const_cast<Chunk *>(this), pos, Block::NormalFace(norm));
 265         if (direct) {
 266                 float direct_light = direct.GetLight();
 267                 if (direct_light > light) {
 268                         light = direct_light;
 269                 }
 270         } else {
 271                 return light;
 272         }
 273
 274         if (Type(BlockAt(index)).luminosity > 0 || direct.GetType().block_light) {
 275                 return light;
 276         }
 277
 278         Block::Face edge[2];
 279         switch (Block::Axis(direct_face)) {
 280                 case 0: // X
 281                         edge[0] = (vtx.y - pos.y) > 0.5f ? Block::FACE_UP : Block::FACE_DOWN;
 282                         edge[1] = (vtx.z - pos.z) > 0.5f ? Block::FACE_FRONT : Block::FACE_BACK;
 283                         break;
 284                 case 1: // Y
 285                         edge[0] = (vtx.z - pos.z) > 0.5f ? Block::FACE_FRONT : Block::FACE_BACK;
 286                         edge[1] = (vtx.x - pos.x) > 0.5f ? Block::FACE_RIGHT : Block::FACE_LEFT;
 287                         break;
 288                 case 2: // Z
 289                         edge[0] = (vtx.x - pos.x) > 0.5f ? Block::FACE_RIGHT : Block::FACE_LEFT;
 290                         edge[1] = (vtx.y - pos.y) > 0.5f ? Block::FACE_UP : Block::FACE_DOWN;
 291                         break;
 292         }
 293
 294         int num = 1;
 295         int occlusion = 0;
 296
 297         BlockLookup next[2] = {
 298                 direct.Next(edge[0]),
 299                 direct.Next(edge[1]),
 300         };
 301
 302         if (next[0]) {
 303                 if (next[0].GetType().block_light) {
 304                         ++occlusion;
 305                 } else {
 306                         light += next[0].GetLight();
 307                         ++num;
 308                 }
 309         }
 310         if (next[1]) {
 311                 if (next[1].GetType().block_light) {
 312                         ++occlusion;
 313                 } else {
 314                         light += next[1].GetLight();
 315                         ++num;
 316                 }
 317         }
 318         if (occlusion < 2) {
 319                 if (next[0]) {
 320                         BlockLookup corner = next[0].Next(edge[1]);
 321                         if (corner) {
 322                                 if (corner.GetType().block_light) {
 323                                         ++occlusion;
 324                                 } else {
 325                                         light += corner.GetLight();
 326                                         ++num;
 327                                 }
 328                         }
 329                 } else if (next[1]) {
 330                         BlockLookup corner = next[1].Next(edge[0]);
 331                         if (corner) {
 332                                 if (corner.GetType().block_light) {
 333                                         ++occlusion;
 334                                 } else {
 335                                         light += corner.GetLight();
 336                                         ++num;
 337                                 }
 338                         }
 339                 }
 340         } else {
 341                 ++occlusion;
 342         }
 343
 344         return (light / num) - (occlusion * 0.8f);
 345 }
 346
 347
 348 bool Chunk::IsSurface(const RoughLocation::Fine &pos) const noexcept {
 349         const Block &block = BlockAt(pos);
 350         if (!Type(block).visible) {
 351                 return false;
 352         }
 353         for (int face = 0; face < Block::FACE_COUNT; ++face) {
 354                 BlockLookup next = BlockLookup(const_cast<Chunk *>(this), pos, Block::Face(face));
 355                 if (!next || !next.GetType().visible) {
 356                         return true;
 357                 }
 358         }
 359         return false;
 360 }
 361
 362
 363 bool Chunk::Intersection(
 364         const Ray &ray,
 365         const glm::mat4 &M,
 366         WorldCollision &coll
 367 ) noexcept {
 368         int idx = 0;
 369         coll.chunk = this;
 370         coll.block = -1;
 371         coll.depth = std::numeric_limits<float>::infinity();
 372         for (int z = 0; z < side; ++z) {
 373                 for (int y = 0; y < side; ++y) {
 374                         for (int x = 0; x < side; ++x, ++idx) {
 375                                 const BlockType &type = Type(idx);
 376                                 if (!type.collision || !type.shape) {
 377                                         continue;
 378                                 }
 379                                 float cur_dist;
 380                                 glm::vec3 cur_norm;
 381                                 if (type.shape->Intersects(ray, M * ToTransform(RoughLocation::Fine(x, y, z), idx), cur_dist, cur_norm)) {
 382                                         if (cur_dist < coll.depth) {
 383                                                 coll.block = idx;
 384                                                 coll.depth = cur_dist;
 385                                                 coll.normal = cur_norm;
 386                                         }
 387                                 }
 388                         }
 389                 }
 390         }
 391
 392         if (coll.block < 0) {
 393                 return false;
 394         } else {
 395                 coll.normal = glm::vec3(BlockAt(coll.block).Transform() * glm::vec4(coll.normal, 0.0f));
 396                 return true;
 397         }
 398 }
 399
 400 bool Chunk::Intersection(
 401         const AABB &box,
 402         const glm::mat4 &Mbox,
 403         const glm::mat4 &Mchunk,
 404         std::vector<WorldCollision> &col
 405 ) noexcept {
 406         bool any = false;
 407         float penetration;
 408         glm::vec3 normal;
 409
 410         if (!blank::Intersection(box, Mbox, Bounds(), Mchunk, penetration, normal)) {
 411                 return false;
 412         }
 413
 414         // box's origin relative to the chunk
 415         const glm::vec3 box_coords(Mbox[3] - Mchunk[3]);
 416         const float box_rad = box.OriginRadius();
 417
 418         // assume a bounding radius of 2 for blocks
 419         constexpr float block_rad = 2.0f;
 420         const float bb_radius = box_rad + block_rad;
 421
 422         const RoughLocation::Fine begin(max(
 423                 RoughLocation::Fine(0),
 424                 RoughLocation::Fine(floor(box_coords - bb_radius))
 425         ));
 426         const RoughLocation::Fine end(min(
 427                 RoughLocation::Fine(side - 1),
 428                 RoughLocation::Fine(ceil(box_coords + bb_radius))
 429         ) - 1);
 430
 431         for (RoughLocation::Fine pos(begin); pos.z < end.y; ++pos.z) {
 432                 for (pos.y = begin.y; pos.y < end.y; ++pos.y) {
 433                         for (pos.x = begin.x; pos.x < end.x; ++pos.x) {
 434                                 int idx = ToIndex(pos);
 435                                 const BlockType &type = Type(idx);
 436                                 if (!type.collision || !type.shape) {
 437                                         continue;
 438                                 }
 439                                 if (type.shape->Intersects(Mchunk * ToTransform(pos, idx), box, Mbox, penetration, normal)) {
 440                                         col.emplace_back(this, idx, penetration, normal);
 441                                         any = true;
 442                                 }
 443                         }
 444                 }
 445         }
 446         return any;
 447 }
 448
 449 bool Chunk::Intersection(
 450         const Entity &entity,
 451         const glm::mat4 &Mentity,
 452         const glm::mat4 &Mchunk,
 453         std::vector<WorldCollision> &col
 454 ) noexcept {
 455         // entity's origin relative to the chunk
 456         const glm::vec3 entity_coords(Mentity[3] - Mchunk[3]);
 457         const float ec_radius = entity.Radius() + Radius();
 458
 459         if (distance_squared(entity_coords, Center()) > ec_radius * ec_radius) {
 460                 return false;
 461         }
 462
 463         if (entity.ID() == 1) {
 464                 std::cout << "chunk: " << (Position() * 16) << ", entity: " << entity.AbsolutePosition() << std::endl;
 465                 std::cout << "\tMentity[3]: " << Mentity[3] << std::endl;
 466                 std::cout << "\tMchunk[3]: " << Mentity[3] << std::endl;
 467         }
 468
 469         bool any = false;
 470         float penetration;
 471         glm::vec3 normal;
 472
 473         // assume a bounding radius of 2 for blocks
 474         constexpr float block_rad = 2.0f;
 475         const float eb_radius = entity.Radius() + block_rad;
 476
 477         const RoughLocation::Fine begin(max(
 478                 RoughLocation::Fine(0),
 479                 RoughLocation::Fine(floor(entity_coords - eb_radius))
 480         ));
 481         const RoughLocation::Fine end(min(
 482                 RoughLocation::Fine(side - 1),
 483                 RoughLocation::Fine(ceil(entity_coords + eb_radius))
 484         ) - 1);
 485
 486         for (RoughLocation::Fine pos(begin); pos.z < end.y; ++pos.z) {
 487                 for (pos.y = begin.y; pos.y < end.y; ++pos.y) {
 488                         for (pos.x = begin.x; pos.x < end.x; ++pos.x) {
 489                                 int idx = ToIndex(pos);
 490                                 const BlockType &type = Type(idx);
 491                                 if (!type.collision || !type.shape) {
 492                                         continue;
 493                                 }
 494                                 if (type.shape->Intersects(Mchunk * ToTransform(pos, idx), entity.Bounds(), Mentity, penetration, normal)) {
 495                                         col.emplace_back(this, idx, penetration, normal);
 496                                         any = true;
 497                                 }
 498                         }
 499                 }
 500         }
 501         return any;
 502 }
 503
 504
 505 namespace {
 506
 507 BlockMesh::Buffer buf;
 508
 509 }
 510
 511 void Chunk::Update(BlockMesh &model) noexcept {
 512         int vtx_count = 0, idx_count = 0;
 513         for (const auto &block : blocks) {
 514                 const BlockType &type = Type(block);
 515                 if (type.visible && type.shape) {
 516                         vtx_count += type.shape->VertexCount();
 517                         idx_count += type.shape->IndexCount();
 518                 }
 519         }
 520         buf.Clear();
 521         buf.Reserve(vtx_count, idx_count);
 522
 523         if (idx_count > 0) {
 524                 int idx = 0;
 525                 BlockMesh::Index vtx_counter = 0;
 526                 for (size_t z = 0; z < side; ++z) {
 527                         for (size_t y = 0; y < side; ++y) {
 528                                 for (size_t x = 0; x < side; ++x, ++idx) {
 529                                         const BlockType &type = Type(BlockAt(idx));
 530                                         const RoughLocation::Fine pos(x, y, z);
 531
 532                                         if (!type.visible || !type.shape || Obstructed(pos).All()) continue;
 533
 534                                         type.FillBlockMesh(buf, ToTransform(pos, idx), vtx_counter);
 535                                         size_t vtx_begin = vtx_counter;
 536                                         vtx_counter += type.shape->VertexCount();
 537
 538                                         for (size_t vtx = vtx_begin; vtx < vtx_counter; ++vtx) {
 539                                                 buf.lights.emplace_back(GetVertexLight(
 540                                                         pos,
 541                                                         buf.vertices[vtx],
 542                                                         type.shape->VertexNormal(vtx - vtx_begin, BlockAt(idx).Transform())
 543                                                 ));
 544                                         }
 545                                 }
 546                         }
 547                 }
 548         }
 549
 550         model.Update(buf);
 551         ClearMesh();
 552 }
 553
 554 Block::FaceSet Chunk::Obstructed(const RoughLocation::Fine &pos) const noexcept {
 555         Block::FaceSet result;
 556
 557         for (int f = 0; f < Block::FACE_COUNT; ++f) {
 558                 Block::Face face = Block::Face(f);
 559                 BlockLookup next(const_cast<Chunk *>(this), pos, face);
 560                 if (next && next.GetType().FaceFilled(next.GetBlock(), Block::Opposite(face))) {
 561                         result.Set(face);
 562                 }
 563         }
 564
 565         return result;
 566 }
 567
 568 glm::mat4 Chunk::ToTransform(const RoughLocation::Fine &pos, int idx) const noexcept {
 569         return glm::translate(ToCoords(pos)) * BlockAt(idx).Transform();
 570 }
 571
 572
 573 BlockLookup::BlockLookup(Chunk *c, const RoughLocation::Fine &p) noexcept
 574 : chunk(c), pos(p) {
 575         while (pos.x >= Chunk::side) {
 576                 if (chunk->HasNeighbor(Block::FACE_RIGHT)) {
 577                         chunk = &chunk->GetNeighbor(Block::FACE_RIGHT);
 578                         pos.x -= Chunk::side;
 579                 } else {
 580                         chunk = nullptr;
 581                         return;
 582                 }
 583         }
 584         while (pos.x < 0) {
 585                 if (chunk->HasNeighbor(Block::FACE_LEFT)) {
 586                         chunk = &chunk->GetNeighbor(Block::FACE_LEFT);
 587                         pos.x += Chunk::side;
 588                 } else {
 589                         chunk = nullptr;
 590                         return;
 591                 }
 592         }
 593         while (pos.y >= Chunk::side) {
 594                 if (chunk->HasNeighbor(Block::FACE_UP)) {
 595                         chunk = &chunk->GetNeighbor(Block::FACE_UP);
 596                         pos.y -= Chunk::side;
 597                 } else {
 598                         chunk = nullptr;
 599                         return;
 600                 }
 601         }
 602         while (pos.y < 0) {
 603                 if (chunk->HasNeighbor(Block::FACE_DOWN)) {
 604                         chunk = &chunk->GetNeighbor(Block::FACE_DOWN);
 605                         pos.y += Chunk::side;
 606                 } else {
 607                         chunk = nullptr;
 608                         return;
 609                 }
 610         }
 611         while (pos.z >= Chunk::side) {
 612                 if (chunk->HasNeighbor(Block::FACE_FRONT)) {
 613                         chunk = &chunk->GetNeighbor(Block::FACE_FRONT);
 614                         pos.z -= Chunk::side;
 615                 } else {
 616                         chunk = nullptr;
 617                         return;
 618                 }
 619         }
 620         while (pos.z < 0) {
 621                 if (chunk->HasNeighbor(Block::FACE_BACK)) {
 622                         chunk = &chunk->GetNeighbor(Block::FACE_BACK);
 623                         pos.z += Chunk::side;
 624                 } else {
 625                         chunk = nullptr;
 626                         return;
 627                 }
 628         }
 629 }
 630
 631 BlockLookup::BlockLookup(Chunk *c, const RoughLocation::Fine &p, Block::Face face) noexcept
 632 : chunk(c), pos(p) {
 633         pos += Block::FaceNormal(face);
 634         if (!Chunk::InBounds(pos)) {
 635                 pos -= Block::FaceNormal(face) * ExactLocation::Extent();
 636                 chunk = &chunk->GetNeighbor(face);
 637         }
 638 }
 639
 640
 641 ChunkLoader::ChunkLoader(
 642         ChunkStore &store,
 643         const Generator &gen,
 644         const WorldSave &save
 645 ) noexcept
 646 : store(store)
 647 , gen(gen)
 648 , save(save) {
 649
 650 }
 651
 652 void ChunkLoader::Update(int dt) {
 653         // check if there's chunks waiting to be loaded
 654         // load until one of load or generation limits was hit
 655         constexpr int max_load = 10;
 656         constexpr int max_gen = 1;
 657         int loaded = 0;
 658         int generated = 0;
 659         while (loaded < max_load && generated < max_gen && store.HasMissing()) {
 660                 if (LoadOne()) {
 661                         ++generated;
 662                 } else {
 663                         ++loaded;
 664                 }
 665         }
 666
 667         // store a few chunks as well
 668         constexpr int max_save = 10;
 669         int saved = 0;
 670         for (Chunk &chunk : store) {
 671                 if (chunk.ShouldUpdateSave()) {
 672                         save.Write(chunk);
 673                         ++saved;
 674                         if (saved >= max_save) {
 675                                 break;
 676                         }
 677                 }
 678         }
 679 }
 680
 681 int ChunkLoader::ToLoad() const noexcept {
 682         return store.EstimateMissing();
 683 }
 684
 685 bool ChunkLoader::LoadOne() {
 686         if (!store.HasMissing()) return false;
 687
 688         ExactLocation::Coarse pos = store.NextMissing();
 689         Chunk *chunk = store.Allocate(pos);
 690         if (!chunk) {
 691                 // chunk store corrupted?
 692                 return false;
 693         }
 694
 695         bool generated = false;
 696         if (save.Exists(pos)) {
 697                 save.Read(*chunk);
 698         } else {
 699                 gen(*chunk);
 700                 generated = true;
 701         }
 702
 703         ChunkIndex *index = store.ClosestIndex(pos);
 704         if (!index) {
 705                 return generated;
 706         }
 707
 708         ExactLocation::Coarse begin(pos - ExactLocation::Coarse(1));
 709         ExactLocation::Coarse end(pos + ExactLocation::Coarse(2));
 710         for (ExactLocation::Coarse iter(begin); iter.z < end.z; ++iter.z) {
 711                 for (iter.y = begin.y; iter.y < end.y; ++iter.y) {
 712                         for (iter.x = begin.x; iter.x < end.x; ++iter.x) {
 713                                 if (index->IsBorder(iter)) continue;
 714                                 Chunk *light_chunk = index->Get(iter);
 715                                 if (!light_chunk) continue;
 716                                 if (index->HasAllSurrounding(iter)) {
 717                                         if (!light_chunk->Lighted()) {
 718                                                 light_chunk->ScanLights();
 719                                         } else {
 720                                                 light_chunk->InvalidateMesh();
 721                                         }
 722                                 }
 723                         }
 724                 }
 725         }
 726
 727         return generated;
 728 }
 729
 730 void ChunkLoader::LoadN(std::size_t n) {
 731         std::size_t end = std::min(n, std::size_t(ToLoad()));
 732         for (std::size_t i = 0; i < end && store.HasMissing(); ++i) {
 733                 LoadOne();
 734         }
 735 }
 736
 737
 738 ChunkRenderer::ChunkRenderer(ChunkIndex &index)
 739 : index(index)
 740 , models(index.TotalChunks())
 741 , block_tex()
 742 , fog_density(0.0f) {
 743
 744 }
 745
 746 ChunkRenderer::~ChunkRenderer() {
 747
 748 }
 749
 750 int ChunkRenderer::MissingChunks() const noexcept {
 751         return index.MissingChunks();
 752 }
 753
 754 void ChunkRenderer::LoadTextures(const AssetLoader &loader, const ResourceIndex &tex_index) {
 755         block_tex.Bind();
 756         loader.LoadTextures(tex_index, block_tex);
 757         block_tex.FilterNearest();
 758 }
 759
 760 void ChunkRenderer::Update(int dt) {
 761         for (int i = 0, updates = 0; updates < dt && i < index.TotalChunks(); ++i) {
 762                 if (!index[i]) continue;
 763                 if (!index[i]->Lighted() && index.HasAllSurrounding(index[i]->Position())) {
 764                         index[i]->ScanLights();
 765                 }
 766                 if (index[i]->ShouldUpdateMesh()) {
 767                         index[i]->Update(models[i]);
 768                         ++updates;
 769                 }
 770         }
 771 }
 772
 773 void ChunkRenderer::Render(Viewport &viewport) {
 774         BlockLighting &chunk_prog = viewport.ChunkProgram();
 775         chunk_prog.SetTexture(block_tex);
 776         chunk_prog.SetFogDensity(fog_density);
 777
 778         for (int i = 0; i < index.TotalChunks(); ++i) {
 779                 if (!index[i]) continue;
 780                 glm::mat4 m(index[i]->Transform(index.Base()));
 781                 glm::mat4 mvp(chunk_prog.GetVP() * m);
 782                 if (!CullTest(Chunk::Bounds(), mvp)) {
 783                         if (index[i]->ShouldUpdateMesh()) {
 784                                 index[i]->Update(models[i]);
 785                         }
 786                         chunk_prog.SetM(m);
 787                         models[i].Draw();
 788                 }
 789         }
 790 }
 791
 792
 793 ChunkIndex::ChunkIndex(ChunkStore &store, const ExactLocation::Coarse &base, int extent)
 794 : store(store)
 795 , base(base)
 796 , extent(extent)
 797 , side_length(2 * extent + 1)
 798 , total_length(side_length * side_length * side_length)
 799 , total_indexed(0)
 800 , last_missing(0)
 801 , stride(1, side_length, side_length * side_length)
 802 , chunks(total_length, nullptr) {
 803         Scan();
 804 }
 805
 806 ChunkIndex::~ChunkIndex() {
 807         Clear();
 808 }
 809
 810 bool ChunkIndex::InRange(const ExactLocation::Coarse &pos) const noexcept {
 811         return Distance(pos) <= extent;
 812 }
 813
 814 bool ChunkIndex::IsBorder(const ExactLocation::Coarse &pos) const noexcept {
 815         return Distance(pos) == extent;
 816 }
 817
 818 int ChunkIndex::Distance(const ExactLocation::Coarse &pos) const noexcept {
 819         return manhattan_radius(pos - base);
 820 }
 821
 822 bool ChunkIndex::HasAllSurrounding(const ExactLocation::Coarse &pos) const noexcept {
 823         ExactLocation::Coarse begin(pos - ExactLocation::Coarse(1));
 824         ExactLocation::Coarse end(pos + ExactLocation::Coarse(2));
 825         for (ExactLocation::Coarse iter(begin); iter.z < end.z; ++iter.z) {
 826                 for (iter.y = begin.y; iter.y < end.y; ++iter.y) {
 827                         for (iter.x = begin.x; iter.x < end.x; ++iter.x) {
 828                                 if (!Get(iter)) return false;
 829                         }
 830                 }
 831         }
 832         return true;
 833 }
 834
 835 int ChunkIndex::IndexOf(const ExactLocation::Coarse &pos) const noexcept {
 836         ExactLocation::Coarse mod_pos(
 837                 GetCol(pos.x),
 838                 GetCol(pos.y),
 839                 GetCol(pos.z)
 840         );
 841         return mod_pos.x * stride.x
 842                 +  mod_pos.y * stride.y
 843                 +  mod_pos.z * stride.z;
 844 }
 845
 846 ExactLocation::Coarse ChunkIndex::PositionOf(int i) const noexcept {
 847         ExactLocation::Coarse zero_pos(
 848                 (i / stride.x) % side_length,
 849                 (i / stride.y) % side_length,
 850                 (i / stride.z) % side_length
 851         );
 852         ExactLocation::Coarse zero_base(
 853                 GetCol(base.x),
 854                 GetCol(base.y),
 855                 GetCol(base.z)
 856         );
 857         ExactLocation::Coarse base_relative(zero_pos - zero_base);
 858         if (base_relative.x > extent) base_relative.x -= side_length;
 859         else if (base_relative.x < -extent) base_relative.x += side_length;
 860         if (base_relative.y > extent) base_relative.y -= side_length;
 861         else if (base_relative.y < -extent) base_relative.y += side_length;
 862         if (base_relative.z > extent) base_relative.z -= side_length;
 863         else if (base_relative.z < -extent) base_relative.z += side_length;
 864         return base + base_relative;
 865 }
 866
 867 Chunk *ChunkIndex::Get(const ExactLocation::Coarse &pos) noexcept {
 868         if (InRange(pos)) {
 869                 return chunks[IndexOf(pos)];
 870         } else {
 871                 return nullptr;
 872         }
 873 }
 874
 875 const Chunk *ChunkIndex::Get(const ExactLocation::Coarse &pos) const noexcept {
 876         if (InRange(pos)) {
 877                 return chunks[IndexOf(pos)];
 878         } else {
 879                 return nullptr;
 880         }
 881 }
 882
 883 void ChunkIndex::Rebase(const ExactLocation::Coarse &new_base) {
 884         if (new_base == base) return;
 885
 886         ExactLocation::Coarse diff(new_base - base);
 887
 888         if (manhattan_radius(diff) > extent) {
 889                 // that's more than half, so probably not worth shifting
 890                 base = new_base;
 891                 Clear();
 892                 Scan();
 893                 store.Clean();
 894                 return;
 895         }
 896
 897         while (diff.x > 0) {
 898                 Shift(Block::FACE_RIGHT);
 899                 --diff.x;
 900         }
 901         while (diff.x < 0) {
 902                 Shift(Block::FACE_LEFT);
 903                 ++diff.x;
 904         }
 905         while (diff.y > 0) {
 906                 Shift(Block::FACE_UP);
 907                 --diff.y;
 908         }
 909         while (diff.y < 0) {
 910                 Shift(Block::FACE_DOWN);
 911                 ++diff.y;
 912         }
 913         while (diff.z > 0) {
 914                 Shift(Block::FACE_FRONT);
 915                 --diff.z;
 916         }
 917         while (diff.z < 0) {
 918                 Shift(Block::FACE_BACK);
 919                 ++diff.z;
 920         }
 921         store.Clean();
 922 }
 923
 924 int ChunkIndex::GetCol(int c) const noexcept {
 925         c %= side_length;
 926         if (c < 0) c += side_length;
 927         return c;
 928 }
 929
 930 void ChunkIndex::Shift(Block::Face f) {
 931         int a_axis = Block::Axis(f);
 932         int b_axis = (a_axis + 1) % 3;
 933         int c_axis = (a_axis + 2) % 3;
 934         int dir = Block::Direction(f);
 935         base[a_axis] += dir;
 936         int a = GetCol(base[a_axis] + (extent * dir));
 937         int a_stride = a * stride[a_axis];
 938         for (int b = 0; b < side_length; ++b) {
 939                 int b_stride = b * stride[b_axis];
 940                 for (int c = 0; c < side_length; ++c) {
 941                         int bc_stride = b_stride + c * stride[c_axis];
 942                         int index = a_stride + bc_stride;
 943                         Unset(index);
 944                         int neighbor = ((a - dir + side_length) % side_length) * stride[a_axis] + bc_stride;
 945                         if (chunks[neighbor] && chunks[neighbor]->HasNeighbor(f)) {
 946                                 Set(index, chunks[neighbor]->GetNeighbor(f));
 947                         }
 948                 }
 949         }
 950 }
 951
 952 void ChunkIndex::Clear() noexcept {
 953         for (int i = 0; i < total_length && total_indexed > 0; ++i) {
 954                 Unset(i);
 955         }
 956 }
 957
 958 void ChunkIndex::Scan() noexcept {
 959         for (Chunk &chunk : store) {
 960                 Register(chunk);
 961         }
 962 }
 963
 964 void ChunkIndex::Register(Chunk &chunk) noexcept {
 965         if (InRange(chunk.Position())) {
 966                 Set(IndexOf(chunk.Position()), chunk);
 967         }
 968 }
 969
 970 void ChunkIndex::Set(int index, Chunk &chunk) noexcept {
 971         Unset(index);
 972         chunks[index] = &chunk;
 973         chunk.Ref();
 974         ++total_indexed;
 975 }
 976
 977 void ChunkIndex::Unset(int index) noexcept {
 978         if (chunks[index]) {
 979                 chunks[index]->UnRef();
 980                 chunks[index] = nullptr;
 981                 --total_indexed;
 982         }
 983 }
 984
 985 ExactLocation::Coarse ChunkIndex::NextMissing() noexcept {
 986         if (MissingChunks() > 0) {
 987                 int roundtrip = last_missing;
 988                 last_missing = (last_missing + 1) % total_length;
 989                 while (chunks[last_missing]) {
 990                         last_missing = (last_missing + 1) % total_length;
 991                         if (last_missing == roundtrip) {
 992                                 break;
 993                         }
 994                 }
 995         }
 996         return PositionOf(last_missing);
 997 }
 998
 999
1000 ChunkStore::ChunkStore(const BlockTypeRegistry &types)
1001 : types(types)
1002 , loaded()
1003 , free()
1004 , indices() {
1005
1006 }
1007
1008 ChunkStore::~ChunkStore() {
1009
1010 }
1011
1012 ChunkIndex &ChunkStore::MakeIndex(const ExactLocation::Coarse &pos, int extent) {
1013         indices.emplace_back(*this, pos, extent);
1014         return indices.back();
1015 }
1016
1017 void ChunkStore::UnregisterIndex(ChunkIndex &index) {
1018         for (auto i = indices.begin(), end = indices.end(); i != end; ++i) {
1019                 if (&*i == &index) {
1020                         indices.erase(i);
1021                         return;
1022                 } else {
1023                         ++i;
1024                 }
1025         }
1026 }
1027
1028 ChunkIndex *ChunkStore::ClosestIndex(const ExactLocation::Coarse &pos) {
1029         ChunkIndex *closest_index = nullptr;
1030         int closest_distance = std::numeric_limits<int>::max();
1031
1032         for (ChunkIndex &index : indices) {
1033                 int distance = index.Distance(pos);
1034                 if (distance < closest_distance) {
1035                         closest_index = &index;
1036                         closest_distance = distance;
1037                 }
1038         }
1039
1040         return closest_index;
1041 }
1042
1043 Chunk *ChunkStore::Get(const ExactLocation::Coarse &pos) {
1044         for (ChunkIndex &index : indices) {
1045                 Chunk *chunk = index.Get(pos);
1046                 if (chunk) {
1047                         return chunk;
1048                 }
1049         }
1050         return nullptr;
1051 }
1052
1053 Chunk *ChunkStore::Allocate(const ExactLocation::Coarse &pos) {
1054         Chunk *chunk = Get(pos);
1055         if (chunk) {
1056                 return chunk;
1057         }
1058         if (free.empty()) {
1059                 loaded.emplace(loaded.begin(), types);
1060         } else {
1061                 loaded.splice(loaded.begin(), free, free.begin());
1062                 loaded.front().Unlink();
1063         }
1064         chunk = &loaded.front();
1065         chunk->Position(pos);
1066         for (ChunkIndex &index : indices) {
1067                 if (index.InRange(pos)) {
1068                         index.Register(*chunk);
1069                 }
1070         }
1071         for (int i = 0; i < Block::FACE_COUNT; ++i) {
1072                 Block::Face face = Block::Face(i);
1073                 ExactLocation::Coarse neighbor_pos(pos + Block::FaceNormal(face));
1074                 Chunk *neighbor = Get(neighbor_pos);
1075                 if (neighbor) {
1076                         chunk->SetNeighbor(face, *neighbor);
1077                 }
1078         }
1079         return chunk;
1080 }
1081
1082 bool ChunkStore::HasMissing() const noexcept {
1083         for (const ChunkIndex &index : indices) {
1084                 if (index.MissingChunks() > 0) {
1085                         return true;
1086                 }
1087         }
1088         return false;
1089 }
1090
1091 int ChunkStore::EstimateMissing() const noexcept {
1092         int missing = 0;
1093         for (const ChunkIndex &index : indices) {
1094                 missing += index.MissingChunks();
1095         }
1096         return missing;
1097 }
1098
1099 ExactLocation::Coarse ChunkStore::NextMissing() noexcept {
1100         for (ChunkIndex &index : indices) {
1101                 if (index.MissingChunks()) {
1102                         return index.NextMissing();
1103                 }
1104         }
1105         return ExactLocation::Coarse(0, 0, 0);
1106 }
1107
1108 void ChunkStore::Clean() {
1109         for (auto i = loaded.begin(), end = loaded.end(); i != end;) {
1110                 if (i->Referenced() || i->ShouldUpdateSave()) {
1111                         ++i;
1112                 } else {
1113                         auto chunk = i;
1114                         ++i;
1115                         free.splice(free.end(), loaded, chunk);
1116                         chunk->Unlink();
1117                         chunk->InvalidateMesh();
1118                 }
1119         }
1120 }
1121
1122 }