src/world/chunk.cpp

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