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                 u8 light2 = n2.getLight(bank, nodemgr);
 314                 if(light2 < oldlight)
 315                 {
 316                         /*
 317                                 And the neighbor is transparent and it has some light
 318                         */
 319                         if(nodemgr->get(n2).light_propagates && light2 != 0)
 320                         {
 321                                 /*
 322                                         Set light to 0 and add to queue
 323                                 */
 324
 325                                 n2.setLight(bank, 0, nodemgr);
 326
 327                                 unspreadLight(bank, n2pos, light2, 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                 u8 light2 = n2.getLight(bank, nodemgr);
 533
 534                 /*
 535                         If the neighbor is brighter than the current node,
 536                         add to list (it will light up this node on its turn)
 537                 */
 538                 if(light2 > undiminish_light(oldlight))
 539                 {
 540                         spreadLight(bank, n2pos, nodemgr);
 541                 }
 542                 /*
 543                         If the neighbor is dimmer than how much light this node
 544                         would spread on it, add to list
 545                 */
 546                 if(light2 < newlight)
 547                 {
 548                         if(nodemgr->get(n2).light_propagates)
 549                         {
 550                                 n2.setLight(bank, newlight, nodemgr);
 551                                 spreadLight(bank, n2pos, nodemgr);
 552                         }
 553                 }
 554         }
 555 }
 556
 557 #if 0
 558 /*
 559         Lights neighbors of from_nodes, collects all them and then
 560         goes on recursively.
 561
 562         NOTE: This is faster on small areas but will overflow the
 563               stack on large areas. Thus it is not used.
 564 */
 565 void VoxelManipulator::spreadLight(enum LightBank bank,
 566                 core::map<v3s16, bool> & from_nodes)
 567 {
 568         if(from_nodes.size() == 0)
 569                 return;
 570
 571         core::map<v3s16, bool> lighted_nodes;
 572         core::map<v3s16, bool>::Iterator j;
 573         j = from_nodes.getIterator();
 574
 575         for(; j.atEnd() == false; j++)
 576         {
 577                 v3s16 pos = j.getNode()->getKey();
 578
 579                 spreadLight(bank, pos);
 580         }
 581 }
 582 #endif
 583
 584 #if 1
 585 /*
 586         Lights neighbors of from_nodes, collects all them and then
 587         goes on recursively.
 588 */
 589 void VoxelManipulator::spreadLight(enum LightBank bank,
 590                 core::map<v3s16, bool> & from_nodes, INodeDefManager *nodemgr)
 591 {
 592         const v3s16 dirs[6] = {
 593                 v3s16(0,0,1), // back
 594                 v3s16(0,1,0), // top
 595                 v3s16(1,0,0), // right
 596                 v3s16(0,0,-1), // front
 597                 v3s16(0,-1,0), // bottom
 598                 v3s16(-1,0,0), // left
 599         };
 600
 601         if(from_nodes.size() == 0)
 602                 return;
 603
 604         core::map<v3s16, bool> lighted_nodes;
 605         core::map<v3s16, bool>::Iterator j;
 606         j = from_nodes.getIterator();
 607
 608         for(; j.atEnd() == false; j++)
 609         {
 610                 v3s16 pos = j.getNode()->getKey();
 611
 612                 emerge(VoxelArea(pos - v3s16(1,1,1), pos + v3s16(1,1,1)));
 613
 614                 u32 i = m_area.index(pos);
 615
 616                 if(m_flags[i] & VOXELFLAG_INEXISTENT)
 617                         continue;
 618
 619                 MapNode &n = m_data[i];
 620
 621                 u8 oldlight = n.getLight(bank, nodemgr);
 622                 u8 newlight = diminish_light(oldlight);
 623
 624                 // Loop through 6 neighbors
 625                 for(u16 i=0; i<6; i++)
 626                 {
 627                         // Get the position of the neighbor node
 628                         v3s16 n2pos = pos + dirs[i];
 629
 630                         try
 631                         {
 632                                 u32 n2i = m_area.index(n2pos);
 633
 634                                 if(m_flags[n2i] & VOXELFLAG_INEXISTENT)
 635                                         continue;
 636
 637                                 MapNode &n2 = m_data[n2i];
 638
 639                                 u8 light2 = n2.getLight(bank, nodemgr);
 640
 641                                 /*
 642                                         If the neighbor is brighter than the current node,
 643                                         add to list (it will light up this node on its turn)
 644                                 */
 645                                 if(light2 > undiminish_light(oldlight))
 646                                 {
 647                                         lighted_nodes.insert(n2pos, true);
 648                                 }
 649                                 /*
 650                                         If the neighbor is dimmer than how much light this node
 651                                         would spread on it, add to list
 652                                 */
 653                                 if(light2 < newlight)
 654                                 {
 655                                         if(nodemgr->get(n2).light_propagates)
 656                                         {
 657                                                 n2.setLight(bank, newlight, nodemgr);
 658                                                 lighted_nodes.insert(n2pos, true);
 659                                         }
 660                                 }
 661                         }
 662                         catch(InvalidPositionException &e)
 663                         {
 664                                 continue;
 665                         }
 666                 }
 667         }
 668
 669         /*dstream<<"spreadLight(): Changed block "
 670                         <<blockchangecount<<" times"
 671                         <<" for "<<from_nodes.size()<<" nodes"
 672                         <<std::endl;*/
 673
 674         if(lighted_nodes.size() > 0)
 675                 spreadLight(bank, lighted_nodes, nodemgr);
 676 }
 677 #endif
 678
 679 //END