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