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 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 }