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