src/chunk.cpp

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