src/voxel.cpp

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