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