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(const 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         VoxelArea voxel_area(p - v3s16(1,1,1), p + v3s16(1,1,1));
 314         addArea(voxel_area);
 315
 316         // Loop through 6 neighbors
 317         for(u16 i=0; i<6; i++)
 318         {
 319                 // Get the position of the neighbor node
 320                 v3s16 n2pos = p + dirs[i];
 321
 322                 u32 n2i = m_area.index(n2pos);
 323
 324                 if(m_flags[n2i] & VOXELFLAG_NO_DATA)
 325                         continue;
 326
 327                 MapNode &n2 = m_data[n2i];
 328
 329                 /*
 330                         If the neighbor is dimmer than what was specified
 331                         as oldlight (the light of the previous node)
 332                 */
 333                 u8 light2 = n2.getLight(bank, nodemgr);
 334                 if(light2 < oldlight)
 335                 {
 336                         /*
 337                                 And the neighbor is transparent and it has some light
 338                         */
 339                         if(nodemgr->get(n2).light_propagates && light2 != 0)
 340                         {
 341                                 /*
 342                                         Set light to 0 and add to queue
 343                                 */
 344
 345                                 n2.setLight(bank, 0, nodemgr);
 346
 347                                 unspreadLight(bank, n2pos, light2, light_sources, nodemgr);
 348
 349                                 /*
 350                                         Remove from light_sources if it is there
 351                                         NOTE: This doesn't happen nearly at all
 352                                 */
 353                                 /*if(light_sources.find(n2pos))
 354                                 {
 355                                         std::cout<<"Removed from light_sources"<<std::endl;
 356                                         light_sources.remove(n2pos);
 357                                 }*/
 358                         }
 359                 }
 360                 else{
 361                         light_sources.insert(n2pos);
 362                 }
 363         }
 364 }
 365
 366 #if 1
 367 /*
 368         Goes recursively through the neighbours of the node.
 369
 370         Alters only transparent nodes.
 371
 372         If the lighting of the neighbour is lower than the lighting of
 373         the node was (before changing it to 0 at the step before), the
 374         lighting of the neighbour is set to 0 and then the same stuff
 375         repeats for the neighbour.
 376
 377         The ending nodes of the routine are stored in light_sources.
 378         This is useful when a light is removed. In such case, this
 379         routine can be called for the light node and then again for
 380         light_sources to re-light the area without the removed light.
 381
 382         values of from_nodes are lighting values.
 383 */
 384 void VoxelManipulator::unspreadLight(enum LightBank bank,
 385                 std::map<v3s16, u8> & from_nodes,
 386                 std::set<v3s16> & light_sources, INodeDefManager *nodemgr)
 387 {
 388         if(from_nodes.size() == 0)
 389                 return;
 390
 391         for(std::map<v3s16, u8>::iterator j = from_nodes.begin();
 392                 j != from_nodes.end(); ++j)
 393         {
 394                 unspreadLight(bank, j->first, j->second, light_sources, nodemgr);
 395         }
 396 }
 397 #endif
 398
 399 #if 0
 400 /*
 401         Goes recursively through the neighbours of the node.
 402
 403         Alters only transparent nodes.
 404
 405         If the lighting of the neighbour is lower than the lighting of
 406         the node was (before changing it to 0 at the step before), the
 407         lighting of the neighbour is set to 0 and then the same stuff
 408         repeats for the neighbour.
 409
 410         The ending nodes of the routine are stored in light_sources.
 411         This is useful when a light is removed. In such case, this
 412         routine can be called for the light node and then again for
 413         light_sources to re-light the area without the removed light.
 414
 415         values of from_nodes are lighting values.
 416 */
 417 void VoxelManipulator::unspreadLight(enum LightBank bank,
 418                 core::map<v3s16, u8> & from_nodes,
 419                 core::map<v3s16, bool> & light_sources)
 420 {
 421         v3s16 dirs[6] = {
 422                 v3s16(0,0,1), // back
 423                 v3s16(0,1,0), // top
 424                 v3s16(1,0,0), // right
 425                 v3s16(0,0,-1), // front
 426                 v3s16(0,-1,0), // bottom
 427                 v3s16(-1,0,0), // left
 428         };
 429
 430         if(from_nodes.size() == 0)
 431                 return;
 432
 433         core::map<v3s16, u8> unlighted_nodes;
 434         core::map<v3s16, u8>::Iterator j;
 435         j = from_nodes.getIterator();
 436
 437         for(; j.atEnd() == false; j++)
 438         {
 439                 v3s16 pos = j.getNode()->getKey();
 440
 441                 addArea(VoxelArea(pos - v3s16(1,1,1), pos + v3s16(1,1,1)));
 442
 443                 //MapNode &n = m_data[m_area.index(pos)];
 444
 445                 u8 oldlight = j.getNode()->getValue();
 446
 447                 // Loop through 6 neighbors
 448                 for(u16 i=0; i<6; i++)
 449                 {
 450                         // Get the position of the neighbor node
 451                         v3s16 n2pos = pos + dirs[i];
 452
 453                         u32 n2i = m_area.index(n2pos);
 454
 455                         if(m_flags[n2i] & VOXELFLAG_NO_DATA)
 456                                 continue;
 457
 458                         MapNode &n2 = m_data[n2i];
 459
 460                         /*
 461                                 If the neighbor is dimmer than what was specified
 462                                 as oldlight (the light of the previous node)
 463                         */
 464                         if(n2.getLight(bank, nodemgr) < oldlight)
 465                         {
 466                                 /*
 467                                         And the neighbor is transparent and it has some light
 468                                 */
 469                                 if(nodemgr->get(n2).light_propagates && n2.getLight(bank, nodemgr) != 0)
 470                                 {
 471                                         /*
 472                                                 Set light to 0 and add to queue
 473                                         */
 474
 475                                         u8 current_light = n2.getLight(bank, nodemgr);
 476                                         n2.setLight(bank, 0);
 477
 478                                         unlighted_nodes.insert(n2pos, current_light);
 479
 480                                         /*
 481                                                 Remove from light_sources if it is there
 482                                                 NOTE: This doesn't happen nearly at all
 483                                         */
 484                                         /*if(light_sources.find(n2pos))
 485                                         {
 486                                                 std::cout<<"Removed from light_sources"<<std::endl;
 487                                                 light_sources.remove(n2pos);
 488                                         }*/
 489                                 }
 490                         }
 491                         else{
 492                                 light_sources.insert(n2pos, true);
 493                         }
 494                 }
 495         }
 496
 497         /*dstream<<"unspreadLight(): Changed block "
 498                         <<blockchangecount<<" times"
 499                         <<" for "<<from_nodes.size()<<" nodes"
 500                         <<std::endl;*/
 501
 502         if(unlighted_nodes.size() > 0)
 503                 unspreadLight(bank, unlighted_nodes, light_sources);
 504 }
 505 #endif
 506
 507 void VoxelManipulator::spreadLight(enum LightBank bank, v3s16 p,
 508                 INodeDefManager *nodemgr)
 509 {
 510         const v3s16 dirs[6] = {
 511                 v3s16(0,0,1), // back
 512                 v3s16(0,1,0), // top
 513                 v3s16(1,0,0), // right
 514                 v3s16(0,0,-1), // front
 515                 v3s16(0,-1,0), // bottom
 516                 v3s16(-1,0,0), // left
 517         };
 518
 519         VoxelArea voxel_area(p - v3s16(1,1,1), p + v3s16(1,1,1));
 520         addArea(voxel_area);
 521
 522         u32 i = m_area.index(p);
 523
 524         if(m_flags[i] & VOXELFLAG_NO_DATA)
 525                 return;
 526
 527         MapNode &n = m_data[i];
 528
 529         u8 oldlight = n.getLight(bank, nodemgr);
 530         u8 newlight = diminish_light(oldlight);
 531
 532         // Loop through 6 neighbors
 533         for(u16 i=0; i<6; i++)
 534         {
 535                 // Get the position of the neighbor node
 536                 v3s16 n2pos = p + dirs[i];
 537
 538                 u32 n2i = m_area.index(n2pos);
 539
 540                 if(m_flags[n2i] & VOXELFLAG_NO_DATA)
 541                         continue;
 542
 543                 MapNode &n2 = m_data[n2i];
 544
 545                 u8 light2 = n2.getLight(bank, nodemgr);
 546
 547                 /*
 548                         If the neighbor is brighter than the current node,
 549                         add to list (it will light up this node on its turn)
 550                 */
 551                 if(light2 > undiminish_light(oldlight))
 552                 {
 553                         spreadLight(bank, n2pos, nodemgr);
 554                 }
 555                 /*
 556                         If the neighbor is dimmer than how much light this node
 557                         would spread on it, add to list
 558                 */
 559                 if(light2 < newlight)
 560                 {
 561                         if(nodemgr->get(n2).light_propagates)
 562                         {
 563                                 n2.setLight(bank, newlight, nodemgr);
 564                                 spreadLight(bank, n2pos, nodemgr);
 565                         }
 566                 }
 567         }
 568 }
 569
 570 #if 0
 571 /*
 572         Lights neighbors of from_nodes, collects all them and then
 573         goes on recursively.
 574
 575         NOTE: This is faster on small areas but will overflow the
 576               stack on large areas. Thus it is not used.
 577 */
 578 void VoxelManipulator::spreadLight(enum LightBank bank,
 579                 core::map<v3s16, bool> & from_nodes)
 580 {
 581         if(from_nodes.size() == 0)
 582                 return;
 583
 584         core::map<v3s16, bool> lighted_nodes;
 585         core::map<v3s16, bool>::Iterator j;
 586         j = from_nodes.getIterator();
 587
 588         for(; j.atEnd() == false; j++)
 589         {
 590                 v3s16 pos = j.getNode()->getKey();
 591
 592                 spreadLight(bank, pos);
 593         }
 594 }
 595 #endif
 596
 597 #if 1
 598 /*
 599         Lights neighbors of from_nodes, collects all them and then
 600         goes on recursively.
 601 */
 602 void VoxelManipulator::spreadLight(enum LightBank bank,
 603                 std::set<v3s16> & from_nodes, INodeDefManager *nodemgr)
 604 {
 605         const v3s16 dirs[6] = {
 606                 v3s16(0,0,1), // back
 607                 v3s16(0,1,0), // top
 608                 v3s16(1,0,0), // right
 609                 v3s16(0,0,-1), // front
 610                 v3s16(0,-1,0), // bottom
 611                 v3s16(-1,0,0), // left
 612         };
 613
 614         if(from_nodes.size() == 0)
 615                 return;
 616
 617         std::set<v3s16> lighted_nodes;
 618
 619         for(std::set<v3s16>::iterator j = from_nodes.begin();
 620                 j != from_nodes.end(); ++j)
 621         {
 622                 v3s16 pos = *j;
 623
 624                 VoxelArea voxel_area(pos - v3s16(1,1,1), pos + v3s16(1,1,1));
 625                 addArea(voxel_area);
 626
 627                 u32 i = m_area.index(pos);
 628
 629                 if(m_flags[i] & VOXELFLAG_NO_DATA)
 630                         continue;
 631
 632                 MapNode &n = m_data[i];
 633
 634                 u8 oldlight = n.getLight(bank, nodemgr);
 635                 u8 newlight = diminish_light(oldlight);
 636
 637                 // Loop through 6 neighbors
 638                 for(u16 i=0; i<6; i++)
 639                 {
 640                         // Get the position of the neighbor node
 641                         v3s16 n2pos = pos + dirs[i];
 642
 643                         try
 644                         {
 645                                 u32 n2i = m_area.index(n2pos);
 646
 647                                 if(m_flags[n2i] & VOXELFLAG_NO_DATA)
 648                                         continue;
 649
 650                                 MapNode &n2 = m_data[n2i];
 651
 652                                 u8 light2 = n2.getLight(bank, nodemgr);
 653
 654                                 /*
 655                                         If the neighbor is brighter than the current node,
 656                                         add to list (it will light up this node on its turn)
 657                                 */
 658                                 if(light2 > undiminish_light(oldlight))
 659                                 {
 660                                         lighted_nodes.insert(n2pos);
 661                                 }
 662                                 /*
 663                                         If the neighbor is dimmer than how much light this node
 664                                         would spread on it, add to list
 665                                 */
 666                                 if(light2 < newlight)
 667                                 {
 668                                         if(nodemgr->get(n2).light_propagates)
 669                                         {
 670                                                 n2.setLight(bank, newlight, nodemgr);
 671                                                 lighted_nodes.insert(n2pos);
 672                                         }
 673                                 }
 674                         }
 675                         catch(InvalidPositionException &e)
 676                         {
 677                                 continue;
 678                         }
 679                 }
 680         }
 681
 682         /*dstream<<"spreadLight(): Changed block "
 683                         <<blockchangecount<<" times"
 684                         <<" for "<<from_nodes.size()<<" nodes"
 685                         <<std::endl;*/
 686
 687         if(lighted_nodes.size() > 0)
 688                 spreadLight(bank, lighted_nodes, nodemgr);
 689 }
 690 #endif
 691
 692 //END