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 "main.h"
  25 #include "utility.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 }
  45
  46 VoxelManipulator::~VoxelManipulator()
  47 {
  48         clear();
  49         if(m_data)
  50                 delete[] m_data;
  51         if(m_flags)
  52                 delete[] m_flags;
  53 }
  54
  55 void VoxelManipulator::clear()
  56 {
  57         // Reset area to volume=0
  58         m_area = VoxelArea();
  59         if(m_data)
  60                 delete[] m_data;
  61         m_data = NULL;
  62         if(m_flags)
  63                 delete[] m_flags;
  64         m_flags = NULL;
  65 }
  66
  67 void VoxelManipulator::print(std::ostream &o, 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                                         u8 m = m_data[m_area.index(x,y,z)].d;
  98                                         u8 pr = m_data[m_area.index(x,y,z)].pressure;
  99                                         if(mode == VOXELPRINT_MATERIAL)
 100                                         {
 101                                                 if(m <= 9)
 102                                                         c = m + '0';
 103                                         }
 104                                         else if(mode == VOXELPRINT_WATERPRESSURE)
 105                                         {
 106                                                 if(m == MATERIAL_WATER)
 107                                                 {
 108                                                         c = 'w';
 109                                                         if(pr <= 9)
 110                                                                 c = pr + '0';
 111                                                 }
 112                                                 else if(m == MATERIAL_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", g_device, &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::interpolate(VoxelArea area)
 224 {
 225         VoxelArea emerge_area = area;
 226         emerge_area.MinEdge -= v3s16(1,1,1);
 227         emerge_area.MaxEdge += v3s16(1,1,1);
 228         emerge(emerge_area);
 229
 230         SharedBuffer<u8> buf(area.getVolume());
 231
 232         for(s32 z=area.MinEdge.Z; z<=area.MaxEdge.Z; z++)
 233         for(s32 y=area.MinEdge.Y; y<=area.MaxEdge.Y; y++)
 234         for(s32 x=area.MinEdge.X; x<=area.MaxEdge.X; x++)
 235         {
 236                 v3s16 p(x,y,z);
 237
 238                 v3s16 dirs[] = {
 239                         v3s16(1,1,0),
 240                         v3s16(1,0,1),
 241                         v3s16(1,-1,0),
 242                         v3s16(1,0,-1),
 243                         v3s16(-1,1,0),
 244                         v3s16(-1,0,1),
 245                         v3s16(-1,-1,0),
 246                         v3s16(-1,0,-1),
 247                 };
 248                 //const v3s16 *dirs = g_26dirs;
 249
 250                 s16 total = 0;
 251                 s16 airness = 0;
 252                 u8 m = MATERIAL_IGNORE;
 253
 254                 for(s16 i=0; i<8; i++)
 255                 //for(s16 i=0; i<26; i++)
 256                 {
 257                         v3s16 p2 = p + dirs[i];
 258
 259                         u8 f = m_flags[m_area.index(p2)];
 260                         assert(!(f & VOXELFLAG_NOT_LOADED));
 261                         if(f & VOXELFLAG_INEXISTENT)
 262                                 continue;
 263
 264                         MapNode &n = m_data[m_area.index(p2)];
 265
 266                         airness += (n.d == MATERIAL_AIR) ? 1 : -1;
 267                         total++;
 268
 269                         if(m == MATERIAL_IGNORE && n.d != MATERIAL_AIR)
 270                                 m = n.d;
 271                 }
 272
 273                 // 1 if air, 0 if not
 274                 buf[area.index(p)] = airness > -total/2 ? MATERIAL_AIR : m;
 275                 //buf[area.index(p)] = airness > -total ? MATERIAL_AIR : m;
 276                 //buf[area.index(p)] = airness >= -7 ? MATERIAL_AIR : m;
 277         }
 278
 279         for(s32 z=area.MinEdge.Z; z<=area.MaxEdge.Z; z++)
 280         for(s32 y=area.MinEdge.Y; y<=area.MaxEdge.Y; y++)
 281         for(s32 x=area.MinEdge.X; x<=area.MaxEdge.X; x++)
 282         {
 283                 v3s16 p(x,y,z);
 284                 m_data[m_area.index(p)].d = buf[area.index(p)];
 285         }
 286 }
 287
 288
 289 void VoxelManipulator::clearFlag(u8 flags)
 290 {
 291         // 0-1ms on moderate area
 292         TimeTaker timer("clearFlag", g_device, &clearflag_time);
 293
 294         v3s16 s = m_area.getExtent();
 295
 296         /*dstream<<"clearFlag clearing area of size "
 297                         <<""<<s.X<<"x"<<s.Y<<"x"<<s.Z<<""
 298                         <<std::endl;*/
 299
 300         //s32 count = 0;
 301
 302         /*for(s32 z=m_area.MinEdge.Z; z<=m_area.MaxEdge.Z; z++)
 303         for(s32 y=m_area.MinEdge.Y; y<=m_area.MaxEdge.Y; y++)
 304         for(s32 x=m_area.MinEdge.X; x<=m_area.MaxEdge.X; x++)
 305         {
 306                 u8 f = m_flags[m_area.index(x,y,z)];
 307                 m_flags[m_area.index(x,y,z)] &= ~flags;
 308                 if(m_flags[m_area.index(x,y,z)] != f)
 309                         count++;
 310         }*/
 311
 312         s32 volume = m_area.getVolume();
 313         for(s32 i=0; i<volume; i++)
 314         {
 315                 m_flags[i] &= ~flags;
 316         }
 317
 318         /*s32 volume = m_area.getVolume();
 319         for(s32 i=0; i<volume; i++)
 320         {
 321                 u8 f = m_flags[i];
 322                 m_flags[i] &= ~flags;
 323                 if(m_flags[i] != f)
 324                         count++;
 325         }
 326
 327         dstream<<"clearFlag changed "<<count<<" flags out of "
 328                         <<volume<<" nodes"<<std::endl;*/
 329 }
 330
 331 int VoxelManipulator::getWaterPressure(v3s16 p, s16 &highest_y, int recur_count)
 332 {
 333         m_flags[m_area.index(p)] |= VOXELFLAG_CHECKED2;
 334
 335         if(p.Y > highest_y)
 336                 highest_y = p.Y;
 337
 338         /*if(recur_count > 1000)
 339                 throw ProcessingLimitException
 340                                 ("getWaterPressure recur_count limit reached");*/
 341
 342         if(recur_count > 10000)
 343                 return -1;
 344
 345         recur_count++;
 346
 347         v3s16 dirs[6] = {
 348                 v3s16(0,1,0), // top
 349                 v3s16(0,0,1), // back
 350                 v3s16(0,0,-1), // front
 351                 v3s16(1,0,0), // right
 352                 v3s16(-1,0,0), // left
 353                 v3s16(0,-1,0), // bottom
 354         };
 355
 356         // Load neighboring nodes
 357         emerge(VoxelArea(p - v3s16(1,1,1), p + v3s16(1,1,1)), 1);
 358
 359         s32 i;
 360         for(i=0; i<6; i++)
 361         {
 362                 v3s16 p2 = p + dirs[i];
 363                 u8 f = m_flags[m_area.index(p2)];
 364                 // Ignore inexistent or checked nodes
 365                 if(f & (VOXELFLAG_INEXISTENT | VOXELFLAG_CHECKED2))
 366                         continue;
 367                 MapNode &n = m_data[m_area.index(p2)];
 368                 // Ignore non-liquid nodes
 369                 if(material_liquid(n.d) == false)
 370                         continue;
 371
 372                 int pr;
 373
 374                 // If at ocean surface
 375                 if(n.pressure == 1 && n.d == MATERIAL_OCEAN)
 376                 {
 377                         pr = 1;
 378                 }
 379                 // Otherwise recurse more
 380                 else
 381                 {
 382                         pr = getWaterPressure(p2, highest_y, recur_count);
 383                         if(pr == -1)
 384                                 continue;
 385                 }
 386
 387                 // If block is at top, pressure here is one higher
 388                 if(i == 0)
 389                 {
 390                         if(pr < 255)
 391                                 pr++;
 392                 }
 393                 // If block is at bottom, pressure here is one lower
 394                 else if(i == 5)
 395                 {
 396                         if(pr > 1)
 397                                 pr--;
 398                 }
 399
 400                 // Node is on the pressure route
 401                 m_flags[m_area.index(p)] |= VOXELFLAG_CHECKED4;
 402
 403                 // Got pressure
 404                 return pr;
 405         }
 406
 407         // Nothing useful found
 408         return -1;
 409 }
 410
 411 void VoxelManipulator::spreadWaterPressure(v3s16 p, int pr,
 412                 VoxelArea request_area,
 413                 core::map<v3s16, u8> &active_nodes,
 414                 int recur_count)
 415 {
 416         //if(recur_count > 10000)
 417                 /*throw ProcessingLimitException
 418                                 ("spreadWaterPressure recur_count limit reached");*/
 419         if(recur_count > 10)
 420                 return;
 421         recur_count++;
 422
 423         /*dstream<<"spreadWaterPressure: p=("
 424                         <<p.X<<","<<p.Y<<","<<p.Z<<")"
 425                         <<", oldpr="<<(int)m_data[m_area.index(p)].pressure
 426                         <<", pr="<<pr
 427                         <<", recur_count="<<recur_count
 428                         <<", request_area=";
 429         request_area.print(dstream);
 430         dstream<<std::endl;*/
 431
 432         m_flags[m_area.index(p)] |= VOXELFLAG_CHECKED3;
 433         m_data[m_area.index(p)].pressure = pr;
 434
 435         v3s16 dirs[6] = {
 436                 v3s16(0,1,0), // top
 437                 v3s16(-1,0,0), // left
 438                 v3s16(1,0,0), // right
 439                 v3s16(0,0,-1), // front
 440                 v3s16(0,0,1), // back
 441                 v3s16(0,-1,0), // bottom
 442         };
 443
 444         // Load neighboring nodes
 445         emerge(VoxelArea(p - v3s16(1,1,1), p + v3s16(1,1,1)), 2);
 446
 447         s32 i;
 448         for(i=0; i<6; i++)
 449         {
 450                 v3s16 p2 = p + dirs[i];
 451
 452                 u8 f = m_flags[m_area.index(p2)];
 453
 454                 // Ignore inexistent and checked nodes
 455                 if(f & (VOXELFLAG_INEXISTENT | VOXELFLAG_CHECKED3))
 456                         continue;
 457
 458                 MapNode &n = m_data[m_area.index(p2)];
 459
 460                 /*
 461                         If material is air:
 462                                 add to active_nodes if there is flow-causing pressure.
 463                         NOTE: Do not remove anything from there. We cannot know
 464                               here if some other neighbor of it causes flow.
 465                 */
 466                 if(n.d == MATERIAL_AIR)
 467                 {
 468                         bool pressure_causes_flow = false;
 469                         // If block is at top
 470                         if(i == 0)
 471                         {
 472                                 //if(pr >= PRESERVE_WATER_VOLUME ? 3 : 2)
 473                                 if(pr >= 3)
 474                                         pressure_causes_flow = true;
 475                         }
 476                         // If block is at bottom
 477                         else if(i == 5)
 478                         {
 479                                 pressure_causes_flow = true;
 480                         }
 481                         // If block is at side
 482                         else
 483                         {
 484                                 //if(pr >= PRESERVE_WATER_VOLUME ? 2 : 1)
 485                                 if(pr >= 2)
 486                                         pressure_causes_flow = true;
 487                         }
 488
 489                         if(pressure_causes_flow)
 490                         {
 491                                 active_nodes[p2] = 1;
 492                         }
 493
 494                         continue;
 495                 }
 496
 497                 // Ignore non-liquid nodes
 498                 if(material_liquid(n.d) == false)
 499                         continue;
 500
 501                 int pr2 = pr;
 502                 // If block is at top, pressure there is lower
 503                 if(i == 0)
 504                 {
 505                         if(pr2 > 0)
 506                                 pr2--;
 507                 }
 508                 // If block is at bottom, pressure there is higher
 509                 else if(i == 5)
 510                 {
 511                         if(pr2 < 255)
 512                                 pr2++;
 513                 }
 514
 515                 // Ignore if correct pressure is already set and is not on
 516                 // request_area.
 517                 // Thus, request_area can be used for updating as much
 518                 // pressure info in some area as possible to possibly
 519                 // make some calls to getWaterPressure unnecessary.
 520                 if(n.pressure == pr2 && request_area.contains(p2) == false)
 521                         continue;
 522
 523                 spreadWaterPressure(p2, pr2, request_area, active_nodes, recur_count);
 524         }
 525 }
 526
 527 void VoxelManipulator::updateAreaWaterPressure(VoxelArea a,
 528                 core::map<v3s16, u8> &active_nodes,
 529                 bool checked3_is_clear)
 530 {
 531         TimeTaker timer("updateAreaWaterPressure", g_device,
 532                         &updateareawaterpressure_time);
 533
 534         emerge(a, 3);
 535
 536         bool checked2_clear = false;
 537
 538         if(checked3_is_clear == false)
 539         {
 540                 //clearFlag(VOXELFLAG_CHECKED3);
 541
 542                 clearFlag(VOXELFLAG_CHECKED3 | VOXELFLAG_CHECKED2);
 543                 checked2_clear = true;
 544         }
 545
 546
 547         for(s32 z=a.MinEdge.Z; z<=a.MaxEdge.Z; z++)
 548         for(s32 y=a.MinEdge.Y; y<=a.MaxEdge.Y; y++)
 549         for(s32 x=a.MinEdge.X; x<=a.MaxEdge.X; x++)
 550         {
 551                 v3s16 p(x,y,z);
 552
 553                 u8 f = m_flags[m_area.index(p)];
 554                 // Ignore inexistent or checked nodes
 555                 if(f & (VOXELFLAG_INEXISTENT | VOXELFLAG_CHECKED3))
 556                         continue;
 557                 MapNode &n = m_data[m_area.index(p)];
 558                 // Ignore non-liquid nodes
 559                 if(material_liquid(n.d) == false)
 560                         continue;
 561
 562                 if(checked2_clear == false)
 563                 {
 564                         clearFlag(VOXELFLAG_CHECKED2);
 565                         checked2_clear = true;
 566                 }
 567
 568                 checked2_clear = false;
 569
 570                 s16 highest_y = -32768;
 571                 int recur_count = 0;
 572                 int pr = -1;
 573
 574                 try
 575                 {
 576                         // 0-1ms @ recur_count <= 100
 577                         //TimeTaker timer("getWaterPressure", g_device);
 578                         pr = getWaterPressure(p, highest_y, recur_count);
 579                 }
 580                 catch(ProcessingLimitException &e)
 581                 {
 582                         //dstream<<"getWaterPressure ProcessingLimitException"<<std::endl;
 583                 }
 584
 585                 if(pr == -1)
 586                 {
 587                         assert(highest_y != -32768);
 588
 589                         pr = highest_y - p.Y + 1;
 590                         if(pr > 255)
 591                                 pr = 255;
 592
 593                         /*dstream<<"WARNING: Pressure at ("
 594                                         <<p.X<<","<<p.Y<<","<<p.Z<<")"
 595                                         <<" = "<<pr
 596                                         //<<" and highest_y == -32768"
 597                                         <<std::endl;
 598                         assert(highest_y != -32768);
 599                         continue;*/
 600                 }
 601
 602                 try
 603                 {
 604                         // 0ms
 605                         //TimeTaker timer("spreadWaterPressure", g_device);
 606                         spreadWaterPressure(p, pr, a, active_nodes, 0);
 607                 }
 608                 catch(ProcessingLimitException &e)
 609                 {
 610                         //dstream<<"getWaterPressure ProcessingLimitException"<<std::endl;
 611                 }
 612         }
 613 }
 614
 615 bool VoxelManipulator::flowWater(v3s16 removed_pos,
 616                 core::map<v3s16, u8> &active_nodes,
 617                 int recursion_depth, bool debugprint,
 618                 u32 stoptime)
 619 {
 620         v3s16 dirs[6] = {
 621                 v3s16(0,1,0), // top
 622                 v3s16(0,0,-1), // front
 623                 v3s16(0,0,1), // back
 624                 v3s16(-1,0,0), // left
 625                 v3s16(1,0,0), // right
 626                 v3s16(0,-1,0), // bottom
 627         };
 628
 629         recursion_depth++;
 630
 631         v3s16 p;
 632         bool from_ocean = false;
 633
 634         // Randomize horizontal order
 635         static s32 cs = 0;
 636         if(cs < 3)
 637                 cs++;
 638         else
 639                 cs = 0;
 640         s16 s1 = (cs & 1) ? 1 : -1;
 641         s16 s2 = (cs & 2) ? 1 : -1;
 642         //dstream<<"s1="<<s1<<", s2="<<s2<<std::endl;
 643
 644         {
 645         TimeTaker timer1("flowWater pre", g_device, &flowwater_pre_time);
 646
 647         // Load neighboring nodes
 648         emerge(VoxelArea(removed_pos - v3s16(1,1,1), removed_pos + v3s16(1,1,1)), 4);
 649
 650         // Ignore incorrect removed_pos
 651         {
 652                 u8 f = m_flags[m_area.index(removed_pos)];
 653                 // Ignore inexistent or checked node
 654                 if(f & (VOXELFLAG_INEXISTENT | VOXELFLAG_CHECKED))
 655                         return false;
 656                 MapNode &n = m_data[m_area.index(removed_pos)];
 657                 // Water can move only to air
 658                 if(n.d != MATERIAL_AIR)
 659                         return false;
 660         }
 661
 662         s32 i;
 663         for(i=0; i<6; i++)
 664         {
 665                 p = removed_pos + v3s16(s1*dirs[i].X, dirs[i].Y, s2*dirs[i].Z);
 666
 667                 u8 f = m_flags[m_area.index(p)];
 668                 // Inexistent or checked nodes can't move
 669                 if(f & (VOXELFLAG_INEXISTENT | VOXELFLAG_CHECKED))
 670                         continue;
 671                 MapNode &n = m_data[m_area.index(p)];
 672                 // Only liquid nodes can move
 673                 if(material_liquid(n.d) == false)
 674                         continue;
 675                 // If block is at top, select it always
 676                 if(i == 0)
 677                 {
 678                         break;
 679                 }
 680                 // If block is at bottom, select it if it has enough pressure
 681                 if(i == 5)
 682                 {
 683                         //if(n.pressure >= PRESERVE_WATER_VOLUME ? 3 : 2)
 684                         if(n.pressure >= 3)
 685                                 break;
 686                         continue;
 687                 }
 688                 // Else block is at some side. Select it if it has enough pressure
 689                 //if(n.pressure >= PRESERVE_WATER_VOLUME ? 2 : 1)
 690                 if(n.pressure >= 2)
 691                 {
 692                         break;
 693                 }
 694         }
 695
 696         // If there is nothing to move, return
 697         if(i==6)
 698                 return false;
 699
 700         /*
 701                 Move water and bubble
 702         */
 703
 704         u8 m = m_data[m_area.index(p)].d;
 705         u8 f = m_flags[m_area.index(p)];
 706
 707         if(m == MATERIAL_OCEAN)
 708                 from_ocean = true;
 709
 710         // Move air bubble if not taking water from ocean
 711         if(from_ocean == false)
 712         {
 713                 m_data[m_area.index(p)].d = m_data[m_area.index(removed_pos)].d;
 714                 m_flags[m_area.index(p)] = m_flags[m_area.index(removed_pos)];
 715         }
 716
 717         m_data[m_area.index(removed_pos)].d = m;
 718         m_flags[m_area.index(removed_pos)] = f;
 719
 720         // Mark removed_pos checked
 721         m_flags[m_area.index(removed_pos)] |= VOXELFLAG_CHECKED;
 722
 723         // If block was dropped from surface, increase pressure
 724         if(i == 0 && m_data[m_area.index(removed_pos)].pressure == 1)
 725         {
 726                 m_data[m_area.index(removed_pos)].pressure = 2;
 727         }
 728
 729         /*
 730         NOTE: This does not work as-is
 731         if(m == MATERIAL_OCEAN)
 732         {
 733                 // If block was raised to surface, increase pressure of
 734                 // source node
 735                 if(i == 5 && m_data[m_area.index(p)].pressure == 1)
 736                 {
 737                         m_data[m_area.index(p)].pressure = 2;
 738                 }
 739         }*/
 740
 741         /*if(debugprint)
 742         {
 743                 dstream<<"VoxelManipulator::flowWater(): Moved bubble:"<<std::endl;
 744                 print(dstream, VOXELPRINT_WATERPRESSURE);
 745         }*/
 746
 747         // Update pressure
 748         VoxelArea a;
 749         a.addPoint(p - v3s16(1,1,1));
 750         a.addPoint(p + v3s16(1,1,1));
 751         a.addPoint(removed_pos - v3s16(1,1,1));
 752         a.addPoint(removed_pos + v3s16(1,1,1));
 753         updateAreaWaterPressure(a, active_nodes);
 754
 755         /*if(debugprint)
 756         {
 757                 dstream<<"VoxelManipulator::flowWater(): Pressure updated:"<<std::endl;
 758                 print(dstream, VOXELPRINT_WATERPRESSURE);
 759                 //std::cin.get();
 760         }*/
 761
 762         if(debugprint)
 763         {
 764                 dstream<<"VoxelManipulator::flowWater(): step done:"<<std::endl;
 765                 print(dstream, VOXELPRINT_WATERPRESSURE);
 766                 //std::cin.get();
 767         }
 768
 769         }//timer1
 770
 771         //if(PRESERVE_WATER_VOLUME)
 772         if(from_ocean == false)
 773         {
 774                 // Flow water to the newly created empty position
 775                 /*flowWater(p, active_nodes, recursion_depth,
 776                                 debugprint, counter, counterlimit);*/
 777                 flowWater(p, active_nodes, recursion_depth,
 778                                 debugprint, stoptime);
 779         }
 780
 781         if(stoptime != 0 && g_device != NULL)
 782         {
 783                 u32 timenow = g_device->getTimer()->getRealTime();
 784                 if(timenow >= stoptime ||
 785                                 (stoptime < 0x80000000 && timenow > 0x80000000))
 786                 {
 787                         dstream<<"flowWater: stoptime reached"<<std::endl;
 788                         throw ProcessingLimitException("flowWater stoptime reached");
 789                 }
 790         }
 791
 792 find_again:
 793
 794         // Try flowing water to empty positions around removed_pos.
 795         // They are checked in reverse order compared to the previous loop.
 796         for(s32 i=5; i>=0; i--)
 797         {
 798                 //v3s16 p = removed_pos + dirs[i];
 799                 p = removed_pos + v3s16(s1*dirs[i].X, dirs[i].Y, s2*dirs[i].Z);
 800
 801                 u8 f = m_flags[m_area.index(p)];
 802                 // Water can't move to inexistent nodes
 803                 if(f & VOXELFLAG_INEXISTENT)
 804                         continue;
 805                 MapNode &n = m_data[m_area.index(p)];
 806                 // Water can only move to air
 807                 if(n.d != MATERIAL_AIR)
 808                         continue;
 809
 810                 // Flow water to node
 811                 bool moved =
 812                 flowWater(p, active_nodes, recursion_depth,
 813                                 debugprint, stoptime);
 814                 /*flowWater(p, active_nodes, recursion_depth,
 815                                 debugprint, counter, counterlimit);*/
 816
 817                 if(moved)
 818                 {
 819                         // Search again from all neighbors
 820                         goto find_again;
 821                 }
 822         }
 823
 824         return true;
 825 }
 826
 827 void VoxelManipulator::flowWater(
 828                 core::map<v3s16, u8> &active_nodes,
 829                 int recursion_depth, bool debugprint,
 830                 u32 timelimit)
 831 {
 832         addarea_time = 0;
 833         emerge_time = 0;
 834         emerge_load_time = 0;
 835         clearflag_time = 0;
 836         updateareawaterpressure_time = 0;
 837         flowwater_pre_time = 0;
 838
 839         if(active_nodes.size() == 0)
 840         {
 841                 dstream<<"flowWater: no active nodes"<<std::endl;
 842                 return;
 843         }
 844
 845         TimeTaker timer1("flowWater (active_nodes)", g_device);
 846
 847         dstream<<"active_nodes.size() = "<<active_nodes.size()<<std::endl;
 848
 849         //int counter = 0;
 850
 851         u32 stoptime = 0;
 852         if(g_device != NULL)
 853         {
 854                 stoptime = g_device->getTimer()->getRealTime() + timelimit;
 855         }
 856
 857         // Count of handled active nodes
 858         u32 handled_count = 0;
 859
 860         try
 861         {
 862
 863         /*
 864                 Take random one at first
 865
 866                 This is randomized only at the first time so that all
 867                 subsequent nodes will be taken at roughly the same position
 868         */
 869         s32 k = 0;
 870         if(active_nodes.size() != 0)
 871                 k = (s32)rand() % (s32)active_nodes.size();
 872
 873         // Flow water to active nodes
 874         for(;;)
 875         //for(s32 h=0; h<1; h++)
 876         {
 877                 if(active_nodes.size() == 0)
 878                         break;
 879
 880                 handled_count++;
 881
 882                 // Clear check flags
 883                 clearFlag(VOXELFLAG_CHECKED);
 884
 885                 //dstream<<"Selecting a new active_node"<<std::endl;
 886
 887 #if 0
 888                 // Take first one
 889                 core::map<v3s16, u8>::Node
 890                                 *n = active_nodes.getIterator().getNode();
 891 #endif
 892
 893 #if 1
 894
 895                 core::map<v3s16, u8>::Iterator
 896                                 i = active_nodes.getIterator().getNode();
 897                 for(s32 j=0; j<k; j++)
 898                 {
 899                         i++;
 900                 }
 901                 core::map<v3s16, u8>::Node *n = i.getNode();
 902
 903                 // Decrement index if less than 0.
 904                 // This keeps us in existing indices always.
 905                 if(k > 0)
 906                         k--;
 907 #endif
 908
 909                 v3s16 p = n->getKey();
 910                 active_nodes.remove(p);
 911                 flowWater(p, active_nodes, recursion_depth,
 912                                 debugprint, stoptime);
 913         }
 914
 915         }
 916         catch(ProcessingLimitException &e)
 917         {
 918                 //dstream<<"getWaterPressure ProcessingLimitException"<<std::endl;
 919         }
 920
 921         v3s16 e = m_area.getExtent();
 922         s32 v = m_area.getVolume();
 923         //dstream<<"flowWater (active): moved "<<counter<<" nodes, "
 924         dstream<<"flowWater (active): "
 925                         <<"area ended up as "
 926                         <<e.X<<"x"<<e.Y<<"x"<<e.Z<<" = "<<v
 927                         <<", handled a_node count: "<<handled_count
 928                         <<", active_nodes.size() = "<<active_nodes.size()
 929                         <<std::endl;
 930
 931         dstream<<"addarea_time: "<<addarea_time
 932                         <<", emerge_time: "<<emerge_time
 933                         <<", emerge_load_time: "<<emerge_load_time
 934                         <<", clearflag_time: "<<clearflag_time
 935                         <<", flowwater_pre_time: "<<flowwater_pre_time
 936                         <<", updateareawaterpressure_time: "<<updateareawaterpressure_time
 937                         <<std::endl;
 938 }
 939
 940
 941 //END