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