src/voxel.cpp

   1 /*
   2 Minetest-c55
   3 Copyright (C) 2010 celeron55, Perttu Ahola <celeron55@gmail.com>
   4
   5 This program is free software; you can redistribute it and/or modify
   6 it under the terms of the GNU General Public License as published by
   7 the Free Software Foundation; either version 2 of the License, or
   8 (at your option) any later version.
   9
  10 This program is distributed in the hope that it will be useful,
  11 but WITHOUT ANY WARRANTY; without even the implied warranty of
  12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13 GNU General Public License for more details.
  14
  15 You should have received a copy of the GNU General Public License along
  16 with this program; if not, write to the Free Software Foundation, Inc.,
  17 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  18 */
  19
  20 #include "voxel.h"
  21 #include "map.h"
  22
  23 // For TimeTaker
  24 #include "utility.h"
  25 #include "gettime.h"
  26
  27 /*
  28         Debug stuff
  29 */
  30 u32 addarea_time = 0;
  31 u32 emerge_time = 0;
  32 u32 emerge_load_time = 0;
  33 u32 clearflag_time = 0;
  34 //u32 getwaterpressure_time = 0;
  35 //u32 spreadwaterpressure_time = 0;
  36 u32 updateareawaterpressure_time = 0;
  37 u32 flowwater_pre_time = 0;
  38
  39
  40 VoxelManipulator::VoxelManipulator():
  41         m_data(NULL),
  42         m_flags(NULL)
  43 {
  44         m_disable_water_climb = false;
  45 }
  46
  47 VoxelManipulator::~VoxelManipulator()
  48 {
  49         clear();
  50         if(m_data)
  51                 delete[] m_data;
  52         if(m_flags)
  53                 delete[] m_flags;
  54 }
  55
  56 void VoxelManipulator::clear()
  57 {
  58         // Reset area to volume=0
  59         m_area = VoxelArea();
  60         if(m_data)
  61                 delete[] m_data;
  62         m_data = NULL;
  63         if(m_flags)
  64                 delete[] m_flags;
  65         m_flags = NULL;
  66 }
  67
  68 void VoxelManipulator::print(std::ostream &o, VoxelPrintMode mode)
  69 {
  70         v3s16 em = m_area.getExtent();
  71         v3s16 of = m_area.MinEdge;
  72         o<<"size: "<<em.X<<"x"<<em.Y<<"x"<<em.Z
  73          <<" offset: ("<<of.X<<","<<of.Y<<","<<of.Z<<")"<<std::endl;
  74
  75         for(s32 y=m_area.MaxEdge.Y; y>=m_area.MinEdge.Y; y--)
  76         {
  77                 if(em.X >= 3 && em.Y >= 3)
  78                 {
  79                         if     (y==m_area.MinEdge.Y+2) o<<"^     ";
  80                         else if(y==m_area.MinEdge.Y+1) o<<"|     ";
  81                         else if(y==m_area.MinEdge.Y+0) o<<"y x-> ";
  82                         else                           o<<"      ";
  83                 }
  84
  85                 for(s32 z=m_area.MinEdge.Z; z<=m_area.MaxEdge.Z; z++)
  86                 {
  87                         for(s32 x=m_area.MinEdge.X; x<=m_area.MaxEdge.X; x++)
  88                         {
  89                                 u8 f = m_flags[m_area.index(x,y,z)];
  90                                 char c;
  91                                 if(f & VOXELFLAG_NOT_LOADED)
  92                                         c = 'N';
  93                                 else if(f & VOXELFLAG_INEXISTENT)
  94                                         c = 'I';
  95                                 else
  96                                 {
  97                                         c = 'X';
  98                                         u8 m = m_data[m_area.index(x,y,z)].d;
  99                                         u8 pr = m_data[m_area.index(x,y,z)].param2;
 100                                         if(mode == VOXELPRINT_MATERIAL)
 101                                         {
 102                                                 if(m <= 9)
 103                                                         c = m + '0';
 104                                         }
 105                                         else if(mode == VOXELPRINT_WATERPRESSURE)
 106                                         {
 107                                                 if(m == CONTENT_WATER)
 108                                                 {
 109                                                         c = 'w';
 110                                                         if(pr <= 9)
 111                                                                 c = pr + '0';
 112                                                 }
 113                                                 else if(liquid_replaces_content(m))
 114                                                 {
 115                                                         c = ' ';
 116                                                 }
 117                                                 else
 118                                                 {
 119                                                         c = '#';
 120                                                 }
 121                                         }
 122                                 }
 123                                 o<<c;
 124                         }
 125                         o<<' ';
 126                 }
 127                 o<<std::endl;
 128         }
 129 }
 130
 131 void VoxelManipulator::addArea(VoxelArea area)
 132 {
 133         // Cancel if requested area has zero volume
 134         if(area.getExtent() == v3s16(0,0,0))
 135                 return;
 136
 137         // Cancel if m_area already contains the requested area
 138         if(m_area.contains(area))
 139                 return;
 140
 141         TimeTaker timer("addArea", &addarea_time);
 142
 143         // Calculate new area
 144         VoxelArea new_area;
 145         // New area is the requested area if m_area has zero volume
 146         if(m_area.getExtent() == v3s16(0,0,0))
 147         {
 148                 new_area = area;
 149         }
 150         // Else add requested area to m_area
 151         else
 152         {
 153                 new_area = m_area;
 154                 new_area.addArea(area);
 155         }
 156
 157         s32 new_size = new_area.getVolume();
 158
 159         /*dstream<<"adding area ";
 160         area.print(dstream);
 161         dstream<<", old area ";
 162         m_area.print(dstream);
 163         dstream<<", new area ";
 164         new_area.print(dstream);
 165         dstream<<", new_size="<<new_size;
 166         dstream<<std::endl;*/
 167
 168         // Allocate and clear new data
 169         MapNode *new_data = new MapNode[new_size];
 170         u8 *new_flags = new u8[new_size];
 171         for(s32 i=0; i<new_size; i++)
 172         {
 173                 new_flags[i] = VOXELFLAG_NOT_LOADED;
 174         }
 175
 176         // Copy old data
 177
 178         for(s32 z=m_area.MinEdge.Z; z<=m_area.MaxEdge.Z; z++)
 179         for(s32 y=m_area.MinEdge.Y; y<=m_area.MaxEdge.Y; y++)
 180         for(s32 x=m_area.MinEdge.X; x<=m_area.MaxEdge.X; x++)
 181         {
 182                 // If loaded, copy data and flags
 183                 if((m_flags[m_area.index(x,y,z)] & VOXELFLAG_NOT_LOADED) == false)
 184                 {
 185                         new_data[new_area.index(x,y,z)] = m_data[m_area.index(x,y,z)];
 186                         new_flags[new_area.index(x,y,z)] = m_flags[m_area.index(x,y,z)];
 187                 }
 188         }
 189
 190         // Replace area, data and flags
 191
 192         m_area = new_area;
 193
 194         MapNode *old_data = m_data;
 195         u8 *old_flags = m_flags;
 196
 197         /*dstream<<"old_data="<<(int)old_data<<", new_data="<<(int)new_data
 198         <<", old_flags="<<(int)m_flags<<", new_flags="<<(int)new_flags<<std::endl;*/
 199
 200         m_data = new_data;
 201         m_flags = new_flags;
 202
 203         if(old_data)
 204                 delete[] old_data;
 205         if(old_flags)
 206                 delete[] old_flags;
 207
 208         //dstream<<"addArea done"<<std::endl;
 209 }
 210
 211 void VoxelManipulator::copyFrom(MapNode *src, VoxelArea src_area,
 212                 v3s16 from_pos, v3s16 to_pos, v3s16 size)
 213 {
 214         for(s16 z=0; z<size.Z; z++)
 215         for(s16 y=0; y<size.Y; y++)
 216         {
 217                 s32 i_src = src_area.index(from_pos.X, from_pos.Y+y, from_pos.Z+z);
 218                 s32 i_local = m_area.index(to_pos.X, to_pos.Y+y, to_pos.Z+z);
 219                 memcpy(&m_data[i_local], &src[i_src], size.X*sizeof(MapNode));
 220                 memset(&m_flags[i_local], 0, size.X);
 221         }
 222 }
 223
 224
 225 void VoxelManipulator::clearFlag(u8 flags)
 226 {
 227         // 0-1ms on moderate area
 228         TimeTaker timer("clearFlag", &clearflag_time);
 229
 230         v3s16 s = m_area.getExtent();
 231
 232         /*dstream<<"clearFlag clearing area of size "
 233                         <<""<<s.X<<"x"<<s.Y<<"x"<<s.Z<<""
 234                         <<std::endl;*/
 235
 236         //s32 count = 0;
 237
 238         /*for(s32 z=m_area.MinEdge.Z; z<=m_area.MaxEdge.Z; z++)
 239         for(s32 y=m_area.MinEdge.Y; y<=m_area.MaxEdge.Y; y++)
 240         for(s32 x=m_area.MinEdge.X; x<=m_area.MaxEdge.X; x++)
 241         {
 242                 u8 f = m_flags[m_area.index(x,y,z)];
 243                 m_flags[m_area.index(x,y,z)] &= ~flags;
 244                 if(m_flags[m_area.index(x,y,z)] != f)
 245                         count++;
 246         }*/
 247
 248         s32 volume = m_area.getVolume();
 249         for(s32 i=0; i<volume; i++)
 250         {
 251                 m_flags[i] &= ~flags;
 252         }
 253
 254         /*s32 volume = m_area.getVolume();
 255         for(s32 i=0; i<volume; i++)
 256         {
 257                 u8 f = m_flags[i];
 258                 m_flags[i] &= ~flags;
 259                 if(m_flags[i] != f)
 260                         count++;
 261         }
 262
 263         dstream<<"clearFlag changed "<<count<<" flags out of "
 264                         <<volume<<" nodes"<<std::endl;*/
 265 }
 266
 267 void VoxelManipulator::unspreadLight(enum LightBank bank, v3s16 p, u8 oldlight,
 268                 core::map<v3s16, bool> & light_sources)
 269 {
 270         v3s16 dirs[6] = {
 271                 v3s16(0,0,1), // back
 272                 v3s16(0,1,0), // top
 273                 v3s16(1,0,0), // right
 274                 v3s16(0,0,-1), // front
 275                 v3s16(0,-1,0), // bottom
 276                 v3s16(-1,0,0), // left
 277         };
 278
 279         emerge(VoxelArea(p - v3s16(1,1,1), p + v3s16(1,1,1)));
 280
 281         // Loop through 6 neighbors
 282         for(u16 i=0; i<6; i++)
 283         {
 284                 // Get the position of the neighbor node
 285                 v3s16 n2pos = p + dirs[i];
 286
 287                 u32 n2i = m_area.index(n2pos);
 288
 289                 if(m_flags[n2i] & VOXELFLAG_INEXISTENT)
 290                         continue;
 291
 292                 MapNode &n2 = m_data[n2i];
 293
 294                 /*
 295                         If the neighbor is dimmer than what was specified
 296                         as oldlight (the light of the previous node)
 297                 */
 298                 if(n2.getLight(bank) < oldlight)
 299                 {
 300                         /*
 301                                 And the neighbor is transparent and it has some light
 302                         */
 303                         if(n2.light_propagates() && n2.getLight(bank) != 0)
 304                         {
 305                                 /*
 306                                         Set light to 0 and add to queue
 307                                 */
 308
 309                                 u8 current_light = n2.getLight(bank);
 310                                 n2.setLight(bank, 0);
 311
 312                                 unspreadLight(bank, n2pos, current_light, light_sources);
 313
 314                                 /*
 315                                         Remove from light_sources if it is there
 316                                         NOTE: This doesn't happen nearly at all
 317                                 */
 318                                 /*if(light_sources.find(n2pos))
 319                                 {
 320                                         std::cout<<"Removed from light_sources"<<std::endl;
 321                                         light_sources.remove(n2pos);
 322                                 }*/
 323                         }
 324                 }
 325                 else{
 326                         light_sources.insert(n2pos, true);
 327                 }
 328         }
 329 }
 330
 331 #if 1
 332 /*
 333         Goes recursively through the neighbours of the node.
 334
 335         Alters only transparent nodes.
 336
 337         If the lighting of the neighbour is lower than the lighting of
 338         the node was (before changing it to 0 at the step before), the
 339         lighting of the neighbour is set to 0 and then the same stuff
 340         repeats for the neighbour.
 341
 342         The ending nodes of the routine are stored in light_sources.
 343         This is useful when a light is removed. In such case, this
 344         routine can be called for the light node and then again for
 345         light_sources to re-light the area without the removed light.
 346
 347         values of from_nodes are lighting values.
 348 */
 349 void VoxelManipulator::unspreadLight(enum LightBank bank,
 350                 core::map<v3s16, u8> & from_nodes,
 351                 core::map<v3s16, bool> & light_sources)
 352 {
 353         if(from_nodes.size() == 0)
 354                 return;
 355
 356         core::map<v3s16, u8>::Iterator j;
 357         j = from_nodes.getIterator();
 358
 359         for(; j.atEnd() == false; j++)
 360         {
 361                 v3s16 pos = j.getNode()->getKey();
 362
 363                 //MapNode &n = m_data[m_area.index(pos)];
 364
 365                 u8 oldlight = j.getNode()->getValue();
 366
 367                 unspreadLight(bank, pos, oldlight, light_sources);
 368         }
 369 }
 370 #endif
 371
 372 #if 0
 373 /*
 374         Goes recursively through the neighbours of the node.
 375
 376         Alters only transparent nodes.
 377
 378         If the lighting of the neighbour is lower than the lighting of
 379         the node was (before changing it to 0 at the step before), the
 380         lighting of the neighbour is set to 0 and then the same stuff
 381         repeats for the neighbour.
 382
 383         The ending nodes of the routine are stored in light_sources.
 384         This is useful when a light is removed. In such case, this
 385         routine can be called for the light node and then again for
 386         light_sources to re-light the area without the removed light.
 387
 388         values of from_nodes are lighting values.
 389 */
 390 void VoxelManipulator::unspreadLight(enum LightBank bank,
 391                 core::map<v3s16, u8> & from_nodes,
 392                 core::map<v3s16, bool> & light_sources)
 393 {
 394         v3s16 dirs[6] = {
 395                 v3s16(0,0,1), // back
 396                 v3s16(0,1,0), // top
 397                 v3s16(1,0,0), // right
 398                 v3s16(0,0,-1), // front
 399                 v3s16(0,-1,0), // bottom
 400                 v3s16(-1,0,0), // left
 401         };
 402
 403         if(from_nodes.size() == 0)
 404                 return;
 405
 406         core::map<v3s16, u8> unlighted_nodes;
 407         core::map<v3s16, u8>::Iterator j;
 408         j = from_nodes.getIterator();
 409
 410         for(; j.atEnd() == false; j++)
 411         {
 412                 v3s16 pos = j.getNode()->getKey();
 413
 414                 emerge(VoxelArea(pos - v3s16(1,1,1), pos + v3s16(1,1,1)));
 415
 416                 //MapNode &n = m_data[m_area.index(pos)];
 417
 418                 u8 oldlight = j.getNode()->getValue();
 419
 420                 // Loop through 6 neighbors
 421                 for(u16 i=0; i<6; i++)
 422                 {
 423                         // Get the position of the neighbor node
 424                         v3s16 n2pos = pos + dirs[i];
 425
 426                         u32 n2i = m_area.index(n2pos);
 427
 428                         if(m_flags[n2i] & VOXELFLAG_INEXISTENT)
 429                                 continue;
 430
 431                         MapNode &n2 = m_data[n2i];
 432
 433                         /*
 434                                 If the neighbor is dimmer than what was specified
 435                                 as oldlight (the light of the previous node)
 436                         */
 437                         if(n2.getLight(bank) < oldlight)
 438                         {
 439                                 /*
 440                                         And the neighbor is transparent and it has some light
 441                                 */
 442                                 if(n2.light_propagates() && n2.getLight(bank) != 0)
 443                                 {
 444                                         /*
 445                                                 Set light to 0 and add to queue
 446                                         */
 447
 448                                         u8 current_light = n2.getLight(bank);
 449                                         n2.setLight(bank, 0);
 450
 451                                         unlighted_nodes.insert(n2pos, current_light);
 452
 453                                         /*
 454                                                 Remove from light_sources if it is there
 455                                                 NOTE: This doesn't happen nearly at all
 456                                         */
 457                                         /*if(light_sources.find(n2pos))
 458                                         {
 459                                                 std::cout<<"Removed from light_sources"<<std::endl;
 460                                                 light_sources.remove(n2pos);
 461                                         }*/
 462                                 }
 463                         }
 464                         else{
 465                                 light_sources.insert(n2pos, true);
 466                         }
 467                 }
 468         }
 469
 470         /*dstream<<"unspreadLight(): Changed block "
 471                         <<blockchangecount<<" times"
 472                         <<" for "<<from_nodes.size()<<" nodes"
 473                         <<std::endl;*/
 474
 475         if(unlighted_nodes.size() > 0)
 476                 unspreadLight(bank, unlighted_nodes, light_sources);
 477 }
 478 #endif
 479
 480 void VoxelManipulator::spreadLight(enum LightBank bank, v3s16 p)
 481 {
 482         const v3s16 dirs[6] = {
 483                 v3s16(0,0,1), // back
 484                 v3s16(0,1,0), // top
 485                 v3s16(1,0,0), // right
 486                 v3s16(0,0,-1), // front
 487                 v3s16(0,-1,0), // bottom
 488                 v3s16(-1,0,0), // left
 489         };
 490
 491         emerge(VoxelArea(p - v3s16(1,1,1), p + v3s16(1,1,1)));
 492
 493         u32 i = m_area.index(p);
 494
 495         if(m_flags[i] & VOXELFLAG_INEXISTENT)
 496                 return;
 497
 498         MapNode &n = m_data[i];
 499
 500         u8 oldlight = n.getLight(bank);
 501         u8 newlight = diminish_light(oldlight);
 502
 503         // Loop through 6 neighbors
 504         for(u16 i=0; i<6; i++)
 505         {
 506                 // Get the position of the neighbor node
 507                 v3s16 n2pos = p + dirs[i];
 508
 509                 u32 n2i = m_area.index(n2pos);
 510
 511                 if(m_flags[n2i] & VOXELFLAG_INEXISTENT)
 512                         continue;
 513
 514                 MapNode &n2 = m_data[n2i];
 515
 516                 /*
 517                         If the neighbor is brighter than the current node,
 518                         add to list (it will light up this node on its turn)
 519                 */
 520                 if(n2.getLight(bank) > undiminish_light(oldlight))
 521                 {
 522                         spreadLight(bank, n2pos);
 523                 }
 524                 /*
 525                         If the neighbor is dimmer than how much light this node
 526                         would spread on it, add to list
 527                 */
 528                 if(n2.getLight(bank) < newlight)
 529                 {
 530                         if(n2.light_propagates())
 531                         {
 532                                 n2.setLight(bank, newlight);
 533                                 spreadLight(bank, n2pos);
 534                         }
 535                 }
 536         }
 537 }
 538
 539 #if 1
 540 /*
 541         Lights neighbors of from_nodes, collects all them and then
 542         goes on recursively.
 543 */
 544 void VoxelManipulator::spreadLight(enum LightBank bank,
 545                 core::map<v3s16, bool> & from_nodes)
 546 {
 547         if(from_nodes.size() == 0)
 548                 return;
 549
 550         core::map<v3s16, bool> lighted_nodes;
 551         core::map<v3s16, bool>::Iterator j;
 552         j = from_nodes.getIterator();
 553
 554         for(; j.atEnd() == false; j++)
 555         {
 556                 v3s16 pos = j.getNode()->getKey();
 557
 558                 spreadLight(bank, pos);
 559         }
 560 }
 561 #endif
 562
 563 #if 0
 564 /*
 565         Lights neighbors of from_nodes, collects all them and then
 566         goes on recursively.
 567 */
 568 void VoxelManipulator::spreadLight(enum LightBank bank,
 569                 core::map<v3s16, bool> & from_nodes)
 570 {
 571         const v3s16 dirs[6] = {
 572                 v3s16(0,0,1), // back
 573                 v3s16(0,1,0), // top
 574                 v3s16(1,0,0), // right
 575                 v3s16(0,0,-1), // front
 576                 v3s16(0,-1,0), // bottom
 577                 v3s16(-1,0,0), // left
 578         };
 579
 580         if(from_nodes.size() == 0)
 581                 return;
 582
 583         core::map<v3s16, bool> lighted_nodes;
 584         core::map<v3s16, bool>::Iterator j;
 585         j = from_nodes.getIterator();
 586
 587         for(; j.atEnd() == false; j++)
 588         {
 589                 v3s16 pos = j.getNode()->getKey();
 590
 591                 emerge(VoxelArea(pos - v3s16(1,1,1), pos + v3s16(1,1,1)));
 592
 593                 u32 i = m_area.index(pos);
 594
 595                 if(m_flags[i] & VOXELFLAG_INEXISTENT)
 596                         continue;
 597
 598                 MapNode &n = m_data[i];
 599
 600                 u8 oldlight = n.getLight(bank);
 601                 u8 newlight = diminish_light(oldlight);
 602
 603                 // Loop through 6 neighbors
 604                 for(u16 i=0; i<6; i++)
 605                 {
 606                         // Get the position of the neighbor node
 607                         v3s16 n2pos = pos + dirs[i];
 608
 609                         try
 610                         {
 611                                 u32 n2i = m_area.index(n2pos);
 612
 613                                 if(m_flags[n2i] & VOXELFLAG_INEXISTENT)
 614                                         continue;
 615
 616                                 MapNode &n2 = m_data[n2i];
 617
 618                                 /*
 619                                         If the neighbor is brighter than the current node,
 620                                         add to list (it will light up this node on its turn)
 621                                 */
 622                                 if(n2.getLight(bank) > undiminish_light(oldlight))
 623                                 {
 624                                         lighted_nodes.insert(n2pos, true);
 625                                 }
 626                                 /*
 627                                         If the neighbor is dimmer than how much light this node
 628                                         would spread on it, add to list
 629                                 */
 630                                 if(n2.getLight(bank) < newlight)
 631                                 {
 632                                         if(n2.light_propagates())
 633                                         {
 634                                                 n2.setLight(bank, newlight);
 635                                                 lighted_nodes.insert(n2pos, true);
 636                                         }
 637                                 }
 638                         }
 639                         catch(InvalidPositionException &e)
 640                         {
 641                                 continue;
 642                         }
 643                 }
 644         }
 645
 646         /*dstream<<"spreadLight(): Changed block "
 647                         <<blockchangecount<<" times"
 648                         <<" for "<<from_nodes.size()<<" nodes"
 649                         <<std::endl;*/
 650
 651         if(lighted_nodes.size() > 0)
 652                 spreadLight(bank, lighted_nodes);
 653 }
 654 #endif
 655
 656 #if 0
 657 int VoxelManipulator::getWaterPressure(v3s16 p, s16 &highest_y, int recur_count)
 658 {
 659         m_flags[m_area.index(p)] |= VOXELFLAG_CHECKED2;
 660
 661         if(p.Y > highest_y)
 662                 highest_y = p.Y;
 663
 664         /*if(recur_count > 1000)
 665                 throw ProcessingLimitException
 666                                 ("getWaterPressure recur_count limit reached");*/
 667
 668         if(recur_count > 10000)
 669                 return -1;
 670
 671         recur_count++;
 672
 673         v3s16 dirs[6] = {
 674                 v3s16(0,1,0), // top
 675                 v3s16(0,0,1), // back
 676                 v3s16(0,0,-1), // front
 677                 v3s16(1,0,0), // right
 678                 v3s16(-1,0,0), // left
 679                 v3s16(0,-1,0), // bottom
 680         };
 681
 682         // Load neighboring nodes
 683         emerge(VoxelArea(p - v3s16(1,1,1), p + v3s16(1,1,1)), 1);
 684
 685         s32 i;
 686         for(i=0; i<6; i++)
 687         {
 688                 v3s16 p2 = p + dirs[i];
 689                 u8 f = m_flags[m_area.index(p2)];
 690                 // Ignore inexistent or checked nodes
 691                 if(f & (VOXELFLAG_INEXISTENT | VOXELFLAG_CHECKED2))
 692                         continue;
 693                 MapNode &n = m_data[m_area.index(p2)];
 694                 // Ignore non-liquid nodes
 695                 if(content_liquid(n.d) == false)
 696                         continue;
 697
 698                 int pr;
 699
 700                 // If at ocean surface
 701                 if(n.pressure == 1 && n.d == CONTENT_WATERSOURCE)
 702                 //if(n.pressure == 1) // Causes glitches but is fast
 703                 {
 704                         pr = 1;
 705                 }
 706                 // Otherwise recurse more
 707                 else
 708                 {
 709                         pr = getWaterPressure(p2, highest_y, recur_count);
 710                         if(pr == -1)
 711                                 continue;
 712                 }
 713
 714                 // If block is at top, pressure here is one higher
 715                 if(i == 0)
 716                 {
 717                         if(pr < 255)
 718                                 pr++;
 719                 }
 720                 // If block is at bottom, pressure here is one lower
 721                 else if(i == 5)
 722                 {
 723                         if(pr > 1)
 724                                 pr--;
 725                 }
 726
 727                 // Node is on the pressure route
 728                 m_flags[m_area.index(p)] |= VOXELFLAG_CHECKED4;
 729
 730                 // Got pressure
 731                 return pr;
 732         }
 733
 734         // Nothing useful found
 735         return -1;
 736 }
 737
 738 void VoxelManipulator::spreadWaterPressure(v3s16 p, int pr,
 739                 VoxelArea request_area,
 740                 core::map<v3s16, u8> &active_nodes,
 741                 int recur_count)
 742 {
 743         //if(recur_count > 10000)
 744                 /*throw ProcessingLimitException
 745                                 ("spreadWaterPressure recur_count limit reached");*/
 746         if(recur_count > 10)
 747                 return;
 748         recur_count++;
 749
 750         /*dstream<<"spreadWaterPressure: p=("
 751                         <<p.X<<","<<p.Y<<","<<p.Z<<")"
 752                         <<", oldpr="<<(int)m_data[m_area.index(p)].pressure
 753                         <<", pr="<<pr
 754                         <<", recur_count="<<recur_count
 755                         <<", request_area=";
 756         request_area.print(dstream);
 757         dstream<<std::endl;*/
 758
 759         m_flags[m_area.index(p)] |= VOXELFLAG_CHECKED3;
 760         m_data[m_area.index(p)].pressure = pr;
 761
 762         v3s16 dirs[6] = {
 763                 v3s16(0,1,0), // top
 764                 v3s16(-1,0,0), // left
 765                 v3s16(1,0,0), // right
 766                 v3s16(0,0,-1), // front
 767                 v3s16(0,0,1), // back
 768                 v3s16(0,-1,0), // bottom
 769         };
 770
 771         // Load neighboring nodes
 772         emerge(VoxelArea(p - v3s16(1,1,1), p + v3s16(1,1,1)), 2);
 773
 774         s32 i;
 775         for(i=0; i<6; i++)
 776         {
 777                 v3s16 p2 = p + dirs[i];
 778
 779                 u8 f = m_flags[m_area.index(p2)];
 780
 781                 // Ignore inexistent and checked nodes
 782                 if(f & (VOXELFLAG_INEXISTENT | VOXELFLAG_CHECKED3))
 783                         continue;
 784
 785                 MapNode &n = m_data[m_area.index(p2)];
 786
 787                 /*
 788                         If material is air:
 789                                 add to active_nodes if there is flow-causing pressure.
 790                         NOTE: Do not remove anything from there. We cannot know
 791                               here if some other neighbor of it causes flow.
 792                 */
 793                 if(liquid_replaces_content(n.d))
 794                 {
 795                         bool pressure_causes_flow = false;
 796                         // If empty block is at top
 797                         if(i == 0)
 798                         {
 799                                 if(m_disable_water_climb)
 800                                         continue;
 801
 802                                 //if(pr >= PRESERVE_WATER_VOLUME ? 3 : 2)
 803                                 if(pr >= 3)
 804                                         pressure_causes_flow = true;
 805                         }
 806                         // If block is at bottom
 807                         else if(i == 5)
 808                         {
 809                                 pressure_causes_flow = true;
 810                         }
 811                         // If block is at side
 812                         else
 813                         {
 814                                 //if(pr >= PRESERVE_WATER_VOLUME ? 2 : 1)
 815                                 if(pr >= 2)
 816                                         pressure_causes_flow = true;
 817                         }
 818
 819                         if(pressure_causes_flow)
 820                         {
 821                                 active_nodes[p2] = 1;
 822                         }
 823
 824                         continue;
 825                 }
 826
 827                 // Ignore non-liquid nodes
 828                 if(content_liquid(n.d) == false)
 829                         continue;
 830
 831                 int pr2 = pr;
 832                 // If block is at top, pressure there is lower
 833                 if(i == 0)
 834                 {
 835                         if(pr2 > 0)
 836                                 pr2--;
 837                 }
 838                 // If block is at bottom, pressure there is higher
 839                 else if(i == 5)
 840                 {
 841                         if(pr2 < 255)
 842                                 pr2++;
 843                 }
 844
 845                 /*if(m_disable_water_climb)
 846                 {
 847                         if(pr2 > 3)
 848                                 pr2 = 3;
 849                 }*/
 850
 851                 // Ignore if correct pressure is already set and is not on
 852                 // request_area.
 853                 // Thus, request_area can be used for updating as much
 854                 // pressure info in some area as possible to possibly
 855                 // make some calls to getWaterPressure unnecessary.
 856                 if(n.pressure == pr2 && request_area.contains(p2) == false)
 857                         continue;
 858
 859                 spreadWaterPressure(p2, pr2, request_area, active_nodes, recur_count);
 860         }
 861 }
 862
 863 void VoxelManipulator::updateAreaWaterPressure(VoxelArea a,
 864                 core::map<v3s16, u8> &active_nodes,
 865                 bool checked3_is_clear)
 866 {
 867         TimeTaker timer("updateAreaWaterPressure", &updateareawaterpressure_time);
 868
 869         emerge(a, 3);
 870
 871         bool checked2_clear = false;
 872
 873         if(checked3_is_clear == false)
 874         {
 875                 //clearFlag(VOXELFLAG_CHECKED3);
 876
 877                 clearFlag(VOXELFLAG_CHECKED3 | VOXELFLAG_CHECKED2);
 878                 checked2_clear = true;
 879         }
 880
 881
 882         for(s32 z=a.MinEdge.Z; z<=a.MaxEdge.Z; z++)
 883         for(s32 y=a.MinEdge.Y; y<=a.MaxEdge.Y; y++)
 884         for(s32 x=a.MinEdge.X; x<=a.MaxEdge.X; x++)
 885         {
 886                 v3s16 p(x,y,z);
 887
 888                 u8 f = m_flags[m_area.index(p)];
 889                 // Ignore inexistent or checked nodes
 890                 if(f & (VOXELFLAG_INEXISTENT | VOXELFLAG_CHECKED3))
 891                         continue;
 892                 MapNode &n = m_data[m_area.index(p)];
 893                 // Ignore non-liquid nodes
 894                 if(content_liquid(n.d) == false)
 895                         continue;
 896
 897                 if(checked2_clear == false)
 898                 {
 899                         clearFlag(VOXELFLAG_CHECKED2);
 900                         checked2_clear = true;
 901                 }
 902
 903                 checked2_clear = false;
 904
 905                 s16 highest_y = -32768;
 906                 int recur_count = 0;
 907                 int pr = -1;
 908
 909                 try
 910                 {
 911                         // 0-1ms @ recur_count <= 100
 912                         //TimeTaker timer("getWaterPressure", g_irrlicht);
 913                         pr = getWaterPressure(p, highest_y, recur_count);
 914                 }
 915                 catch(ProcessingLimitException &e)
 916                 {
 917                         //dstream<<"getWaterPressure ProcessingLimitException"<<std::endl;
 918                 }
 919
 920                 if(pr == -1)
 921                 {
 922                         assert(highest_y != -32768);
 923
 924                         pr = highest_y - p.Y + 1;
 925                         if(pr > 255)
 926                                 pr = 255;
 927
 928                         /*dstream<<"WARNING: Pressure at ("
 929                                         <<p.X<<","<<p.Y<<","<<p.Z<<")"
 930                                         <<" = "<<pr
 931                                         //<<" and highest_y == -32768"
 932                                         <<std::endl;
 933                         assert(highest_y != -32768);
 934                         continue;*/
 935                 }
 936
 937                 try
 938                 {
 939                         // 0ms
 940                         //TimeTaker timer("spreadWaterPressure", g_irrlicht);
 941                         spreadWaterPressure(p, pr, a, active_nodes, 0);
 942                 }
 943                 catch(ProcessingLimitException &e)
 944                 {
 945                         //dstream<<"getWaterPressure ProcessingLimitException"<<std::endl;
 946                 }
 947         }
 948 }
 949
 950 bool VoxelManipulator::flowWater(v3s16 removed_pos,
 951                 core::map<v3s16, u8> &active_nodes,
 952                 int recursion_depth, bool debugprint,
 953                 u32 stoptime)
 954 {
 955         v3s16 dirs[6] = {
 956                 v3s16(0,1,0), // top
 957                 v3s16(0,0,-1), // front
 958                 v3s16(0,0,1), // back
 959                 v3s16(-1,0,0), // left
 960                 v3s16(1,0,0), // right
 961                 v3s16(0,-1,0), // bottom
 962         };
 963
 964         recursion_depth++;
 965
 966         v3s16 p;
 967         bool from_ocean = false;
 968
 969         // Randomize horizontal order
 970         static s32 cs = 0;
 971         if(cs < 3)
 972                 cs++;
 973         else
 974                 cs = 0;
 975         s16 s1 = (cs & 1) ? 1 : -1;
 976         s16 s2 = (cs & 2) ? 1 : -1;
 977         //dstream<<"s1="<<s1<<", s2="<<s2<<std::endl;
 978
 979         {
 980         TimeTaker timer1("flowWater pre", &flowwater_pre_time);
 981
 982         // Load neighboring nodes
 983         emerge(VoxelArea(removed_pos - v3s16(1,1,1), removed_pos + v3s16(1,1,1)), 4);
 984
 985         // Ignore incorrect removed_pos
 986         {
 987                 u8 f = m_flags[m_area.index(removed_pos)];
 988                 // Ignore inexistent or checked node
 989                 if(f & (VOXELFLAG_INEXISTENT | VOXELFLAG_CHECKED))
 990                         return false;
 991                 MapNode &n = m_data[m_area.index(removed_pos)];
 992                 // Ignore nodes to which the water can't go
 993                 if(liquid_replaces_content(n.d) == false)
 994                         return false;
 995         }
 996
 997         s32 i;
 998         for(i=0; i<6; i++)
 999         {
1000                 // Don't raise water from bottom
1001                 if(m_disable_water_climb && i == 5)
1002                         continue;
1003
1004                 p = removed_pos + v3s16(s1*dirs[i].X, dirs[i].Y, s2*dirs[i].Z);
1005
1006                 u8 f = m_flags[m_area.index(p)];
1007                 // Inexistent or checked nodes can't move
1008                 if(f & (VOXELFLAG_INEXISTENT | VOXELFLAG_CHECKED))
1009                         continue;
1010                 MapNode &n = m_data[m_area.index(p)];
1011                 // Only liquid nodes can move
1012                 if(content_liquid(n.d) == false)
1013                         continue;
1014                 // If block is at top, select it always
1015                 if(i == 0)
1016                 {
1017                         break;
1018                 }
1019                 // If block is at bottom, select it if it has enough pressure
1020                 if(i == 5)
1021                 {
1022                         //if(n.pressure >= PRESERVE_WATER_VOLUME ? 3 : 2)
1023                         if(n.pressure >= 3)
1024                                 break;
1025                         continue;
1026                 }
1027                 // Else block is at some side. Select it if it has enough pressure
1028                 //if(n.pressure >= PRESERVE_WATER_VOLUME ? 2 : 1)
1029                 if(n.pressure >= 2)
1030                 {
1031                         break;
1032                 }
1033         }
1034
1035         // If there is nothing to move, return
1036         if(i==6)
1037                 return false;
1038
1039         /*
1040                 Move water and bubble
1041         */
1042
1043         u8 m = m_data[m_area.index(p)].d;
1044         u8 f = m_flags[m_area.index(p)];
1045
1046         if(m == CONTENT_WATERSOURCE)
1047                 from_ocean = true;
1048
1049         // Move air bubble if not taking water from ocean
1050         if(from_ocean == false)
1051         {
1052                 m_data[m_area.index(p)].d = m_data[m_area.index(removed_pos)].d;
1053                 m_flags[m_area.index(p)] = m_flags[m_area.index(removed_pos)];
1054         }
1055
1056         /*
1057                 This has to be done to copy the brightness of a light source
1058                 correctly. Otherwise unspreadLight will fuck up when water
1059                 has replaced a light source.
1060         */
1061         u8 light = m_data[m_area.index(removed_pos)].getLightBanksWithSource();
1062
1063         m_data[m_area.index(removed_pos)].d = m;
1064         m_flags[m_area.index(removed_pos)] = f;
1065
1066         m_data[m_area.index(removed_pos)].setLightBanks(light);
1067
1068         // Mark removed_pos checked
1069         m_flags[m_area.index(removed_pos)] |= VOXELFLAG_CHECKED;
1070
1071         // If block was dropped from surface, increase pressure
1072         if(i == 0 && m_data[m_area.index(removed_pos)].pressure == 1)
1073         {
1074                 m_data[m_area.index(removed_pos)].pressure = 2;
1075         }
1076
1077         /*
1078         NOTE: This does not work as-is
1079         if(m == CONTENT_WATERSOURCE)
1080         {
1081                 // If block was raised to surface, increase pressure of
1082                 // source node
1083                 if(i == 5 && m_data[m_area.index(p)].pressure == 1)
1084                 {
1085                         m_data[m_area.index(p)].pressure = 2;
1086                 }
1087         }*/
1088
1089         /*if(debugprint)
1090         {
1091                 dstream<<"VoxelManipulator::flowWater(): Moved bubble:"<<std::endl;
1092                 print(dstream, VOXELPRINT_WATERPRESSURE);
1093         }*/
1094
1095         // Update pressure
1096         VoxelArea a;
1097         a.addPoint(p - v3s16(1,1,1));
1098         a.addPoint(p + v3s16(1,1,1));
1099         a.addPoint(removed_pos - v3s16(1,1,1));
1100         a.addPoint(removed_pos + v3s16(1,1,1));
1101         updateAreaWaterPressure(a, active_nodes);
1102
1103         /*if(debugprint)
1104         {
1105                 dstream<<"VoxelManipulator::flowWater(): Pressure updated:"<<std::endl;
1106                 print(dstream, VOXELPRINT_WATERPRESSURE);
1107                 //std::cin.get();
1108         }*/
1109
1110         if(debugprint)
1111         {
1112                 dstream<<"VoxelManipulator::flowWater(): step done:"<<std::endl;
1113                 print(dstream, VOXELPRINT_WATERPRESSURE);
1114                 //std::cin.get();
1115         }
1116
1117         }//timer1
1118
1119         //if(PRESERVE_WATER_VOLUME)
1120         if(from_ocean == false)
1121         {
1122                 // Flow water to the newly created empty position
1123                 /*flowWater(p, active_nodes, recursion_depth,
1124                                 debugprint, counter, counterlimit);*/
1125                 flowWater(p, active_nodes, recursion_depth,
1126                                 debugprint, stoptime);
1127         }
1128
1129         if(stoptime != 0)
1130         {
1131                 u32 timenow = getTimeMs();
1132                 // Well, it is a bit hard to guess because we don't know the
1133                 // start time...
1134                 bool overflow = timenow < stoptime - 100000;
1135                 if(timenow >= stoptime || overflow)
1136                 {
1137                         dstream<<"flowWater: stoptime reached"<<std::endl;
1138                         throw ProcessingLimitException("flowWater stoptime reached");
1139                 }
1140         }
1141
1142 find_again:
1143
1144         // Try flowing water to empty positions around removed_pos.
1145         // They are checked in reverse order compared to the previous loop.
1146         for(s32 i=5; i>=0; i--)
1147         {
1148                 // Don't try to flow to top
1149                 if(m_disable_water_climb && i == 0)
1150                         continue;
1151
1152                 //v3s16 p = removed_pos + dirs[i];
1153                 p = removed_pos + v3s16(s1*dirs[i].X, dirs[i].Y, s2*dirs[i].Z);
1154
1155                 u8 f = m_flags[m_area.index(p)];
1156                 // Water can't move to inexistent nodes
1157                 if(f & VOXELFLAG_INEXISTENT)
1158                         continue;
1159                 MapNode &n = m_data[m_area.index(p)];
1160                 // Water can only move to air
1161                 if(liquid_replaces_content(n.d) == false)
1162                         continue;
1163
1164                 // Flow water to node
1165                 bool moved =
1166                 flowWater(p, active_nodes, recursion_depth,
1167                                 debugprint, stoptime);
1168                 /*flowWater(p, active_nodes, recursion_depth,
1169                                 debugprint, counter, counterlimit);*/
1170
1171                 if(moved)
1172                 {
1173                         // Search again from all neighbors
1174                         goto find_again;
1175                 }
1176         }
1177
1178         return true;
1179 }
1180
1181 void VoxelManipulator::flowWater(
1182                 core::map<v3s16, u8> &active_nodes,
1183                 int recursion_depth, bool debugprint,
1184                 u32 timelimit)
1185 {
1186         addarea_time = 0;
1187         emerge_time = 0;
1188         emerge_load_time = 0;
1189         clearflag_time = 0;
1190         updateareawaterpressure_time = 0;
1191         flowwater_pre_time = 0;
1192
1193         if(active_nodes.size() == 0)
1194         {
1195                 dstream<<"flowWater: no active nodes"<<std::endl;
1196                 return;
1197         }
1198
1199         //TimeTaker timer1("flowWater (active_nodes)", g_irrlicht);
1200
1201         //dstream<<"active_nodes.size() = "<<active_nodes.size()<<std::endl;
1202
1203
1204         u32 stoptime = 0;
1205         stoptime = getTimeMs() + timelimit;
1206
1207         // Count of handled active nodes
1208         u32 handled_count = 0;
1209
1210         try
1211         {
1212
1213         /*
1214                 Take random one at first
1215
1216                 This is randomized only at the first time so that all
1217                 subsequent nodes will be taken at roughly the same position
1218         */
1219         s32 k = 0;
1220         if(active_nodes.size() != 0)
1221                 k = (s32)myrand() % (s32)active_nodes.size();
1222
1223         // Flow water to active nodes
1224         for(;;)
1225         //for(s32 h=0; h<1; h++)
1226         {
1227                 if(active_nodes.size() == 0)
1228                         break;
1229
1230                 handled_count++;
1231
1232                 // Clear check flags
1233                 clearFlag(VOXELFLAG_CHECKED);
1234
1235                 //dstream<<"Selecting a new active_node"<<std::endl;
1236
1237 #if 0
1238                 // Take first one
1239                 core::map<v3s16, u8>::Node
1240                                 *n = active_nodes.getIterator().getNode();
1241 #endif
1242
1243 #if 1
1244
1245                 core::map<v3s16, u8>::Iterator
1246                                 i = active_nodes.getIterator().getNode();
1247                 for(s32 j=0; j<k; j++)
1248                 {
1249                         i++;
1250                 }
1251                 core::map<v3s16, u8>::Node *n = i.getNode();
1252
1253                 // Decrement index if less than 0.
1254                 // This keeps us in existing indices always.
1255                 if(k > 0)
1256                         k--;
1257 #endif
1258
1259                 v3s16 p = n->getKey();
1260                 active_nodes.remove(p);
1261                 flowWater(p, active_nodes, recursion_depth,
1262                                 debugprint, stoptime);
1263         }
1264
1265         }
1266         catch(ProcessingLimitException &e)
1267         {
1268                 //dstream<<"getWaterPressure ProcessingLimitException"<<std::endl;
1269         }
1270
1271         /*v3s16 e = m_area.getExtent();
1272         s32 v = m_area.getVolume();
1273         dstream<<"flowWater (active): "
1274                         <<"area ended up as "
1275                         <<e.X<<"x"<<e.Y<<"x"<<e.Z<<" = "<<v
1276                         <<", handled a_node count: "<<handled_count
1277                         <<", active_nodes.size() = "<<active_nodes.size()
1278                         <<std::endl;
1279         dstream<<"addarea_time: "<<addarea_time
1280                         <<", emerge_time: "<<emerge_time
1281                         <<", emerge_load_time: "<<emerge_load_time
1282                         <<", clearflag_time: "<<clearflag_time
1283                         <<", flowwater_pre_time: "<<flowwater_pre_time
1284                         <<", updateareawaterpressure_time: "<<updateareawaterpressure_time
1285                         <<std::endl;*/
1286 }
1287 #endif
1288
1289 //END