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