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