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