src/voxel.cpp

   1 /*
   2 Minetest-c55
   3 Copyright (C) 2010 celeron55, Perttu Ahola <celeron55@gmail.com>
   4
   5 This program is free software; you can redistribute it and/or modify
   6 it under the terms of the GNU General Public License as published by
   7 the Free Software Foundation; either version 2 of the License, or
   8 (at your option) any later version.
   9
  10 This program is distributed in the hope that it will be useful,
  11 but WITHOUT ANY WARRANTY; without even the implied warranty of
  12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13 GNU General Public License for more details.
  14
  15 You should have received a copy of the GNU General Public License along
  16 with this program; if not, write to the Free Software Foundation, Inc.,
  17 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  18 */
  19
  20 #include "voxel.h"
  21 #include "map.h"
  22
  23 // For TimeTaker
  24 #include "utility.h"
  25 #include "gettime.h"
  26
  27 /*
  28         Debug stuff
  29 */
  30 u32 addarea_time = 0;
  31 u32 emerge_time = 0;
  32 u32 emerge_load_time = 0;
  33 u32 clearflag_time = 0;
  34 //u32 getwaterpressure_time = 0;
  35 //u32 spreadwaterpressure_time = 0;
  36 u32 updateareawaterpressure_time = 0;
  37 u32 flowwater_pre_time = 0;
  38
  39
  40 VoxelManipulator::VoxelManipulator():
  41         m_data(NULL),
  42         m_flags(NULL)
  43 {
  44         m_disable_water_climb = false;
  45 }
  46
  47 VoxelManipulator::~VoxelManipulator()
  48 {
  49         clear();
  50         if(m_data)
  51                 delete[] m_data;
  52         if(m_flags)
  53                 delete[] m_flags;
  54 }
  55
  56 void VoxelManipulator::clear()
  57 {
  58         // Reset area to volume=0
  59         m_area = VoxelArea();
  60         if(m_data)
  61                 delete[] m_data;
  62         m_data = NULL;
  63         if(m_flags)
  64                 delete[] m_flags;
  65         m_flags = NULL;
  66 }
  67
  68 void VoxelManipulator::print(std::ostream &o, VoxelPrintMode mode)
  69 {
  70         v3s16 em = m_area.getExtent();
  71         v3s16 of = m_area.MinEdge;
  72         o<<"size: "<<em.X<<"x"<<em.Y<<"x"<<em.Z
  73          <<" offset: ("<<of.X<<","<<of.Y<<","<<of.Z<<")"<<std::endl;
  74
  75         for(s32 y=m_area.MaxEdge.Y; y>=m_area.MinEdge.Y; y--)
  76         {
  77                 if(em.X >= 3 && em.Y >= 3)
  78                 {
  79                         if     (y==m_area.MinEdge.Y+2) o<<"^     ";
  80                         else if(y==m_area.MinEdge.Y+1) o<<"|     ";
  81                         else if(y==m_area.MinEdge.Y+0) o<<"y x-> ";
  82                         else                           o<<"      ";
  83                 }
  84
  85                 for(s32 z=m_area.MinEdge.Z; z<=m_area.MaxEdge.Z; z++)
  86                 {
  87                         for(s32 x=m_area.MinEdge.X; x<=m_area.MaxEdge.X; x++)
  88                         {
  89                                 u8 f = m_flags[m_area.index(x,y,z)];
  90                                 char c;
  91                                 if(f & VOXELFLAG_NOT_LOADED)
  92                                         c = 'N';
  93                                 else if(f & VOXELFLAG_INEXISTENT)
  94                                         c = 'I';
  95                                 else
  96                                 {
  97                                         c = 'X';
  98                                         u8 m = m_data[m_area.index(x,y,z)].d;
  99                                         u8 pr = m_data[m_area.index(x,y,z)].param2;
 100                                         if(mode == VOXELPRINT_MATERIAL)
 101                                         {
 102                                                 if(m <= 9)
 103                                                         c = m + '0';
 104                                         }
 105                                         else if(mode == VOXELPRINT_WATERPRESSURE)
 106                                         {
 107                                                 if(m == CONTENT_WATER)
 108                                                 {
 109                                                         c = 'w';
 110                                                         if(pr <= 9)
 111                                                                 c = pr + '0';
 112                                                 }
 113                                                 else if(m == CONTENT_AIR)
 114                                                 {
 115                                                         c = ' ';
 116                                                 }
 117                                                 else
 118                                                 {
 119                                                         c = '#';
 120                                                 }
 121                                         }
 122                                 }
 123                                 o<<c;
 124                         }
 125                         o<<' ';
 126                 }
 127                 o<<std::endl;
 128         }
 129 }
 130
 131 void VoxelManipulator::addArea(VoxelArea area)
 132 {
 133         // Cancel if requested area has zero volume
 134         if(area.getExtent() == v3s16(0,0,0))
 135                 return;
 136
 137         // Cancel if m_area already contains the requested area
 138         if(m_area.contains(area))
 139                 return;
 140
 141         TimeTaker timer("addArea", &addarea_time);
 142
 143         // Calculate new area
 144         VoxelArea new_area;
 145         // New area is the requested area if m_area has zero volume
 146         if(m_area.getExtent() == v3s16(0,0,0))
 147         {
 148                 new_area = area;
 149         }
 150         // Else add requested area to m_area
 151         else
 152         {
 153                 new_area = m_area;
 154                 new_area.addArea(area);
 155         }
 156
 157         s32 new_size = new_area.getVolume();
 158
 159         /*dstream<<"adding area ";
 160         area.print(dstream);
 161         dstream<<", old area ";
 162         m_area.print(dstream);
 163         dstream<<", new area ";
 164         new_area.print(dstream);
 165         dstream<<", new_size="<<new_size;
 166         dstream<<std::endl;*/
 167
 168         // Allocate and clear new data
 169         MapNode *new_data = new MapNode[new_size];
 170         u8 *new_flags = new u8[new_size];
 171         for(s32 i=0; i<new_size; i++)
 172         {
 173                 new_flags[i] = VOXELFLAG_NOT_LOADED;
 174         }
 175
 176         // Copy old data
 177
 178         for(s32 z=m_area.MinEdge.Z; z<=m_area.MaxEdge.Z; z++)
 179         for(s32 y=m_area.MinEdge.Y; y<=m_area.MaxEdge.Y; y++)
 180         for(s32 x=m_area.MinEdge.X; x<=m_area.MaxEdge.X; x++)
 181         {
 182                 // If loaded, copy data and flags
 183                 if((m_flags[m_area.index(x,y,z)] & VOXELFLAG_NOT_LOADED) == false)
 184                 {
 185                         new_data[new_area.index(x,y,z)] = m_data[m_area.index(x,y,z)];
 186                         new_flags[new_area.index(x,y,z)] = m_flags[m_area.index(x,y,z)];
 187                 }
 188         }
 189
 190         // Replace area, data and flags
 191
 192         m_area = new_area;
 193
 194         MapNode *old_data = m_data;
 195         u8 *old_flags = m_flags;
 196
 197         /*dstream<<"old_data="<<(int)old_data<<", new_data="<<(int)new_data
 198         <<", old_flags="<<(int)m_flags<<", new_flags="<<(int)new_flags<<std::endl;*/
 199
 200         m_data = new_data;
 201         m_flags = new_flags;
 202
 203         if(old_data)
 204                 delete[] old_data;
 205         if(old_flags)
 206                 delete[] old_flags;
 207
 208         //dstream<<"addArea done"<<std::endl;
 209 }
 210
 211 void VoxelManipulator::copyFrom(MapNode *src, VoxelArea src_area,
 212                 v3s16 from_pos, v3s16 to_pos, v3s16 size)
 213 {
 214         for(s16 z=0; z<size.Z; z++)
 215         for(s16 y=0; y<size.Y; y++)
 216         {
 217                 s32 i_src = src_area.index(from_pos.X, from_pos.Y+y, from_pos.Z+z);
 218                 s32 i_local = m_area.index(to_pos.X, to_pos.Y+y, to_pos.Z+z);
 219                 memcpy(&m_data[i_local], &src[i_src], size.X*sizeof(MapNode));
 220                 memset(&m_flags[i_local], 0, size.X);
 221         }
 222 }
 223
 224
 225 void VoxelManipulator::clearFlag(u8 flags)
 226 {
 227         // 0-1ms on moderate area
 228         TimeTaker timer("clearFlag", &clearflag_time);
 229
 230         v3s16 s = m_area.getExtent();
 231
 232         /*dstream<<"clearFlag clearing area of size "
 233                         <<""<<s.X<<"x"<<s.Y<<"x"<<s.Z<<""
 234                         <<std::endl;*/
 235
 236         //s32 count = 0;
 237
 238         /*for(s32 z=m_area.MinEdge.Z; z<=m_area.MaxEdge.Z; z++)
 239         for(s32 y=m_area.MinEdge.Y; y<=m_area.MaxEdge.Y; y++)
 240         for(s32 x=m_area.MinEdge.X; x<=m_area.MaxEdge.X; x++)
 241         {
 242                 u8 f = m_flags[m_area.index(x,y,z)];
 243                 m_flags[m_area.index(x,y,z)] &= ~flags;
 244                 if(m_flags[m_area.index(x,y,z)] != f)
 245                         count++;
 246         }*/
 247
 248         s32 volume = m_area.getVolume();
 249         for(s32 i=0; i<volume; i++)
 250         {
 251                 m_flags[i] &= ~flags;
 252         }
 253
 254         /*s32 volume = m_area.getVolume();
 255         for(s32 i=0; i<volume; i++)
 256         {
 257                 u8 f = m_flags[i];
 258                 m_flags[i] &= ~flags;
 259                 if(m_flags[i] != f)
 260                         count++;
 261         }
 262
 263         dstream<<"clearFlag changed "<<count<<" flags out of "
 264                         <<volume<<" nodes"<<std::endl;*/
 265 }
 266
 267 void VoxelManipulator::unspreadLight(enum LightBank bank, v3s16 p, u8 oldlight,
 268                 core::map<v3s16, bool> & light_sources)
 269 {
 270         v3s16 dirs[6] = {
 271                 v3s16(0,0,1), // back
 272                 v3s16(0,1,0), // top
 273                 v3s16(1,0,0), // right
 274                 v3s16(0,0,-1), // front
 275                 v3s16(0,-1,0), // bottom
 276                 v3s16(-1,0,0), // left
 277         };
 278
 279         emerge(VoxelArea(p - v3s16(1,1,1), p + v3s16(1,1,1)));
 280
 281         // Loop through 6 neighbors
 282         for(u16 i=0; i<6; i++)
 283         {
 284                 // Get the position of the neighbor node
 285                 v3s16 n2pos = p + dirs[i];
 286
 287                 u32 n2i = m_area.index(n2pos);
 288
 289                 if(m_flags[n2i] & VOXELFLAG_INEXISTENT)
 290                         continue;
 291
 292                 MapNode &n2 = m_data[n2i];
 293
 294                 /*
 295                         If the neighbor is dimmer than what was specified
 296                         as oldlight (the light of the previous node)
 297                 */
 298                 if(n2.getLight(bank) < oldlight)
 299                 {
 300                         /*
 301                                 And the neighbor is transparent and it has some light
 302                         */
 303                         if(n2.light_propagates() && n2.getLight(bank) != 0)
 304                         {
 305                                 /*
 306                                         Set light to 0 and add to queue
 307                                 */
 308
 309                                 u8 current_light = n2.getLight(bank);
 310                                 n2.setLight(bank, 0);
 311
 312                                 unspreadLight(bank, n2pos, current_light, light_sources);
 313
 314                                 /*
 315                                         Remove from light_sources if it is there
 316                                         NOTE: This doesn't happen nearly at all
 317                                 */
 318                                 /*if(light_sources.find(n2pos))
 319                                 {
 320                                         std::cout<<"Removed from light_sources"<<std::endl;
 321                                         light_sources.remove(n2pos);
 322                                 }*/
 323                         }
 324                 }
 325                 else{
 326                         light_sources.insert(n2pos, true);
 327                 }
 328         }
 329 }
 330
 331 #if 1
 332 /*
 333         Goes recursively through the neighbours of the node.
 334
 335         Alters only transparent nodes.
 336
 337         If the lighting of the neighbour is lower than the lighting of
 338         the node was (before changing it to 0 at the step before), the
 339         lighting of the neighbour is set to 0 and then the same stuff
 340         repeats for the neighbour.
 341
 342         The ending nodes of the routine are stored in light_sources.
 343         This is useful when a light is removed. In such case, this
 344         routine can be called for the light node and then again for
 345         light_sources to re-light the area without the removed light.
 346
 347         values of from_nodes are lighting values.
 348 */
 349 void VoxelManipulator::unspreadLight(enum LightBank bank,
 350                 core::map<v3s16, u8> & from_nodes,
 351                 core::map<v3s16, bool> & light_sources)
 352 {
 353         if(from_nodes.size() == 0)
 354                 return;
 355
 356         core::map<v3s16, u8>::Iterator j;
 357         j = from_nodes.getIterator();
 358
 359         for(; j.atEnd() == false; j++)
 360         {
 361                 v3s16 pos = j.getNode()->getKey();
 362
 363                 //MapNode &n = m_data[m_area.index(pos)];
 364
 365                 u8 oldlight = j.getNode()->getValue();
 366
 367                 unspreadLight(bank, pos, oldlight, light_sources);
 368         }
 369 }
 370 #endif
 371
 372 #if 0
 373 /*
 374         Goes recursively through the neighbours of the node.
 375
 376         Alters only transparent nodes.
 377
 378         If the lighting of the neighbour is lower than the lighting of
 379         the node was (before changing it to 0 at the step before), the
 380         lighting of the neighbour is set to 0 and then the same stuff
 381         repeats for the neighbour.
 382
 383         The ending nodes of the routine are stored in light_sources.
 384         This is useful when a light is removed. In such case, this
 385         routine can be called for the light node and then again for
 386         light_sources to re-light the area without the removed light.
 387
 388         values of from_nodes are lighting values.
 389 */
 390 void VoxelManipulator::unspreadLight(enum LightBank bank,
 391                 core::map<v3s16, u8> & from_nodes,
 392                 core::map<v3s16, bool> & light_sources)
 393 {
 394         v3s16 dirs[6] = {
 395                 v3s16(0,0,1), // back
 396                 v3s16(0,1,0), // top
 397                 v3s16(1,0,0), // right
 398                 v3s16(0,0,-1), // front
 399                 v3s16(0,-1,0), // bottom
 400                 v3s16(-1,0,0), // left
 401         };
 402
 403         if(from_nodes.size() == 0)
 404                 return;
 405
 406         core::map<v3s16, u8> unlighted_nodes;
 407         core::map<v3s16, u8>::Iterator j;
 408         j = from_nodes.getIterator();
 409
 410         for(; j.atEnd() == false; j++)
 411         {
 412                 v3s16 pos = j.getNode()->getKey();
 413
 414                 emerge(VoxelArea(pos - v3s16(1,1,1), pos + v3s16(1,1,1)));
 415
 416                 //MapNode &n = m_data[m_area.index(pos)];
 417
 418                 u8 oldlight = j.getNode()->getValue();
 419
 420                 // Loop through 6 neighbors
 421                 for(u16 i=0; i<6; i++)
 422                 {
 423                         // Get the position of the neighbor node
 424                         v3s16 n2pos = pos + dirs[i];
 425
 426                         u32 n2i = m_area.index(n2pos);
 427
 428                         if(m_flags[n2i] & VOXELFLAG_INEXISTENT)
 429                                 continue;
 430
 431                         MapNode &n2 = m_data[n2i];
 432
 433                         /*
 434                                 If the neighbor is dimmer than what was specified
 435                                 as oldlight (the light of the previous node)
 436                         */
 437                         if(n2.getLight(bank) < oldlight)
 438                         {
 439                                 /*
 440                                         And the neighbor is transparent and it has some light
 441                                 */
 442                                 if(n2.light_propagates() && n2.getLight(bank) != 0)
 443                                 {
 444                                         /*
 445                                                 Set light to 0 and add to queue
 446                                         */
 447
 448                                         u8 current_light = n2.getLight(bank);
 449                                         n2.setLight(bank, 0);
 450
 451                                         unlighted_nodes.insert(n2pos, current_light);
 452
 453                                         /*
 454                                                 Remove from light_sources if it is there
 455                                                 NOTE: This doesn't happen nearly at all
 456                                         */
 457                                         /*if(light_sources.find(n2pos))
 458                                         {
 459                                                 std::cout<<"Removed from light_sources"<<std::endl;
 460                                                 light_sources.remove(n2pos);
 461                                         }*/
 462                                 }
 463                         }
 464                         else{
 465                                 light_sources.insert(n2pos, true);
 466                         }
 467                 }
 468         }
 469
 470         /*dstream<<"unspreadLight(): Changed block "
 471                         <<blockchangecount<<" times"
 472                         <<" for "<<from_nodes.size()<<" nodes"
 473                         <<std::endl;*/
 474
 475         if(unlighted_nodes.size() > 0)
 476                 unspreadLight(bank, unlighted_nodes, light_sources);
 477 }
 478 #endif
 479
 480 void VoxelManipulator::spreadLight(enum LightBank bank, v3s16 p)
 481 {
 482         const v3s16 dirs[6] = {
 483                 v3s16(0,0,1), // back
 484                 v3s16(0,1,0), // top
 485                 v3s16(1,0,0), // right
 486                 v3s16(0,0,-1), // front
 487                 v3s16(0,-1,0), // bottom
 488                 v3s16(-1,0,0), // left
 489         };
 490
 491         emerge(VoxelArea(p - v3s16(1,1,1), p + v3s16(1,1,1)));
 492
 493         u32 i = m_area.index(p);
 494
 495         if(m_flags[i] & VOXELFLAG_INEXISTENT)
 496                 return;
 497
 498         MapNode &n = m_data[i];
 499
 500         u8 oldlight = n.getLight(bank);
 501         u8 newlight = diminish_light(oldlight);
 502
 503         // Loop through 6 neighbors
 504         for(u16 i=0; i<6; i++)
 505         {
 506                 // Get the position of the neighbor node
 507                 v3s16 n2pos = p + dirs[i];
 508
 509                 u32 n2i = m_area.index(n2pos);
 510
 511                 if(m_flags[n2i] & VOXELFLAG_INEXISTENT)
 512                         continue;
 513
 514                 MapNode &n2 = m_data[n2i];
 515
 516                 /*
 517                         If the neighbor is brighter than the current node,
 518                         add to list (it will light up this node on its turn)
 519                 */
 520                 if(n2.getLight(bank) > undiminish_light(oldlight))
 521                 {
 522                         spreadLight(bank, n2pos);
 523                 }
 524                 /*
 525                         If the neighbor is dimmer than how much light this node
 526                         would spread on it, add to list
 527                 */
 528                 if(n2.getLight(bank) < newlight)
 529                 {
 530                         if(n2.light_propagates())
 531                         {
 532                                 n2.setLight(bank, newlight);
 533                                 spreadLight(bank, n2pos);
 534                         }
 535                 }
 536         }
 537 }
 538
 539 #if 1
 540 /*
 541         Lights neighbors of from_nodes, collects all them and then
 542         goes on recursively.
 543 */
 544 void VoxelManipulator::spreadLight(enum LightBank bank,
 545                 core::map<v3s16, bool> & from_nodes)
 546 {
 547         if(from_nodes.size() == 0)
 548                 return;
 549
 550         core::map<v3s16, bool> lighted_nodes;
 551         core::map<v3s16, bool>::Iterator j;
 552         j = from_nodes.getIterator();
 553
 554         for(; j.atEnd() == false; j++)
 555         {
 556                 v3s16 pos = j.getNode()->getKey();
 557
 558                 spreadLight(bank, pos);
 559         }
 560 }
 561 #endif
 562
 563 #if 0
 564 /*
 565         Lights neighbors of from_nodes, collects all them and then
 566         goes on recursively.
 567 */
 568 void VoxelManipulator::spreadLight(enum LightBank bank,
 569                 core::map<v3s16, bool> & from_nodes)
 570 {
 571         const v3s16 dirs[6] = {
 572                 v3s16(0,0,1), // back
 573                 v3s16(0,1,0), // top
 574                 v3s16(1,0,0), // right
 575                 v3s16(0,0,-1), // front
 576                 v3s16(0,-1,0), // bottom
 577                 v3s16(-1,0,0), // left
 578         };
 579
 580         if(from_nodes.size() == 0)
 581                 return;
 582
 583         core::map<v3s16, bool> lighted_nodes;
 584         core::map<v3s16, bool>::Iterator j;
 585         j = from_nodes.getIterator();
 586
 587         for(; j.atEnd() == false; j++)
 588         {
 589                 v3s16 pos = j.getNode()->getKey();
 590
 591                 emerge(VoxelArea(pos - v3s16(1,1,1), pos + v3s16(1,1,1)));
 592
 593                 u32 i = m_area.index(pos);
 594
 595                 if(m_flags[i] & VOXELFLAG_INEXISTENT)
 596                         continue;
 597
 598                 MapNode &n = m_data[i];
 599
 600                 u8 oldlight = n.getLight(bank);
 601                 u8 newlight = diminish_light(oldlight);
 602
 603                 // Loop through 6 neighbors
 604                 for(u16 i=0; i<6; i++)
 605                 {
 606                         // Get the position of the neighbor node
 607                         v3s16 n2pos = pos + dirs[i];
 608
 609                         try
 610                         {
 611                                 u32 n2i = m_area.index(n2pos);
 612
 613                                 if(m_flags[n2i] & VOXELFLAG_INEXISTENT)
 614                                         continue;
 615
 616                                 MapNode &n2 = m_data[n2i];
 617
 618                                 /*
 619                                         If the neighbor is brighter than the current node,
 620                                         add to list (it will light up this node on its turn)
 621                                 */
 622                                 if(n2.getLight(bank) > undiminish_light(oldlight))
 623                                 {
 624                                         lighted_nodes.insert(n2pos, true);
 625                                 }
 626                                 /*
 627                                         If the neighbor is dimmer than how much light this node
 628                                         would spread on it, add to list
 629                                 */
 630                                 if(n2.getLight(bank) < newlight)
 631                                 {
 632                                         if(n2.light_propagates())
 633                                         {
 634                                                 n2.setLight(bank, newlight);
 635                                                 lighted_nodes.insert(n2pos, true);
 636                                         }
 637                                 }
 638                         }
 639                         catch(InvalidPositionException &e)
 640                         {
 641                                 continue;
 642                         }
 643                 }
 644         }
 645
 646         /*dstream<<"spreadLight(): Changed block "
 647                         <<blockchangecount<<" times"
 648                         <<" for "<<from_nodes.size()<<" nodes"
 649                         <<std::endl;*/
 650
 651         if(lighted_nodes.size() > 0)
 652                 spreadLight(bank, lighted_nodes);
 653 }
 654 #endif
 655
 656 //END