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 }