1 module dminer.core.chunk;
2 
3 import dminer.core.minetypes;
4 import dminer.core.blocks;
5 import dminer.core.world;
6 import dlangui.graphics.scene.mesh;
7 
8 
9 version = FAST_VISIBILITY_PATH;
10 
11 // Y range: 0..CHUNK_DY-1
12 immutable int CHUNK_DY = 128;
13 
14 //immutable int CHUNKS_Y = CHUNK_DY >> 3; // actually, it's not limited
15 
16 immutable int CHUNKS_BITS_X = 9;
17 immutable int CHUNKS_BITS_Z = 9;
18 immutable int CHUNKS_X = (1 << CHUNKS_BITS_X); // X range: -CHUNKS_X*8 .. CHUNKS_X*8
19 immutable int CHUNKS_Z = (1 << CHUNKS_BITS_Z); // Z range: -CHUNKS_Z*8 .. CHUNKS_Z*8
20 immutable int CHUNKS_X_MASK = (CHUNKS_X << 1) - 1;
21 immutable int CHUNKS_Z_MASK = (CHUNKS_Z << 1) - 1;
22 
23 version = SmallChunksGC;
24 
25 interface CellVisitor {
26     //void newDirection(ref Position camPosition);
27     //void visitFace(World world, ref Position camPosition, Vector3d pos, cell_t cell, Dir face);
28     void visit(World world, ref Position camPosition, Vector3d pos, cell_t cell, int visibleFaces);
29 }
30 
31 interface ChunkVisitor {
32     bool visit(World world, SmallChunk * chunk);
33 }
34 
35 // vertical stack of chunks with same X, Z, and different Y
36 struct ChunkStack {
37     protected int _minChunkY;
38     protected int _chunkCount;
39     version (SmallChunksGC) {
40         protected SmallChunk * [] _chunks;
41     } else {
42         protected SmallChunk ** _chunks;
43     }
44     /// get chunk from stack by chunk Y index
45     SmallChunk * get(int chunkY) {
46         int idx = chunkY - _minChunkY;
47         if (idx < 0 || idx >= _chunkCount)
48             return null;
49         return _chunks[idx];
50     }
51     @property int topNonEmptyY() {
52         return ((_minChunkY + _chunkCount) << 3) - 1;
53     }
54     void set(int chunkY, SmallChunk * item) {
55         int idx = chunkY - _minChunkY;
56         if (idx >= 0 && idx < _chunkCount) {
57             if (_chunks[idx]) {
58                 if (_chunks[idx] is item)
59                     return;
60                 _chunks[idx].release;
61             }
62             _chunks[idx] = item;
63             return;
64         } else if (!_chunkCount) {
65             // need to reallocate
66             // initial allocation
67             _minChunkY = chunkY;
68             _chunkCount = 1;
69             _chunks = allocChunks(1);
70             _chunks[0] = item;
71         } else {
72             // need to reallocate
73             // realloc
74             int newMinY;
75             int newChunkCount;
76             if (chunkY < _minChunkY) {
77                 newMinY = chunkY;
78                 newChunkCount = _minChunkY + _chunkCount - newMinY;
79             } else {
80                 newMinY = _minChunkY;
81                 newChunkCount = chunkY - _minChunkY + 1;
82             }
83             SmallChunk *[] newChunks = allocChunks(newChunkCount);
84             // copy old data
85             for(int i = 0; i < _chunkCount; i++)
86                 newChunks[i + _minChunkY - newMinY] = _chunks[i];
87             newChunks[chunkY - newMinY] = item;
88             freeChunks(_chunks);
89             _chunkCount = newChunkCount;
90             _minChunkY = newMinY;
91             _chunks = newChunks;
92         }
93     }
94     version (SmallChunksGC) {
95         private SmallChunk* [] allocChunks(int len) {
96             if (len <= 0)
97                 return null;
98             SmallChunk* [] res = new SmallChunk* [len];
99             return res;
100         }
101         private void freeChunks(ref SmallChunk *[] chunks) {
102             if (chunks) {
103                 destroy(chunks);
104                 chunks = null;
105             }
106         }
107     } else {
108         private SmallChunk ** allocChunks(int len) {
109             if (len <= 0)
110                 return null;
111             import core.stdc.stdlib : malloc;
112             SmallChunk ** res = cast(SmallChunk **) malloc(len * (SmallChunk *).sizeof);
113             for(int i = 0; i < len; i++)
114                 res[i] = null;
115             return res;
116         }
117         private void freeChunks(ref SmallChunk ** chunks) {
118             if (chunks) {
119                 import core.stdc.stdlib : free;
120                 free(chunks);
121                 chunks = null;
122             }
123         }
124     }
125     void clear() {
126         if (_chunkCount) {
127             for(int i = 0; i < _chunkCount; i++) {
128                 _chunks[i].release;
129             }
130             freeChunks(_chunks);
131         }
132         _chunks = null;
133         _chunkCount = 0;
134         _minChunkY = -1;
135     }
136     ~this() {
137         clear();
138     }
139 }
140 
141 /// 8x8x8 chunk
142 struct SmallChunk {
143     protected cell_t[8*8*8] cells; // 512 bytes
144     protected ubyte[8*8*8] sunlight; // 512 bytes
145     protected ulong[8] opaquePlanesX; // 64 bytes WEST to EAST
146     protected ulong[8] opaquePlanesY; // 64 bytes DOWN to UP
147     protected ulong[8] opaquePlanesZ; // 64 bytes NORTH to SOUTH
148     protected ulong[8] visiblePlanesX; // 64 bytes WEST to EAST
149     protected ulong[8] visiblePlanesY; // 64 bytes DOWN to UP
150     protected ulong[8] visiblePlanesZ; // 64 bytes NORTH to SOUTH
151     protected ulong[8] canPassPlanesX; // 64 bytes WEST to EAST
152     protected ulong[8] canPassPlanesY; // 64 bytes DOWN to UP
153     protected ulong[8] canPassPlanesZ; // 64 bytes NORTH to SOUTH
154 
155     protected ubyte[6] canPassFromTo; // index is FROM direction, ubyte is DirMask of TO direction; 1 means can pass FROM .. TO
156     //ulong[6][6] canPassFromTo; // 288 bytes
157     SmallChunk * [6] nearChunks;
158     protected Vector3d _pos;
159     private Mesh _minerMesh;
160     protected bool dirty;
161     protected bool dirtyMesh = true;
162     protected bool empty;
163     protected bool visible;
164     protected bool dirtyVisible;
165 
166 
167     version (SmallChunksGC) {
168         static SmallChunk * alloc(int x, int y, int z) {
169             SmallChunk * res = new SmallChunk();
170             res._pos.x = x & (~7);
171             res._pos.y = y & (~7);
172             res._pos.z = z & (~7);
173             return res;
174         }
175         void release() {
176             destroy(this);
177         }
178 
179     } else {
180         static SmallChunk * alloc(int x, int y, int z) nothrow @nogc {
181             import core.stdc.stdlib : malloc;
182             SmallChunk * res = cast(SmallChunk *)malloc(SmallChunk.sizeof);
183             *res = SmallChunk.init;
184             res._pos.x = x & (~7);
185             res._pos.y = y & (~7);
186             res._pos.z = z & (~7);
187             return res;
188         }
189         void release() {
190             if (!(&this))
191                 return;
192             compact();
193             import core.stdc.stdlib : free;
194             free(&this);
195         }
196 
197     }
198 
199     /// return chunk position in world (aligned to chunk origin)
200     @property ref const(Vector3d) position() {
201         return _pos;
202     }
203 
204     /// returns true if chunk contains any visible faces
205     @property bool hasVisibleFaces() {
206         if (dirty)
207             generateMasks();
208         if (dirtyVisible) {
209             dirtyVisible = false;
210             ubyte[64*8] visibleFaceFlags;
211             visible = findVisibleFaces(visibleFaceFlags) > 0;
212         }
213         return visible;
214     }
215 
216     /// destroys mesh
217     void compact() {
218         if (_minerMesh) {
219             destroy(_minerMesh);
220             _minerMesh = null;
221             dirtyMesh = true;
222         }
223     }
224 
225     static int calcIndex(int x, int y, int z) {
226         return ((((y&7) << 3) | (z&7)) << 3) | (x&7);
227     }
228     cell_t getCell(int x, int y, int z) const {
229         return cells[((((y&7) << 3) | (z&7)) << 3) | (x&7)];
230     }
231     void setCell(int x, int y, int z, cell_t value) {
232         dirty = true;
233         cells[((((y&7) << 3) | (z&7)) << 3) | (x&7)] = value;
234     }
235     cell_t getCellNoCheck(int x, int y, int z) const {
236         return cells[(((y << 3) | z) << 3) | x];
237     }
238     /// get can pass mask for direction
239     ulong getSideCanPassToMask(Dir dir) {
240         if (dirty)
241             generateMasks();
242         final switch (dir) with (Dir) {
243             case NORTH:
244                 return canPassPlanesZ[0];
245             case SOUTH:
246                 return canPassPlanesZ[7];
247             case WEST:
248                 return canPassPlanesX[0];
249             case EAST:
250                 return canPassPlanesX[7];
251             case UP:
252                 return canPassPlanesY[7];
253             case DOWN:
254                 return canPassPlanesY[0];
255         }
256     }
257     /// to this chunk for nearby chunk
258     ulong getSideCanPassFromMask(Dir dir) {
259         SmallChunk * chunk = nearChunks[dir];
260         if (!chunk)
261             return 0xFFFFFFFFFFFFFFFF; // can pass ALL
262         return chunk.getSideCanPassToMask(opposite(dir));
263     }
264 
265     void visitVisibleFaces(World world, CellVisitor visitor) {
266         if (dirty)
267             generateMasks();
268         if (empty)
269             return;
270         ubyte[64*8] visibleFaceFlags;
271         findVisibleFaces(visibleFaceFlags);
272         int index = 0;
273         for (int y = 0; y < 8; y++) {
274             for (int z = 0; z < 8; z++) {
275                 for (int x = 0; x < 8; x++) {
276                     int visibleFaces = visibleFaceFlags[index];
277                     if (visibleFaces) {
278                         visitor.visit(world, world.camPosition, Vector3d(_pos.x + x, _pos.y + y, _pos.z + z), cells[index], visibleFaces);
279                     }
280                     index++;
281                 }
282             }
283         }
284     }
285 
286     /// get mesh for chunk (generate if not exists)
287     Mesh getMesh(World world) {
288         if (dirty)
289             generateMasks();
290         if (empty)
291             return null;
292         //if (!_minerMesh) {
293         //    _minerMesh = new Mesh(VertexFormat(VertexElementType.POSITION, VertexElementType.NORMAL, VertexElementType.COLOR, VertexElementType.TEXCOORD0));
294         //    dirtyMesh = true;
295         //}
296         Mesh oldMesh = _minerMesh;
297         if (dirtyMesh) {
298             if (_minerMesh)
299                 _minerMesh.reset();
300             ubyte[64*8] visibleFaceFlags;
301             findVisibleFaces(visibleFaceFlags);
302             int index = 0;
303             for (int y = 0; y < 8; y++) {
304                 for (int z = 0; z < 8; z++) {
305                     for (int x = 0; x < 8; x++) {
306                         int visibleFaces = visibleFaceFlags[index];
307                         if (visibleFaces) {
308 
309                             if (!_minerMesh) {
310                                 _minerMesh = new Mesh(VertexFormat(VertexElementType.POSITION, VertexElementType.NORMAL, VertexElementType.COLOR, VertexElementType.TEXCOORD0));
311                             }
312 
313                             BlockDef def = BLOCK_DEFS[cells[index]];
314                             def.createFaces(world, world.camPosition, Vector3d(_pos.x + x, _pos.y + y, _pos.z + z), visibleFaces, _minerMesh);
315                         }
316                         index++;
317                     }
318                 }
319             }
320             dirtyMesh = false;
321         }
322         if (_minerMesh && !_minerMesh.vertexCount) {
323             destroy(_minerMesh);
324             _minerMesh = null;
325         }
326         return _minerMesh;
327     }
328 
329     private int findVisibleFaces(ref ubyte[64*8] visibleFaceFlags) {
330         int count = 0;
331         ulong[8] visibleFacesNorth;
332         ulong canPass = getSideCanPassFromMask(Dir.NORTH);
333         for (int i = 0; i < 8; i++) {
334             visibleFacesNorth[i] = visiblePlanesZ[i] & canPass;
335             canPass = canPassPlanesZ[i];
336         }
337         ulong[8] visibleFacesSouth;
338         canPass = getSideCanPassFromMask(Dir.SOUTH);
339         for (int i = 7; i >= 0; i--) {
340             visibleFacesSouth[i] = visiblePlanesZ[i] & canPass;
341             canPass = canPassPlanesZ[i];
342         }
343         ulong[8] visibleFacesWest;
344         canPass = getSideCanPassFromMask(Dir.WEST);
345         for (int i = 0; i < 8; i++) {
346             visibleFacesWest[i] = visiblePlanesX[i] & canPass;
347             canPass = canPassPlanesX[i];
348         }
349         //xPlanesToZplanes(visibleFacesWest);
350         ulong[8] visibleFacesEast;
351         canPass = getSideCanPassFromMask(Dir.EAST);
352         for (int i = 7; i >= 0; i--) {
353             visibleFacesEast[i] = visiblePlanesX[i] & canPass;
354             canPass = canPassPlanesX[i];
355         }
356         ulong[8] visibleFacesUp;
357         canPass = getSideCanPassFromMask(Dir.UP);
358         for (int i = 7; i >= 0; i--) {
359             visibleFacesUp[i] = visiblePlanesY[i] & canPass;
360             canPass = canPassPlanesY[i];
361         }
362         ulong[8] visibleFacesDown;
363         canPass = getSideCanPassFromMask(Dir.DOWN);
364         for (int i = 0; i < 8; i++) {
365             visibleFacesDown[i] = visiblePlanesY[i] & canPass;
366             canPass = canPassPlanesY[i];
367         }
368         ulong xplanemask;
369         ulong yplanemask;
370         ulong zplanemask;
371         for (int x = 0; x < 8; x++) {
372             for (int y = 0; y < 8; y++) {
373                 for (int z = 0; z < 8; z++) {
374                     xplanemask = cast(ulong)1 << ((y << 3) | z);
375                     yplanemask = cast(ulong)1 << ((z << 3) | x);
376                     zplanemask = cast(ulong)1 << ((y << 3) | x);
377                     int visibleFaces = 0;
378                     if (visibleFacesNorth[z] & zplanemask)
379                         visibleFaces |= DirMask.MASK_NORTH;
380                     if (visibleFacesSouth[z] & zplanemask)
381                         visibleFaces |= DirMask.MASK_SOUTH;
382                     if (visibleFacesWest[x] & xplanemask)
383                         visibleFaces |= DirMask.MASK_WEST;
384                     if (visibleFacesEast[x] & xplanemask)
385                         visibleFaces |= DirMask.MASK_EAST;
386                     if (visibleFacesUp[y] & yplanemask)
387                         visibleFaces |= DirMask.MASK_UP;
388                     if (visibleFacesDown[y] & yplanemask)
389                         visibleFaces |= DirMask.MASK_DOWN;
390                     visibleFaceFlags[calcIndex(x, y, z)] = cast(ubyte)visibleFaces;
391                     if (visibleFaces)
392                         count++;
393                     //if (visibleFaces) {
394                     //    visitor.visit(pos.x + x, pos.y + y, pos.z + z, getCell(x, y, z), visibleFaces);
395                     //}
396                 }
397             }
398         }
399         return count;
400     }
401     /*
402       X planes (WEST EAST): z, y
403          z=0  z=1  z=2  z=3  z=4  z=5  z=6  z=7
404     y=0   0    1    2    3    4    5    6    7
405     y=1   8    9   10   11   12   13   14   15
406     y=2  16   17   18   19   29   21   22   23
407     y=3  24   25   26   27   28   29   30   31
408     y=4  32   33   34   35   36   37   38   39
409     y=5  40   41   42   43   44   45   46   47
410     y=6  48   49   50   51   52   53   54   55
411     y=7  56   57   58   59   60   61   62   63
412 
413       Y planes (DOWN UP): x, z
414          x=0  x=1  x=2  x=3  x=4  x=5  x=6  x=7
415     z=0   0    1    2    3    4    5    6    7
416     z=1   8    9   10   11   12   13   14   15
417     z=2  16   17   18   19   29   21   22   23
418     z=3  24   25   26   27   28   29   30   31
419     z=4  32   33   34   35   36   37   38   39
420     z=5  40   41   42   43   44   45   46   47
421     z=6  48   49   50   51   52   53   54   55
422     z=7  56   57   58   59   60   61   62   63
423 
424       Z planes (NORTH SOUTH): x, y
425          x=0  x=1  x=2  x=3  x=4  x=5  x=6  x=7
426     y=0   0    1    2    3    4    5    6    7
427     y=1   8    9   10   11   12   13   14   15
428     y=2  16   17   18   19   29   21   22   23
429     y=3  24   25   26   27   28   29   30   31
430     y=4  32   33   34   35   36   37   38   39
431     y=5  40   41   42   43   44   45   46   47
432     y=6  48   49   50   51   52   53   54   55
433     y=7  56   57   58   59   60   61   62   63
434     */
435     private void generateMasks() {
436         // x planes: z,y
437         for(int x = 0; x < 8; x++) {
438             ulong opaqueFlags = 0;
439             ulong canPassFlags = 0;
440             ulong visibleFlags = 0;
441             ulong mask = 1;
442             for (int y = 0; y < 8; y++) {
443                 for (int z = 0; z < 8; z++) {
444                     cell_t cell = cells[(((y << 3) | z) << 3) | x];
445                     if (BLOCK_TYPE_OPAQUE.ptr[cell])
446                         opaqueFlags |= mask;
447                     if (BLOCK_TYPE_CAN_PASS.ptr[cell])
448                         canPassFlags |= mask;
449                     if (BLOCK_TYPE_VISIBLE.ptr[cell])
450                         visibleFlags |= mask;
451                     mask = mask << 1;
452                 }
453             }
454             opaquePlanesX[x] = opaqueFlags;
455             canPassPlanesX[x] = canPassFlags;
456             visiblePlanesX[x] = visibleFlags;
457         }
458         // y planes : x,z
459         for(int y = 0; y < 8; y++) {
460             ulong opaqueFlags = 0;
461             ulong canPassFlags = 0;
462             ulong visibleFlags = 0;
463             ulong mask = 1;
464             for (int z = 0; z < 8; z++) {
465                 for (int x = 0; x < 8; x++) {
466                     cell_t cell = cells[(((y << 3) | z) << 3) | x];
467                     if (BLOCK_TYPE_OPAQUE.ptr[cell])
468                         opaqueFlags |= mask;
469                     if (BLOCK_TYPE_CAN_PASS.ptr[cell])
470                         canPassFlags |= mask;
471                     if (BLOCK_TYPE_VISIBLE.ptr[cell])
472                         visibleFlags |= mask;
473                     mask = mask << 1;
474                 }
475             }
476             opaquePlanesY[y] = opaqueFlags;
477             canPassPlanesY[y] = canPassFlags;
478             visiblePlanesY[y] = visibleFlags;
479         }
480         // z planes: x,y
481         for(int z = 0; z < 8; z++) {
482             ulong opaqueFlags = 0;
483             ulong canPassFlags = 0;
484             ulong visibleFlags = 0;
485             ulong mask = 1;
486             for (int y = 0; y < 8; y++) {
487                 for (int x = 0; x < 8; x++) {
488                     cell_t cell = cells[(((y << 3) | z) << 3) | x];
489                     if (BLOCK_TYPE_OPAQUE.ptr[cell])
490                         opaqueFlags |= mask;
491                     if (BLOCK_TYPE_CAN_PASS.ptr[cell])
492                         canPassFlags |= mask;
493                     if (BLOCK_TYPE_VISIBLE.ptr[cell])
494                         visibleFlags |= mask;
495                     mask = mask << 1;
496                 }
497             }
498             opaquePlanesZ[z] = opaqueFlags;
499             canPassPlanesZ[z] = canPassFlags;
500             visiblePlanesZ[z] = visibleFlags;
501         }
502 
503         // can pass from to
504         for (Dir from = Dir.min; from <= Dir.max; ++from) {
505             fillCanPassFrom(from);
506         }
507         dirty = false;
508         empty = (visiblePlanesZ[0]|visiblePlanesZ[1]|visiblePlanesZ[2]|visiblePlanesZ[3]|
509                  visiblePlanesZ[4]|visiblePlanesZ[5]|visiblePlanesZ[6]|visiblePlanesZ[7]) == 0;
510         dirtyVisible = !empty;
511         dirtyMesh = true;
512     }
513 
514     /// returns DirMask of available pass direction for specified FROM direction
515     ubyte getCanPassFromFlags(Dir dirFrom) {
516         return canPassFromTo[dirFrom];
517     }
518 
519     protected void fillCanPassFrom(Dir dirFrom) {
520         ulong[8] planes;
521         ulong mask = 0xFFFFFFFFFFFFFFFFL;
522         ubyte res = 0;
523         final switch (dirFrom) {
524             case Dir.NORTH:
525                 for (int i = 7; i >= 0; i--) {
526                     mask = spreadZPlane(mask, canPassPlanesZ[i], DirMask.MASK_ALL);
527                     if (!mask)
528                         break;
529                     planes[i] = mask;
530                 }
531                 if (planes[0])
532                     res |= DirMask.MASK_NORTH;
533                 if (xPlaneFromZplanes(planes, 0))
534                     res |= DirMask.MASK_WEST;
535                 if (xPlaneFromZplanes(planes, 7))
536                     res |= DirMask.MASK_EAST;
537                 if (yPlaneFromZplanes(planes, 0))
538                     res |= DirMask.MASK_DOWN;
539                 if (yPlaneFromZplanes(planes, 7))
540                     res |= DirMask.MASK_UP;
541                 break;
542             case Dir.SOUTH:
543                 for (int i = 0; i <= 7; i++) {
544                     mask = spreadZPlane(mask, canPassPlanesZ[i], DirMask.MASK_ALL);
545                     if (!mask)
546                         break;
547                     planes[i] = mask;
548                 }
549                 if (planes[7])
550                     res |= DirMask.MASK_SOUTH;
551                 if (xPlaneFromZplanes(planes, 0))
552                     res |= DirMask.MASK_WEST;
553                 if (xPlaneFromZplanes(planes, 7))
554                     res |= DirMask.MASK_EAST;
555                 if (yPlaneFromZplanes(planes, 0))
556                     res |= DirMask.MASK_DOWN;
557                 if (yPlaneFromZplanes(planes, 7))
558                     res |= DirMask.MASK_UP;
559                 break;
560             case Dir.WEST: // x--
561                 for (int i = 7; i >= 0; i--) {
562                     mask = spreadXPlane(mask, canPassPlanesX[i], DirMask.MASK_ALL);
563                     if (!mask)
564                         break;
565                     planes[i] = mask;
566                 }
567                 if (planes[0])
568                     res |= DirMask.MASK_WEST;
569                 if (zPlaneFromXplanes(planes, 0))
570                     res |= DirMask.MASK_NORTH;
571                 if (zPlaneFromXplanes(planes, 7))
572                     res |= DirMask.MASK_SOUTH;
573                 if (yPlaneFromXplanes(planes, 0))
574                     res |= DirMask.MASK_DOWN;
575                 if (yPlaneFromXplanes(planes, 7))
576                     res |= DirMask.MASK_UP;
577                 break;
578             case Dir.EAST: // x++
579                 for (int i = 0; i <= 7; i++) {
580                     mask = spreadXPlane(mask, canPassPlanesX[i], DirMask.MASK_ALL);
581                     if (!mask)
582                         break;
583                     planes[i] = mask;
584                 }
585                 if (planes[7])
586                     res |= DirMask.MASK_EAST;
587                 if (zPlaneFromXplanes(planes, 0))
588                     res |= DirMask.MASK_NORTH;
589                 if (zPlaneFromXplanes(planes, 7))
590                     res |= DirMask.MASK_SOUTH;
591                 if (yPlaneFromXplanes(planes, 0))
592                     res |= DirMask.MASK_DOWN;
593                 if (yPlaneFromXplanes(planes, 7))
594                     res |= DirMask.MASK_UP;
595                 break;
596             case Dir.DOWN: // y--
597                 for (int i = 7; i >= 0; i--) {
598                     mask = spreadYPlane(mask, canPassPlanesY[i], DirMask.MASK_ALL);
599                     if (!mask)
600                         break;
601                     planes[i] = mask;
602                 }
603                 if (planes[0])
604                     res |= DirMask.MASK_DOWN;
605                 if (zPlaneFromYplanes(planes, 0))
606                     res |= DirMask.MASK_NORTH;
607                 if (zPlaneFromYplanes(planes, 7))
608                     res |= DirMask.MASK_SOUTH;
609                 if (xPlaneFromYplanes(planes, 0))
610                     res |= DirMask.MASK_WEST;
611                 if (xPlaneFromYplanes(planes, 7))
612                     res |= DirMask.MASK_EAST;
613                 break;
614             case Dir.UP: // y--
615                 for (int i = 0; i <= 7; i++) {
616                     mask = spreadYPlane(mask, canPassPlanesY[i], DirMask.MASK_ALL);
617                     if (!mask)
618                         break;
619                     planes[i] = mask;
620                 }
621                 if (planes[7])
622                     res |= DirMask.MASK_UP;
623                 if (zPlaneFromYplanes(planes, 0))
624                     res |= DirMask.MASK_NORTH;
625                 if (zPlaneFromYplanes(planes, 7))
626                     res |= DirMask.MASK_SOUTH;
627                 if (xPlaneFromYplanes(planes, 0))
628                     res |= DirMask.MASK_WEST;
629                 if (xPlaneFromYplanes(planes, 7))
630                     res |= DirMask.MASK_EAST;
631                 break;
632         }
633         canPassFromTo[dirFrom] = res;
634     }
635 
636     static void spreadFlags(ulong src, ref ulong[8] planes, ref ulong[8] dst, int start, int end, ubyte spreadMask) {
637         if (start < end) {
638             for (int i = start; i <= end; ++i) {
639                 ulong mask = src;
640                 if (spreadMask & SpreadMask.SpreadLeft)
641                     mask |= ((src << 1) & 0xFEFEFEFEFEFEFEFE);
642                 if (spreadMask & SpreadMask.SpreadRight)
643                     mask |= ((src >> 1) & 0x7F7F7F7F7F7F7F7F);
644                 if (spreadMask & SpreadMask.SpreadUp)
645                     mask |= ((src << 8) & 0xFFFFFFFFFFFFFF00);
646                 if (spreadMask & SpreadMask.SpreadDown)
647                     mask |= ((src >> 8) & 0x00FFFFFFFFFFFFFF);
648                 src = planes[i] & mask;
649                 dst[i] = src;
650             }
651         } else {
652             for (int i = end; i >= start; --i) {
653                 ulong mask = src;
654                 if (spreadMask & SpreadMask.SpreadLeft)
655                     mask |= ((src << 1) & 0xFEFEFEFEFEFEFEFE);
656                 if (spreadMask & SpreadMask.SpreadRight)
657                     mask |= ((src >> 1) & 0x7F7F7F7F7F7F7F7F);
658                 if (spreadMask & SpreadMask.SpreadUp)
659                     mask |= ((src << 8) & 0xFFFFFFFFFFFFFF00);
660                 if (spreadMask & SpreadMask.SpreadDown)
661                     mask |= ((src >> 8) & 0x00FFFFFFFFFFFFFF);
662                 src = planes[i] & mask;
663                 dst[i] = src;
664             }
665         }
666     }
667 
668     ulong canPass(ulong mask, Dir dir, Dir to, ubyte dirMask = DirMask.MASK_ALL) {
669         ulong[8] planes;
670         ubyte spreadMask = DIR_AND_MASK_TO_SPREAD_FLAGS[dirMask][dir];
671         final switch(dir) with (Dir) {
672             case NORTH:
673                 spreadFlags(mask, canPassPlanesZ, planes, 0, 7, spreadMask);
674                 final switch (to) {
675                     case NORTH:
676                         return planes[7];
677                     case SOUTH:
678                         return planes[0];
679                     case EAST:
680                         return slicePlane7(planes);
681                     case WEST:
682                         return slicePlane0(planes);
683                     case UP:
684                         return slicePlane7(planes);
685                     case DOWN:
686                         return slicePlane0(planes);
687                 }
688             case SOUTH:
689                 spreadFlags(mask, canPassPlanesZ, planes, 7, 0, spreadMask);
690                 final switch (to) {
691                     case NORTH:
692                         return planes[7];
693                     case SOUTH:
694                         return planes[0];
695                     case EAST:
696                         return slicePlane7(planes);
697                     case WEST:
698                         return slicePlane0(planes);
699                     case UP:
700                         return slicePlane7(planes);
701                     case DOWN:
702                         return slicePlane0(planes);
703                 }
704             case WEST:
705                 spreadFlags(mask, canPassPlanesX, planes, 7, 0, spreadMask);
706                 final switch (to) {
707                     case NORTH:
708                         return slicePlane7(planes);
709                     case SOUTH:
710                         return slicePlane0(planes);
711                     case EAST:
712                         return planes[7];
713                     case WEST:
714                         return planes[0];
715                     case UP:
716                         return slicePlane7(planes);
717                     case DOWN:
718                         return slicePlane0(planes);
719                 }
720             case EAST:
721                 spreadFlags(mask, canPassPlanesX, planes, 0, 7, spreadMask);
722                 final switch (to) {
723                     case NORTH:
724                         return slicePlane7(planes);
725                     case SOUTH:
726                         return slicePlane0(planes);
727                     case EAST:
728                         return planes[7];
729                     case WEST:
730                         return planes[0];
731                     case UP:
732                         return slicePlane7(planes);
733                     case DOWN:
734                         return slicePlane0(planes);
735                 }
736             case UP:
737                 spreadFlags(mask, canPassPlanesY, planes, 0, 7, spreadMask);
738                 final switch (to) {
739                     case NORTH:
740                         return slicePlane7(planes);
741                     case SOUTH:
742                         return slicePlane0(planes);
743                     case EAST:
744                         return slicePlane7(planes);
745                     case WEST:
746                         return slicePlane0(planes);
747                     case UP:
748                         return planes[7];
749                     case DOWN:
750                         return planes[0];
751                 }
752             case DOWN:
753                 spreadFlags(mask, canPassPlanesY, planes, 7, 0, spreadMask);
754                 final switch (to) {
755                     case NORTH:
756                         return slicePlane7(planes);
757                     case SOUTH:
758                         return slicePlane0(planes);
759                     case EAST:
760                         return slicePlane7(planes);
761                     case WEST:
762                         return slicePlane0(planes);
763                     case UP:
764                         return planes[7];
765                     case DOWN:
766                         return planes[0];
767                 }
768         }
769     }
770 
771     static ulong slicePlane0(ref ulong[8] planes) {
772         ulong res = 0;
773         for (int i = 0; i < 8; i++) {
774             res |= (planes[i] & 0x0101010101010101) << i;
775         }
776         return res;
777     }
778 
779     static ulong slicePlane7(ref ulong[8] planes) {
780         ulong res = 0;
781         for (int i = 0; i < 8; i++) {
782             res |= (planes[i] & 0x8080808080808080) >> (7 - i);
783         }
784         return res;
785     }
786 }
787 
788 enum SpreadMask : ubyte {
789     SpreadLeft = 1,
790     SpreadRight = 2,
791     SpreadUp = 4,
792     SpreadDown = 8,
793 }
794 
795 ubyte dirMaskToSpreadMask(Dir dir, ubyte dirMask) {
796     ubyte res = 0;
797     final switch (dir) with (Dir) {
798         case NORTH: // from north
799         case SOUTH:
800             res |= (dirMask & DirMask.MASK_UP) ? SpreadMask.SpreadUp : 0;
801             res |= (dirMask & DirMask.MASK_DOWN) ? SpreadMask.SpreadDown : 0;
802             res |= (dirMask & DirMask.MASK_EAST) ? SpreadMask.SpreadLeft : 0;
803             res |= (dirMask & DirMask.MASK_WEST) ? SpreadMask.SpreadRight : 0;
804             break;
805         case WEST:
806         case EAST:
807             res |= (dirMask & DirMask.MASK_UP) ? SpreadMask.SpreadUp : 0;
808             res |= (dirMask & DirMask.MASK_DOWN) ? SpreadMask.SpreadDown : 0;
809             res |= (dirMask & DirMask.MASK_NORTH) ? SpreadMask.SpreadLeft : 0;
810             res |= (dirMask & DirMask.MASK_SOUTH) ? SpreadMask.SpreadRight : 0;
811             break;
812         case UP:
813         case DOWN:
814             res |= (dirMask & DirMask.MASK_EAST) ? SpreadMask.SpreadLeft : 0;
815             res |= (dirMask & DirMask.MASK_WEST) ? SpreadMask.SpreadRight : 0;
816             res |= (dirMask & DirMask.MASK_NORTH) ? SpreadMask.SpreadUp : 0;
817             res |= (dirMask & DirMask.MASK_SOUTH) ? SpreadMask.SpreadDown : 0;
818             break;
819     }
820     return res;
821 }
822 
823 // immutable SpreadMask[DirMask][Dir] DIR_AND_MASK_TO_SPREAD_FLAGS
824 mixin(generateDirMaskSource());
825 
826 string generateDirMaskSource() {
827     import std.conv : to;
828     char[] src;
829     src ~= "immutable ubyte[64][6] DIR_AND_MASK_TO_SPREAD_FLAGS = [\n";
830     for (Dir from = Dir.min; from <= Dir.max; from++) {
831         if (from)
832             src ~= ",\n";
833         src ~= "    // ";
834         src ~= to!string(from);
835         src ~= "\n    [";
836         for (ubyte mask = 0; mask < 64; mask++) {
837             ubyte res = dirMaskToSpreadMask(from, mask);
838             if (mask)
839                 src ~= ", ";
840             if (mask == 32)
841                 src ~= "\n     ";
842             src ~= to!string(res);
843         }
844         src ~= "]";
845     }
846     src ~= "\n];\n";
847     return src.dup;
848 }
849 
850 void testDirMaskToSpreadMask() {
851     import dlangui.core.logger;
852     for (Dir from = Dir.min; from <= Dir.max; from++) {
853         for (ubyte mask = 0; mask < 64; mask++) {
854             ubyte res = dirMaskToSpreadMask(from, mask);
855             char[]buf;
856             buf ~= "[";
857             if (mask & DirMask.MASK_NORTH) buf ~= " NORTH";
858             if (mask & DirMask.MASK_SOUTH) buf ~= " SOUTH";
859             if (mask & DirMask.MASK_WEST) buf ~= " WEST";
860             if (mask & DirMask.MASK_EAST) buf ~= " EAST";
861             if (mask & DirMask.MASK_UP) buf ~= " UP";
862             if (mask & DirMask.MASK_DOWN) buf ~= " DOWN";
863             buf ~= " ] => (";
864             if (res & SpreadMask.SpreadLeft) buf ~= " SpreadLeft";
865             if (res & SpreadMask.SpreadRight) buf ~= " SpreadRight";
866             if (res & SpreadMask.SpreadUp) buf ~= " SpreadUp";
867             if (res & SpreadMask.SpreadDown) buf ~= " SpreadDown";
868             buf ~= " )";
869             Log.d("dirMaskToSpreadMask ", from, "  ", buf);
870         }
871     }
872     Log.d("Source: \n", generateDirMaskSource());
873 }
874 
875 
876 /// mask for available spread direction for chunk dest visited from camera chunk position origin
877 ubyte calcSpreadMask(Vector3d dest, Vector3d origin) {
878     ubyte res = 0;
879     if (dest.x < origin.x) {
880         res |= DirMask.MASK_WEST;
881     } else if (dest.x > origin.x) {
882         res |= DirMask.MASK_EAST;
883     } else {
884         res |= DirMask.MASK_WEST | DirMask.MASK_EAST;
885     }
886     if (dest.y < origin.y) {
887         res |= DirMask.MASK_DOWN;
888     } else if (dest.y > origin.y) {
889         res |= DirMask.MASK_UP;
890     } else {
891         res |= DirMask.MASK_DOWN | DirMask.MASK_UP;
892     }
893     if (dest.z < origin.z) {
894         res |= DirMask.MASK_NORTH;
895     } else if (dest.z > origin.z) {
896         res |= DirMask.MASK_SOUTH;
897     } else {
898         res |= DirMask.MASK_NORTH | DirMask.MASK_SOUTH;
899     }
900     return res;
901 }
902 
903 /*
904       Z planes (NORTH SOUTH): x, y
905          x=0  x=1  x=2  x=3  x=4  x=5  x=6  x=7
906     y=0   0    1    2    3    4    5    6    7
907     y=1   8    9   10   11   12   13   14   15
908     y=2  16   17   18   19   29   21   22   23
909     y=3  24   25   26   27   28   29   30   31
910     y=4  32   33   34   35   36   37   38   39
911     y=5  40   41   42   43   44   45   46   47
912     y=6  48   49   50   51   52   53   54   55
913     y=7  56   57   58   59   60   61   62   63
914 */
915 ulong spreadZPlane(ulong mask, ulong canPassMask, ubyte spreadToDirMask) {
916     ulong res = mask & canPassMask;
917     if (!res)
918         return 0;
919     if (spreadToDirMask & DirMask.MASK_WEST) { // x--
920         res |= ((mask & 0xFEFEFEFEFEFEFEFEL) >> 1) & canPassMask;
921     }
922     if (spreadToDirMask & DirMask.MASK_EAST) { // x++
923         res |= ((mask & 0x7f7f7f7f7f7f7f7fL) << 1) & canPassMask;
924     }
925     if (spreadToDirMask & DirMask.MASK_UP) { // y++
926         res |= ((mask & 0x00ffffffffffffffL) << 8) & canPassMask;
927     }
928     if (spreadToDirMask & DirMask.MASK_DOWN) { // y--
929         res |= ((mask & 0xffffffffffffff00L) >> 8) & canPassMask;
930     }
931     return res;
932 }
933 
934     /*
935       X planes (WEST EAST): z, y
936          z=0  z=1  z=2  z=3  z=4  z=5  z=6  z=7
937     y=0   0    1    2    3    4    5    6    7
938     y=1   8    9   10   11   12   13   14   15
939     y=2  16   17   18   19   29   21   22   23
940     y=3  24   25   26   27   28   29   30   31
941     y=4  32   33   34   35   36   37   38   39
942     y=5  40   41   42   43   44   45   46   47
943     y=6  48   49   50   51   52   53   54   55
944     y=7  56   57   58   59   60   61   62   63
945     */
946 ulong spreadXPlane(ulong mask, ulong canPassMask, ubyte spreadToDirMask) {
947     ulong res = mask & canPassMask;
948     if (!res)
949         return 0;
950     if (spreadToDirMask & DirMask.MASK_NORTH) { // z--
951         res |= ((mask & 0xFEFEFEFEFEFEFEFEL) >> 1) & canPassMask;
952     }
953     if (spreadToDirMask & DirMask.MASK_SOUTH) { // z++
954         res |= ((mask & 0x7f7f7f7f7f7f7f7fL) << 1) & canPassMask;
955     }
956     if (spreadToDirMask & DirMask.MASK_UP) { // y++
957         res |= ((mask & 0x00ffffffffffffffL) << 8) & canPassMask;
958     }
959     if (spreadToDirMask & DirMask.MASK_DOWN) { // y--
960         res |= ((mask & 0xffffffffffffff00L) >> 8) & canPassMask;
961     }
962     return res;
963 }
964 
965     /*
966 
967       Y planes (DOWN UP): x, z
968          x=0  x=1  x=2  x=3  x=4  x=5  x=6  x=7
969     z=0   0    1    2    3    4    5    6    7
970     z=1   8    9   10   11   12   13   14   15
971     z=2  16   17   18   19   29   21   22   23
972     z=3  24   25   26   27   28   29   30   31
973     z=4  32   33   34   35   36   37   38   39
974     z=5  40   41   42   43   44   45   46   47
975     z=6  48   49   50   51   52   53   54   55
976     z=7  56   57   58   59   60   61   62   63
977 
978     */
979 
980 ulong spreadYPlane(ulong mask, ulong canPassMask, ubyte spreadToDirMask) {
981     ulong res = mask & canPassMask;
982     if (!res)
983         return 0;
984     if (spreadToDirMask & DirMask.MASK_WEST) { // x--
985         res |= ((mask & 0xFEFEFEFEFEFEFEFEL) >> 1) & canPassMask;
986     }
987     if (spreadToDirMask & DirMask.MASK_EAST) { // x++
988         res |= ((mask & 0x7f7f7f7f7f7f7f7fL) << 1) & canPassMask;
989     }
990     if (spreadToDirMask & DirMask.MASK_SOUTH) { // z++
991         res |= ((mask & 0x00ffffffffffffffL) << 8) & canPassMask;
992     }
993     if (spreadToDirMask & DirMask.MASK_NORTH) { // z--
994         res |= ((mask & 0xffffffffffffff00L) >> 8) & canPassMask;
995     }
996     return res;
997 }
998 
999     /*
1000             Z planes (NORTH SOUTH): x, y
1001                 x=0  x=1  x=2  x=3  x=4  x=5  x=6  x=7
1002         y=0   0    1    2    3    4    5    6    7
1003         y=1   8    9   10   11   12   13   14   15
1004         y=2  16   17   18   19   29   21   22   23
1005         y=3  24   25   26   27   28   29   30   31
1006         y=4  32   33   34   35   36   37   38   39
1007         y=5  40   41   42   43   44   45   46   47
1008         y=6  48   49   50   51   52   53   54   55
1009         y=7  56   57   58   59   60   61   62   63
1010 
1011           X planes (WEST EAST): z, y
1012              z=0  z=1  z=2  z=3  z=4  z=5  z=6  z=7
1013         y=0   0    1    2    3    4    5    6    7
1014         y=1   8    9   10   11   12   13   14   15
1015         y=2  16   17   18   19   29   21   22   23
1016         y=3  24   25   26   27   28   29   30   31
1017         y=4  32   33   34   35   36   37   38   39
1018         y=5  40   41   42   43   44   45   46   47
1019         y=6  48   49   50   51   52   53   54   55
1020         y=7  56   57   58   59   60   61   62   63
1021     */
1022 ulong xPlaneFromZplanes(ref ulong[8] planes, int x) {
1023     ulong res = 0;
1024     for (int z = 0; z < 8; z++) {
1025         ulong n = planes[z]; // one plane == z
1026         n = n >> x; // move to low bit
1027         n &=  0x0101010101010101L;
1028         n = n << z; // move to Z bit
1029         res |= n;
1030     }
1031     return res;
1032 }
1033 
1034     /*
1035             Z planes (NORTH SOUTH): x, y
1036              x=0  x=1  x=2  x=3  x=4  x=5  x=6  x=7
1037         y=0   0    1    2    3    4    5    6    7
1038         y=1   8    9   10   11   12   13   14   15
1039         y=2  16   17   18   19   29   21   22   23
1040         y=3  24   25   26   27   28   29   30   31
1041         y=4  32   33   34   35   36   37   38   39
1042         y=5  40   41   42   43   44   45   46   47
1043         y=6  48   49   50   51   52   53   54   55
1044         y=7  56   57   58   59   60   61   62   63
1045 
1046           Y planes (DOWN UP): x, z
1047              x=0  x=1  x=2  x=3  x=4  x=5  x=6  x=7
1048         z=0   0    1    2    3    4    5    6    7
1049         z=1   8    9   10   11   12   13   14   15
1050         z=2  16   17   18   19   29   21   22   23
1051         z=3  24   25   26   27   28   29   30   31
1052         z=4  32   33   34   35   36   37   38   39
1053         z=5  40   41   42   43   44   45   46   47
1054         z=6  48   49   50   51   52   53   54   55
1055         z=7  56   57   58   59   60   61   62   63
1056     */
1057 ulong yPlaneFromZplanes(ref ulong[8] planes, int y) {
1058     ulong res = 0;
1059     for (int z = 0; z < 8; z++) {
1060         ulong n = planes[z]; // one plane == z
1061         n = n >> (y * 8); // move to low byte
1062         n &= 0xFF;
1063         n = n << (z * 8); // move to Z position
1064         res |= n;
1065     }
1066     return res;
1067 }
1068 
1069 /*
1070 X planes (WEST EAST): z, y
1071     z=0  z=1  z=2  z=3  z=4  z=5  z=6  z=7
1072 y=0   0    1    2    3    4    5    6    7
1073 y=1   8    9   10   11   12   13   14   15
1074 y=2  16   17   18   19   29   21   22   23
1075 y=3  24   25   26   27   28   29   30   31
1076 y=4  32   33   34   35   36   37   38   39
1077 y=5  40   41   42   43   44   45   46   47
1078 y=6  48   49   50   51   52   53   54   55
1079 y=7  56   57   58   59   60   61   62   63
1080 
1081 Z planes (NORTH SOUTH): x, y
1082     x=0  x=1  x=2  x=3  x=4  x=5  x=6  x=7
1083 y=0   0    1    2    3    4    5    6    7
1084 y=1   8    9   10   11   12   13   14   15
1085 y=2  16   17   18   19   29   21   22   23
1086 y=3  24   25   26   27   28   29   30   31
1087 y=4  32   33   34   35   36   37   38   39
1088 y=5  40   41   42   43   44   45   46   47
1089 y=6  48   49   50   51   52   53   54   55
1090 y=7  56   57   58   59   60   61   62   63
1091 
1092 */
1093 ulong zPlaneFromXplanes(ref ulong[8] planes, int z) {
1094     ulong res = 0;
1095     for (int x = 0; x < 8; x++) {
1096         ulong n = planes[x]; // one plane == z
1097         n = n >> z; // move to low bit
1098         n &=  0x0101010101010101L;
1099         n = n << x; // move to X bit
1100         res |= n;
1101     }
1102     return res;
1103 }
1104 
1105 /*
1106 X planes (WEST EAST): z, y
1107     z=0  z=1  z=2  z=3  z=4  z=5  z=6  z=7
1108 y=0   0    1    2    3    4    5    6    7
1109 y=1   8    9   10   11   12   13   14   15
1110 y=2  16   17   18   19   29   21   22   23
1111 y=3  24   25   26   27   28   29   30   31
1112 y=4  32   33   34   35   36   37   38   39
1113 y=5  40   41   42   43   44   45   46   47
1114 y=6  48   49   50   51   52   53   54   55
1115 y=7  56   57   58   59   60   61   62   63
1116 
1117 Y planes (DOWN UP): x, z
1118     x=0  x=1  x=2  x=3  x=4  x=5  x=6  x=7
1119 z=0   0    1    2    3    4    5    6    7
1120 z=1   8    9   10   11   12   13   14   15
1121 z=2  16   17   18   19   29   21   22   23
1122 z=3  24   25   26   27   28   29   30   31
1123 z=4  32   33   34   35   36   37   38   39
1124 z=5  40   41   42   43   44   45   46   47
1125 z=6  48   49   50   51   52   53   54   55
1126 z=7  56   57   58   59   60   61   62   63
1127 */
1128 // move bit 0 -> 0, 1->8, 2->16, 3->24, .. 7->56
1129 ulong flipBitsLeft(ulong n) {
1130     n &=  0xFFL; //
1131     return ((n&1) | ((n&2) << 7) | ((n&4) << 14) | ((n&8) << 21) | ((n&16) << 28) | ((n&32) << 35) | ((n&64) << 42) | ((n&128)<< 49)) & 0x0101010101010101L;
1132 }
1133 ulong yPlaneFromXplanes(ref ulong[8] planes, int y) {
1134     ulong res = 0;
1135     for (int x = 0; x < 8; x++) {
1136         ulong n = planes[x]; // one plane == z
1137         n = n >> (y * 8); // move to low byte
1138         n = flipBitsLeft(n);
1139         n = n << (x); // move to x position
1140         res |= n;
1141     }
1142     return res;
1143 }
1144 
1145 /*
1146    Y planes (DOWN UP): x, z
1147     x=0  x=1  x=2  x=3  x=4  x=5  x=6  x=7
1148 z=0   0    1    2    3    4    5    6    7
1149 z=1   8    9   10   11   12   13   14   15
1150 z=2  16   17   18   19   29   21   22   23
1151 z=3  24   25   26   27   28   29   30   31
1152 z=4  32   33   34   35   36   37   38   39
1153 z=5  40   41   42   43   44   45   46   47
1154 z=6  48   49   50   51   52   53   54   55
1155 z=7  56   57   58   59   60   61   62   63
1156 
1157 Z planes (NORTH SOUTH): x, y
1158     x=0  x=1  x=2  x=3  x=4  x=5  x=6  x=7
1159 y=0   0    1    2    3    4    5    6    7
1160 y=1   8    9   10   11   12   13   14   15
1161 y=2  16   17   18   19   29   21   22   23
1162 y=3  24   25   26   27   28   29   30   31
1163 y=4  32   33   34   35   36   37   38   39
1164 y=5  40   41   42   43   44   45   46   47
1165 y=6  48   49   50   51   52   53   54   55
1166 y=7  56   57   58   59   60   61   62   63
1167 
1168 */
1169 ulong zPlaneFromYplanes(ref ulong[8] planes, int z) {
1170     ulong res = 0;
1171     for (int y = 0; y < 8; y++) {
1172         ulong n = planes[y]; // one plane == z
1173         n = n >> (z * 8); // move to low byte
1174         n &= 0xFF;
1175         n = n << (y * 8); // move to Z position
1176         res |= n;
1177     }
1178     return res;
1179 }
1180 
1181 /*
1182 Y planes (DOWN UP): x, z
1183     x=0  x=1  x=2  x=3  x=4  x=5  x=6  x=7
1184 z=0   0    1    2    3    4    5    6    7
1185 z=1   8    9   10   11   12   13   14   15
1186 z=2  16   17   18   19   29   21   22   23
1187 z=3  24   25   26   27   28   29   30   31
1188 z=4  32   33   34   35   36   37   38   39
1189 z=5  40   41   42   43   44   45   46   47
1190 z=6  48   49   50   51   52   53   54   55
1191 z=7  56   57   58   59   60   61   62   63
1192 
1193 X planes (WEST EAST): z, y
1194     z=0  z=1  z=2  z=3  z=4  z=5  z=6  z=7
1195 y=0   0    1    2    3    4    5    6    7
1196 y=1   8    9   10   11   12   13   14   15
1197 y=2  16   17   18   19   29   21   22   23
1198 y=3  24   25   26   27   28   29   30   31
1199 y=4  32   33   34   35   36   37   38   39
1200 y=5  40   41   42   43   44   45   46   47
1201 y=6  48   49   50   51   52   53   54   55
1202 y=7  56   57   58   59   60   61   62   63
1203 */
1204 // move bit 0 -> 0, 8->1, 16->2, 24->3, .. 56->7
1205 ulong flipBitsRight(ulong n) {
1206     n &=  0x0101010101010101L; //
1207     return (n | (n >> 7) | (n >> 14) | (n >> 21) | (n >> 28) | (n >> 35) | (n >> 42) | (n >> 49)) & 255;
1208 }
1209 ulong xPlaneFromYplanes(ref ulong[8] planes, int x) {
1210     ulong res = 0;
1211     for (int y = 0; y < 8; y++) {
1212         ulong n = planes[y]; // one plane == y
1213         n = n >> x; // move to low bit
1214         n = flipBitsRight(n);
1215         n = n << (y * 8); // move to y byte
1216         res |= n;
1217     }
1218     return res;
1219 }
1220 
1221 struct Planes(immutable Dir dir) {
1222     ulong[8] planes;
1223     alias planes this;
1224     bool opIndex(int x, int y, int z) {
1225         static if (dir == Dir.NORTH || dir == Dir.SOUTH) {
1226             // Z planes
1227             ulong zplanemask = cast(ulong)1 << ((y << 3) | x);
1228             return (planes[z] & zplanemask) != 0;
1229         } else static if (dir == Dir.WEST || dir == Dir.EAST) {
1230             // X planes
1231             ulong xplanemask = cast(ulong)1 << ((y << 3) | z);
1232             return (planes[x] & xplanemask) != 0;
1233         } else {
1234             // Y planes
1235             ulong yplanemask = cast(ulong)1 << ((z << 3) | x);
1236             return (planes[y] & yplanemask) != 0;
1237         }
1238     }
1239     void opIndexAssign(bool value, int x, int y, int z) {
1240         static if (dir == Dir.NORTH || dir == Dir.SOUTH) {
1241             // Z planes
1242             ulong zplanemask = cast(ulong)1 << ((y << 3) | x);
1243             if (value)
1244                 planes[z] |= zplanemask;
1245             else
1246                 planes[z] &= ~zplanemask;
1247         } else static if (dir == Dir.WEST || dir == Dir.EAST) {
1248             // X planes
1249             ulong xplanemask = cast(ulong)1 << ((y << 3) | z);
1250             if (value)
1251                 planes[x] |= xplanemask;
1252             else
1253                 planes[x] &= ~xplanemask;
1254         } else {
1255             // Y planes
1256             ulong yplanemask = cast(ulong)1 << ((z << 3) | x);
1257             if (value)
1258                 planes[y] |= yplanemask;
1259             else
1260                 planes[y] &= ~yplanemask;
1261         }
1262     }
1263 }
1264 
1265 struct AllPlanes {
1266     Planes!(Dir.NORTH) zplanes;
1267     Planes!(Dir.WEST) xplanes;
1268     Planes!(Dir.DOWN) yplanes;
1269     bool opIndex(int x, int y, int z) {
1270         bool vx = xplanes[x, y, z];
1271         bool vy = yplanes[x, y, z];
1272         bool vz = zplanes[x, y, z];
1273         assert(vx == vy && vx == vz);
1274         return vx;
1275     }
1276     void opIndexAssign(bool value, int x, int y, int z) {
1277         xplanes[x, y, z] = value;
1278         yplanes[x, y, z] = value;
1279         zplanes[x, y, z] = value;
1280     }
1281     void testAllPlanesEqual() {
1282         for (int x = 0; x < 8; x++)
1283             for (int y = 0; y < 8; y++)
1284                 for (int z = 0; z < 8; z++)
1285                     opIndex(x, y, z);
1286     }
1287     void testPlanesExtract() {
1288 
1289         testAllPlanesEqual();
1290 
1291         ulong n, m;
1292 
1293         n = xPlaneFromYplanes(yplanes, 0);
1294         m = xplanes.planes[0];
1295         assert(n == m);
1296 
1297         for (int i = 0; i < 8; i++) {
1298             n = xPlaneFromYplanes(yplanes, i);
1299             assert(n == xplanes.planes[i]);
1300             n = zPlaneFromYplanes(yplanes, i);
1301             assert(n == zplanes.planes[i]);
1302             n = xPlaneFromZplanes(zplanes, i);
1303             assert(n == xplanes.planes[i]);
1304             n = yPlaneFromZplanes(zplanes, i);
1305             assert(n == yplanes.planes[i]);
1306             n = zPlaneFromXplanes(xplanes, i);
1307             assert(n == zplanes.planes[i]);
1308             n = yPlaneFromXplanes(xplanes, i);
1309             assert(n == yplanes.planes[i]);
1310         }
1311     }
1312 }
1313 
1314 void testPlanes() {
1315     AllPlanes v;
1316     v[0, 1, 2] = true;
1317     v.testPlanesExtract();
1318     v[5, 0, 6] = true;
1319     v[7, 2, 0] = true;
1320     v[6, 7, 7] = true;
1321     v[3, 3, 7] = true;
1322     v[6, 5, 3] = true;
1323     v.testPlanesExtract();
1324     v[5, 0, 6] = true;
1325     v[3, 4, 5] = true;
1326     v[6, 2, 3] = true;
1327     v[1, 7, 6] = true;
1328     v.testPlanesExtract();
1329     v[3, 4, 5] = false;
1330     v[6, 2, 3] = false;
1331     v.testPlanesExtract();
1332 }
1333 
1334 version(FAST_VISIBILITY_PATH) {
1335     struct VisibilityCheckChunk {
1336         SmallChunk * chunk;
1337         ulong[6] maskFrom;
1338         ulong[6] maskTo;
1339         Vector3d pos;
1340         ubyte visitedFromDirMask;
1341         ubyte spreadToDirMask;
1342         void setMask(ulong mask, Dir fromDir) {
1343             maskFrom[fromDir] |= mask;
1344             visitedFromDirMask |= (1 << fromDir);
1345         }
1346 
1347 
1348         void traceFrom(Dir fromDir) {
1349             ubyte m = chunk ? chunk.getCanPassFromFlags(fromDir) : DirMask.MASK_ALL;
1350             for (ubyte dir = 0; dir < 6; dir++) {
1351                 ubyte flag = cast(ubyte)(1 << dir);
1352                 if (flag & spreadToDirMask)
1353                     if (m & flag)
1354                         maskTo[dir] |= 0xFFFFFFFFFFFFFFFFL;
1355             }
1356 
1357         }
1358 
1359         void tracePaths() {
1360             for (Dir dirFrom = Dir.min; dirFrom <= Dir.max; dirFrom++) {
1361                 if ((visitedFromDirMask & (1 << dirFrom)))
1362                     traceFrom(dirFrom);
1363             }
1364         }
1365     }
1366 } else {
1367     struct VisibilityCheckChunk {
1368         SmallChunk * chunk;
1369         ulong[6] maskFrom;
1370         ulong[6] maskTo;
1371         Vector3d pos;
1372         ubyte visitedFromDirMask;
1373         ubyte spreadToDirMask;
1374         void setMask(ulong mask, Dir fromDir) {
1375             maskFrom[fromDir] |= mask;
1376             visitedFromDirMask |= (1 << fromDir);
1377         }
1378         /*
1379         Z planes (NORTH SOUTH): x, y
1380         x=0  x=1  x=2  x=3  x=4  x=5  x=6  x=7
1381         y=0   0    1    2    3    4    5    6    7
1382         y=1   8    9   10   11   12   13   14   15
1383         y=2  16   17   18   19   29   21   22   23
1384         y=3  24   25   26   27   28   29   30   31
1385         y=4  32   33   34   35   36   37   38   39
1386         y=5  40   41   42   43   44   45   46   47
1387         y=6  48   49   50   51   52   53   54   55
1388         y=7  56   57   58   59   60   61   62   63
1389         */
1390         void applyZPlanesTrace(ref ulong[8] planes) {
1391             if (spreadToDirMask & DirMask.MASK_WEST) { // x--
1392                 // X planes (WEST EAST): z, y
1393                 maskTo[Dir.WEST] |= xPlaneFromZplanes(planes, 0);
1394             }
1395             if (spreadToDirMask & DirMask.MASK_EAST) { // x++
1396                 // X planes (WEST EAST): z, y
1397                 maskTo[Dir.EAST] |= xPlaneFromZplanes(planes, 7);
1398             }
1399             if (spreadToDirMask & DirMask.MASK_DOWN) { // y--
1400                 // Y planes (DOWN UP): x, z
1401                 maskTo[Dir.DOWN] |= yPlaneFromZplanes(planes, 0);
1402             }
1403             if (spreadToDirMask & DirMask.MASK_UP) { // y++
1404                 // Y planes (DOWN UP): x, z
1405                 maskTo[Dir.UP] |= yPlaneFromZplanes(planes, 7);
1406             }
1407         }
1408 
1409         void applyYPlanesTrace(ref ulong[8] planes) {
1410             if (spreadToDirMask & DirMask.MASK_WEST) { // x--
1411                 // X planes (WEST EAST): z, y
1412                 maskTo[Dir.WEST] |= xPlaneFromYplanes(planes, 0);
1413             }
1414             if (spreadToDirMask & DirMask.MASK_EAST) { // x++
1415                 // X planes (WEST EAST): z, y
1416                 maskTo[Dir.EAST] |= xPlaneFromYplanes(planes, 7);
1417             }
1418             if (spreadToDirMask & DirMask.MASK_NORTH) { // z--
1419                 // Z planes (NORTH SOUTH): x, y
1420                 maskTo[Dir.NORTH] |= zPlaneFromYplanes(planes, 0);
1421             }
1422             if (spreadToDirMask & DirMask.MASK_SOUTH) { // z++
1423                 // Z planes (NORTH SOUTH): x, y
1424                 maskTo[Dir.SOUTH] |= zPlaneFromYplanes(planes, 7);
1425             }
1426         }
1427 
1428         void applyXPlanesTrace(ref ulong[8] planes) {
1429             if (spreadToDirMask & DirMask.MASK_NORTH) { // z--
1430                 // Z planes (NORTH SOUTH): x, y
1431                 maskTo[Dir.NORTH] |= zPlaneFromXplanes(planes, 0);
1432             }
1433             if (spreadToDirMask & DirMask.MASK_SOUTH) { // z++
1434                 // Z planes (NORTH SOUTH): x, y
1435                 maskTo[Dir.SOUTH] |= zPlaneFromXplanes(planes, 7);
1436             }
1437             if (spreadToDirMask & DirMask.MASK_DOWN) { // y--
1438                 // Y planes (DOWN UP): x, z
1439                 maskTo[Dir.DOWN] |= yPlaneFromXplanes(planes, 0);
1440             }
1441             if (spreadToDirMask & DirMask.MASK_UP) { // y++
1442                 // Y planes (DOWN UP): x, z
1443                 maskTo[Dir.UP] |= yPlaneFromXplanes(planes, 7);
1444             }
1445         }
1446 
1447 
1448         void tracePaths() {
1449             if (!chunk) {
1450                 // empty chunk - assuming transparent
1451                 for (ubyte dir = 0; dir < 6; dir++) {
1452                     if (spreadToDirMask & (1 << dir))
1453                         maskTo[dir] |= 0xFFFFFFFFFFFFFFFFL;
1454                 }
1455                 return;
1456             }
1457             if (auto mask = maskFrom[Dir.NORTH]) {
1458                 ulong[8] planes;
1459                 for (int i = 7; i >= 0; i--) {
1460                     mask = spreadZPlane(mask, chunk.canPassPlanesZ[i], spreadToDirMask);
1461                     if (!mask)
1462                         break;
1463                     planes[i] = mask;
1464                 }
1465                 maskTo[Dir.NORTH] |= planes[0];
1466                 applyZPlanesTrace(planes);
1467             } else if (auto mask = maskFrom[Dir.SOUTH]) {
1468                 ulong[8] planes;
1469                 for (int i = 0; i <= 7; i++) {
1470                     mask = spreadZPlane(mask, chunk.canPassPlanesZ[i], spreadToDirMask);
1471                     if (!mask)
1472                         break;
1473                     planes[i] = mask;
1474                 }
1475                 maskTo[Dir.SOUTH] |= planes[7];
1476                 applyYPlanesTrace(planes);
1477             }
1478             if (auto mask = maskFrom[Dir.DOWN]) {
1479                 ulong[8] planes;
1480                 for (int i = 7; i >= 0; i--) {
1481                     mask = spreadYPlane(mask, chunk.canPassPlanesY[i], spreadToDirMask);
1482                     if (!mask)
1483                         break;
1484                     planes[i] = mask;
1485                 }
1486                 maskTo[Dir.DOWN] |= planes[0];
1487                 applyYPlanesTrace(planes);
1488             } else if (auto mask = maskFrom[Dir.UP]) {
1489                 ulong[8] planes;
1490                 for (int i = 0; i <= 7; i++) {
1491                     mask = spreadYPlane(mask, chunk.canPassPlanesY[i], spreadToDirMask);
1492                     if (!mask)
1493                         break;
1494                     planes[i] = mask;
1495                 }
1496                 maskTo[Dir.UP] |= planes[7];
1497                 applyYPlanesTrace(planes);
1498             }
1499             if (auto mask = maskFrom[Dir.WEST]) {
1500                 ulong[8] planes;
1501                 for (int i = 7; i >= 0; i--) {
1502                     mask = spreadXPlane(mask, chunk.canPassPlanesX[i], spreadToDirMask);
1503                     if (!mask)
1504                         break;
1505                     planes[i] = mask;
1506                 }
1507                 maskTo[Dir.WEST] |= planes[0];
1508                 applyXPlanesTrace(planes);
1509             } else if (auto mask = maskFrom[Dir.EAST]) {
1510                 ulong[8] planes;
1511                 for (int i = 0; i <= 7; i++) {
1512                     mask = spreadXPlane(mask, chunk.canPassPlanesX[i], spreadToDirMask);
1513                     if (!mask)
1514                         break;
1515                     planes[i] = mask;
1516                 }
1517                 maskTo[Dir.EAST] |= planes[7];
1518                 applyXPlanesTrace(planes);
1519             }
1520         }
1521     }
1522 }
1523 
1524 
1525 /// Diamond iterator for visibility check
1526 struct VisibilityCheckIterator {
1527     World world;
1528     Vector3d startPos;
1529     Vector3d camPos;
1530     SmallChunk * startChunk;
1531     ChunkVisitor visitor;
1532     int maxHeight;
1533     int maxDistance;
1534     int maxDistanceSquared;
1535     VisibilityCheckChunk[] plannedChunks;
1536     VisibilityCheckChunk[] visitedChunks;
1537     /// get or add planned chunk by position
1538     VisibilityCheckChunk * getOrAddPlannedChunk(Vector3d pos) {
1539         foreach(ref p; plannedChunks) {
1540             if (p.pos == pos)
1541                 return &p;
1542         }
1543         VisibilityCheckChunk plan;
1544         plan.pos = pos;
1545         plannedChunks ~= plan;
1546         return &plannedChunks[$ - 1];
1547     }
1548     // step 1: plan visiting chunk
1549     void planVisitingChunk(Vector3d p, Dir fromDir, ulong mask) {
1550         // mask test
1551         if (!mask)
1552             return;
1553         if (p.y > maxHeight + 16 && p.y > startPos.y)
1554             return;
1555         // distance test
1556         Vector3d diff = (p + Vector3d(4,4,4)) - camPos;
1557         if (diff.squaredLength() > maxDistanceSquared)
1558             return;
1559         int distance = diff.squaredLength;
1560         if (distance > 16*16) {
1561             diff = (diff * 256 + cameraDirection * 16) / 256;
1562             //diff += cameraDirection;
1563             // direction test (TODO)
1564             int dot = diff.dot(cameraDirection);
1565             if (dot < 8000)
1566                 return;
1567         }
1568         //....
1569         // plan visiting
1570         VisibilityCheckChunk * plan = getOrAddPlannedChunk(p);
1571         if (!plan.chunk) {
1572             plan.chunk = world.getCellChunk(p.x, p.y, p.z);
1573         }
1574         plan.setMask(mask, fromDir);
1575     }
1576     // step 2: visit all planned chunks: move planned to visited; trace paths; plan new visits
1577     void visitPlannedChunks() {
1578         import std.algorithm : swap;
1579         swap(visitedChunks, plannedChunks);
1580         plannedChunks.length = 0;
1581         foreach (ref p; visitedChunks) {
1582             if (!visitor.visit(world, p.chunk))
1583                 continue;
1584             /// set mask of spread directions
1585             p.spreadToDirMask = calcSpreadMask(p.pos, startPos);
1586             p.tracePaths();
1587             ubyte mask = p.spreadToDirMask;
1588             Vector3d pos = p.pos;
1589 
1590             if ((mask & DirMask.MASK_NORTH) && p.maskTo[Dir.NORTH]) { // z--
1591                 planVisitingChunk(Vector3d(pos.x, pos.y, pos.z - 8), Dir.NORTH, p.maskTo[Dir.NORTH]);
1592             }
1593             if ((mask & DirMask.MASK_SOUTH) && p.maskTo[Dir.SOUTH]) { // z++
1594                 planVisitingChunk(Vector3d(pos.x, pos.y, pos.z + 8), Dir.SOUTH, p.maskTo[Dir.SOUTH]);
1595             }
1596             if ((mask & DirMask.MASK_WEST) && p.maskTo[Dir.WEST]) { // x--
1597                 planVisitingChunk(Vector3d(pos.x - 8, pos.y, pos.z), Dir.WEST, p.maskTo[Dir.WEST]);
1598             }
1599             if ((mask & DirMask.MASK_EAST) && p.maskTo[Dir.EAST]) { // x++
1600                 planVisitingChunk(Vector3d(pos.x + 8, pos.y, pos.z), Dir.EAST, p.maskTo[Dir.EAST]);
1601             }
1602             if ((mask & DirMask.MASK_DOWN) && p.maskTo[Dir.DOWN]) { // y--
1603                 planVisitingChunk(Vector3d(pos.x, pos.y - 8, pos.z), Dir.DOWN, p.maskTo[Dir.DOWN]);
1604             }
1605             if ((mask & DirMask.MASK_UP) && p.maskTo[Dir.UP]) { // y++
1606                 planVisitingChunk(Vector3d(pos.x, pos.y + 8, pos.z), Dir.UP, p.maskTo[Dir.UP]);
1607             }
1608         }
1609     }
1610     void start(World world, Vector3d startPos, int maxDistance) {
1611         this.world = world;
1612         this.startChunk = world.getCellChunk(startPos.x, startPos.y, startPos.z);
1613         //if (!startChunk)
1614         //    return;
1615         startPos.x &= ~7;
1616         startPos.y &= ~7;
1617         startPos.z &= ~7;
1618         this.startPos = startPos; // position aligned by 8 cells
1619         plannedChunks.assumeSafeAppend;
1620         plannedChunks.length = 0;
1621         visitedChunks.assumeSafeAppend;
1622         visitedChunks.length = 0;
1623         maxDistanceSquared = maxDistance * maxDistance;
1624         this.maxDistance = maxDistance;
1625         maxHeight = world.regionHeight(startPos.x, startPos.z, maxDistance + 8) & 0xFFFFFF8 + 7;
1626         import dlangui.core.logger;
1627         Log.d("startPos: ", startPos, "  maxHeight:", maxHeight);
1628     }
1629     Vector3d cameraDirection;
1630     void visitVisibleChunks(ChunkVisitor visitor, Vector3d cameraDirection) {
1631         this.visitor = visitor;
1632         this.cameraDirection = cameraDirection;
1633         Vector3d cameraOffset = cameraDirection;
1634         cameraOffset.x /= 7;
1635         cameraOffset.y /= 7;
1636         cameraOffset.z /= 7;
1637         this.camPos = startPos - cameraOffset;
1638         //if (!startChunk)
1639         //    return;
1640         visitor.visit(world, startChunk);
1641         if (auto mask = startChunk ? startChunk.getSideCanPassToMask(Dir.NORTH) : 0xFFFFFFFFFFFFFFFFL)
1642             planVisitingChunk(Vector3d(startPos.x, startPos.y, startPos.z - 8), Dir.NORTH, mask);
1643         if (auto mask = startChunk ? startChunk.getSideCanPassToMask(Dir.SOUTH) : 0xFFFFFFFFFFFFFFFFL)
1644             planVisitingChunk(Vector3d(startPos.x, startPos.y, startPos.z + 8), Dir.SOUTH, mask);
1645         if (auto mask = startChunk ? startChunk.getSideCanPassToMask(Dir.WEST) : 0xFFFFFFFFFFFFFFFFL)
1646             planVisitingChunk(Vector3d(startPos.x - 8, startPos.y, startPos.z), Dir.WEST, mask);
1647         if (auto mask = startChunk ? startChunk.getSideCanPassToMask(Dir.EAST) : 0xFFFFFFFFFFFFFFFFL)
1648             planVisitingChunk(Vector3d(startPos.x + 8, startPos.y, startPos.z), Dir.EAST, mask);
1649         if (auto mask = startChunk ? startChunk.getSideCanPassToMask(Dir.DOWN) : 0xFFFFFFFFFFFFFFFFL)
1650             planVisitingChunk(Vector3d(startPos.x, startPos.y - 8, startPos.z), Dir.DOWN, mask);
1651         if (auto mask = startChunk ? startChunk.getSideCanPassToMask(Dir.UP) : 0xFFFFFFFFFFFFFFFFL)
1652             planVisitingChunk(Vector3d(startPos.x, startPos.y + 8, startPos.z), Dir.UP, mask);
1653         for (int d = 0; d < maxDistance; d += 5) {
1654             if (!plannedChunks.length)
1655                 break;
1656             visitPlannedChunks();
1657         }
1658     }
1659 }