src/chunk.cpp

   1 #include "chunk.hpp"
   2
   3 #include "generator.hpp"
   4
   5 #include <limits>
   6 #include <queue>
   7 #include <glm/gtx/transform.hpp>
   8
   9
  10 namespace blank {
  11
  12 Chunk::Chunk(const BlockTypeRegistry &types)
  13 : types(&types)
  14 , neighbor{ 0, 0, 0, 0, 0, 0 }
  15 , blocks()
  16 , light()
  17 , model()
  18 , position(0, 0, 0)
  19 , dirty(false) {
  20
  21 }
  22
  23 Chunk::Chunk(Chunk &&other)
  24 : types(other.types)
  25 , blocks(std::move(other.blocks))
  26 , light(std::move(other.light))
  27 , model(std::move(other.model))
  28 , position(other.position)
  29 , dirty(other.dirty) {
  30         for (size_t i = 0; i < Block::FACE_COUNT; ++i) {
  31                 neighbor[i] = other.neighbor[i];
  32         }
  33 }
  34
  35 Chunk &Chunk::operator =(Chunk &&other) {
  36         types = other.types;
  37         for (size_t i = 0; i < Block::FACE_COUNT; ++i) {
  38                 neighbor[i] = other.neighbor[i];
  39         }
  40         blocks = std::move(other.blocks);
  41         light = std::move(other.light);
  42         model = std::move(other.model);
  43         position = other.position;
  44         dirty = other.dirty;
  45         return *this;
  46 }
  47
  48
  49 void Chunk::SetNeighbor(Chunk &other) {
  50         if (other.position == position + Pos(-1, 0, 0)) {
  51                 neighbor[Block::FACE_LEFT] = &other;
  52                 other.neighbor[Block::FACE_RIGHT] = this;
  53         } else if (other.position == position + Pos(1, 0, 0)) {
  54                 neighbor[Block::FACE_RIGHT] = &other;
  55                 other.neighbor[Block::FACE_LEFT] = this;
  56         } else if (other.position == position + Pos(0, -1, 0)) {
  57                 neighbor[Block::FACE_DOWN] = &other;
  58                 other.neighbor[Block::FACE_UP] = this;
  59         } else if (other.position == position + Pos(0, 1, 0)) {
  60                 neighbor[Block::FACE_UP] = &other;
  61                 other.neighbor[Block::FACE_DOWN] = this;
  62         } else if (other.position == position + Pos(0, 0, -1)) {
  63                 neighbor[Block::FACE_BACK] = &other;
  64                 other.neighbor[Block::FACE_FRONT] = this;
  65         } else if (other.position == position + Pos(0, 0, 1)) {
  66                 neighbor[Block::FACE_FRONT] = &other;
  67                 other.neighbor[Block::FACE_BACK] = this;
  68         }
  69 }
  70
  71 void Chunk::ClearNeighbors() {
  72         for (int i = 0; i < Block::FACE_COUNT; ++i) {
  73                 neighbor[i] = nullptr;
  74         }
  75 }
  76
  77 void Chunk::Unlink() {
  78         if (neighbor[Block::FACE_UP]) {
  79                 neighbor[Block::FACE_UP]->neighbor[Block::FACE_DOWN] = nullptr;
  80         }
  81         if (neighbor[Block::FACE_DOWN]) {
  82                 neighbor[Block::FACE_DOWN]->neighbor[Block::FACE_UP] = nullptr;
  83         }
  84         if (neighbor[Block::FACE_LEFT]) {
  85                 neighbor[Block::FACE_LEFT]->neighbor[Block::FACE_RIGHT] = nullptr;
  86         }
  87         if (neighbor[Block::FACE_RIGHT]) {
  88                 neighbor[Block::FACE_RIGHT]->neighbor[Block::FACE_LEFT] = nullptr;
  89         }
  90         if (neighbor[Block::FACE_FRONT]) {
  91                 neighbor[Block::FACE_FRONT]->neighbor[Block::FACE_BACK] = nullptr;
  92         }
  93         if (neighbor[Block::FACE_BACK]) {
  94                 neighbor[Block::FACE_BACK]->neighbor[Block::FACE_FRONT] = nullptr;
  95         }
  96 }
  97
  98 void Chunk::Relink() {
  99         if (neighbor[Block::FACE_UP]) {
 100                 neighbor[Block::FACE_UP]->neighbor[Block::FACE_DOWN] = this;
 101         }
 102         if (neighbor[Block::FACE_DOWN]) {
 103                 neighbor[Block::FACE_DOWN]->neighbor[Block::FACE_UP] = this;
 104         }
 105         if (neighbor[Block::FACE_LEFT]) {
 106                 neighbor[Block::FACE_LEFT]->neighbor[Block::FACE_RIGHT] = this;
 107         }
 108         if (neighbor[Block::FACE_RIGHT]) {
 109                 neighbor[Block::FACE_RIGHT]->neighbor[Block::FACE_LEFT] = this;
 110         }
 111         if (neighbor[Block::FACE_FRONT]) {
 112                 neighbor[Block::FACE_FRONT]->neighbor[Block::FACE_BACK] = this;
 113         }
 114         if (neighbor[Block::FACE_BACK]) {
 115                 neighbor[Block::FACE_BACK]->neighbor[Block::FACE_FRONT] = this;
 116         }
 117 }
 118
 119
 120 namespace {
 121
 122 struct SetNode {
 123
 124         Chunk *chunk;
 125         Chunk::Pos pos;
 126
 127         SetNode(Chunk *chunk, Chunk::Pos pos)
 128         : chunk(chunk), pos(pos) { }
 129
 130         int Get() const { return chunk->GetLight(pos); }
 131         void Set(int level) { chunk->SetLight(pos, level); }
 132
 133         bool HasNext(Block::Face face) {
 134                 const BlockLookup next(chunk, pos, face);
 135                 return next.result && !next.chunk->Type(*next.result).block_light;
 136         }
 137         SetNode GetNext(Block::Face face) {
 138                 const BlockLookup next(chunk, pos, face);
 139                 return SetNode(next.chunk, next.pos);
 140         }
 141
 142 };
 143
 144 struct UnsetNode
 145 : public SetNode {
 146
 147         int level;
 148
 149         UnsetNode(Chunk *chunk, Chunk::Pos pos)
 150         : SetNode(chunk, pos), level(Get()) { }
 151
 152         UnsetNode(const SetNode &set)
 153         : SetNode(set), level(Get()) { }
 154
 155
 156         bool HasNext(Block::Face face) {
 157                 const BlockLookup next(chunk, pos, face);
 158                 return next.result;
 159         }
 160         UnsetNode GetNext(Block::Face face) { return UnsetNode(SetNode::GetNext(face)); }
 161
 162 };
 163
 164 std::queue<SetNode> light_queue;
 165 std::queue<UnsetNode> dark_queue;
 166
 167 void work_light() {
 168         while (!light_queue.empty()) {
 169                 SetNode node = light_queue.front();
 170                 light_queue.pop();
 171
 172                 int level = node.Get() - 1;
 173                 for (int face = 0; face < Block::FACE_COUNT; ++face) {
 174                         if (node.HasNext(Block::Face(face))) {
 175                                 SetNode other = node.GetNext(Block::Face(face));
 176                                 if (other.Get() < level) {
 177                                         other.Set(level);
 178                                         light_queue.emplace(other);
 179                                 }
 180                         }
 181                 }
 182         }
 183 }
 184
 185 void work_dark() {
 186         while (!dark_queue.empty()) {
 187                 UnsetNode node = dark_queue.front();
 188                 dark_queue.pop();
 189
 190                 for (int face = 0; face < Block::FACE_COUNT; ++face) {
 191                         if (node.HasNext(Block::Face(face))) {
 192                                 UnsetNode other = node.GetNext(Block::Face(face));
 193                                 // TODO: if there a light source here with the same level this will err
 194                                 if (other.Get() != 0 && other.Get() < node.level) {
 195                                         other.Set(0);
 196                                         dark_queue.emplace(other);
 197                                 } else {
 198                                         light_queue.emplace(other);
 199                                 }
 200                         }
 201                 }
 202         }
 203 }
 204
 205 }
 206
 207 void Chunk::SetBlock(int index, const Block &block) {
 208         const BlockType &old_type = Type(blocks[index]);
 209         const BlockType &new_type = Type(block);
 210
 211         blocks[index] = block;
 212
 213         if (&old_type == &new_type) return;
 214
 215         if (new_type.luminosity > old_type.luminosity) {
 216                 // light added
 217                 SetLight(index, new_type.luminosity);
 218                 light_queue.emplace(this, ToPos(index));
 219                 work_light();
 220         } else if (new_type.luminosity < old_type.luminosity) {
 221                 // light removed
 222                 dark_queue.emplace(this, ToPos(index));
 223                 SetLight(index, 0);
 224                 work_dark();
 225                 SetLight(index, new_type.luminosity);
 226                 light_queue.emplace(this, ToPos(index));
 227                 work_light();
 228         } else if (new_type.block_light && !old_type.block_light) {
 229                 // obstacle added
 230                 dark_queue.emplace(this, ToPos(index));
 231                 SetLight(index, 0);
 232                 work_dark();
 233                 work_light();
 234         } else if (!new_type.block_light && old_type.block_light) {
 235                 // obstacle removed
 236                 int level = 0;
 237                 for (int face = 0; face < Block::FACE_COUNT; ++face) {
 238                         Pos next_pos(ToPos(index) + Block::FaceNormal(Block::Face(face)));
 239                         int next_level = 0;
 240                         if (InBounds(next_pos)) {
 241                                 next_level = GetLight(next_pos);
 242                         } else {
 243                                 if (HasNeighbor(Block::Face(face))) {
 244                                         next_pos -= (Block::FaceNormal(Block::Face(face)) * Chunk::Extent());
 245                                         next_level = GetNeighbor(Block::Face(face)).GetLight(next_pos);
 246                                 }
 247                         }
 248                         if (level < next_level) {
 249                                 level = next_level;
 250                         }
 251                 }
 252                 if (level > 1) {
 253                         SetLight(index, level - 1);
 254                         light_queue.emplace(this, ToPos(index));
 255                         work_light();
 256                 }
 257         }
 258 }
 259
 260 const Block *Chunk::FindNext(const Pos &pos, Block::Face face) const {
 261         Pos next_pos(pos + Block::FaceNormal(face));
 262         if (InBounds(next_pos)) {
 263                 return &BlockAt(pos + Block::FaceNormal(face));
 264         } else if (HasNeighbor(face)) {
 265                 return &GetNeighbor(face).BlockAt(next_pos - (Block::FaceNormal(face) * Extent()));
 266         } else {
 267                 return nullptr;
 268         }
 269 }
 270
 271
 272 void Chunk::SetLight(int index, int level) {
 273         if (light[index] != level) {
 274                 light[index] = level;
 275                 Invalidate();
 276         }
 277 }
 278
 279 int Chunk::GetLight(int index) const {
 280         return light[index];
 281 }
 282
 283 float Chunk::GetVertexLight(int index, const BlockModel::Position &vtx, const BlockModel::Normal &norm) const {
 284         float light = GetLight(index);
 285         Chunk::Pos pos(ToPos(index));
 286
 287         Block::Face direct_face(Block::NormalFace(norm));
 288         const Chunk *direct_chunk = this;
 289         Chunk::Pos direct_pos(pos + Block::FaceNormal(direct_face));
 290         if (!InBounds(direct_pos)) {
 291                 if (HasNeighbor(direct_face)) {
 292                         direct_chunk = &GetNeighbor(direct_face);
 293                         direct_pos -= (Block::FaceNormal(direct_face) * Extent());
 294                         float direct_light = direct_chunk->GetLight(direct_pos);
 295                         if (direct_light > light) {
 296                                 light = direct_light;
 297                         }
 298                 }
 299         } else {
 300                 float direct_light = direct_chunk->GetLight(direct_pos);
 301                 if (direct_light > light) {
 302                         light = direct_light;
 303                 }
 304         }
 305
 306         // cheap alternative until AO etc are implemented
 307         // to tell the faces apart
 308
 309         if (direct_face == Block::FACE_LEFT || direct_face == Block::FACE_RIGHT) {
 310                 light -= 0.2;
 311         } else if (direct_face == Block::FACE_FRONT || direct_face == Block::FACE_BACK) {
 312                 light -= 0.4;
 313         }
 314
 315         return light;
 316 }
 317
 318
 319 bool Chunk::IsSurface(const Pos &pos) const {
 320         const Block &block = BlockAt(pos);
 321         if (!Type(block).visible) {
 322                 return false;
 323         }
 324         for (int face = 0; face < Block::FACE_COUNT; ++face) {
 325                 const Block *next = FindNext(pos, Block::Face(face));
 326                 if (!next || !Type(*next).visible) {
 327                         return true;
 328                 }
 329         }
 330         return false;
 331 }
 332
 333
 334 void Chunk::Allocate() {
 335         blocks.resize(Size(), Block(0));
 336         light.resize(Size(), 0);
 337 }
 338
 339
 340 void Chunk::Draw() {
 341         if (dirty) {
 342                 Update();
 343         }
 344         model.Draw();
 345 }
 346
 347
 348 bool Chunk::Intersection(
 349         const Ray &ray,
 350         const glm::mat4 &M,
 351         int &blkid,
 352         float &dist,
 353         glm::vec3 &normal
 354 ) const {
 355         // TODO: should be possible to heavily optimize this
 356         int id = 0;
 357         blkid = -1;
 358         dist = std::numeric_limits<float>::infinity();
 359         for (int z = 0; z < Depth(); ++z) {
 360                 for (int y = 0; y < Height(); ++y) {
 361                         for (int x = 0; x < Width(); ++x, ++id) {
 362                                 if (!Type(blocks[id]).visible) {
 363                                         continue;
 364                                 }
 365                                 float cur_dist;
 366                                 glm::vec3 cur_norm;
 367                                 if (Type(blocks[id]).shape->Intersects(ray, M * ToTransform(id), cur_dist, cur_norm)) {
 368                                         if (cur_dist < dist) {
 369                                                 blkid = id;
 370                                                 dist = cur_dist;
 371                                                 normal = cur_norm;
 372                                         }
 373                                 }
 374                         }
 375                 }
 376         }
 377
 378         if (blkid < 0) {
 379                 return false;
 380         } else {
 381                 normal = glm::vec3(BlockAt(blkid).Transform() * glm::vec4(normal, 0.0f));
 382                 return true;
 383         }
 384 }
 385
 386 void Chunk::Position(const Pos &pos) {
 387         position = pos;
 388 }
 389
 390 glm::mat4 Chunk::Transform(const Pos &offset) const {
 391         return glm::translate((position - offset) * Extent());
 392 }
 393
 394
 395 namespace {
 396
 397 BlockModel::Buffer buf;
 398
 399 }
 400
 401 void Chunk::CheckUpdate() {
 402         if (dirty) {
 403                 Update();
 404         }
 405 }
 406
 407 void Chunk::Update() {
 408         int vtx_count = 0, idx_count = 0;
 409         for (const auto &block : blocks) {
 410                 const Shape *shape = Type(block).shape;
 411                 vtx_count += shape->VertexCount();
 412                 idx_count += shape->VertexIndexCount();
 413         }
 414         buf.Clear();
 415         buf.Reserve(vtx_count, idx_count);
 416
 417         BlockModel::Index vtx_counter = 0;
 418         for (size_t i = 0; i < Size(); ++i) {
 419                 const BlockType &type = Type(blocks[i]);
 420
 421                 if (!type.visible || Obstructed(i)) continue;
 422
 423                 type.FillBlockModel(buf, ToTransform(i), vtx_counter);
 424                 size_t vtx_begin = vtx_counter;
 425                 vtx_counter += type.shape->VertexCount();
 426
 427                 for (size_t vtx = vtx_begin; vtx < vtx_counter; ++vtx) {
 428                         buf.lights.emplace_back(GetVertexLight(i, buf.vertices[vtx], buf.normals[vtx]));
 429                 }
 430         }
 431
 432         model.Update(buf);
 433         dirty = false;
 434 }
 435
 436 bool Chunk::Obstructed(int idx) const {
 437         Chunk::Pos pos(ToPos(idx));
 438
 439         Chunk::Pos left_pos(pos + Chunk::Pos(-1, 0, 0));
 440         const Block *left_block = nullptr;
 441         if (InBounds(left_pos)) {
 442                 left_block = &BlockAt(left_pos);
 443         } else if (HasNeighbor(Block::FACE_LEFT)) {
 444                 left_pos += Chunk::Pos(Width(), 0, 0);
 445                 left_block = &GetNeighbor(Block::FACE_LEFT).BlockAt(left_pos);
 446         } else {
 447                 return false;
 448         }
 449         if (!Type(*left_block).FaceFilled(*left_block, Block::FACE_RIGHT)) {
 450                 return false;
 451         }
 452
 453         Chunk::Pos right_pos(pos + Chunk::Pos(1, 0, 0));
 454         const Block *right_block = nullptr;
 455         if (InBounds(right_pos)) {
 456                 right_block = &BlockAt(right_pos);
 457         } else if (HasNeighbor(Block::FACE_RIGHT)) {
 458                 right_pos += Chunk::Pos(-Width(), 0, 0);
 459                 right_block = &GetNeighbor(Block::FACE_RIGHT).BlockAt(right_pos);
 460         } else {
 461                 return false;
 462         }
 463         if (!Type(*right_block).FaceFilled(*right_block, Block::FACE_LEFT)) {
 464                 return false;
 465         }
 466
 467         Chunk::Pos down_pos(pos + Chunk::Pos(0, -1, 0));
 468         const Block *down_block = nullptr;
 469         if (InBounds(down_pos)) {
 470                 down_block = &BlockAt(down_pos);
 471         } else if (HasNeighbor(Block::FACE_DOWN)) {
 472                 down_pos += Chunk::Pos(0, Height(), 0);
 473                 down_block = &GetNeighbor(Block::FACE_DOWN).BlockAt(down_pos);
 474         } else {
 475                 return false;
 476         }
 477         if (!Type(*down_block).FaceFilled(*down_block, Block::FACE_UP)) {
 478                 return false;
 479         }
 480
 481         Chunk::Pos up_pos(pos + Chunk::Pos(0, 1, 0));
 482         const Block *up_block = nullptr;
 483         if (InBounds(up_pos)) {
 484                 up_block = &BlockAt(up_pos);
 485         } else if (HasNeighbor(Block::FACE_UP)) {
 486                 up_pos += Chunk::Pos(0, -Height(), 0);
 487                 up_block = &GetNeighbor(Block::FACE_UP).BlockAt(up_pos);
 488         } else {
 489                 return false;
 490         }
 491         if (!Type(*up_block).FaceFilled(*up_block, Block::FACE_DOWN)) {
 492                 return false;
 493         }
 494
 495         Chunk::Pos back_pos(pos + Chunk::Pos(0, 0, -1));
 496         const Block *back_block = nullptr;
 497         if (InBounds(back_pos)) {
 498                 back_block = &BlockAt(back_pos);
 499         } else if (HasNeighbor(Block::FACE_BACK)) {
 500                 back_pos += Chunk::Pos(0, 0, Depth());
 501                 back_block = &GetNeighbor(Block::FACE_BACK).BlockAt(back_pos);
 502         } else {
 503                 return false;
 504         }
 505         if (!Type(*back_block).FaceFilled(*back_block, Block::FACE_FRONT)) {
 506                 return false;
 507         }
 508
 509         Chunk::Pos front_pos(pos + Chunk::Pos(0, 0, 1));
 510         const Block *front_block = nullptr;
 511         if (InBounds(front_pos)) {
 512                 front_block = &BlockAt(front_pos);
 513         } else if (HasNeighbor(Block::FACE_FRONT)) {
 514                 front_pos += Chunk::Pos(0, 0, -Depth());
 515                 front_block = &GetNeighbor(Block::FACE_FRONT).BlockAt(front_pos);
 516         } else {
 517                 return false;
 518         }
 519         if (!Type(*front_block).FaceFilled(*front_block, Block::FACE_BACK)) {
 520                 return false;
 521         }
 522
 523         return true;
 524 }
 525
 526 glm::mat4 Chunk::ToTransform(int idx) const {
 527         return glm::translate(glm::mat4(1.0f), ToCoords(idx)) * blocks[idx].Transform();
 528 }
 529
 530
 531 BlockLookup::BlockLookup(Chunk *c, const Chunk::Pos &p)
 532 : chunk(c), pos(p), result(nullptr) {
 533         while (pos.x >= Chunk::Width()) {
 534                 if (chunk->HasNeighbor(Block::FACE_RIGHT)) {
 535                         chunk = &chunk->GetNeighbor(Block::FACE_RIGHT);
 536                         pos.x -= Chunk::Width();
 537                 } else {
 538                         return;
 539                 }
 540         }
 541         while (pos.x < 0) {
 542                 if (chunk->HasNeighbor(Block::FACE_LEFT)) {
 543                         chunk = &chunk->GetNeighbor(Block::FACE_LEFT);
 544                         pos.x += Chunk::Width();
 545                 } else {
 546                         return;
 547                 }
 548         }
 549         while (pos.y >= Chunk::Height()) {
 550                 if (chunk->HasNeighbor(Block::FACE_UP)) {
 551                         chunk = &chunk->GetNeighbor(Block::FACE_UP);
 552                         pos.y -= Chunk::Height();
 553                 } else {
 554                         return;
 555                 }
 556         }
 557         while (pos.y < 0) {
 558                 if (chunk->HasNeighbor(Block::FACE_DOWN)) {
 559                         chunk = &chunk->GetNeighbor(Block::FACE_DOWN);
 560                         pos.y += Chunk::Height();
 561                 } else {
 562                         return;
 563                 }
 564         }
 565         while (pos.z >= Chunk::Depth()) {
 566                 if (chunk->HasNeighbor(Block::FACE_FRONT)) {
 567                         chunk = &chunk->GetNeighbor(Block::FACE_FRONT);
 568                         pos.z -= Chunk::Depth();
 569                 } else {
 570                         return;
 571                 }
 572         }
 573         while (pos.z < 0) {
 574                 if (chunk->HasNeighbor(Block::FACE_BACK)) {
 575                         chunk = &chunk->GetNeighbor(Block::FACE_BACK);
 576                         pos.z += Chunk::Depth();
 577                 } else {
 578                         return;
 579                 }
 580         }
 581         result = &chunk->BlockAt(pos);
 582 }
 583
 584 BlockLookup::BlockLookup(Chunk *c, const Chunk::Pos &p, Block::Face face)
 585 : chunk(c), pos(p), result(nullptr) {
 586         pos += Block::FaceNormal(face);
 587         if (Chunk::InBounds(pos)) {
 588                 result = &chunk->BlockAt(pos);
 589         } else {
 590                 pos -= Block::FaceNormal(face) * Chunk::Extent();
 591                 if (chunk->HasNeighbor(face)) {
 592                         chunk = &chunk->GetNeighbor(face);
 593                         result = &chunk->BlockAt(pos);
 594                 }
 595         }
 596 }
 597
 598
 599 ChunkLoader::ChunkLoader(const Config &config, const BlockTypeRegistry &reg, const Generator &gen)
 600 : base(0, 0, 0)
 601 , reg(reg)
 602 , gen(gen)
 603 , loaded()
 604 , to_generate()
 605 , to_free()
 606 , load_dist(config.load_dist)
 607 , unload_dist(config.unload_dist) {
 608
 609 }
 610
 611 namespace {
 612
 613 struct ChunkLess {
 614
 615         explicit ChunkLess(const Chunk::Pos &base)
 616         : base(base) { }
 617
 618         bool operator ()(const Chunk::Pos &a, const Chunk::Pos &b) const {
 619                 Chunk::Pos da(base - a);
 620                 Chunk::Pos db(base - b);
 621                 return
 622                         da.x * da.x + da.y * da.y + da.z * da.z <
 623                         db.x * db.x + db.y * db.y + db.z * db.z;
 624         }
 625
 626         Chunk::Pos base;
 627
 628 };
 629
 630 }
 631
 632 void ChunkLoader::Generate(const Chunk::Pos &from, const Chunk::Pos &to) {
 633         for (int z = from.z; z < to.z; ++z) {
 634                 for (int y = from.y; y < to.y; ++y) {
 635                         for (int x = from.x; x < to.x; ++x) {
 636                                 Chunk::Pos pos(x, y, z);
 637                                 if (Known(pos)) {
 638                                         continue;
 639                                 } else if (pos == base) {
 640                                         Generate(pos);
 641
 642                                 //      light testing
 643                                 //      for (int i = 0; i < 16; ++i) {
 644                                 //              for (int j = 0; j < 16; ++j) {
 645                                 //                      loaded.back().SetBlock(Chunk::Pos{  i, j,  0 }, Block(1));
 646                                 //                      loaded.back().SetBlock(Chunk::Pos{  i, j, 15 }, Block(1));
 647                                 //                      loaded.back().SetBlock(Chunk::Pos{  0, j,  i }, Block(1));
 648                                 //                      loaded.back().SetBlock(Chunk::Pos{ 15, j,  i }, Block(1));
 649                                 //              }
 650                                 //      }
 651                                 //      loaded.back().SetBlock(Chunk::Pos{  1,  0,  1 }, Block(13));
 652                                 //      loaded.back().SetBlock(Chunk::Pos{ 14,  0,  1 }, Block(13));
 653                                 //      loaded.back().SetBlock(Chunk::Pos{  1,  0, 14 }, Block(13));
 654                                 //      loaded.back().SetBlock(Chunk::Pos{ 14,  0, 14 }, Block(13));
 655                                 //      loaded.back().SetBlock(Chunk::Pos{  1, 15,  1 }, Block(13));
 656                                 //      loaded.back().SetBlock(Chunk::Pos{ 14, 15,  1 }, Block(13));
 657                                 //      loaded.back().SetBlock(Chunk::Pos{  1, 15, 14 }, Block(13));
 658                                 //      loaded.back().SetBlock(Chunk::Pos{ 14, 15, 14 }, Block(13));
 659                                 //      loaded.back().SetBlock(Chunk::Pos{  7,  7,  0 }, Block(13));
 660                                 //      loaded.back().SetBlock(Chunk::Pos{  8,  7,  0 }, Block(13));
 661                                 //      loaded.back().SetBlock(Chunk::Pos{  7,  8,  0 }, Block(13));
 662                                 //      loaded.back().SetBlock(Chunk::Pos{  8,  8,  0 }, Block(13));
 663                                 //      loaded.back().SetBlock(Chunk::Pos{  7,  7, 15 }, Block(13));
 664                                 //      loaded.back().SetBlock(Chunk::Pos{  8,  7, 15 }, Block(13));
 665                                 //      loaded.back().SetBlock(Chunk::Pos{  7,  8, 15 }, Block(13));
 666                                 //      loaded.back().SetBlock(Chunk::Pos{  8,  8, 15 }, Block(13));
 667                                 //      loaded.back().SetBlock(Chunk::Pos{  0,  7,  7 }, Block(13));
 668                                 //      loaded.back().SetBlock(Chunk::Pos{  0,  7,  8 }, Block(13));
 669                                 //      loaded.back().SetBlock(Chunk::Pos{  0,  8,  7 }, Block(13));
 670                                 //      loaded.back().SetBlock(Chunk::Pos{  0,  8,  8 }, Block(13));
 671                                 //      loaded.back().SetBlock(Chunk::Pos{ 15,  7,  7 }, Block(13));
 672                                 //      loaded.back().SetBlock(Chunk::Pos{ 15,  7,  8 }, Block(13));
 673                                 //      loaded.back().SetBlock(Chunk::Pos{ 15,  8,  7 }, Block(13));
 674                                 //      loaded.back().SetBlock(Chunk::Pos{ 15,  8,  8 }, Block(13));
 675                                 //      loaded.back().Invalidate();
 676                                 //      loaded.back().CheckUpdate();
 677
 678                                 //      orientation testing
 679                                 //      for (int i = 0; i < Block::FACE_COUNT; ++i) {
 680                                 //              for (int j = 0; j < Block::TURN_COUNT; ++j) {
 681                                 //                      loaded.back().BlockAt(512 * j + 2 * i) = Block(3 * (j + 1), Block::Face(i), Block::Turn(j));
 682                                 //              }
 683                                 //      }
 684                                 //      loaded.back().Invalidate();
 685                                 //      loaded.back().CheckUpdate();
 686                                 } else {
 687                                         to_generate.emplace_back(pos);
 688                                 }
 689                         }
 690                 }
 691         }
 692         to_generate.sort(ChunkLess(base));
 693 }
 694
 695 Chunk &ChunkLoader::Generate(const Chunk::Pos &pos) {
 696         loaded.emplace_back(reg);
 697         Chunk &chunk = loaded.back();
 698         chunk.Position(pos);
 699         Insert(chunk);
 700         gen(chunk);
 701         return chunk;
 702 }
 703
 704 void ChunkLoader::Insert(Chunk &chunk) {
 705         for (Chunk &other : loaded) {
 706                 chunk.SetNeighbor(other);
 707         }
 708 }
 709
 710 void ChunkLoader::Remove(Chunk &chunk) {
 711         chunk.Unlink();
 712 }
 713
 714 Chunk *ChunkLoader::Loaded(const Chunk::Pos &pos) {
 715         for (Chunk &chunk : loaded) {
 716                 if (chunk.Position() == pos) {
 717                         return &chunk;
 718                 }
 719         }
 720         return nullptr;
 721 }
 722
 723 bool ChunkLoader::Queued(const Chunk::Pos &pos) {
 724         for (const Chunk::Pos &chunk : to_generate) {
 725                 if (chunk == pos) {
 726                         return true;
 727                 }
 728         }
 729         return nullptr;
 730 }
 731
 732 bool ChunkLoader::Known(const Chunk::Pos &pos) {
 733         if (Loaded(pos)) return true;
 734         return Queued(pos);
 735 }
 736
 737 Chunk &ChunkLoader::ForceLoad(const Chunk::Pos &pos) {
 738         Chunk *chunk = Loaded(pos);
 739         if (chunk) {
 740                 return *chunk;
 741         }
 742
 743         for (auto iter(to_generate.begin()), end(to_generate.end()); iter != end; ++iter) {
 744                 if (*iter == pos) {
 745                         to_generate.erase(iter);
 746                         break;
 747                 }
 748         }
 749
 750         return Generate(pos);
 751 }
 752
 753 void ChunkLoader::Rebase(const Chunk::Pos &new_base) {
 754         if (new_base == base) {
 755                 return;
 756         }
 757         base = new_base;
 758
 759         // unload far away chunks
 760         for (auto iter(loaded.begin()), end(loaded.end()); iter != end;) {
 761                 if (std::abs(base.x - iter->Position().x) > unload_dist
 762                                 || std::abs(base.y - iter->Position().y) > unload_dist
 763                                 || std::abs(base.z - iter->Position().z) > unload_dist) {
 764                         auto saved = iter;
 765                         Remove(*saved);
 766                         ++iter;
 767                         to_free.splice(to_free.end(), loaded, saved);
 768                 } else {
 769                         ++iter;
 770                 }
 771         }
 772         // abort far away queued chunks
 773         for (auto iter(to_generate.begin()), end(to_generate.end()); iter != end;) {
 774                 if (std::abs(base.x - iter->x) > unload_dist
 775                                 || std::abs(base.y - iter->y) > unload_dist
 776                                 || std::abs(base.z - iter->z) > unload_dist) {
 777                         iter = to_generate.erase(iter);
 778                 } else {
 779                         ++iter;
 780                 }
 781         }
 782         // add missing new chunks
 783         GenerateSurrounding(base);
 784 }
 785
 786 void ChunkLoader::GenerateSurrounding(const Chunk::Pos &pos) {
 787         const Chunk::Pos offset(load_dist, load_dist, load_dist);
 788         Generate(pos - offset, pos + offset);
 789 }
 790
 791 void ChunkLoader::Update() {
 792         bool reused = false;
 793         if (!to_generate.empty()) {
 794                 Chunk::Pos pos(to_generate.front());
 795
 796                 for (auto iter(to_free.begin()), end(to_free.end()); iter != end; ++iter) {
 797                         if (iter->Position() == pos) {
 798                                 iter->Relink();
 799                                 loaded.splice(loaded.end(), to_free, iter);
 800                                 reused = true;
 801                                 break;
 802                         }
 803                 }
 804
 805                 if (!reused) {
 806                         if (to_free.empty()) {
 807                                 loaded.emplace_back(reg);
 808                         } else {
 809                                 to_free.front().ClearNeighbors();
 810                                 loaded.splice(loaded.end(), to_free, to_free.begin());
 811                                 reused = true;
 812                         }
 813                         Chunk &chunk = loaded.back();
 814                         chunk.Position(pos);
 815                         Insert(chunk);
 816                         gen(chunk);
 817                 }
 818                 to_generate.pop_front();
 819         }
 820
 821         if (!reused && !to_free.empty()) {
 822                 to_free.pop_front();
 823         }
 824 }
 825
 826 }