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